Bibliotheque de programmes BSML

Les primitives décrites dans la section précédente constituent le noyau de la bibliothèque BSMLlib. Elles sont suffisantes pour exprimer tous les algorithmes BSP. Malgré leur caractère universel, il est souhaitable d’avoir un ensemble de fonctions dites utilitaires pour simplifier la programmation de ces algorithmes et rendre le code plus lisible. Toutes les fonctions décrites dans cette section sont ainsi implantées en utilisant uniquement ces primitives. Nous utiliserons aussi couramment l’application d’une même fonction séquentielle en chaque compo- sante d’un vecteur parallèle, c’est-à-dire l’application de la même fonction en chaque processeur. Pour cela, nous définissons une série de fonctions parfun d’applications parallèles d’une même fonction dont seules les arités diffèrent : Dans les sections qui vont suivre, tous les tests de performances ont été effectués sur une grappe de 6 nœuds chacun doté de 1Go de RAM. Les nœuds sont des Intel pentium IV 2.8 Ghz avec des cartes Gigabit Ethernet et interconnectés par un réseau Gigabit Ethernet (10/100/1000). Une Mandrake Clic 2.0 a été utilisée comme système d’exploitation et les programme ont été compilés avec OCaml 3.08.2 en mode natif. Chacun des programmes a été exécuté 100 fois de suite et la moyenne des exécutions a été prise pour les graphiques. Les versions de la BSMLlib utilisant la PUB [40], MPI ou directement les fonctionnalités TCP/IP d’OCaml ont été utilisées. Nous nous sommes servis de la version TCP/IP de la PUB ainsi que de la version MPICH de MPI.

Notre premier exemple est un échange total répliqué, c’est-à-dire que le résultat sera une liste répliquée, en chaque processeur, des valeurs des composantes du vecteur parallèle. Ainsi, chaque processeur contient une valeur et le résultat de (rpl_total v rpl_total est une fonction qui peut être utilisée pour définir d’autres fonctions (que nous utiliserons mas- sivement pour l’implantation des structures de données parallèles, cf chapitre 8) telles que parfun_total, qui permet d’appliquer une fonction séquentielle à chaque composante d’un vecteur parallèle, fait un échange total de ces valeurs et enfin applique une autre fonction sur ce résultat : Quand la taille de la valeur à diffuser est importante, et suivant les paramètres BSP de la machine, l’algorithme de diffusion en deux phases décrit dans [34, 117] peut s’avérer plus efficace. La figure 5.3 illustre la méthode utilisée. L’émission en deux super-étapes procède commme suit : le processeur de départ «découpe» son message en p messages et envoie chacun d’eux aux p−1 autres processeurs (première super- étape). Ensuite, chaque processeur envoie son bout de message aux autres processeurs (échange total) et pour finir chaque processeur «recolle» les morceaux reçus. La formule de coût BSP est alors :La figure 5.5 montre les performances mesurées avec au processeur 0 (processeur émetteur) une liste d’en- tiers. Sur les deux graphiques, la longueur de cette liste va de manière croissante. Sur notre cluster de test, les performances de la diffusion en deux phases sont moins bonnes que celles de la diffusion directe. Cela est dû au temps de «recollage» des listes qui est proportionel à la longueur de la liste du processeur émet- teur. Pour contourner ce problème, nous pourrions utiliser des tableaux, permettant ainsi un «découpage» (ainsi qu’un «recollage») en un temps proportionel à p.

Fonctions pour le calcul des préfixes

Notre troisième exemple est le calcul parallèle classique des préfixes d’un ensemble de valeurs avec un opérateur associatif admettant un élément neutre. Pour représenter cet ensemble, nous faisons l’hypothèse que chaque processeur en mémorise une partie sous la forme d’une liste d’éléments. Nous avons donc un vecteur parallèle de listes d’éléments. Prenons pour exemple, l’expression suivante pour une machine à 3 processeurs (avec e = 1 comme élément neutre) permettant de calculer les factorielles de 1 à 5 : Pour ce calcul, nous avons donc besoin, tout d’abord, d’une fonction pour la réduction parallèle, c’est- à-dire réduire, via un opérateur, les valeurs d’un vecteur parallèle. Ceci équivaut à calculer au processeur i, la réduction des valeurs contenue par les processeurs j tel que j < i. Prenons par exemple, l’expression suivante :La figure 5.7 montre les performances mesurées avec en chaque processeur une liste de flottants (chacune de même longueur). La somme de flottants a été utilisée comme opérateur. Sur les deux graphiques, les longueurs de ces listes vont croissant.Comme expliqué précédemment, la BSMLlib contient une primitive synchrone de projection qui est néces- saire pour tous les algorithmes dont la séquence d’exécution parallèle (c’est-à-dire le comportement global) dépend d’une valeur locale (d’un processeur). Considérons comme quatrième et dernier exemple le pro- blème de convertir une valeur de type α list par (un vecteur de listes, c’est-à-dire une liste par processeur) en une valeur de type α par list (liste de vecteurs parallèles).