MODÈLES ET LANGAGES PARALLÈLES DE «HAUT NIVEAU»

Le modèle PRAM. Le premier modèle théorique de machines parallèles à avoir été réellement utilisé est le modèle PRAM, Parallel Random Access Machine, introduit dans [110]. Ce modèle comprendp processeurs et une mémoire partagée. Chaque processeur dispose, en outre, d’une mémoire locale de petite taille. Les processeurs opèrent de façon synchrone, où, à chaque étape d’un algorithme PRAM, certains processeurs sont actifs et exécutent la même opération qui est soit un calcul en mémoire locale, soit une lecture de la mémoire partagée, soit une écriture dans cette même mémoire. Les autres processeurs sont inactifs. De plus, selon le mode d’accès (concurrent ou exclusif durant la lecture ou l’écriture) à la mémoire partagée, une machine PRAM est classifiée comme suit :

• Le modèle EREW PRAM (Exclusif Read, Exlusif Write) permet à un seul processeur au plus, durant une étape de l’algorithme, d’avoir accès à une cellule de la mémoire partagée afin d’y lire ou d’y écrire. Tout comportement contraire n’est pas acceptéé ;

• Le modèle CREW PRAM (Concurrent Read, Exclusif Write) : la lecture d’une cellule de mémoire partagée par plusieurs processeurs est permise. Toutefois, une écriture simultanée n’est pas tolérée ;

• Le modèle CRCW PRAM (Concurrent Read, Concurrent Write) introduit des conflits lorsque plu-sieurs processeurs écrivent dans la même cellule de la mémoire partagée. De nombreux modèles ont été proposés pour permettent de résoudre les conflits ainsi créés comme par exemple ;

• Le modèle QRQW PRAM (Queue Read, Queue Write) [118] qui n’autorise, pour chaque cellule mémoire, qu’à un seul processeur la lecture ou l’écriture. Toutes les autres demandes de lecture ou d’écriture des autres processeurs sont stockées dans une «file» pour être exécutées dans une étape ultérieure [56]. Le temps d’accès à une cellule de la mémoire partagée, à un instant donné, est alors proportionnel au nombre d’accès concurrents (en lecture ou en écriture) à cette même cellule.

Les modèles PRAM permettent une description simple et universelle des algorithmes parallèles. Malheu-reusement, ils ignorent les coûts de communications inter-processeurs, rendant les temps d’exécution des algorithmes difficilement prévisibles sur un grand nombre d’architectures parallèles comme les grappes de PC. Les modèles BSP et MPM, eux, sont portables sur un plus grand nombre d’architectures.

Le modèle LogP. Le modèle LogP, introduit dans [79], est un modèle asynchrone pour machines à la mémoire distribuée. Contrairement au modèle BSP, la synchronisation y est abandonnée dans le but de refléter, et ceci de manière plus précise, les caractéristiques des machines réelles, par l’utilisation de quatre paramètres :

1. L est la latence (latency en anglais) liée à la communication d’un message contenant un octet (ou plutôt, un petit nombre d’octets) d’un processeur à un autre ,

2. o est le surcoût (overhead en anglais) dans une communication liée à l’envoi ou à la réception d’un message,

3. g est le temps minimum écoulégap( dans la littérature anglo-saxonne) entre deux envois ou réceptions consécutifs de messages sur un processeur,

4. P est le nombre de couples processeurs/mémoires.

Dans ce modèle, lors d’une communication point à point, l’envoi d’un message contenant un paquet de données nécessite un temps2 × o + L, alors que l’envoi de n paquets de données ne nécessite que 2 × o + L + (n − 1) × max(o, g). Les paramètres L, g et o sont exprimés comme étant des multiples du cycle du processeur (durée d’une exécution de calcul élémentaire). Le modèle suppose que le réseau d’interconnexions a une capacité finie, de manière à ce que, au plus ⌈L/g⌉ messages puissent transiter via le réseau à un moment donné. Le modèle LogP tente ainsi de résoudre le problème de saturation du ré-seau d’interconnexions, en supposant que seuls des messages élémentaires (de petite taille) peuvent être échangés entre les processeurs.

Des extensions de ce modèle comme LogGP [4] ou LogP étendu [281], ont été proposées pour supporter des communications mettant en œuvre des messages longs. Not ons qu’il est possible de simuler le modèle BSP dans le modèle LogP et vice versa [32]. Néanmoins, les auteurs de cet article notent que le modèle BSP est plus simple d’utilisation et permet une meilleure portabilité. De plus, d’un point vue asymptotique, les deux modèles sont équivalents. Le modèle MPM permet de s’affranchir des synchronisations globales BSP. Il est donc un modèle asynchrone mais plus structuré queLogP et possède les mêmes paramètres que ceux du modèle BSP (seules leurs valeurs changent).

