Compositions parallèles

NOUS avons vu que BSML est un langage parallèle permettant la programmation fonctionnelle BSP. Basé sur BSP, il permet une estimation du temps d’exécution du programme et est confluent, donc sans inter-blocage. Malheureusement, les primitives de BSML sont plates, dans le sens que les processus explicites du langage (les vecteurs parallèles), partitionnent de manière directe les processeurs d’une unité BSP. Il est souvent trop difficile d’exprimer des algorithmes «diviser-pour-régner» («divide- and-conquer» dans la littérature anglo-saxonne) sans avoir à traduire ces algorithmes en des algorithmes en mode direct. Ce chapitre présente la sémantique et l’implantation d’une nouvelle primitive pour BSML qui facilite l’écrire de ces algorithmes diviser-pour-régner parallèles.

Cette primitive est appelée superposition car elle peut être vue comme la composition parallèle de deux processus BSP utilisant chacun l’ensemble des processeurs de la machine. Nous donnerons aussi un exemple d’application et le modèle de coût BSP La sous-synchronisation, c’est-à-dire la synchronisation d’une partie seulement des processeurs de la ma- chine, est une fonctionnalité d’une grande variété de modèles de programmation parallèle (indépendants ou dérivés du modèle BSP [89, 41]). La présence et l’utilisation de la sous-synchronisation sont justifiées par la nécessité de pouvoir décomposer récursivement un problème en sous-problèmes indépendants les uns des autres. Cette technique algorithmique est appelée «diviser-pour-régner», et dans le cas de la programmation parallèle, simplifié l’écriture de certains programmes.

Pour évaluer deux programmes parallèles sur une même machine on peut la partitionner en deux et évaluer indépendamment chacun des programmes sur chacune des partitions. Toutefois, en procédant ainsi, le modèle BSP est perdu puisqu’alors la synchronisation globale de chaque sous-machine ne coûtera plus l. Pour conserver le modèle BSP, ce qui est souhaitable [133], il faut donc que les barrières de synchronisation concernent toute la machine. Le modèle BSP n’autorise pas la sous-synchronisation : les barrières sont collectives.

C’est souvent considéré comme un obstacle pour la programmation parallèle d’algorithmes diviser-pour-régner en BSP (et dans notre cas, en BSML). Dans l’article [243], les auteurs ont noté que pour de grandes applications, la perte d’efficacité et d’expressivité due à la contrainte des barrières globales, est compensée par les avantages des communications BSP (notamment l’efficacité accrue des transferts de données sur certaines architectures) qui rendent la programmation parallèle plus simple. Pourtant, la technique dite diviser-pour-régner est une méthode naturelle pour la conception et l’implantation de nombreux algorithmes. La transformation manuelle d’un programme utilisant des techniques diviser-pour-régner en un programme sans ces techniques est un travail fastidieux où il est facile de se trom- per. Les auteurs de la BSPlib [147] font remarquer que le désavantage principal du partionnement par groupe de processeurs (c’est-à-dire la sous-synchronisation) est une perte de la prévision des performances du modèle de coût ([133] donne des arguments, sur des cas pratiques, en défaveur de la sous-synchronisation).

Cette restriction a été levée avec la «juxtaposition parallèle» de [190]. Le principal problème avec cette approche est que la nature purement fonctionnelle de BSML est perdue. En effet cette primitive effectue un effet de bord sur le nombre de processeurs rendant impossible la preuve assistée par ordinateur des programmes BSML utilisant la juxtaposition, comme il est fait au chapitre 6 avec des programmes BSML «plats», ou alors il faut passer les programmes par une phase préalable de transformation [183] (mais avec une perte des coûts BSP initiaux). Dans [258], l’auteur avance l’hypothèse que le paradigme diviser-pour-régner peut s’insérer naturelle- ment dans le modèle BSP sans avoir besoin de la sous-synchronisation. Il propose une méthode pour la programmation diviser-pour-régner qui est en adéquation avec le modèle des barrières de synchronisations globales du modèle BSP.

Cette méthode est basée sur un entrelacement de processus légers, appelés super-threads de manière fonctionnelle ce type d’algorithmes. Dans ce papier, la superposition est simplement décrite en terme d’une sémantique de haut niveau. Dans ce cas, la superposition est équivalente à la création d’une paire. Dans ce chapitre, nous allons détailler une sémantique à «petits pas» qui donne plus précisément le fonctionnement de cette nouvelle primitive. Cela nous aidera pour concevoir une nouvelle implantation de la BSMLlib et pour comparer les coûts BSP des programmes avec ou sans super-threads. Premièrement, nous décrirons informellement la nouvelle primitive BSML et les conséquences de son fonctionnement sur les traits non-fonctionnels de BSML. Ensuite, nous donnerons deux sémantiques à petits pas, afin de comparer les coûts BSP de cette primitive. Nous donnerons ensuite quelques détails sur la nouvelle implantation de BSML. Pour finir, nous donnerons deux exemples d’application de cette primitive.