Programmation fonctionnelle BSP

Programmation fonctionnelle BSP

Bulk-Synchronous Parallelism

Le modèle de programmation parallèle BSP (Bulk Synchronous Parallelism) [34, 201, 202, 203, 204, 263] décrit une architecture parallèle (abstraite), un modèle d’exécution et un modèle de coût. L’objectif d’un tel modèle est de fournir un niveau d’abstraction facilitant, d’une part la portabilité des programmes sur une grande variété d’architectures parallèles, et d’autre part de permettre la prévision des performances d’un même programme sur différentes machines parallèles réelles.

Ainsi, le modèle BSP fournit une machine abstraite dont les opérations sont de plus haut niveau que celles de la majorité des modèles de programma tion parallèle [35, 162, 242] mais autorise aussi de prévoir les temps d’exécution de manière réaliste.

Architecture parallèle BSP

Un ordinateur parallèle BSP possède trois ensembles de composants : 1. Un ensemble homogène de paires processeur-mémoire (généralement des processeurs séquentiels avec des blocs locaux de mémoire), 2. Unréseau de communication permettant l’échange de messages entre ses paires, 3. Une unité de synchronisation globale qui exécute des demandes collectives de barrières de synchro nisation. Figure 2.1 — Une super-étape BSP L’objectif des barrières de synchronisation est de garantir la cohérence des données communiquées entre les processeurs et cela sans que l’ordre des séquences de communication n’affecte le traitement des diffé rents processeurs.

De nombreuses architectures réelles peuvent être vues comme des ordinateurs parallèles BSP. Les ma chines à mémoirepartagéepeuvent,par exemple,êtreutilisées de telle sorte que chaqueprocesseurn’accède qu’à une partie (qui sera alors «privée») de la mémoire partagée et les communications peuvent être faites en utilisant des zones de la mémoire partagée réservées à cet usage. De plus, l’unité de synchronisation est rarement physique mais plutôt logicielle (l’article [148] présente plusieurs algorithmes à cet effet).

Les performances d’un ordinateur BSP sont caractérisées par trois paramètres exprimés en multiples de la vitesse des processeurs (sinon, la vitesse des processeurs s, est donnée en tant que quatrième paramètre) : 1. Le nombrede paires processeur-mémoire p; 2. Le temps l nécessaire à la réalisation d’une barrière de synchronisation; 3. Le temps g pour un échange collectif de messages entre les différentes paires processeur-mémoire, appelé 1-relation et dans laquelle chaque processeur envoie et/ou reçoit au plus un mot; le réseau peut réaliser un échange,

appelé h-relation (chaque processeur envoie et/ou reçoit au plus h mots) en un temps h ×g. Ainsi, une h-relation est une communication globale où chaque processeur peut envoyer ou recevoir au plus h mots. En pratique, ces paramètres peuvent être facilement obtenus en utilisant des tests [147]. En général, les paramètres l et g dépendent du nombre de processeurs p et de la topologiedu réseau. Par exemple, dans une machine parallèle dite «en hypercube», la valeur de l est de l’ordre de O(logp) alors qu’elle est de l’ordre de O(p) dans un réseau linéaire.

Modèle d’exécution

L’exécution d’un programmeBSP est uneséquencede super-étapes. Chaquesuper-étapeest divisée en trois phases successives et logiquement disjointes (voir à la figure 2.1) : 1. Chaqueprocesseurutilise les données qu’il détient localement pour faire des calculs de façon séquen tielle et pour demander des transferts depuis ou vers d’autres processeurs;

2. Le réseau réalise les échanges de données demandés à la phase précédente; 3. Unebarrièrede synchronisationglobale terminela super-étape. À l’issue de cette barrière de synchro nisation globale, les données échangées sont effectivement disponibles pour la nouvelle super-étape qui commence alors