Le modèle CGM. Le modèle CGM (Coarse Grained Multicomputer) a été introduidans [94]. Une ma-chine CGM est constituée dep processeurs P1 , . . . , Pp où chaque processeur dispose d’une mémoire locale de taille O(s/p) (certains travaux, comme dans [174], supposent une mémoirelocale de taille Ω(n/p) où n est la taille des données à traiter). La taille de la mémoire ocale de chaque processeur est supérieure à celle donnée par le modèle PRAM, ce qui qualifie ce modèle de «gros grain». Ce modèle est en fait une version simplifiée du modèle BSP qui s’affranchit des paramètresl et g, ainsi que de l’étape de synchronisation.

Un algorithme CGM est une suite d’étapes alternant d’une part du calcul local et d’autre part une ronde de communication globale. Dans cette ronde, une seule h-relation, avec h = O(n/p), est effectuée, c’est-à-dire chaque processeur envoie ou reçoit au plus O(n/p) données. Le temps d’exécution d’un algorithme CGM est donc la somme des traitements locaux avec celui des rondes de communication. Notons que dans le modèle CGM, une étape de traitement combinant du calcul local suivi d’une ronde de communication est équivalent à une super-étape du modèle BSP.

Le modèle CGM a été utilisé pour définir de nombreux algorithmes [90] comme par exemple des algo-rithmes sur les graphs [64]. Néanmoins, un algorithme CGM est facilement simulable comme un algorithme BSP [90], ce qui fait que, généralement, les coûts de l’algorithme sont donnés dans les deux modèles. De plus, le modèle CGM est dans certains cas, comme dans [18, 19, 20], trop rigide car le rééquilibrage des charges de certains algorithmes ou la distribution des données (l’implantation des structures de données pa-rallèles présentée dans ce manuscrit en est aussi un exemple), peuvent nécessiter desh-relations de volumes h imprévisibles.

Mémoires externes. Le modèle des disques parallèles (Parallel Disk Model, PDM), introduit dans [269], est employé pour modéliser une hiérarchie à deux niveaux de mémoires, se composant deD disques parallèles et avec p ≥ 1 processeurs inter-connectés par une mémoire partagée ou unréseau. La mesure de coût de PDM est le nombre d’opérations d’E/S exigées par unalgorithme où les éléments peuvent être transférés sur la mémoire interne aux disques en une seule opération d’E/S. Le modèle PDM capture les calculs et les coûts d’E/S, mais il a été conçu pour un type spécifique de réseau de transmission où les opérations de communication prennent une simple unité de temps, comparable à une instruction de l’unité centrale de traitement. Le modèle BSP (et les modèles en dérivant), capturent mieux les communications et leurs coûts pour une classe plus générale de réseaux mais neapturentc pas les coûts des E/S.

Un algorithme parallèleout-of-core pour le calcul de l’inversion de grandes matrices a été présenté dans [61]. L’algorithme emploie seulement la diffusion comme primitive de communication. Celle-ci a un coût proche de la diffusion directe BSP. Les coûts des E/S sont similaires aux nôtres (voir au chapitre 9), c’est-à-dire linéaires (et non constants) à la taille de la donnée écrite (ou lue) sur les disques parallèles.

Dans l’article [81], les auteurs se sont concentrés sur l’optimisation de quelques algorithmes parallèles de tri. Ces algorithmes utilisent les mémoires externes ainsi que de multiples couches de mémoire de la machine parallèle, comme par exemple les caches (ou tampons) de la mémoire vive ou des disques. Les auteurs se sont servis d’un langage de bas niveau et le grand nombre de paramètres de ce modèle implique une complexité algorithmique difficilement analysable. Aussi, dans l’article [92], les auteurs ont implanté des opérations d’E/S pour mesurer leur modèle mais toujoursà l’aide d’un langage de bas niveau. De la même manière, une bibliothèque d’E/S pour une extention à mémoire externe d’un modèle proche de BSP est décrite dans [132].

À notre connaissance, notre bibliothèque est la première po ur une extention du modèle BSP avec des mémoires externes, appelés EM-BSP (comprenant disques locaux ou disques partagés), et pour un langage fonctionnel parallèle doté d’une sémantique formelle et d’un modèle formel de coût.

