Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 12
Parallélisation des programmes
Année 2002-2003

Suite N°2...

12.3.3 Orchestration

Le type d'architecture sur laquelle les programmes seront exécutés : message ou mémoire commune apparaît pleinement ici.

Trois modèles seront présentés successivement.
Le premier, dit à données parallèles, exploite la régularité des données en utilisant une séquence de commande commune à tous les processus.
Le second, dit à mémoire commune, crée autant de structures de commande que de processus et utilise des primitives de synchronisation et d'exclusion mutuelle pour les sections critiques.
Le troisième relève de la communication par messages.

12.3.3.1 Orchestration en modèle de données parallèles

La structure de commande est commune à tous les processus. Il peut convenir pour un problème parfaitement à données régulières uniformément traitées avec un seul processus. La décomposition du tableau de données et les affectations de lignes se suffisent par elles mêmes. Les parties spécifiques au parallélisme sont en caractères italiques dans le pseudocode ci-dessous.

Les déclarations hors boucles sont globales, les déclarations dans la boucle principale sont locales.

Les boucles pour_tout signifient que la boucle est valable uniformément pour tous les processus.

ALLOUER réalise la réservation de la zone de variables partagées pour le tableau.

La variable diffloc différence locale est locale à chaque processus.

Les appels RÉPARTIR et RÉDUIRE sont de type bibliothèque ou macros ou encore font partie de l'environnement de programmation, leur code est inséré à la compilation.

RÉPARTIR spécifie l'affectation des itérations aux processus, qui portent par BLOC sur des blocs contigus de lignes sans décomposition des colonnes.

RÉDUIRE fait l'addition de tous les diffloc, constituant la variable globale diff.

Les bonnes propriétés de ces données régulières ne sont hélas pas toujours présentes. Il faut alors envisager un autre modèle dans lequel chaque processus aura sa structure de commande propre et où la communication sera faite à l'initiative de chacun.

Exercice 5 : Analyser les variantes en itération séparée et écrire un programme leur correspondant.

12.3.3.2 Orchestration en modèle d'adresses communes

Nous déclarons comme précédemment un tableau commun à deux dimensions. Les processus y accéderont par lecture ou écriture selon leurs besoins comme dans un calcul séquentiel. Nous avons besoin de mécanismes de création et de synchronisation de processus. Ces primitives sont normalement fournies par l'environnement de programmation. En voici la liste.

CRÉER (p,proc,arg) Crée p processus qui exécuteront la procédure proc avec arg comme arguments.
ALLOUER (nom,taille) Alloue à la variable A des données partagées en quantité 'taille'.
BLOQUE (nom) Met en œuvre une exclusion mutuelle sur 'nom'.
DÉBLOQUE (nom) Libère l'exclusion mutuelle.
PORTE (nombre) Crée une synchronisation globale en suspendant le fonctionnement jusqu'à ce que 'nombre' processus soient terminés.
ATTEND_LA_FIN Attend que tous les processus soient terminés.
ATTEND (drapeau) Attend que drapeau soit en position, utilisé pour une synchronisation point à point.
POSITIONNE DRAPEAU(bin) bin = 1 positionne le drapeau, 0 ôte la position.

Les primitives spécifiques du parallélisme sont BLOQUE, DÉBLOQUE, PORTE, ATTEND_LA_FIN, ATTEND et POSITIONNE_DRAPEAU en italiques. Un pseudocode possible est fourni ci-après.

Examinons les différences par rapport à la solution précédente.

La procédure principale main est lancée par le système d'exploitation. Elle contient les déclarations et la lecture des paramètres (dont n qui est toujours le paramètre (n+2)X(n+2)). Le tableau A est créé puis initialisé par ALLOUER dans l'espace partagé. Les variables déclarées hors la procédure main sont globales; diffloc, maxloc, i, j etc. sont des variables privées de chaque processus.

Le programme crée ensuite les processus au nombre de nbproc-1. Chacun, ainsi que le processus principal va exécuter RÉSOUDRE, ce qui fera bien en tout nbproc processus dans un système symétrique.

Chaque processus est égal aux autres pour l'exécution de RÉSOUDRE. Il est repéré dans le système par un nom sous la forme du numéro ident, lisible comme variable locale. On l'utilise pour définir les bornes d'action de chaque processus.

On remarque qu'ici chaque processus prend séparément la décision d'exécuter une boucle supplémentaire sur le vu de diffloc, variable locale, mais cette décision est la même pour tous puisque la valeur considérée est la même après la PORTE. Il s'agit d'un léger surcroît de travail pour chaque processus.

La paire BLOQUE - DÉBLOQUE des lignes 25a à 25c, crée une exclusion mutuelle sous la forme d'un section critique pour éviter les mises à jour croisées de la variable diff.

Ces verrous peuvent être coûteux en temps car susceptibles de mettre des opérations en séquence.

La primitive PORTE manipule un entier sémaphore sans file d'attente. Elle gère le point de synchronisation commun.

Le code n'est pas, ici non plus, très différent de la solution séquentielle. Il diffère par les primitives ajoputées d'allocation et de synchronisation, ainsi que par quelques variantes dans les variables de service.

Nous avons traité le cas d'un système multiprocesseur autonome. S'il s'agissait d'un multiprocesseur hébergé par un hôte, les différences porteraient sur le programme principal, exécuté par l'hôte qui connaît nécessairement le nombre de processeurs. Il n'y aurait donc pas besoin de la primitive CRÉER. Le système hôte émettrait les procédures en autant d'exemplaires aux destinataires.

