Résumé #9: Les machines parallèles

À lire: pp. 604 à 607 3/3, 612 1/2 à 615 1/2, 618 1/2 à 619 1/2, 620 9/10 à 621 2/3, 630 1/2 à 632 1/2, 633 1/2 à 636 2/3.

9.1 Introduction

- Malgré l'augmentation importante de la puissance et des performances des processeurs, de nombreuses applications ne peuvent toujours pas être traitées en un temps raisonnable sur un ordinateur traditionnel, e.g., simulation de phénomènes physiques (prédiction météorologique, physique nucléaire) ou biologiques (analyse de protéines), traitement d'images, analyse du langage parlé, etc. Pour ces applications, des superordinateurs ou des machines parallèles doivent être utilisés.

- Désavantage des superordinateurs classiques: Très coûteux (pcq. leur mise en oeuvre utilise une technologie hautement sophistiquée, e.g., circuits hautement optimisés, réfrigération, etc.) et pas vraiment d'usage général.

- Solution alternative pour obtenir des machines plus performantes: Machines avec plusieurs processeurs travaillant en parallèle = Machines parallèles.

- Principe de base des machines parallèles =

Obtenir une grande puissance de calcul par l'utilisation d'un grand nombre de processeurs standards de faible coût.

- Classification de Flynn pour les machines parallèles: Classe les machines selon le parallélisme du flux des données et des instructions:

• SISD = Single Instruction stream, Single Data stream: Uniprocesseur classique exécutant (du point de vue du programmeur) une seule instruction à la fois, e.g., machine RISC moderne.
• SIMD = Single Instruction stream, Multiple Data streams: Machine où une seule instruction s'exécute sur plusieurs données indépendantes à la fois.
• MISD = Multiple Instruction streams, Single Data stream: Aucune machine connue.
• MIMD = Multiple Instruction streams, Multiple Data streams: Plusieurs instructions distinctes s'exécutant sur des données indépendantes.

9.2 Machines SIMDs

- Très courantes parmi les premières machines parallèles mais de moins en moins usité de nos jours.

- Ce sont, typiquement, des machines qui manipulent des tableaux (matrices) de données, conduisant à du ``parallélisme de données''.

- Exemple: Soit A, B et C des tableaux 16 16 de nombres points-flottants:

• VAR A, B, C: ARRAY[1..16, 1..16] OF REAL;

Soit une machine SIMD avec 256 processeurs. Si l'on répartit les (256) éléments de A et B entre les divers processeurs, alors le temps requis pour l'addition matricielle suivante est simplement le temps requis pour une (1) addition point-flottante:

• C := A + B; (* C[i,j] := A[i,j] + B[i,j], pour 1 <= i, j <= 16 *)

- Motivations initiales pour de telles machines:

• Obtenir une machine parallèle de coût faible en dupliquant uniquement les unités d'exécution sans dupliquer l'unité de contrôle.
• Minimiser l'espace mémoire requis en ayant une seule copie du code.

- Désavantage majeur: Excellent pour des programmes manipulant des tableaux uniformes de données, mais, autrement, très difficile à programmer et à utiliser efficacement (les instructions conditionnelles peuvent conduire un grand nombre de processeurs à rester inactifs).

9.3 Machines MIMDs

- Idée de base = Obtenir une machine parallèle puissante en interconnectant plusieurs processeurs ordinaires.

- Deux grandes classes:

• Multiprocesseurs: Tous les processeurs partagent la même mémoire via un bus commun. La communication entre les processeurs se fait via la mémoire partagée.
• Multiordinateurs: Chaque processeur possède sa propre mémoire indépendante et est relié aux autres processeurs via un réseau d'interconnexion. La communication entre les processeurs se fait généralement par l'échange de messages.

9.4 Programmation des machines MIMDs

- Problème très difficile: Demande d'organiser la division du travail entre les processeurs, de répartir les données entre les divers modules de mémoire, de planifier la communication des informations entre les processeurs, d'assurer leur synchronisation, etc. Probablement une raison importante pour laquelle les machines parallèles sont encore assez peu utilisées.

9.5 Machines MIMDs avec bus

- Bus:

• Ensemble de fils servant de lien de communication entre les divers sous-systèmes de la machine.
• Avantages: Coût faible (un seul ensemble de fils); utilisation souple (facile d'ajouter de nouveaux composants).
• Désavantages: Ne permet pas plusieurs accès simultanés; la vitesse maximale de transmission diminue lorsque le nombre de composants et la longueur du bus augmente.

- Multiprocesseur avec mémoire partagée via bus:

• Chaque processeur possède son propre cache, dans le but de diminuer le nombre d'accès à la mémoire.
• Avantages: Solution simple et peu coûteuse; l'utilisation du cache permet de réduire de façon importante le trafic sur le bus (donc de diminuer les conflits d'accès).
• Désavantages: Impose une limite importante au nombre maximum de processeurs pouvant être utilisés (à cause des conflits d'accès au bus); Problème de la cohérence des caches.

- Les machines parallèles construites au cours des 10 dernières années furent surtout des multiprocesseurs avec bus, pcq. plus faciles à construire.

9.5 Machines MIMDs avec réseau

- Réseau:

• Avantages: Contrairement au bus, permet que plusieurs communications soient en cours simultanément. Permet aussi d'interconnecter un plus grand nombre de processeurs.
• Désavantage: Plus coûteux qu'un bus.
• Topologie statique: Les liens entre les noeuds (noeud = processeur + mémoire) sont fixes. Un noeud communique directement uniquement avec ses voisins immédiats. Les autres communications doivent se faire en plusieurs étapes.
• Topologie dynamique: Les liens entre les noeuds sont créés selon les besoins (via l'établissement d'une connexion temporaire dans le réseau). Permet à un noeud de communiquer directement avec n'importe quel autre noeud (ou presque).

- Multiordinateur = Machine MIMD avec réseau: Chaque noeud est composé d'un processeur et de sa mémoire (et du cache associé) et communique avec les autres noeuds via le réseau d'interconnexion.

- Machines parallèles plus récentes et à venir:

• Multiordinateurs avec réseau, pcq. vont permettre d'obtenir des machines utilisant un plus grand nombre de processeurs.
• Machines avec mémoire physique distribuée mais ayant, du point de vue du programmeur, une mémoire globale partagée (mémoire virtuelle).