Modèles pour les algorithmes «diviser-pour-régner» et la sous-synchronisation. Une façon d’implanter des algorithmes «diviser-pour-régner» BSP, dans le cadre d’un langage à objets, est présentée dans [258]. Il n’y a, pour l’instant, ni de sémantique formele ni d’implantation. Le principe des opérations des objets est très proche de la superposition parallèle. Lemême auteur propose dans l’article [197] une nouvelle extension du modèle BSP qui permet d’aborder facilement les algorithmes «diviser-pour-régner», en ajoutant un niveau supplémentaire au modèle BSP et de nouveaux paramètres.

L’article [280] présente un langage à patrons qui offre des patrons «diviser-pour-régner». Toutefois, le modèle de coût n’est plus le modèle BSP mais le modèle D-BSP [89] qui permet la synchronisation de sous-réseaux. Des arguments pour rejeter une telle possibilité sont présentés dans [133].

Dans la bibliothèque BSPlib [147], la synchronisation de sous-réseaux n’est pas autorisée comme ex-pliqué dans les articles [133, 242]. La bibliothèque PUB [40] offre des caractéristiques supplémentaires par rapport à la proposition de standard BSPlib notamment, l a synchronisation de sous-réseaux (suivant le modèle BSP* [23]). Un exemple d’application implantée en utilisant ces possibilités est donné dans [41].

Modèles pour la désynchronisation. Il existe de nombreux travaux sur la désynchronisation des barrières BSP qui se basent sur différentes méthodes de comptage de messages [6, 103, 166]. À notre connaissance, la seule extension qui a donné lieu à une implantation disponible est celle que l’on trouve dans la bibliothèque PUB. La synchronisation bsp_oblsync prend en argument le nombre de messages devant être reçus par le processeur à une super-étape donnée.Lorsque ce nombre de messages a été reçu, le processeur passe à la super-étape d’après sans prendre part à une synchronisation globale. Le modèle de coût MPM est plus simple et MSPML permet en plus une confluence des résultats qui n’est pas garantie avec la primitive bsp_oblsync de la PUB.

On trouve de nombreux langages fonctionnels pour la programmation parallèle. Les présenter tous serait trop long. Nous avons donc choisi de ne présenter que les plusintéressants pour notre propos.

Le langage Eden [28, 52, 167] étend Haskell avec des primitives de créations dynamiques de processus qui échangent des données sur des canaux de communications implicites vus par le programmeur comme des «listes paresseuses». La création et l’exécutionde processus se fait avec : process :: (Trans a, Trans b) => (a -> b) -> Process a b ( # ) :: (Trans a, Trans b) => Process a b -> a -> b tel que (process (\x -> e1)) # e2 permet la création d’un processus qui exécuterae1 avec e2 comme paramètre. Le processus parent est responsable du transfert des données vers ce nouveau processus. Un canal de communication implicite a donc été construit entre ces deux processus. Le programmeur peut aussi créer ses propres canaux avec les fonctions suivantes:

class NFData a => Trans a where (…)

type ChanName a = …

new :: Trans a => (ChanName a -> a -> b) -> b

parfill :: Trans a => ChanName a -> a -> b -> b

où Trans est une sous-classe de NFData (Normal Form Data), l’ensemble des données transmissibles. L’implantation (avec ces fonctionnalités) d’un patron «diviser-pour-régner» a été présentée dans [29]. Au-cun modèle de parallélisme n’est utilisé dans ce langage. Laprévision des performances y est donc très difficile, à la différence de BSML qui repose sur le modèle BSP.

Gph. GpH [137, 260] est aussi une extension du langage Haskell. Gph utilise un parallélisme explicite avec deux constructeurs «Par» et «Seq». Toutes les expressions données au constructeur «Seq» seront éva-luées séquentiellement, tandis qu’un processus est exécut pour évaluer l’expression donnée au constructeur «Par». La programmation parallèle y est donc donnée dans sa version la plus simple. Mais aucune prédic-tion des performances n’y est possible car la création des processus dépend des heuristiques du système. De même, aucun modèle de parallélisme n’est utilisé.

Dans ces extentions parallèles de Haskell (Gph et Eden), la sûreté et la confluence des opérations d’E/S sont assurées par l’utilisation demonads [270] et de mémoires externes locales. L’utilisation de disques partagés n’est pas spécifiée. Ces langages parallèles autorisent également aux processeurs d’échanger des canaux d’écriture ou de lecture et donnent ainsi la possibilité à un processeur d’écrire (ou de lire) sur les fichiers d’un autre processeur (si celui-ci n’est pas déjà ou vert en écriture). Cela augmente l’expressivité du langage mais diminue fortement la prévision des performances car il devient difficile de donner un coût au opérations d’E/S : elles peuvent être locales ou nécessiter le réseau. Trop de communications sont ainsi cachées.