12.3.3.3. Orchestration en modèle d'échange de messages

• La première différence majeure est que nous n'avons pas ici la possibilité, ni l'utilité de créer un tableau commun dans une mémoire commune éventuelle. Le programme sera beaucoup moins ressemblant à un programme séquentiel. Les données seront écrites dans les mémoires locales sous la forme de structures plus petites, sur lesquelles le processus correspondant opèrera.
• La seconde différence importante est la nature des outils de synchronisation.

Aux primitives :

BLOQUE, DÉBLOQUE, PORTE, ATTEND-LA_FIN, ATTEND et POSITIONNE_DRAPEAU, correspondent ici les primitives :
ENVOYER, RECEVOIR, POUR_TOUS et ACCUMULER, les deux dernières non utilisées ici.

Il n'est créé que nbproc-1 processus car le processus principal existe déjà et par défaut exécutera lui aussi la procédure Résoudre.

Le tableau A est réparti en nbproc tableaux, chacun sous le nom de Aloc, dans les mémoires locales. Ces tableaux ont n/nbproc+2 lignes et n+2 colonnes. Le chargement initial de ces tableaux locaux n'est pas détaillé, il est fait par la macro ALLOC.

La synchronisation se fait par les deux primitives ENVOYER et RECEVOIR. Elles ont été écrites ici sous une forme simplifiée. En toute rigueur elles devraient contenir la taille précise du message : taille d'un flottant, d'un entier, d'un caractère, d'une chaîne etc. On a remplacé ces tailles par la lettre t (sauf pour les chaînes) afin de ne pas alourdir la notation sans nécessité.

Ces primitives ne sont pas équivalentes en termes de communication. L'exécution de la première provoque une migration effective dans le réseau. La seconde ne fait que lire dans le tampon (privé ou global) si un message s'y trouve. Si oui elle le lit et modifie la mémoire locale en conséquence, sinon le processus attend que ce message soit disponible. C'est ainsi que la synchronisation se fait sur RECEVOIR et non sur ENVOYER.

Les arguments de ENVOYER sont ici l'adresse de début des données à émettre, la taille (simple =t ou multiple : n*t), l'identification du destinataire, et une marque, étiquette du message, figurée ici toujours en majuscules.

Les arguments de RECEVOIR sont ici l'adresse locale où écrire le message, la taille du message, l'identification de l'émetteur (son numéro), et la marque optionnelle (écrite ici en majuscules). La marque est utilisée dans le cas d'un tampon de messages pour identifier précisément le message parmi ceux qui sont attendus.

On remarque que les adresses de début des données à émettre et de début de la zone de rangement sont écrites sous la forme du nom d'une variable. Il s'agit plus précisément d'un pointeur au sens du langage C.

Il n'est pas dans notre propos de détailler les différentes sémantiques des primitives que l'on peut rencontrer dans des systèmes différents. Grossièrement, elles ont deux types principaux synchrone et asynchrone. Dans le type synchrone, ENVOYER provoque la mise en attente du processus émetteur jusqu'à ce qu'il ait reçu confirmation de la réception par le retour d'un accusé de prise en charge par le receveur. Dans le type asynchrone, utilisé ici, le message est mis en file d'attente, locale ou globale, et le processus émetteur poursuit son activité.

On trouve des variantes selon les environnements de programmation et notamment la paire POUR_TOUS et ACCUMULER ( broadcast-reduce). Il s'agit de primitives telles que la première provoque une émission d'un processus vers tous et la seconde la réception (avec accumulation) par un seul processus des messages envoyés par tous les autres. Aucun rendez-vous ou autre synchronisation n'est nécessaire car les ENVOYER et RECEVOIR jouent ce rôle.

On remarque dans la dernière occurrence de ENVOYER le signe * au lieu de l'identification du destinataire. Cette autre syntaxe est du type : envoyer à tous. Cette variante élimine la nécessité de la primitive POUR_TOUS.

À ce stade, il est utile de comparer le primitives utilisées à la lumière des principes de la logistique.

La comparaison va porter sur :

BLOQUE, DÉBLOQUE, PORTE, ATTEND-LA_FIN, ATTEND et POSITIONNE_DRAPEAU, d'une part,

ENVOYER, RECEVOIR, POUR_TOUS et ACCUMULER, d'autre part.

La première observation est le statut différent des deux communications :

• dans la communication dans le temps, par mémoire commune, ce qui n'est pas interdit par le blocage, est permis;
• dans la communication dans l'espace, par passage de message, ce qui n'est pas explicitement fait, ou autorisé, une émission comme une réception ne peut pas se faire et peut donc être considéré comme interdit.

Le correspondant de DÉBLOQUE est alors : POUR_QUI_VEUT, variante de POUR_TOUS, sans obligation de réception.

La PORTE a pour correspondant ACCUMULER avec vérification par le processus qui reçoit du fait qu'un seuil est atteint.

ATTEND_LA_FIN a un sens voisin, le seuil à atteindre est la réception d'un envoi de fin par tous les processus.

ATTEND et son outil POSITIONNE_DRAPEAU est une primitive inessentielle car elle peut être construite par entente entre les processus sous la forme de l'utilisation d'un mot en mémoire.

Exercice 6 : L'utilisation de primitives synchrones peut provoquer des interblocages selon les ordres respectifs d'émission et de réception. Qu'en serait-il alors du programme ci-dessus ?

Exercice 7 : Récrire la partie relative au cumul des différences avec les primitives POUR_TOUS et ACCUMULER.