Architectures des systèmes informatiques
CHAPITRE 12
Parallélisation des programmes
Année 2002-2003
Suite
N°3...
Despite
the difficulty of identifying representative parallel applications and
the immaturity of of parallel software (langages and
programming environments)...
David Culler, Jaswinder Pal Singh et Anoop Gupta,
Parallel computer architecture, a hardware/software approach
En
dépit de la difficulté à trouver des applications
parallèles représentatives et de l'immaturité du logiciel
parallèle (langages et environnements de programmation)...
12.4 L'ÉVALUATION DES SYSTÈMES PARALLÈLES
La situation
Dans un domaine beaucoup plus récent et moins bien maîtrisé que l'ordinateur série, il n'est pas étonnant que l'on constate que l'évaluation est encore dans l'enfance. On se reportera aux méthodes d'évaluation des machines série. Demeure toutefois le besoin de comparer des configurations entre elles.
Les moyens
Malgré leur caractère illusoire, les Mips sont utilisés ici aussi, comme les Mflops. Ce sont de simples additions des Mips ou Mflops de chaque processeur de l'ensemble.
Sachant que pour un processeur simple ces nombres n'ont pas grand sens, en faire des additions n'apportera pas de signification.
Le besoin de comparaison cité plus haut a poussé dans la voie des bancs d'essais à l'exclusion de toute autre ambition. La difficulté est plus grande ici car il faut distinguer entre les deux modes de communication.
Les principaux :
| Banc d'essai | Mode de communication |
| ScaLapack | messages |
| TPC-A, TPC-B, TPC-C | les deux |
| SPLASH 2 | mémoire commune |
| NAS | les deux, à la main |
| PARKBENCH | messages |
| SPEC/HPCG | en cours de définition |
Le dernier est issu pour partie du groupe Spec qui réalise par ailleurs les specmarks et d'un groupe d'évaluation des machines SIMD ou machines vectorielles, le Perfect (sic) club (Pormance evaluation for cost effective transformations).
Scalapack est constitué par les programmes de calcul algébrique linéaire LAPACK, variante de LINPACK, issue du Laboratoire de Los Alamos au lieu du laboratoire Lawrence Livermore. Il contient des résolutions de systèmes d'équations, des calculs de valeurs propres, des produits de matrices etc...
Le Transaction processing performance
council ou TPC, a créé un jeu de bancs d'essais publics nommés
A, B et C. Ils veulent être représentatifs de différentes
utilisations des machines parallèles et mode transactionnel et d'accès
à des bases de données. Ils produisent le débit en
nombre de transactions par seconde ainsi que le prix par transaction.
A et C, plus complet portent
sur les transactions,
B porte sur la mise à
jour des bases.
SPLASH (Stanford paralleL applications for shared memory) est spécialisé les architectures à mémoire commune avec cohérence de cache. Il contient sept applications complètes et des programmes de calcul. Il est plus ou moins spécialisé dans le calcul scientifique et le calcul graphique.
NAS vient de la NASA. Il est consacré au calcul scientifique. Il contient des calculs de transformées de Fourier à trois dimensions et d'autres programmes complexes.
PARKBENCH est plus original que les précédents. Il est constitué de micro bancs d'essais. Il a été créé pour des systèmes à messages et a été étendu aux mémoires communes.
Le contenu de ce chapitre est très loin d'épuiser le champ de la parallélisation des programmes. Le sujet traité à titre d'exemple relève de la catégorie générale des transformations linéaires locales. Si la matrice de transformation était celle d'une transformation orthogonale de Walsh, d'Hadamard ou toute autre, seuls la taille du voisinage et les coefficients de calcul seraient modifiés.
Dans le cas des transformations globales, les processus sont alourdis par la table des coefficients qui ne peut plus être écrite dans une formule de calcul. Elle doit être construite une seule fois et émise vers chaque mémoire locale s'il y a lieu.
Un mot de conclusion sur les
dispositifs de synchronisation. La synchronisation est un phénomène
temporel.
 |
|
|
Une émission, forcément datée, et sa réception sont les outils les plus directement adéquats, ils sont donc les plus simples. Vouloir synchroniser par un 'tableau noir' comme l'est l'écriture en mémoire partagée nécessite normalement des outils supplémentaires pour prendre en compte non pas le temps directement mais l'état d'avancement des processus. La communication par messages, réalisée par une boite à lettres est une forme intermédiaire entre les deux précédentes.
Parmi les dizaines de langages parallèles existant à l'heure actuelle on peut citer quelques uns des plus utilisés.
COMPLÉMENT SUR LES MINIPROCESSUS ou processus légers (lightweight) ou «threads»
Le traitement d'un problème conduit parfois à programmer des tâches indépendantes, que l'on soit en mono ou multiprocesseur. On peut alors implanter ces tâches par des processus parallèles. Cependant, on constate que créer un processus est coûteux en temps. Certains langages ont prévu l'écriture de miniprocessus. Un miniprocessus peut être vu comme un flot de contrôle séquentiel à l'intérieur d'un processus et non comme un autre processus. Chacun partage avec d'autres code et données du programme. Il utilise les ressources du programme et ne dispose que du contexte d'exécution, la pile, les registres, le compteur ordinal. La création et la gestion d'un miniprocessus sont ainsi moins coûteux en temps et en ressources que celles d'un processus.
Leur ordonnancement est fait :
COMPLÉMENTS SUR LES PRIMITIVES DE SYNCHRONISATION, COMMUNICATION et PLACEMENT
Dans notre exemple, les primitives de communication sont fournies par le système d'exploitation. Elles ne sont pas faciles à concevoir et à écrire. Elles ralentissent la durée totale d'exécution, on essaye de minimiser ce temps en étudiant au mieux les protocoles d'échanges de messages. Ceci est fait en deux temps, la validation (ils doivent arriver à destination) et l'optimisation qui dépend des modèles de communication et de l'architecture du réseau. Le placement des processus et l'ordonnancement des tâches sont à réaliser de telle sorte qu'on recouvre au maximum les communications par les calculs.
Les communications sont étudiées soit pour des machines ou des modèles de machines soit pour des algorithmes parallèles particuliers.
Dans le premier cas figurent les hypercubes et les arbres épais. Les travaux portent sur l'interblocage et le routage dans le réseau de nœuds. Les algorithmes sont nettement hors du domaine de ces notes.
Pour programmer de manière efficace ces systèmes parallèles, on a écrit des outils et des environnements de programmation. Cependant il n'existe que des outils rudimentaires pour les protocoles de communication globale comme la diffusion, le multicast ou l'échange total, même si un effort a été entrepris sur ce point avec par exemple la bibliothèque de communication PVM (équipe de J. Dongarra à UTK) qui est devenue usuelle.
Placement, Ordonnancement
Les performances d'une simulation distribuée dépendent fortement du partage de la charge de calcul (service de clients) entre les différents processeurs.
Le partage de charge pour des applications statiques, comme des problèmes d'algèbre linéaire, est fait par un placement et un ordonnancement qui peuvent être calculés avant l'exécution dans ce cas où l'on connaît bien à l'avance le déroulement de l'application. Pour les applications dynamiques, il faut coupler cela à une répartition dynamique qui peut se traduire par une placement dynamique ou une migration.
De nombreuses solutions de partage de charge ont été proposées.
Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 12
Parallélisation des programmes
Année 2002-2003