Architectures et Algorithmique Parallèles

Ce document présente les concepts fondamentaux des architectures parallèles et de l’algorithmique parallèle. Il s’adresse principalement aux étudiants en informatique ou en génie informatique souhaitant comprendre les bases des architectures matérielles parallèles, leurs classifications, ainsi que les modèles de calcul associés.

Tendance générale et motivation du parallélisme

Depuis plus de 40 ans, l’évolution des microprocesseurs a été marquée par la réduction de la taille des transistors, permettant d’intégrer toujours plus de transistors dans un même processeur, d’augmenter la fréquence des horloges et de réduire la consommation énergétique. Cette évolution a conduit à :

• élargir les bus et les registres,
• créer des caches,
• construire des pipelines,
• augmenter le nombre d’unités fonctionnelles,
• augmenter le nombre de fils d’exécution (cœurs de calcul).

Cependant, les architectures séquentielles traditionnelles basées sur le modèle de von Neumann atteignent leurs limites en termes de performance, capacité d’accès à la mémoire et tolérance aux pannes. Les besoins croissants des applications (calcul scientifique, traitement d’images, data mining) nécessitent des ressources CPU et mémoire de plus en plus importantes.

Le parallélisme apparaît alors comme une solution incontournable car :

• une même opération peut être réalisée simultanément par plusieurs processeurs sur des données différentes,
• des opérations différentes peuvent être exécutées en parallèle,
• cela permet d’accélérer les calculs complexes ou répétitifs sur de larges ensembles de données.

Applications parallèles

Les architectures parallèles sont utilisées dans divers domaines :

• simulations et modélisations industrielles (Renault, aéronautique),
• météorologie et climatologie,
• réalité virtuelle et augmentée,
• simulation temps réel de phénomènes physiques,
• cinéma (effets spéciaux, films d’animation).

Mesures de puissance de calcul

Deux unités sont couramment utilisées pour mesurer la puissance de calcul :

• MIPS (Machine Instructions Per Second) : nombre d’instructions exécutées par seconde,
• FLOPS (Floating Point Operations Per Second) : nombre d’opérations en virgule flottante effectuées par seconde.

Architectures parallèles : définition et classification

Un ordinateur parallèle est une machine composée de plusieurs processeurs (identiques ou non) qui coopèrent pour traiter une application. Sa performance dépend à la fois des performances individuelles des ressources et de leur agencement (latence, débit).

Les architectures parallèles sont construites à partir des composants d’une architecture séquentielle (unités de traitement, unités de contrôle, mémoire, entrées/sorties) reliés par un réseau de communication interne.

Classification de Flynn (1969)

La classification la plus connue des architectures parallèles est celle de Flynn, qui distingue quatre catégories selon le nombre de flux d’instructions et de données :

• SISD (Single Instruction stream, Single Data stream) : architecture séquentielle classique où une instruction est exécutée sur une donnée à la fois.
• MISD (Multiple Instruction stream, Single Data stream) : machines spécialisées (ex. systoliques) où plusieurs instructions sont exécutées simultanément sur la même donnée.
• SIMD (Single Instruction stream, Multiple Data stream) : plusieurs processeurs exécutent la même instruction en même temps sur des données différentes. Adapté aux traitements réguliers (ex. calcul matriciel, traitement d’image).
• MIMD (Multiple Instruction stream, Multiple Data stream) : chaque processeur exécute son propre code sur des données différentes, de façon synchrone ou asynchrone. C’est la catégorie la plus répandue aujourd’hui (multi-cœurs, clusters).

Exemple d’architecture SISD

Dans une architecture SISD, l’unité de contrôle (UC) reçoit un flux d’instructions (FI) depuis la mémoire (UM) et les envoie à l’unité de traitement (UT), qui effectue les opérations sur un flux de données (FD) également issu de la mémoire.

Exemple simple :

pour i de 1 à n faire
  v(i) = v1(i) + v2(i)

Chaque addition est réalisée séquentiellement sur une donnée à la fois.

Exécution SIMD

Dans une architecture SIMD, tous les processeurs exécutent la même instruction simultanément, mais sur des données différentes. Cette exécution est synchrone et déterministe. Par exemple, pour un traitement d’image, chaque processeur peut appliquer un filtre sur une partie différente de l’image.

Lorsqu’une instruction conditionnelle est rencontrée (if... then... else), tous les processeurs reçoivent les instructions des deux branches, mais seuls ceux dont la condition locale est vraie exécutent la branche correspondante, les autres restent inactifs.

Exemple d’exécution conditionnelle SIMD

if (cond)
  blocV;
else
  blocA;
blocB;

Chaque processeur active un bit local ACTIF selon la condition cond. Seuls les processeurs avec ACTIF = VRAI exécutent blocV, les autres blocA. Tous exécutent ensuite blocB.

Architecture MIMD

