ML parallèle minimalement synchrone

Modèle de coût et d’exécution

Plutôt que de passer directement à la conception d’un modèle et d’un langage à deux niveaux pour l’utilisation de grappes de machines parallèles, nous avons considéré la conception d’un langage proche de BSML mais sans les barrières de synchronisation. Il est souvent admis que les barrières de synchronisation ne sont pas un handicap pour les performances (dans le cas d’une seule machine parallèle), notamment parce qu’une vue globale du calcul permet des optimisations qui ne sont pas possibles dans le cas d’un parallélisme moins structuré (voir par exemple [164]).

L’éventualité de performances un peu moins bonnes n’est pas si désavantageuse compte tenu de la plus grande facilité de conception, de correction et de vérification des algorithmes (et des programmes). Toutefois il y a de nombreux programmes parallèles implémentés, en particulier en MPI, qui ne suivent pas le modèle BSP mais pour lesquels on souhaite pouvoir raisonner sur le coût. C’est ce qui a conduit au modèle BSP sans barrière (BSP without barrier, BSPWB, en anglais) [232] puis au modèle MPM [231, 36]. BSPWB est un modèle directement inspiré du modèle BSP.

Il propose de remplacer la notion de superétape par la notion de m-étape définie comme suit. À chaque m-étape, chaque processeur effectue une phase de calcul suivie par une phase de communication. Durant la phase de communication, les processeurs échangent les données dont ils ont besoin pour la m-étape suivante. La machine parallèle est caractérisée par les trois paramètres suivants (les deux derniers sont exprimés comme multiples de la puissance de calcul s des processeurs) : • Le nombre de processeurs p ; • La latence L du réseau ; • Le temps g pour échanger un mot entre deux processeurs. Le temps nécessaire à un processeur i pour exécuter une m-étape s est t(s,i) borné par Ts le temps nécessaire à l’exécution de la m-étape s par la machine parallèle.

Langage MSPML

Il n’y a pas d’implantation d’un langage MSPML complet mais une implantation partielle sous forme d’une bibliothèque pour OCaml. 194 CHAPITRE 10. ML PARALLÈLE MINIMALEMENT SYNCHRONE La bibliothèque MSPMLlib est basée sur les éléments donnés à la figure 10.2. La structure de données parallèle (appelée vecteur parallèle), l’accès aux paramètres de la machine parallèle (mais ici les paramètres MPM), la création de vecteur parallèle, l’application point-à-point sont identiques aux primitives de la BSMLlib.

Les différences proviennent des primitives pour les communications : les communications sont exprimées à l’aide des primitives mget et mat. La primitive mget permet à un processeur de demander des données à plusieurs processeurs durant la même m-étape et d’envoyer des messages différents à des demandeurs différents. Sa sémantique est : mget f0 · · · fp−1 b0 · · · bp−1 = g0 · · · gp−1 où gi = fun j→if (0 ≤ j < p − 1) then (if (bi j) then (fj i) else None) else None

La primitive mat permet à des processeurs de projeter leurs valeurs et donc de les diffuser aux autres processeurs. Ces diffusions ne sont effectuées que si les autres processeurs ont besoin de ces valeurs. La sémantique de cette primitive est donc : mat v0 · · · vp−1 f = g où g = funj→if (0 ≤ j < p − 1) then (if (f j) then vj else None) else None Notons qu’en BSML, les primitives de communication n’ont qu’un argument (les valeurs à envoyer), alors qu’en MSPML ces primitives en ont deux : les valeurs qui peuvent être envoyées et les processeurs qui nécessitent ces valeurs. Ensuite, dans les deux langages, le résultat est une (ou des) fonction(s) donnant les valeurs reçues.