Architectures SIMD/MIMD pour calculateurs parallèles

Architectures de calculateurs massivément parallèles

• Différents types d'architectures sont étudiés: SIMD/MIMD
• Les calculateurs massivément parallèles ont trois composants de base : processeur, réseau d'interconnexion et mémoire.

Structure générale d'un calculateur (massivément) parallèle

• La mémoire contient des données et des instructions
• Le réseau d'interconnexion relie les processeurs et la mémoire.
• Les processeurs (PE) sont interconnectés pour le traitement parallèle des données.

Plan de l'étude

• L'introduction est incluse dans le plan
• Le principe des architectures SIMD/MIMD est abordé
• Un processeur élémentaire est expliqué
• Le rôle du réseau d'interconnexion est détaillé
• L'organisation de la mémoire est décrite
• Quelques exemples de machines sont présentés

Classification (1)

• La classification de Flynn est une approche de base pour les architectures SIMD/MIMD.
• SISD : Un seul flux d'instruction, un seul flux de données
• SIMD : Un seul flux d'instruction, multiple flux de données
• MIMD : Multiple flux d'instruction, multiple flux de données

Organisation de la mémoire

• La mémoire partagée partage un espace d'adressage unique par tous les processeurs
• La mémoire distribuée : Chaque processeur possède sa propre mémoire.

Pipelines

• Une opération dans une unité fonctionnelle est divisée en plusieurs étapes élémentaires.
• L'exemple donné est l'additionneur flottant (4 étapes).
• Le pipeline est applicable aux opérations flottantes, aux opérations de lecture/écriture mémoire, et à l'unité de contrôle.
  • Des tableaux illustrent la séquence d'exécution dans un pipeline.

Pipelines (suite)

• Le temps de traversée de l'étage i du pipeline est noté Ti
• Le temps d'exécution d'une séquence de n opérations noté T(n)
  • T(n) = temps de startup (α) + nombre d'étapes (η) x temps par étape (τ)
• La vitesse d'exécution V(n) est donnée par : V(n) = n / T(n) = n / (α + ητ)

Parallélisme entre unités fonctionnelles

• Plusieurs unités fonctionnelles peuvent exécuter différentes instructions en parallèle.
• Les exemples incluent additionneur, multiplieur, unité lecture/écriture mémoire.
• Le parallélisme est applicable avec des unités de pipeline.

Machines SIMD

• Chaque instruction est diffusée à tous les processeurs.
• Chaque processeur exécute l'instruction ou reste inactif (bit d'inhibition).
• Structure mémoire en bancs indépendants
• Le réseau d'interconnexion est un permuteur synchrone.

Machines SIMD (suite)

• Les vecteurs sont divisés en tranches de P éléments au plus.
• L'algorithme DO i = 1, n c(i) = a(i) + b(i) est une illustration.
• Des diagrammes/exemples de l'implantation des données dans les bancs mémoire illustrent les conflits de bancs.

Machines SIMD (suite)

• Des exemples d'implantations mémoire différentes sont données.
• L'implantation des données dans les mémoires pose le problème des conflits de bancs.
• Le réseau d'interconnexion devient crucial pour réaliser le parallélisme.

Machines SIMD (suite)

• Les performances des machines SIMD sont en plateau.

Variante à mémoire locale

• Il n'y a pas de différence fondamentale avec le cas mémoire commune.
• Le nombre de processeurs est égal (ou peut être différent) au nombre de bancs mémoire.
• Se préter mieux à l'intégragion.
• Nécessité de faire transiter les données par la mémoire locale.

Premier bilan des machines SIMD

• Les avantages incluent une architecture simple, répétitive, modulaire, les processeurs élémentaires simples et le fonctionnement synchrone.
• Les inconvénients incluent les possibilités de parallélisme trop réduites et une architecture spécialisée.

Architectures MIMD mémoire commune

• Les processeurs sont autonomes et s'assurent de leur synchronisation.
• Un espace d'adressage unique est utilisé.
• Le réseau d'interconnexion fonctionne comme un commutateur téléphonique.
• Le mouvement explicite des données entre processeurs n'est pas nécessaire.

Machines MIMD à mémoire distribuée

• Les processeurs et la mémoire sont autonomes.
• L'espace d'adressage est distribué, limité au banc mémoire associé.
• Le réseau fonctionne par échanges de messages.
• Le mouvement explicite des données est nécessaire entre les processeurs.

Topologies des machines à mémoire distribuée

• Machines à mémoire distribuée peuvent avoir des topologies de grille 2D, 3D ou tore
• L'hypercube est une autre topologie possible
• Les liens de communication sont explicités pour chacune des topologies

Premier bilan : machine MIMD à mémoire partagée

• Les avantages incluent une programmation simple et l'absence de migrations inutiles des données.
• Les inconvénients incluent la difficulté de la réalisation et les performances du réseau qui impactent la performance globale.

Premier bilan : machine MIMD à mémoire distribuée

• Les avantages incluent la facilité d'extension et les bonnes performances mémoire.
• Les inconvénients incluent une programmation qui gère les communications entre processeurs, les problèmes de performances en accès mémoire non locaux.
• Une tendance est de fournir un espace d'adressage unique au programmeur.

Processeurs élémentaires (machines SIMD)

• Les processeurs spécialisés sont possibles sans séquenceur complet.
• Exemples : processeurs 1 bit (DAP, Connection Machine 1 & 2), processeurs 4 bits (Maspar), couplage avec des opérateurs flottants (CM2).

Processeurs élémentaires (machines MIMD)

• Les microprocesseurs standards peuvent être utilisés (peu de contraintes).
• Nécessité de synchronisations et de gestion des communications.
• Le processeur peut assurer le routage des données.
• Les exemples incluent le transputer (solution partielle).

Algorithmique parallèle

• L'impact du parallélisme sur les performances est variable et dépendant de l'application.
• Nouvelles mesures de complexité sont introduites : longueur de vecteurs, largeur du parallélisme et volume de communication.

Algorithmique parallèle (suite)

• Définitions des notions de T₁, Tp(A), Speedup Sp(A) et Efficiency Ep(A) sont données
• Les propriétés Sp(A) ≤ p et Ep(A) ≤ 1 sont présentées

Un résultat général sur la machine parallèle

Propriété des vecteurs

Machines vectorielles

• Les machines vectorielles incluent des unités scalaires et des unités vectorielles.
• Elles permettent le traitement de données scalaires et vectorielles.
• L'exemple de la machine CRAY est cité comme exemple d'unité matérielle capable d'opérer sur des scalaires et des vecteurs.

Opérations vectorielles

• Les opérations vectorielles étendent les opérations arithmétiques classiques aux opérations sur les vecteurs.
• Des exemples d'opérations vectorielles composantes à composante et de réduction sont donnés.

Exemples

• Des exemples de manipulation de vecteurs et d'instructions vectorielles sont détaillés.

Vue logicielle des opérations vectorielles

• La vue logicielle des opérations vectorielles décompose l'exécution en phases de chargement, d'opérations synchrones, de rangement et d'exécution séquentielle.

Exemple

• L'exemple montre une boucle dont la formulation vectorielle est équivalente
• L'importance du masque pour les opérations conditionnelles est soulignée.

Intérêt de la notion de masque

• Les branchements conditionnels peuvent être traités efficacement à l'aide de masques.
• Un exemple montre comment un code avec branchements IF peut être transformé en opérations vectorielles utilisant un masque.