Dans une architecture MIMD, chaque processeur exécute son propre flux d’instructions sur des données différentes. Ces exécutions peuvent être synchrones ou asynchrones, déterministes ou non. On distingue deux sous-types :

• MIMD à mémoire partagée (multiprocesseurs) : tous les processeurs accèdent à une mémoire globale partagée, souvent via un bus ou un réseau d’interconnexion.
• MIMD à mémoire distribuée (multicalculateurs) : chaque processeur possède sa propre mémoire locale et communique avec les autres via un réseau d’interconnexion.

Mémoire partagée dans MIMD

La mémoire partagée permet un accès direct et transparent à toute la mémoire par tous les processeurs. Elle est construite à partir de plusieurs modules mémoire reliés par un réseau d’interconnexion. Ce modèle minimise la latence d’accès mais limite l’extensibilité à un grand nombre de processeurs.

Pour éviter la surcharge du bus mémoire, on utilise des mémoires caches entre les processeurs et le bus. Ces caches conservent les mots mémoire récemment accédés, réduisant ainsi le trafic sur le bus.

Des commutateurs (ex. CROSSBAR, OMEGA) peuvent être utilisés pour construire des multiprocesseurs avec plus de 64 processeurs, en reliant les processeurs aux modules mémoire via une matrice de commutation ou un réseau de commutateurs 2x2.

Illustrations d’architectures mémoire partagée

• SMP (Symmetric Multiprocessor) : mémoire unique partagée avec accès uniforme (temps d’accès identique pour tous les processeurs). Généralement un petit nombre de processeurs connectés via un bus central.
• NUMA (Non-Uniform Memory Access) : mémoire partagée mais avec des temps d’accès différents selon la localisation de la mémoire.
• CC-NUMA (Cache-Coherent NUMA) : extension de NUMA avec cohérence des caches.
• COMA (Cache-Only Memory Access) : mémoire accessible uniquement via des caches.

Mémoire distribuée dans MIMD

Dans ce modèle, chaque processeur a sa mémoire locale privée. Les données sont stockées dans la mémoire locale d’un ou plusieurs nœuds. Pour accéder aux données d’autres nœuds, les processeurs doivent échanger des messages via un réseau d’interconnexion. Ce modèle est fortement lié au modèle de programmation par passage de messages.

Les architectures distribuées utilisent souvent des topologies d’interconnexion complexes, comme des hypercubes ou des maillages, avec des routeurs pour gérer les communications entre nœuds.

Illustrations d’architectures mémoire distribuée

• Structure abstraite : ensemble de nœuds composés chacun d’un processeur et d’une mémoire locale.
• Hypercube : réseau d’interconnexion où chaque nœud est connecté à plusieurs autres selon une topologie en hypercube.
• DMA (Direct Memory Access) : mécanisme permettant un accès direct à la mémoire via le réseau.
• Réseau en maillage : routeurs connectent les nœuds selon une topologie en grille.

Glossaire des termes clés

• Architecture SISD : architecture séquentielle avec un seul flux d’instructions et un seul flux de données.
• Architecture MISD : architecture avec plusieurs flux d’instructions exécutant simultanément sur un seul flux de données.
• Architecture SIMD : architecture où plusieurs processeurs exécutent la même instruction sur des données différentes.
• Architecture MIMD : architecture où plusieurs processeurs exécutent des instructions différentes sur des données différentes.
• Multiprocesseur : système MIMD à mémoire partagée.
• Multicalculateur : système MIMD à mémoire distribuée.
• Pipeline : technique permettant de découper une opération en plusieurs étapes traitées en parallèle pour augmenter le débit.
• Cache : mémoire rapide intermédiaire entre le processeur et la mémoire principale, utilisée pour réduire la latence d’accès.
• Bus : canal de communication partagé entre plusieurs composants.
• Commutateur : dispositif permettant de connecter plusieurs processeurs à plusieurs modules mémoire de façon flexible.
• Hypercube : topologie d’interconnexion en forme de cube multidimensionnel utilisée dans les architectures distribuées.
• DMA (Direct Memory Access) : mécanisme permettant de transférer des données directement entre mémoire et périphériques sans intervention du processeur.

Points clés à retenir

• Le parallélisme est une réponse aux limites des architectures séquentielles face aux besoins croissants en puissance de calcul.
• La classification de Flynn distingue quatre types d’architectures selon les flux d’instructions et de données : SISD, MISD, SIMD, MIMD.
• Les architectures SIMD conviennent aux traitements réguliers et synchrones, tandis que les architectures MIMD sont plus flexibles et répandues.
• Dans MIMD, la mémoire peut être partagée (multiprocesseurs) ou distribuée (multicalculateurs), chaque modèle ayant ses avantages et contraintes.
• Les techniques comme le pipeline, les caches et les commutateurs améliorent les performances des architectures parallèles.
• La communication entre processeurs est un enjeu majeur, gérée via des bus, réseaux d’interconnexion ou passage de messages selon l’architecture.