Compositions paralleles

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, doncsans inter-blocage. Malheureusement, les primitives de BSML sont plates, dans le sens que lesprocessus explicites du langage (les vecteurs parallèles), partitionnent de manière directe les processeurs d’une unité BSP. Il est souvant 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, simplifie 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 consi- déré comme un obstacle pour la programmation parallèle d’algorihmes 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’im- plantation 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 mo- dèle de coût ([133] donne des arguments, sur des cas pratiques, en défaveur de la sous-synchronisation).

Pour exprimer les algorithmes diviser-pour-régner en BSML, [188] a tout d’abord proposé une nouvelle primitive appelée «composition parallèle». Mais celle-ci était limitée à la composition de deux programmes BSML dont les évaluations nécessitaient le même nombre de super-étapes. C’était évidemment restrictif et le respect de cette contrainte échoyait au programmeur.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éhode 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- threadsde 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.