Architecture d'ordinateur parallèle - Guide rapide

Au cours des 50 dernières années, il y a eu d'énormes développements dans les performances et les capacités d'un système informatique. Cela a été possible grâce à la technologie VLSI (Very Large Scale Integration). La technologie VLSI permet de loger un grand nombre de composants sur une seule puce et d'augmenter les fréquences d'horloge. Par conséquent, plusieurs opérations peuvent être effectuées à la fois, en parallèle.

Le traitement parallèle est également associé à la localisation des données et à la communication des données. Parallel Computer Architecture est la méthode d'organisation de toutes les ressources pour maximiser les performances et la programmabilité dans les limites données par la technologie et le coût à tout moment.

Pourquoi une architecture parallèle?

L'architecture informatique parallèle ajoute une nouvelle dimension dans le développement de système informatique en utilisant de plus en plus de processeurs. En principe, les performances obtenues en utilisant un grand nombre de processeurs sont supérieures aux performances d'un seul processeur à un moment donné.

Tendances des applications

Avec l'avancement de la capacité matérielle, la demande d'une application performante a également augmenté, ce qui à son tour a imposé une demande au développement de l'architecture informatique.

Avant l'ère des microprocesseurs, un système informatique très performant était obtenu par une technologie de circuit exotique et une organisation de la machine, ce qui les rendait coûteux. Maintenant, un système informatique très performant est obtenu en utilisant plusieurs processeurs, et les applications les plus importantes et les plus exigeantes sont écrites sous forme de programmes parallèles. Ainsi, pour des performances plus élevées, des architectures parallèles et des applications parallèles doivent être développées.

Augmenter les performances d'une application Speedup est le facteur clé à considérer. Speedup sur p processeurs est défini comme -

$$Speedup(p \ processors)\equiv\frac{Performance(p \ processors)}{Performance(1 \ processor)}$$

Pour le problème résolu unique,

$$performance \ of \ a \ computer \ system = \frac{1}{Time \ needed \ to \ complete \ the \ problem}$$ $$Speedup \ _{fixed \ problem} (p \ processors) =\frac{Time(1 \ processor)}{Time(p \ processor)}$$

Informatique scientifique et technique

L'architecture parallèle est devenue indispensable dans le calcul scientifique (comme la physique, la chimie, la biologie, l'astronomie, etc.) et les applications d'ingénierie (comme la modélisation de réservoir, l'analyse des flux d'air, l'efficacité de la combustion, etc.). Dans presque toutes les applications, il existe une demande énorme de visualisation de la sortie de calcul, ce qui entraîne une demande de développement de calcul parallèle pour augmenter la vitesse de calcul.

Informatique commerciale

Dans l'informatique commerciale (comme la vidéo, les graphiques, les bases de données, OLTP, etc.), des ordinateurs à grande vitesse sont également nécessaires pour traiter une énorme quantité de données dans un délai spécifié. Desktop utilise des programmes multithread qui ressemblent presque aux programmes parallèles. Cela exige à son tour de développer une architecture parallèle.

Tendances technologiques

Avec le développement de la technologie et de l'architecture, il existe une forte demande pour le développement d'applications performantes. Les expériences montrent que les ordinateurs parallèles peuvent fonctionner beaucoup plus rapidement que les processeurs uniques les plus développés. De plus, des ordinateurs parallèles peuvent être développés dans la limite de la technologie et du coût.

La principale technologie utilisée ici est la technologie VLSI. Par conséquent, de nos jours, de plus en plus de transistors, de portes et de circuits peuvent être installés dans la même zone. Avec la réduction de la taille de la caractéristique VLSI de base, la fréquence d'horloge s'améliore également proportionnellement à elle, tandis que le nombre de transistors augmente avec le carré. On peut s'attendre à ce que l'utilisation de nombreux transistors à la fois (parallélisme) fonctionne bien mieux qu'en augmentant la fréquence d'horloge

Les tendances technologiques suggèrent que le bloc de base à puce unique offrira une capacité de plus en plus grande. Par conséquent, la possibilité de placer plusieurs processeurs sur une seule puce augmente.

Tendances architecturales

Le développement technologique décide de ce qui est faisable; l'architecture convertit le potentiel de la technologie en performances et capacités.Parallelism et localitysont deux méthodes où de plus grands volumes de ressources et plus de transistors améliorent les performances. Cependant, ces deux méthodes se disputent les mêmes ressources. Lorsque plusieurs opérations sont exécutées en parallèle, le nombre de cycles nécessaires pour exécuter le programme est réduit.

Cependant, des ressources sont nécessaires pour soutenir chacune des activités simultanées. Des ressources sont également nécessaires pour allouer le stockage local. La meilleure performance est obtenue par un plan d'action intermédiaire qui utilise des ressources pour utiliser un certain degré de parallélisme et un degré de localité.

Généralement, l'histoire de l'architecture informatique a été divisée en quatre générations ayant les technologies de base suivantes -

• Les tubes à vide
• Transistors
• Circuits intégrés
• VLSI

Jusqu'en 1985, la durée était dominée par la croissance du parallélisme au niveau des bits. Microprocesseurs 4 bits suivis de 8 bits, 16 bits, etc. Pour réduire le nombre de cycles nécessaires pour effectuer une opération 32 bits complète, la largeur du chemin de données a été doublée. Plus tard, des opérations 64 bits ont été introduites.

La croissance de instruction-level-parallelisma dominé le milieu des années 80 au milieu des années 90. L'approche RISC a montré qu'il était simple de canaliser les étapes de traitement des instructions de sorte qu'en moyenne, une instruction soit exécutée dans presque chaque cycle. La croissance de la technologie des compilateurs a rendu les pipelines d'instructions plus productifs.

Au milieu des années 80, les ordinateurs à microprocesseur se composaient de

• Une unité de traitement d'entiers
• Une unité à virgule flottante
• Un contrôleur de cache
• SRAM pour les données du cache
• Stockage des tags

À mesure que la capacité de la puce augmentait, tous ces composants ont été fusionnés en une seule puce. Ainsi, une seule puce consistait en un matériel séparé pour l'arithmétique des entiers, les opérations en virgule flottante, les opérations de mémoire et les opérations de branchement. Outre le pipelining des instructions individuelles, il récupère plusieurs instructions à la fois et les envoie en parallèle à différentes unités fonctionnelles lorsque cela est possible. Ce type de parallélisme de niveau d'instruction est appelésuperscalar execution.

Des machines parallèles ont été développées avec plusieurs architectures distinctes. Dans cette section, nous aborderons différentes architectures informatiques parallèles et la nature de leur convergence.

Architecture de communication

L'architecture parallèle améliore les concepts conventionnels de l'architecture informatique avec l'architecture de communication. L'architecture informatique définit les abstractions critiques (comme la limite utilisateur-système et la limite matériel-logiciel) et la structure organisationnelle, tandis que l'architecture de communication définit les opérations de base de communication et de synchronisation. Il aborde également la structure organisationnelle.

Le modèle de programmation est la couche supérieure. Les applications sont écrites dans un modèle de programmation. Les modèles de programmation parallèle incluent -

• Espace d'adressage partagé
• Message passant
• Programmation parallèle de données

Shared addressla programmation est comme l'utilisation d'un babillard électronique, où l'on peut communiquer avec une ou plusieurs personnes en affichant des informations à un endroit particulier, qui est partagé par toutes les autres personnes. L'activité individuelle est coordonnée en notant qui fait quelle tâche.

Message passing est comme un appel téléphonique ou des lettres où un destinataire spécifique reçoit des informations d'un expéditeur spécifique.

Data parallella programmation est une forme organisée de coopération. Ici, plusieurs personnes effectuent une action sur des éléments séparés d'un ensemble de données simultanément et partagent des informations à l'échelle mondiale.

La memoire partagée

Les multiprocesseurs à mémoire partagée sont l'une des classes les plus importantes de machines parallèles. Il offre un meilleur débit sur les charges de travail multiprogrammées et prend en charge les programmes parallèles.

Dans ce cas, tous les systèmes informatiques permettent à un processeur et à un ensemble de contrôleurs d'E / S d'accéder à un ensemble de modules de mémoire par une certaine interconnexion matérielle. La capacité de mémoire est augmentée en ajoutant des modules de mémoire et la capacité d'E / S est augmentée en ajoutant des périphériques au contrôleur d'E / S ou en ajoutant un contrôleur d'E / S supplémentaire. La capacité de traitement peut être augmentée en attendant qu'un processeur plus rapide soit disponible ou en ajoutant plus de processeurs.

Toutes les ressources sont organisées autour d'un bus mémoire central. Grâce au mécanisme d'accès au bus, n'importe quel processeur peut accéder à n'importe quelle adresse physique du système. Comme tous les processeurs sont équidistants de tous les emplacements mémoire, le temps d'accès ou la latence de tous les processeurs est le même sur un emplacement mémoire. C'est appelésymmetric multiprocessor.

Architecture de transmission de messages

L'architecture de passage de messages est également une classe importante de machines parallèles. Il assure la communication entre les processeurs sous forme d'opérations d'E / S explicites. Dans ce cas, la communication est combinée au niveau des E / S, au lieu du système de mémoire.

Dans l'architecture de passage de messages, la communication utilisateur est exécutée à l'aide d'appels de système d'exploitation ou de bibliothèque qui exécutent de nombreuses actions de niveau inférieur, qui incluent l'opération de communication réelle. Il en résulte une distance entre le modèle de programmation et les opérations de communication au niveau matériel physique.

Send et receiveest les opérations de communication de niveau utilisateur les plus courantes dans le système de transmission de messages. Envoyer spécifie un tampon de données local (qui doit être transmis) et un processeur distant de réception. Receive spécifie un processus d'envoi et un tampon de données local dans lequel les données transmises seront placées. Dans l'opération d'envoi, unidentifier ou un tag est attaché au message et l'opération de réception spécifie la règle de correspondance comme une étiquette spécifique d'un processeur spécifique ou n'importe quelle étiquette de n'importe quel processeur.

La combinaison d'un envoi et d'une réception correspondante complète une copie de mémoire à mémoire. Chaque extrémité spécifie son adresse de données locale et un événement de synchronisation par paire.

Convergence

Le développement du matériel et des logiciels a effacé la frontière claire entre la mémoire partagée et les camps de transmission de messages. Le passage de messages et un espace d'adressage partagé représentent deux modèles de programmation distincts; chacun donne un paradigme transparent pour le partage, la synchronisation et la communication. Cependant, les structures de base de la machine ont convergé vers une organisation commune.

Traitement parallèle des données

Une autre classe importante de machines parallèles est appelée de manière variée: matrices de processeurs, architecture parallèle de données et machines à instruction multiple à instruction unique. La caractéristique principale du modèle de programmation est que les opérations peuvent être exécutées en parallèle sur chaque élément d'une grande structure de données régulière (comme un tableau ou une matrice).

Les langages de programmation parallèles de données sont généralement appliqués en visualisant l'espace d'adressage local d'un groupe de processus, un par processeur, formant un espace global explicite. Comme tous les processeurs communiquent ensemble et qu'il existe une vue globale de toutes les opérations, un espace d'adressage partagé ou un passage de message peuvent être utilisés.

Problèmes de conception fondamentaux

Le développement d'un modèle de programmation ne peut à lui seul augmenter l'efficacité de l'ordinateur ni le développement du matériel à lui seul. Cependant, le développement de l'architecture informatique peut faire la différence dans les performances de l'ordinateur. Nous pouvons comprendre le problème de conception en nous concentrant sur la manière dont les programmes utilisent une machine et sur les technologies de base fournies.

Dans cette section, nous discuterons de l'abstraction de la communication et des exigences de base du modèle de programmation.

Abstraction de la communication

L'abstraction de la communication est la principale interface entre le modèle de programmation et l'implémentation du système. C'est comme le jeu d'instructions qui fournit une plate-forme pour que le même programme puisse s'exécuter correctement sur de nombreuses implémentations. Les opérations à ce niveau doivent être simples.

L'abstraction de la communication est comme un contrat entre le matériel et le logiciel, qui permet à l'autre la flexibilité de s'améliorer sans affecter le travail.

Exigences du modèle de programmation

Un programme parallèle a un ou plusieurs threads fonctionnant sur des données. Un modèle de programmation parallèle définit quelles données les threads peuventname, lequel operations peut être effectuée sur les données nommées, et quel ordre est suivi par les opérations.

Pour confirmer que les dépendances entre les programmes sont appliquées, un programme parallèle doit coordonner l'activité de ses threads.

Le traitement parallèle a été développé en tant que technologie efficace dans les ordinateurs modernes pour répondre à la demande de performances supérieures, de coûts inférieurs et de résultats précis dans des applications réelles. Les événements simultanés sont courants dans les ordinateurs d'aujourd'hui en raison de la pratique de la multiprogrammation, du multitraitement ou du multicomputing.

Les ordinateurs modernes disposent de progiciels puissants et étendus. Pour analyser le développement des performances des ordinateurs, nous devons d'abord comprendre le développement de base du matériel et des logiciels.

• Computer Development Milestones - Il y a deux grandes étapes de développement de l'ordinateur - mechanical ou electromechanicalles pièces. Les ordinateurs modernes ont évolué après l'introduction des composants électroniques. Les électrons à haute mobilité dans les ordinateurs électroniques ont remplacé les pièces opérationnelles dans les ordinateurs mécaniques. Pour la transmission d'informations, le signal électrique qui se déplace presque à la vitesse d'une lumière a remplacé les engrenages ou leviers mécaniques.

• Elements of Modern computers - Un système informatique moderne comprend du matériel informatique, des jeux d'instructions, des programmes d'application, un logiciel système et une interface utilisateur.

Les problèmes informatiques sont classés en calcul numérique, raisonnement logique et traitement transactionnel. Certains problèmes complexes peuvent nécessiter la combinaison des trois modes de traitement.

• Evolution of Computer Architecture- Au cours des quatre dernières décennies, l'architecture informatique a subi des changements révolutionnaires. Nous avons commencé avec l'architecture Von Neumann et maintenant nous avons des multi-ordinateurs et des multiprocesseurs.

• Performance of a computer system- Les performances d'un système informatique dépendent à la fois des capacités de la machine et du comportement du programme. La capacité de la machine peut être améliorée grâce à une meilleure technologie matérielle, des fonctionnalités architecturales avancées et une gestion efficace des ressources. Le comportement du programme est imprévisible car il dépend de l'application et des conditions d'exécution

Multiprocesseurs et multi-ordinateurs

Dans cette section, nous aborderons deux types d'ordinateurs parallèles -

• Multiprocessors
• Multicomputers

Multi-ordinateurs à mémoire partagée

Les trois modèles de multiprocesseurs à mémoire partagée les plus courants sont:

Accès mémoire uniforme (UMA)

Dans ce modèle, tous les processeurs partagent la mémoire physique de manière uniforme. Tous les processeurs ont le même temps d'accès à tous les mots mémoire. Chaque processeur peut avoir une mémoire cache privée. La même règle est suivie pour les périphériques.

Lorsque tous les processeurs ont un accès égal à tous les périphériques, le système est appelé symmetric multiprocessor. Lorsque seul un ou quelques processeurs peuvent accéder aux périphériques, le système est appeléasymmetric multiprocessor.

Accès mémoire non uniforme (NUMA)

Dans le modèle multiprocesseur NUMA, le temps d'accès varie en fonction de l'emplacement du mot mémoire. Ici, la mémoire partagée est physiquement répartie entre tous les processeurs, appelés mémoires locales. La collection de toutes les mémoires locales forme un espace d'adressage global auquel tous les processeurs peuvent accéder.

Architecture de mémoire cache uniquement (COMA)

Le modèle COMA est un cas particulier du modèle NUMA. Ici, toutes les mémoires principales distribuées sont converties en mémoires cache.

• Distributed - Memory Multicomputers- Un système multi-ordinateurs à mémoire distribuée se compose de plusieurs ordinateurs, appelés nœuds, interconnectés par un réseau de transmission de messages. Chaque nœud agit comme un ordinateur autonome doté d'un processeur, d'une mémoire locale et parfois de périphériques d'E / S. Dans ce cas, toutes les mémoires locales sont privées et ne sont accessibles qu'aux processeurs locaux. C'est pourquoi, les machines traditionnelles sont appeléesno-remote-memory-access (NORMA) Machines.

Ordinateurs multivecteurs et SIMD

Dans cette section, nous aborderons les supercalculateurs et les processeurs parallèles pour le traitement vectoriel et le parallélisme des données.

Supercalculateurs vectoriels

Dans un ordinateur vectoriel, un processeur vectoriel est connecté au processeur scalaire en tant que fonction facultative. L'ordinateur hôte charge d'abord le programme et les données dans la mémoire principale. Ensuite, l'unité de contrôle scalaire décode toutes les instructions. Si les instructions décodées sont des opérations scalaires ou des opérations de programme, le processeur scalaire exécute ces opérations à l'aide de pipelines fonctionnels scalaires.

D'autre part, si les instructions décodées sont des opérations vectorielles, alors les instructions seront envoyées à l'unité de contrôle vectoriel.

Supercalculateurs SIMD

Dans les ordinateurs SIMD, un nombre «N» de processeurs sont connectés à une unité de contrôle et tous les processeurs ont leurs unités de mémoire individuelles. Tous les processeurs sont connectés par un réseau d'interconnexion.

Modèles PRAM et VLSI

Le modèle idéal donne un cadre approprié pour développer des algorithmes parallèles sans tenir compte des contraintes physiques ou des détails de mise en œuvre.

Les modèles peuvent être appliqués pour obtenir des limites de performances théoriques sur des ordinateurs parallèles ou pour évaluer la complexité VLSI sur la surface de la puce et le temps opérationnel avant la fabrication de la puce.

Machines à accès aléatoire parallèle

Sheperdson et Sturgis (1963) ont modélisé les ordinateurs Uniprocesseurs conventionnels comme des machines à accès aléatoire (RAM). Fortune et Wyllie (1978) ont développé un modèle de machine à accès aléatoire parallèle (PRAM) pour modéliser un ordinateur parallèle idéalisé sans surcharge d'accès mémoire et synchronisation.

Une PRAM à N-processeurs possède une unité de mémoire partagée. Cette mémoire partagée peut être centralisée ou répartie entre les processeurs. Ces processeurs fonctionnent sur un cycle synchronisé de mémoire de lecture, de mémoire d'écriture et de calcul. Ainsi, ces modèles spécifient comment les opérations de lecture et d'écriture simultanées sont gérées.

Voici les opérations de mise à jour de la mémoire possibles -

• Exclusive read (ER) - Dans cette méthode, à chaque cycle, un seul processeur est autorisé à lire à partir de n'importe quel emplacement mémoire.

• Exclusive write (EW) - Dans cette méthode, au moins un processeur est autorisé à écrire dans un emplacement mémoire à la fois.

• Concurrent read (CR) - Il permet à plusieurs processeurs de lire les mêmes informations à partir du même emplacement mémoire dans le même cycle.

• Concurrent write (CW)- Il permet des opérations d'écriture simultanées vers le même emplacement mémoire. Pour éviter les conflits d'écriture, certaines politiques sont mises en place.

Modèle de complexité VLSI

Les ordinateurs parallèles utilisent des puces VLSI pour fabriquer des matrices de processeurs, des matrices de mémoire et des réseaux de commutation à grande échelle.

De nos jours, les technologies VLSI sont bidimensionnelles. La taille d'une puce VLSI est proportionnelle à la quantité d'espace de stockage (mémoire) disponible dans cette puce.

Nous pouvons calculer la complexité spatiale d'un algorithme par la zone de puce (A) de l'implémentation de puce VLSI de cet algorithme. Si T est le temps (latence) nécessaire pour exécuter l'algorithme, alors AT donne une limite supérieure sur le nombre total de bits traités par la puce (ou E / S). Pour certains calculs, il existe une borne inférieure, f (s), telle que

AT ² > = O (f (s))

Où A = surface de la puce et T = temps

Pistes de développement architectural

L'évolution des ordinateurs parallèles je l'ai répandue le long des pistes suivantes -

• Plusieurs pistes de processeur
  • Piste multiprocesseur
  • Piste multi-ordinateur
• Piste de données multiples
  • Piste vectorielle
  • Piste SIMD
• Piste de plusieurs threads
  • Piste multithread
  • Piste Dataflow

  Dans multiple processor track, on suppose que différents threads s'exécutent simultanément sur différents processeurs et communiquent via un système de mémoire partagée (piste multiprocesseur) ou de passage de messages (piste multi-ordinateur).

  Dans multiple data track, on suppose que le même code est exécuté sur la quantité massive de données. Cela se fait en exécutant les mêmes instructions sur une séquence d'éléments de données (piste vectorielle) ou en exécutant la même séquence d'instructions sur un ensemble similaire de données (piste SIMD).

  Dans multiple threads track, on suppose que l'exécution entrelacée de différents threads sur le même processeur permet de masquer les délais de synchronisation entre les threads s'exécutant sur différents processeurs. L'entrelacement des threads peut être grossier (piste multithread) ou fin (piste de flux de données).

  Dans les années 80, un processeur à usage spécial était populaire pour fabriquer des multi-ordinateurs appelés Transputer. Un transputer se composait d'un processeur central, d'une petite mémoire SRAM, d'une interface de mémoire principale DRAM et de quatre canaux de communication, le tout sur une seule puce. Pour établir une communication informatique parallèle, des canaux ont été connectés pour former un réseau de Transputers. Mais il manque de puissance de calcul et ne peut donc pas répondre à la demande croissante d'applications parallèles. Ce problème a été résolu par le développement de processeurs RISC et il était également bon marché.

  L'ordinateur parallèle moderne utilise des microprocesseurs qui utilisent le parallélisme à plusieurs niveaux comme le parallélisme au niveau des instructions et le parallélisme au niveau des données.

  Processeurs hautes performances

  Les processeurs RISC et RISCy dominent aujourd'hui le marché des ordinateurs parallèles.

  Les caractéristiques du RISC traditionnel sont -

  • A peu de modes d'adressage.
  • A un format fixe pour les instructions, généralement 32 ou 64 bits.
  • A des instructions de chargement / stockage dédiées pour charger les données de la mémoire pour enregistrer et stocker les données du registre vers la mémoire.
  • Les opérations arithmétiques sont toujours effectuées sur les registres.
  • Utilise le pipelining.

  La plupart des microprocesseurs de nos jours sont superscalaires, c'est-à-dire que dans un ordinateur parallèle plusieurs pipelines d'instructions sont utilisés. Par conséquent, les processeurs superscalaires peuvent exécuter plus d'une instruction en même temps. L'efficacité des processeurs superscalaires dépend de la quantité de parallélisme de niveau instruction (ILP) disponible dans les applications. Pour garder les pipelines remplis, les instructions au niveau matériel sont exécutées dans un ordre différent de celui du programme.

  De nombreux microprocesseurs modernes utilisent une approche de super pipelining . En super pipelining , pour augmenter la fréquence d'horloge, le travail effectué au sein d'un étage de pipeline est réduit et le nombre d'étages de pipeline est augmenté.

  Processeurs VLIW (Very Large Instruction Word)

  Ceux-ci sont dérivés d'une microprogrammation horizontale et d'un traitement superscalaire. Les instructions des processeurs VLIW sont très volumineuses. Les opérations au sein d'une même instruction sont exécutées en parallèle et sont transmises aux unités fonctionnelles appropriées pour exécution. Ainsi, après avoir récupéré une instruction VLIW, ses opérations sont décodées. Ensuite, les opérations sont envoyées aux unités fonctionnelles dans lesquelles elles sont exécutées en parallèle.

  Processeurs vectoriels

  Les processeurs vectoriels sont du coprocesseur en microprocesseur à usage général. Les processeurs vectoriels sont généralement des registres-registres ou des mémoires-mémoire. Une instruction vectorielle est extraite et décodée, puis une certaine opération est effectuée pour chaque élément des vecteurs d'opérande, alors que dans un processeur normal, une opération vectorielle nécessite une structure de boucle dans le code. Pour le rendre plus efficace, les processeurs vectoriels enchaînent plusieurs opérations vectorielles ensemble, c'est-à-dire que le résultat d'une opération vectorielle est transmis à une autre comme opérande.

  Mise en cache

  Les caches sont un élément important des microprocesseurs haute performance. Tous les 18 mois, la vitesse des microprocesseurs devient deux fois, mais les puces DRAM pour la mémoire principale ne peuvent rivaliser avec cette vitesse. Ainsi, les caches sont introduits pour combler l'écart de vitesse entre le processeur et la mémoire. Un cache est une mémoire SRAM rapide et petite. De nombreux autres caches sont appliqués dans les processeurs modernes tels que les caches TLB, les caches d'instructions et de données, etc.

  Cache mappé direct

  Dans les caches mappés directement, une fonction «modulo» est utilisée pour le mappage un à un des adresses de la mémoire principale aux emplacements de cache. Comme une même entrée de cache peut avoir plusieurs blocs de mémoire principale mappés sur elle, le processeur doit être capable de déterminer si un bloc de données dans le cache est le bloc de données réellement nécessaire. Cette identification se fait en stockant une étiquette avec un bloc de cache.

  Cache entièrement associatif

  Un mappage entièrement associatif permet de placer un bloc de cache n'importe où dans le cache. En utilisant une politique de remplacement, le cache détermine une entrée de cache dans laquelle il stocke un bloc de cache. Les caches entièrement associatifs ont un mappage flexible, ce qui minimise le nombre de conflits d'entrée de cache. Puisqu'une mise en œuvre entièrement associative est coûteuse, celles-ci ne sont jamais utilisées à grande échelle.

  Cache associatif d'ensemble

  Un mappage associatif d'ensemble est une combinaison d'un mappage direct et d'un mappage entièrement associatif. Dans ce cas, les entrées de cache sont subdivisées en ensembles de cache. Comme dans le mappage direct, il existe un mappage fixe des blocs de mémoire vers un ensemble dans le cache. Mais à l'intérieur d'un ensemble de cache, un bloc de mémoire est mappé de manière totalement associative.

  Stratégies de cache

  Outre le mécanisme de mappage, les caches ont également besoin d'une gamme de stratégies qui spécifient ce qui doit se passer dans le cas de certains événements. Dans le cas de caches associatifs (ensemble), le cache doit déterminer quel bloc de cache doit être remplacé par un nouveau bloc entrant dans le cache.

  Certaines stratégies de remplacement bien connues sont -

  • Premier entré, premier sorti (FIFO)
  • Le moins récemment utilisé (LRU)

  Nous aborderons les multiprocesseurs et les multi-ordinateurs dans ce chapitre.

  Interconnexions système multiprocesseur

  Le traitement parallèle nécessite l'utilisation d'interconnexions système efficaces pour une communication rapide entre les périphériques d'entrée / sortie et les périphériques, les multiprocesseurs et la mémoire partagée.

  Systèmes de bus hiérarchiques

  Un système de bus hiérarchique consiste en une hiérarchie de bus reliant divers systèmes et sous-systèmes / composants dans un ordinateur. Chaque bus est composé d'un certain nombre de lignes de signal, de commande et d'alimentation. Différents bus tels que les bus locaux, les bus de fond de panier et les bus d'E / S sont utilisés pour exécuter différentes fonctions d'interconnexion.

  Les bus locaux sont les bus implémentés sur les cartes de circuits imprimés. Un bus de fond de panier est un circuit imprimé sur lequel de nombreux connecteurs sont utilisés pour brancher des cartes fonctionnelles. Les bus qui connectent des périphériques d'entrée / sortie à un système informatique sont appelés bus d'E / S.

  Commutateur crossbar et mémoire multiport

  Les réseaux commutés fournissent des interconnexions dynamiques entre les entrées et les sorties. Les systèmes de petite ou moyenne taille utilisent principalement des réseaux crossbar. Les réseaux à plusieurs étages peuvent être étendus aux systèmes plus grands, si le problème de latence accrue peut être résolu.

  L'organisation du commutateur crossbar et de la mémoire multiport est un réseau à une seule étape. Bien qu'un réseau à une seule étape soit moins coûteux à construire, plusieurs passes peuvent être nécessaires pour établir certaines connexions. Un réseau à plusieurs étages comprend plus d'un étage de boîtiers de commutation. Ces réseaux devraient pouvoir connecter n'importe quelle entrée à n'importe quelle sortie.

  Réseaux à plusieurs étages et combinés

  Les réseaux à plusieurs étages ou réseaux d'interconnexion à plusieurs étages sont une classe de réseaux informatiques à haut débit qui se compose principalement d'éléments de traitement à une extrémité du réseau et d'éléments de mémoire à l'autre extrémité, connectés par des éléments de commutation.

  Ces réseaux sont appliqués pour construire de plus grands systèmes multiprocesseurs. Cela comprend Omega Network, Butterfly Network et bien d'autres.

  Multicomputers

  Les multi-ordinateurs sont des architectures MIMD à mémoire distribuée. Le diagramme suivant montre un modèle conceptuel d'un multi-ordinateur -

  

  Les multi-ordinateurs sont des machines de transmission de messages qui appliquent une méthode de commutation de paquets pour échanger des données. Ici, chaque processeur dispose d'une mémoire privée, mais pas d'espace d'adressage global car un processeur ne peut accéder qu'à sa propre mémoire locale. La communication n'est donc pas transparente: ici les programmeurs doivent mettre explicitement des primitives de communication dans leur code.

  Ne pas avoir de mémoire accessible globalement est un inconvénient des multi-ordinateurs. Cela peut être résolu en utilisant les deux schémas suivants -

  • Mémoire partagée virtuelle (VSM)
  • Mémoire virtuelle partagée (SVM)

  Dans ces schémas, le programmeur d'application suppose une grande mémoire partagée qui est globalement adressable. Si nécessaire, les références mémoire faites par les applications sont traduites dans le paradigme de transmission de messages.

  Mémoire partagée virtuelle (VSM)

  VSM est une implémentation matérielle. Ainsi, le système de mémoire virtuelle du système d'exploitation est implémenté de manière transparente au-dessus de VSM. Ainsi, le système d'exploitation pense qu'il fonctionne sur une machine avec une mémoire partagée.

  Mémoire virtuelle partagée (SVM)

  SVM est une implémentation logicielle au niveau du système d'exploitation avec prise en charge matérielle de l'unité de gestion de la mémoire (MMU) du processeur. Ici, l'unité de partage est constituée des pages de mémoire du système d'exploitation.

  Si un processeur adresse un emplacement mémoire particulier, la MMU détermine si la page mémoire associée à l'accès mémoire se trouve ou non dans la mémoire locale. Si la page n'est pas dans la mémoire, dans un système informatique normal, elle est permutée à partir du disque par le système d'exploitation. Mais, dans SVM, le système d'exploitation récupère la page du nœud distant qui possède cette page particulière.

  Trois générations de multi-ordinateurs

  Dans cette section, nous aborderons trois générations de multi-ordinateurs.

  Choix de conception dans le passé

  Lors de la sélection d'une technologie de processeur, un concepteur de multi-ordinateurs choisit des processeurs à grain moyen à faible coût comme éléments de base. La majorité des ordinateurs parallèles sont construits avec des microprocesseurs standard du commerce. La mémoire distribuée a été choisie pour les ordinateurs multiples plutôt que l'utilisation de la mémoire partagée, ce qui limiterait l'évolutivité. Chaque processeur possède sa propre unité de mémoire locale.

  Pour le schéma d'interconnexion, les multi-ordinateurs ont des réseaux directs point à point de passage de messages plutôt que des réseaux de commutation d'adresses. Pour la stratégie de contrôle, le concepteur de multi-ordinateurs choisit les opérations asynchrones MIMD, MPMD et SMPD. Le Cosmic Cube de Caltech (Seitz, 1983) est le premier multi-ordinateurs de première génération.

  Développement présent et futur

  Les ordinateurs de nouvelle génération ont évolué de multi-ordinateurs à grain moyen à fin en utilisant une mémoire virtuelle partagée à l'échelle mondiale. Les multi-ordinateurs de deuxième génération sont encore utilisés à l'heure actuelle. Mais en utilisant un meilleur processeur comme i386, i860, etc., les ordinateurs de deuxième génération se sont beaucoup développés.

  Les ordinateurs de troisième génération sont les ordinateurs de prochaine génération sur lesquels les nœuds implémentés VLSI seront utilisés. Chaque nœud peut avoir un processeur 14-MIPS, des canaux de routage à 20 Mo / s et 16 Ko de RAM intégrés sur une seule puce.

  Le système Intel Paragon

  Auparavant, des nœuds homogènes étaient utilisés pour créer des multi-ordinateurs hypercube, car toutes les fonctions étaient données à l'hôte. Donc, cela a limité la bande passante d'E / S. Ainsi, pour résoudre des problèmes à grande échelle de manière efficace ou à haut débit, ces ordinateurs ne pouvaient pas être utilisés. Le système Intel Paragon a été conçu pour surmonter cette difficulté. Il a transformé le multi-ordinateur en un serveur d'applications avec un accès multi-utilisateur dans un environnement réseau.

  Mécanismes de transmission de messages

  Les mécanismes de transmission de messages dans un réseau multi-ordinateurs nécessitent une prise en charge matérielle et logicielle spéciale. Dans cette section, nous discuterons de certains schémas.

  Schémas de routage des messages

  Dans le multi-ordinateur avec schéma de routage de stockage et de retransmission, les paquets sont la plus petite unité de transmission d'informations. Dans les réseaux routés par trou de ver, les paquets sont ensuite divisés en flits. La longueur du paquet est déterminée par le schéma de routage et l'implémentation du réseau, tandis que la longueur du flit est affectée par la taille du réseau.

  Dans Store and forward routing, les paquets sont l'unité de base de la transmission d'informations. Dans ce cas, chaque nœud utilise un tampon de paquets. Un paquet est transmis d'un nœud source à un nœud de destination via une séquence de nœuds intermédiaires. La latence est directement proportionnelle à la distance entre la source et la destination.

  Dans wormhole routing, la transmission du nœud source au nœud de destination se fait via une séquence de routeurs. Tous les flits d'un même paquet sont transmis de manière inséparable en pipeline. Dans ce cas, seul le flit d'en-tête sait où va le paquet.

  Blocage et canaux virtuels

  Un canal virtuel est un lien logique entre deux nœuds. Il est formé par un tampon flit dans le nœud source et le nœud récepteur, et un canal physique entre eux. Lorsqu'un canal physique est alloué pour une paire, un tampon source est associé à un tampon récepteur pour former un canal virtuel.

  Lorsque tous les canaux sont occupés par des messages et qu'aucun des canaux du cycle n'est libéré, une situation de blocage se produit. Pour éviter cela, un schéma de contournement des blocages doit être suivi.

  Dans ce chapitre, nous discuterons des protocoles de cohérence de cache pour faire face aux problèmes d'incohérence multicache.

  Le problème de cohérence du cache

  Dans un système multiprocesseur, une incohérence des données peut se produire entre des niveaux adjacents ou au sein du même niveau de la hiérarchie de mémoire. Par exemple, le cache et la mémoire principale peuvent avoir des copies incohérentes du même objet.

  Comme plusieurs processeurs fonctionnent en parallèle, et indépendamment plusieurs caches peuvent posséder différentes copies du même bloc de mémoire, cela crée cache coherence problem. Cache coherence schemes aider à éviter ce problème en maintenant un état uniforme pour chaque bloc de données mis en cache.

  

  Soit X un élément de données partagées qui a été référencé par deux processeurs, P1 et P2. Au début, trois copies de X sont cohérentes. Si le processeur P1 écrit une nouvelle donnée X1 dans le cache, en utilisantwrite-through policy, la même copie sera immédiatement écrite dans la mémoire partagée. Dans ce cas, une incohérence se produit entre la mémoire cache et la mémoire principale. Lorsqu'unwrite-back policy est utilisé, la mémoire principale sera mise à jour lorsque les données modifiées dans le cache sont remplacées ou invalides.

  En général, il existe trois sources de problème d'incohérence -

  • Partage de données inscriptibles
  • Migration de processus
  • Activité d'E / S

  Protocoles de bus Snoopy

  Les protocoles Snoopy assurent la cohérence des données entre la mémoire cache et la mémoire partagée via un système de mémoire basé sur le bus. Write-invalidate et write-update les politiques sont utilisées pour maintenir la cohérence du cache.

  
  

  Dans ce cas, nous avons trois processeurs P1, P2 et P3 ayant une copie cohérente de l'élément de données «X» dans leur mémoire cache locale et dans la mémoire partagée (Figure-a). Le processeur P1 écrit X1 dans sa mémoire cache en utilisantwrite-invalidate protocol. Ainsi, toutes les autres copies sont invalidées via le bus. Il est noté «I» (Figure-b). Les blocs invalides sont également appelésdirty, c'est-à-dire qu'ils ne doivent pas être utilisés. lewrite-update protocolmet à jour toutes les copies de cache via le bus. En utilisantwrite back cache, la copie mémoire est également mise à jour (Figure-c).

  

  Événements et actions de cache

  Les événements et actions suivants se produisent lors de l'exécution des commandes d'accès à la mémoire et d'invalidation -

  • Read-miss- Lorsqu'un processeur veut lire un bloc et qu'il n'est pas dans le cache, une lecture-échec se produit. Cela initie unbus-readopération. Si aucune copie sale n'existe, la mémoire principale qui a une copie cohérente fournit une copie à la mémoire cache demandeuse. Si une copie sale existe dans une mémoire cache distante, ce cache restreindra la mémoire principale et enverra une copie à la mémoire cache demandeuse. Dans les deux cas, la copie du cache entrera dans l'état valide après un échec de lecture.

  • Write-hit - Si la copie est sale ou reservedstate, l'écriture se fait localement et le nouvel état est sale. Si le nouvel état est valide, la commande d’invalidation d’écriture est diffusée à tous les caches, annulant leurs copies. Lorsque la mémoire partagée est écrite, l'état résultant est réservé après cette première écriture.

  • Write-miss- Si un processeur ne parvient pas à écrire dans la mémoire cache locale, la copie doit provenir soit de la mémoire principale, soit d'une mémoire cache distante avec un bloc sale. Cela se fait en envoyant unread-invalidatecommande, qui invalidera toutes les copies de cache. Ensuite, la copie locale est mise à jour avec un état sale.

  • Read-hit - La lecture-hit est toujours effectuée dans la mémoire cache locale sans provoquer de transition d'état ou utiliser le bus snoopy pour l'invalidation.

  • Block replacement- Lorsqu'une copie est sale, elle doit être réécrite dans la mémoire principale par la méthode de remplacement de bloc. Cependant, lorsque la copie est dans un état valide ou réservé ou invalide, aucun remplacement n'aura lieu.

  Protocoles basés sur l'annuaire

  En utilisant un réseau à plusieurs étages pour construire un grand multiprocesseur avec des centaines de processeurs, les protocoles de cache snoopy doivent être modifiés pour s'adapter aux capacités du réseau. La diffusion étant très coûteuse à réaliser dans un réseau à plusieurs étages, les commandes de cohérence ne sont envoyées qu'aux caches qui conservent une copie du bloc. C'est la raison du développement de protocoles basés sur des répertoires pour les multiprocesseurs connectés au réseau.

  Dans un système de protocoles basé sur un répertoire, les données à partager sont placées dans un répertoire commun qui maintient la cohérence entre les caches. Ici, le répertoire agit comme un filtre où les processeurs demandent l'autorisation de charger une entrée de la mémoire primaire vers sa mémoire cache. Si une entrée est modifiée, le répertoire la met à jour ou invalide les autres caches avec cette entrée.

  Mécanismes de synchronisation matérielle

  La synchronisation est une forme particulière de communication où, au lieu du contrôle des données, des informations sont échangées entre des processus de communication résidant dans le même processeur ou dans des processeurs différents.

  Les systèmes multiprocesseurs utilisent des mécanismes matériels pour mettre en œuvre des opérations de synchronisation de bas niveau. La plupart des multiprocesseurs ont des mécanismes matériels pour imposer des opérations atomiques telles que des opérations de lecture de mémoire, d'écriture ou de lecture-modification-écriture pour implémenter certaines primitives de synchronisation. Outre les opérations de mémoire atomique, certaines interruptions interprocesseurs sont également utilisées à des fins de synchronisation.

  Cohérence du cache dans les machines à mémoire partagée

  Le maintien de la cohérence du cache est un problème dans un système multiprocesseur lorsque les processeurs contiennent de la mémoire cache locale. L'incohérence des données entre les différents caches se produit facilement dans ce système.

  Les principaux domaines de préoccupation sont:

  • Partage de données inscriptibles
  • Migration de processus
  • Activité d'E / S

  Partage de données inscriptibles

  Lorsque deux processeurs (P1 et P2) ont le même élément de données (X) dans leurs caches locaux et qu'un processus (P1) écrit dans l'élément de données (X), comme les caches sont le cache local en écriture de P1, la mémoire principale est également mis à jour. Maintenant, lorsque P2 essaie de lire l'élément de données (X), il ne trouve pas X car l'élément de données dans le cache de P2 est devenu obsolète.

  

  Migration de processus

  Dans la première étape, le cache de P1 a l'élément de données X, tandis que P2 n'a rien. Un processus sur P2 écrit d'abord sur X puis migre vers P1. Maintenant, le processus commence à lire l'élément de données X, mais comme le processeur P1 a des données obsolètes, le processus ne peut pas les lire. Ainsi, un processus sur P1 écrit dans l'élément de données X puis migre vers P2. Après la migration, un processus sur P2 commence à lire l'élément de données X mais il trouve une version obsolète de X dans la mémoire principale.

  

  Activité d'E / S

  Comme illustré sur la figure, un périphérique d'E / S est ajouté au bus dans une architecture multiprocesseur à deux processeurs. Au début, les deux caches contiennent l'élément de données X. Lorsque le périphérique d'E / S reçoit un nouvel élément X, il stocke le nouvel élément directement dans la mémoire principale. Maintenant, lorsque P1 ou P2 (supposons que P1) essaie de lire l'élément X, il obtient une copie obsolète. Ainsi, P1 écrit dans l'élément X. Maintenant, si le périphérique d'E / S tente de transmettre X, il obtient une copie obsolète.

  

  Accès mémoire uniforme (UMA)

  L'architecture UMA (Uniform Memory Access) signifie que la mémoire partagée est la même pour tous les processeurs du système. Les classes populaires de machines UMA, couramment utilisées pour les serveurs (de fichiers), sont les multiprocesseurs symétriques (SMP). Dans un SMP, toutes les ressources système telles que la mémoire, les disques, les autres périphériques d'E / S, etc. sont accessibles par les processeurs de manière uniforme.

  Accès mémoire non uniforme (NUMA)

  Dans l'architecture NUMA, il existe plusieurs clusters SMP ayant un réseau interne indirect / partagé, qui sont connectés dans un réseau de transmission de messages évolutif. Ainsi, l'architecture NUMA est une architecture de mémoire distribuée physiquement partagée de manière logique.

  Dans une machine NUMA, le contrôleur de cache d'un processeur détermine si une référence mémoire est locale à la mémoire du SMP ou si elle est distante. Pour réduire le nombre d'accès à la mémoire distante, les architectures NUMA appliquent généralement des processeurs de mise en cache qui peuvent mettre en cache les données distantes. Mais lorsque les caches sont impliqués, la cohérence du cache doit être maintenue. Donc, ces systèmes sont également connus sous le nom de CC-NUMA (Cache Coherent NUMA).

  Architecture de mémoire cache uniquement (COMA)

  Les machines COMA sont similaires aux machines NUMA, à la seule différence que les mémoires principales des machines COMA agissent comme des caches à mappage direct ou à association d'ensemble. Les blocs de données sont hachés vers un emplacement dans le cache DRAM en fonction de leurs adresses. Les données récupérées à distance sont en fait stockées dans la mémoire principale locale. De plus, les blocs de données n'ont pas de domicile fixe, ils peuvent se déplacer librement dans tout le système.

  Les architectures COMA ont pour la plupart un réseau de transmission de messages hiérarchique. Un commutateur dans un tel arbre contient un répertoire avec des éléments de données comme sous-arborescence. Étant donné que les données n'ont pas d'emplacement d'origine, elles doivent être explicitement recherchées. Cela signifie qu'un accès distant nécessite une traversée le long des commutateurs dans l'arborescence pour rechercher dans leurs répertoires les données requises. Ainsi, si un commutateur du réseau reçoit plusieurs demandes de son sous-arbre pour les mêmes données, il les combine en une seule demande qui est envoyée au parent du commutateur. Lorsque les données demandées sont renvoyées, le commutateur en envoie plusieurs copies dans son sous-arbre.

COMA contre CC-NUMA

Voici les différences entre COMA et CC-NUMA.

• COMA a tendance à être plus flexible que CC-NUMA car COMA prend en charge de manière transparente la migration et la réplication des données sans avoir besoin du système d'exploitation.

• Les machines COMA sont coûteuses et complexes à construire car elles nécessitent un matériel de gestion de mémoire non standard et le protocole de cohérence est plus difficile à mettre en œuvre.

• Les accès à distance dans COMA sont souvent plus lents que ceux dans CC-NUMA car le réseau arborescent doit être traversé pour trouver les données.

Il existe de nombreuses méthodes pour réduire le coût du matériel. Une méthode consiste à intégrer l'aide à la communication et le réseau moins étroitement dans le nœud de traitement et à augmenter la latence et l'occupation des communications.

Une autre méthode consiste à fournir une réplication et une cohérence automatiques dans le logiciel plutôt que dans le matériel. Cette dernière méthode assure la réplication et la cohérence dans la mémoire principale et peut s'exécuter à une variété de granularités. Il permet l'utilisation de pièces de base disponibles dans le commerce pour les nœuds et l'interconnexion, ce qui minimise le coût du matériel. Cela met la pression sur le programmeur pour obtenir de bonnes performances.

Modèles de cohérence de la mémoire détendue

Le modèle de cohérence de la mémoire pour un espace d'adressage partagé définit les contraintes dans l'ordre dans lequel les opérations de mémoire aux mêmes emplacements ou à des emplacements différents semblent s'exécuter les unes par rapport aux autres. En fait, toute couche système qui prend en charge un modèle de dénomination d'espace d'adressage partagé doit avoir un modèle de cohérence de la mémoire qui comprend l'interface du programmeur, l'interface utilisateur-système et l'interface matériel-logiciel. Le logiciel qui interagit avec cette couche doit connaître son propre modèle de cohérence de la mémoire.

Spécifications du système

La spécification système d'une architecture spécifie l'ordre et la réorganisation des opérations de mémoire et les performances qui peuvent en être réellement obtenues.

Voici les quelques modèles de spécification utilisant les assouplissements dans l'ordre du programme -

• Relaxing the Write-to-Read Program Order- Cette classe de modèles permet au matériel de supprimer la latence des opérations d'écriture qui a été manquée dans la mémoire cache de premier niveau. Lorsque l'échec d'écriture se trouve dans le tampon d'écriture et n'est pas visible pour les autres processeurs, le processeur peut effectuer des lectures qui frappent dans sa mémoire cache ou même une seule lecture qui manque dans sa mémoire cache.

• Relaxing the Write-to-Read and Write-to-Write Program Orders- Permettre aux écritures de contourner les écritures précédentes en attente à divers emplacements permet de fusionner plusieurs écritures dans le tampon d'écriture avant de mettre à jour la mémoire principale. Ainsi, plusieurs écritures ne se chevauchent pas et deviennent visibles dans le désordre. La motivation est de minimiser davantage l'impact de la latence d'écriture sur le temps de pause du processeur et d'augmenter l'efficacité de la communication entre les processeurs en rendant les nouvelles valeurs de données visibles pour les autres processeurs.

• Relaxing All Program Orders- Aucune commande de programme n'est assurée par défaut à l'exception des dépendances de données et de contrôle au sein d'un processus. Ainsi, l'avantage est que les multiples requêtes de lecture peuvent être en attente en même temps, et dans l'ordre du programme peuvent être contournées par des écritures ultérieures, et peuvent elles-mêmes se terminer dans le désordre, ce qui nous permet de masquer la latence de lecture. Ce type de modèle est particulièrement utile pour les processeurs planifiés dynamiquement, qui peuvent continuer après les échecs de lecture vers d'autres références mémoire. Ils permettent de nombreux réorganisations, voire l'élimination des accès qui sont effectués par les optimisations du compilateur.

L'interface de programmation

Les interfaces de programmation supposent que les ordres de programme ne doivent pas du tout être maintenus entre les opérations de synchronisation. Il est garanti que toutes les opérations de synchronisation sont explicitement étiquetées ou identifiées comme telles. La bibliothèque d'exécution ou le compilateur traduit ces opérations de synchronisation en opérations appropriées de préservation de l'ordre requises par la spécification du système.

Le système assure alors des exécutions séquentiellement cohérentes même s'il peut réorganiser les opérations parmi les opérations de synchronisation de la manière qu'il souhaite sans interrompre les dépendances à un emplacement dans un processus. Cela permet au compilateur une flexibilité suffisante parmi les points de synchronisation pour les réorganisations qu'il souhaite, et autorise également le processeur à effectuer autant de réorganisations que le permet son modèle de mémoire. Au niveau de l'interface du programmeur, le modèle de cohérence doit être au moins aussi faible que celui de l'interface matérielle, mais ne doit pas nécessairement être le même.

Mécanismes de traduction

Dans la plupart des microprocesseurs, traduire des étiquettes en mécanismes de maintien d'ordre revient à insérer une instruction de barrière de mémoire appropriée avant et / ou après chaque opération étiquetée comme une synchronisation. Cela enregistrerait des instructions avec des chargements / magasins individuels indiquant les commandes à appliquer et en évitant des instructions supplémentaires. Cependant, étant donné que les opérations sont généralement peu fréquentes, ce n'est pas la voie que la plupart des microprocesseurs ont suivie jusqu'à présent.

Surmonter les limitations de capacité

Nous avons discuté des systèmes qui assurent la réplication automatique et la cohérence matérielle uniquement dans la mémoire cache du processeur. Un cache de processeur, sans qu'il soit d'abord répliqué dans la mémoire principale locale, réplique les données allouées à distance directement sur référence.

Un problème avec ces systèmes est que la portée de la réplication locale est limitée au cache matériel. Si un bloc est remplacé de la mémoire cache, il doit être extrait de la mémoire distante lorsqu'il est à nouveau nécessaire. Le but principal des systèmes discutés dans cette section est de résoudre le problème de capacité de réplication, tout en offrant une cohérence matérielle et une granularité fine des blocs de cache pour plus d'efficacité.

Caches tertiaires

Pour résoudre le problème de capacité de réplication, une méthode consiste à utiliser un cache d'accès distant volumineux mais plus lent. Cela est nécessaire pour la fonctionnalité, lorsque les nœuds de la machine sont eux-mêmes des multiprocesseurs à petite échelle et peuvent simplement être agrandis pour les performances. Il contiendra également les blocs distants répliqués qui ont été remplacés depuis la mémoire cache du processeur local.

Architectures de mémoire cache uniquement (COMA)

Dans les machines COMA, chaque bloc de mémoire de toute la mémoire principale est associé à une balise matérielle. Il n'y a pas de nœud fixe où il y a toujours l'assurance d'être alloué à un bloc de mémoire. Les données migrent dynamiquement ou sont répliquées dans les mémoires principales des nœuds qui y accèdent / les attirent. Lorsqu'un bloc distant est accédé, il est répliqué dans la mémoire d'attraction et introduit dans le cache, et est maintenu cohérent dans les deux endroits par le matériel. Un bloc de données peut résider dans n'importe quelle mémoire d'attraction et peut se déplacer facilement de l'une à l'autre.

Réduction des coûts matériels

Réduire les coûts signifie déplacer certaines fonctionnalités du matériel spécialisé vers des logiciels exécutés sur le matériel existant. Il est beaucoup plus facile pour un logiciel de gérer la réplication et la cohérence dans la mémoire principale que dans le cache matériel. Les méthodes peu coûteuses ont tendance à assurer la réplication et la cohérence dans la mémoire principale. Pour contrôler efficacement la cohérence, chacun des autres composants fonctionnels de l'assistance peut bénéficier d'une spécialisation et d'une intégration matérielles.

Les efforts de recherche visent à réduire le coût avec différentes approches, par exemple en effectuant un contrôle d'accès dans du matériel spécialisé, mais en attribuant d'autres activités aux logiciels et au matériel de base. Une autre approche consiste à effectuer un contrôle d'accès dans le logiciel et est conçue pour attribuer une abstraction d'espace d'adressage partagé cohérente sur les nœuds et les réseaux de base sans support matériel spécialisé.

Implications pour les logiciels parallèles

Le modèle de cohérence de la mémoire détendue nécessite que les programmes parallèles étiquettent les accès conflictuels souhaités en tant que points de synchronisation. Un langage de programmation fournit un support pour étiqueter certaines variables en tant que synchronisation, qui sera ensuite traduite par le compilateur en instruction de préservation d'ordre appropriée. Pour restreindre la réorganisation des accès à la mémoire partagée par les compilateurs, le compilateur peut utiliser des étiquettes par lui-même.

Un interconnection networkdans une machine parallèle transfère les informations de n'importe quel nœud source vers n'importe quel nœud de destination souhaité. Cette tâche doit être effectuée avec une latence aussi faible que possible. Il devrait permettre à un grand nombre de ces transferts d'avoir lieu simultanément. De plus, il devrait être peu coûteux par rapport au coût du reste de la machine.

Le réseau est composé de liens et de commutateurs, ce qui permet d'envoyer les informations du nœud source au nœud de destination. Un réseau est spécifié par sa topologie, son algorithme de routage, sa stratégie de commutation et son mécanisme de contrôle de flux.

Structure organisationnelle

Les réseaux d'interconnexion sont composés des trois éléments de base suivants:

• Links- Un lien est un câble d'une ou plusieurs fibres optiques ou fils électriques avec un connecteur à chaque extrémité attaché à un commutateur ou un port d'interface réseau. Grâce à cela, un signal analogique est transmis d'une extrémité, reçu à l'autre pour obtenir le flux d'informations numériques d'origine.

• Switches- Un commutateur est composé d'un ensemble de ports d'entrée et de sortie, d'une «barre transversale» interne connectant toutes les entrées à toutes les sorties, d'une mémoire tampon interne et d'une logique de contrôle pour effectuer la connexion d'entrée-sortie à chaque instant. Généralement, le nombre de ports d'entrée est égal au nombre de ports de sortie.

• Network Interfaces- L'interface réseau se comporte très différemment des nœuds de commutation et peut être connectée via des liaisons spéciales. L'interface réseau formate les paquets et construit les informations de routage et de contrôle. Il peut avoir des tampons d'entrée et de sortie, par rapport à un commutateur. Il peut effectuer une vérification des erreurs de bout en bout et un contrôle de flux. Par conséquent, son coût est influencé par sa complexité de traitement, sa capacité de stockage et le nombre de ports.

Réseau d'interconnexion

Les réseaux d'interconnexion sont composés d'éléments de commutation. La topologie est le modèle permettant de connecter les commutateurs individuels à d'autres éléments, tels que les processeurs, les mémoires et autres commutateurs. Un réseau permet l'échange de données entre les processeurs dans le système parallèle.

• Direct connection networks- Les réseaux directs ont des connexions point à point entre les nœuds voisins. Ces réseaux sont statiques, ce qui signifie que les connexions point à point sont fixes. Quelques exemples de réseaux directs sont les anneaux, les maillages et les cubes.

• Indirect connection networks- Les réseaux indirects n'ont pas de voisins fixes. La topologie de communication peut être modifiée dynamiquement en fonction des demandes de l'application. Les réseaux indirects peuvent être subdivisés en trois parties: les réseaux de bus, les réseaux à plusieurs étages et les commutateurs crossbar.

  • Bus networks- Un réseau de bus est composé d'un certain nombre de lignes de bit sur lesquelles un certain nombre de ressources sont attachées. Lorsque les bus utilisent les mêmes lignes physiques pour les données et les adresses, les données et les lignes d'adresse sont multiplexées dans le temps. Lorsqu'il y a plusieurs maîtres de bus connectés au bus, un arbitre est nécessaire.

  • Multistage networks- Un réseau à plusieurs étages se compose de plusieurs étages de commutateurs. Il est composé de commutateurs «axb» qui sont connectés en utilisant un modèle de connexion interétage (ISC) particulier. Les petits éléments de commutation 2x2 sont un choix courant pour de nombreux réseaux à plusieurs étages. Le nombre d'étages détermine le retard du réseau. En choisissant différents modèles de connexion inter-étages, divers types de réseau à plusieurs étages peuvent être créés.

  • Crossbar switches- Un commutateur crossbar contient une matrice d'éléments de commutation simples qui peuvent s'allumer et s'éteindre pour créer ou interrompre une connexion. En activant un élément de commutation dans la matrice, une connexion entre un processeur et une mémoire peut être établie. Les commutateurs crossbar ne sont pas bloquants, c'est-à-dire que toutes les permutations de communication peuvent être effectuées sans blocage.

Évaluation des compromis de conception dans la topologie de réseau

Si la principale préoccupation est la distance de routage, alors la dimension doit être maximisée et un hypercube créé. Dans le routage store-and-forward, en supposant que le degré de commutation et le nombre de liens ne constituent pas un facteur de coût significatif, et que le nombre de liens ou le degré de commutation sont les principaux coûts, la dimension doit être minimisée et un maillage construit.

Dans le pire des cas, le modèle de trafic pour chaque réseau, il est préférable d'avoir des réseaux de grande dimension où tous les chemins sont courts. Dans les modèles où chaque nœud communique avec seulement un ou deux voisins proches, il est préférable d'avoir des réseaux de faible dimension, car seules quelques-unes des dimensions sont réellement utilisées.

Routage

L'algorithme de routage d'un réseau détermine lequel des chemins possibles de la source à la destination est utilisé comme routes et comment la route suivie par chaque paquet particulier est déterminée. Le routage par ordre de dimension limite l'ensemble des chemins légaux de sorte qu'il y ait exactement un itinéraire de chaque source à chaque destination. Celle obtenue en parcourant d'abord la bonne distance dans la dimension d'ordre supérieur, puis la dimension suivante et ainsi de suite.

Mécanismes de routage

L'arithmétique, la sélection de port basée sur la source et la recherche de table sont trois mécanismes que les commutateurs à grande vitesse utilisent pour déterminer le canal de sortie à partir des informations contenues dans l'en-tête de paquet. Tous ces mécanismes sont plus simples que le type de calcul de routage général implémenté dans les routeurs LAN et WAN traditionnels. Dans les réseaux informatiques parallèles, le commutateur doit prendre la décision de routage pour toutes ses entrées à chaque cycle, le mécanisme doit donc être simple et rapide.

Routage déterministe

Un algorithme de routage est déterministe si la route empruntée par un message est déterminée exclusivement par sa source et sa destination, et non par un autre trafic sur le réseau. Si un algorithme de routage ne sélectionne que les chemins les plus courts vers la destination, il est minimal, sinon il est non minimal.

Liberté de blocage

Un blocage peut se produire dans diverses situations. Lorsque deux nœuds tentent de s'envoyer des données et que chacun commence à envoyer avant que l'un ou l'autre ne les reçoive, un blocage «frontal» peut se produire. Un autre cas de blocage se produit, lorsqu'il y a plusieurs messages en concurrence pour les ressources au sein du réseau.

La technique de base pour prouver qu'un réseau est sans blocage, consiste à effacer les dépendances qui peuvent survenir entre les canaux à la suite de messages circulant à travers les réseaux et à montrer qu'il n'y a pas de cycles dans le graphe de dépendance de canal global; il n'y a donc pas de modèle de trafic pouvant conduire à une impasse. La manière courante de procéder consiste à numéroter les ressources de canal de telle sorte que tous les itinéraires suivent une séquence particulière croissante ou décroissante, de sorte qu'aucun cycle de dépendance ne se produise.

Conception de commutateur

La conception d'un réseau dépend de la conception du commutateur et de la manière dont les commutateurs sont câblés ensemble. Le degré du commutateur, ses mécanismes de routage internes et sa mise en mémoire tampon interne déterminent quelles topologies peuvent être prises en charge et quels algorithmes de routage peuvent être implémentés. Comme tout autre composant matériel d'un système informatique, un commutateur réseau contient le chemin des données, le contrôle et le stockage.

Les ports

Le nombre total de broches est en fait le nombre total de ports d'entrée et de sortie multiplié par la largeur du canal. Comme le périmètre de la puce croît lentement par rapport à la zone, les commutateurs ont tendance à être limités par les broches.

Chemin de données interne

Le chemin de données est la connectivité entre chacun de l'ensemble de ports d'entrée et chaque port de sortie. Elle est généralement appelée barre transversale interne. Une barre transversale non bloquante est celle où chaque port d'entrée peut être connecté à une sortie distincte dans n'importe quelle permutation simultanément.

Tampons de canal

L'organisation du stockage tampon au sein du commutateur a un impact important sur les performances du commutateur. Les routeurs et commutateurs traditionnels ont tendance à avoir de grands tampons SRAM ou DRAM externes à la structure du commutateur, tandis que dans les commutateurs VLSI, le tampon est interne au commutateur et sort du même budget de silicium que le chemin de données et la section de contrôle. Au fur et à mesure que la taille et la densité de la puce augmentent, plus de mémoire tampon est disponible et le concepteur de réseau a plus d'options, mais l'immobilier tampon reste un choix de premier ordre et son organisation est importante.

Contrôle de flux

Lorsque plusieurs flux de données dans le réseau tentent d'utiliser les mêmes ressources réseau partagées en même temps, certaines mesures doivent être prises pour contrôler ces flux. Si nous ne voulons perdre aucune donnée, certains des flux doivent être bloqués tandis que d'autres continuent.

Le problème du contrôle de flux se pose dans tous les réseaux et à plusieurs niveaux. Mais il est qualitativement différent dans les réseaux informatiques parallèles que dans les réseaux locaux et étendus. Dans les ordinateurs parallèles, le trafic réseau doit être fourni à peu près aussi précisément que le trafic sur un bus et il existe un très grand nombre de flux parallèles sur une très petite échelle de temps.

La vitesse des microprocesseurs a augmenté de plus d'un facteur dix par décennie, mais la vitesse des mémoires de base (DRAM) n'a fait que doubler, c'est-à-dire que le temps d'accès est divisé par deux. Par conséquent, la latence d'accès à la mémoire en termes de cycles d'horloge du processeur augmente d'un facteur six en 10 ans. Les multiprocesseurs ont intensifié le problème.

Dans les systèmes à base de bus, l'établissement d'un bus à bande passante élevée entre le processeur et la mémoire tend à augmenter la latence d'obtention des données à partir de la mémoire. Lorsque la mémoire est physiquement distribuée, la latence du réseau et de l'interface réseau s'ajoute à celle de l'accès à la mémoire locale sur le nœud.

La latence augmente généralement avec la taille de la machine, car plus de nœuds impliquent plus de communication par rapport au calcul, plus de sauts dans le réseau pour la communication générale et probablement plus de conflits. L'objectif principal de la conception matérielle est de réduire la latence de l'accès aux données tout en maintenant une bande passante élevée et évolutive.

Présentation de la tolérance de latence

La manière dont la tolérance de latence est gérée est mieux comprise en examinant les ressources de la machine et la manière dont elles sont utilisées. Du point de vue du processeur, l'architecture de communication d'un nœud à un autre peut être considérée comme un pipeline. Les étapes du pipeline incluent les interfaces réseau à la source et à la destination, ainsi que dans les liaisons réseau et les commutateurs en cours de route. Il existe également des étapes dans l'assistance à la communication, le système de mémoire / cache locale et le processeur principal, en fonction de la façon dont l'architecture gère la communication.

Le problème d'utilisation dans la structure de communication de base est que le processeur ou l'architecture de communication est occupé à un moment donné, et dans le pipeline de communication, une seule étape est occupée à la fois alors que le mot unique transmis fait son chemin de la source à la destination. L'objectif de la tolérance de latence est de chevaucher autant que possible l'utilisation de ces ressources.

Tolérance de latence dans la transmission de messages explicites

Le transfert réel de données lors de la transmission de messages est généralement lancé par l'expéditeur, à l'aide d'une opération d'envoi. Une opération de réception ne motive pas en elle-même la communication de données, mais copie plutôt des données d'un tampon entrant dans l'espace d'adressage d'application. La communication initiée par le récepteur est effectuée en émettant un message de demande au processus qui est la source des données. Le processus renvoie ensuite les données via un autre envoi.

Une opération d'envoi synchrone a une latence de communication égale au temps nécessaire pour communiquer toutes les données du message à la destination, et au temps de traitement de réception et au temps pour un accusé de réception à renvoyer. La latence d'une opération de réception synchrone est sa surcharge de traitement; qui comprend la copie des données dans l'application, et la latence supplémentaire si les données ne sont pas encore arrivées. Nous aimerions masquer ces latences, y compris les frais généraux si possible, aux deux extrémités.

Tolérance de latence dans un espace d'adressage partagé

La communication de base s'effectue via des lectures et des écritures dans un espace d'adressage partagé. Pour plus de commodité, on parle de communication en lecture-écriture. La communication initiée par le récepteur est effectuée avec des opérations de lecture qui entraînent l'accès aux données de la mémoire ou du cache d'un autre processeur. S'il n'y a pas de mise en cache des données partagées, la communication initiée par l'expéditeur peut être effectuée par écrit sur des données qui sont allouées dans des mémoires distantes.

Avec la cohérence du cache, l'effet des écritures est plus complexe: soit les écritures conduisent à l'expéditeur, soit la communication initiée par le récepteur dépend du protocole de cohérence du cache. Soit initiée par le récepteur, soit par l'émetteur, la communication dans un espace d'adressage partagé lecture-écriture supporté par le matériel est naturellement fine, ce qui rend la latence de tolérance très importante.

Bloquer le transfert de données dans un espace d'adressage partagé

Dans un espace d'adressage partagé, soit par matériel soit par logiciel, la fusion des données et l'initiation de blocs-transferts peuvent être effectués explicitement dans le programme utilisateur ou de manière transparente par le système. Les transferts de blocs explicites sont lancés en exécutant une commande similaire à un envoi dans le programme utilisateur. La commande d'envoi est expliquée par l'assistance à la communication, qui transfère les données en pipeline du nœud source à la destination. À la destination, l'assistance à la communication extrait les mots de données de l'interface réseau et les stocke aux emplacements spécifiés.

Il existe deux principales différences entre l'envoi et la réception de messages, qui découlent tous deux du fait que le processus d'envoi peut spécifier directement les structures de données du programme où les données doivent être placées à la destination, puisque ces emplacements sont dans l'espace d'adressage partagé. .

Poursuite des événements passés à longue latence dans un espace d'adressage partagé

Si l'opération de mémoire est rendue non bloquante, un processeur peut passer une opération de mémoire à d'autres instructions. Pour les écritures, cela est généralement assez simple à implémenter si l'écriture est placée dans un tampon d'écriture, et le processeur continue pendant que le tampon se charge d'émettre l'écriture dans le système de mémoire et de suivre son achèvement si nécessaire. La différence est que contrairement à une écriture, une lecture est généralement suivie très rapidement d'une instruction qui a besoin de la valeur renvoyée par la lecture.

Pré-communication dans un espace d'adressage partagé

La pré-communication est une technique qui a déjà été largement adoptée dans les microprocesseurs commerciaux, et son importance est susceptible d'augmenter à l'avenir. Une instruction de prélecture ne remplace pas la lecture réelle de l'élément de données, et l'instruction de prélecture elle-même doit être non bloquante, si elle doit atteindre son objectif de masquer la latence par chevauchement.

Dans ce cas, comme les données partagées ne sont pas mises en cache, les données pré-extraites sont introduites dans une structure matérielle spéciale appelée tampon de prélecture. Lorsque le mot est effectivement lu dans un registre lors de l'itération suivante, il est lu à partir de la tête du tampon de prélecture plutôt qu'à partir de la mémoire. Si la latence pour masquer était beaucoup plus grande que le temps de calcul d'une itération de boucle unique, nous prélèverions plusieurs itérations à l'avance et il y aurait potentiellement plusieurs mots dans le tampon de prélecture à la fois.

Multithreading dans un espace d'adressage partagé

En termes de masquage de différents types de latence, le multithreading supporté par le matériel est peut-être la technique polyvalente. Elle présente les avantages conceptuels suivants par rapport aux autres approches -

• Il ne nécessite aucune analyse ou assistance logicielle particulière.

• Comme il est invoqué dynamiquement, il peut gérer des situations imprévisibles, comme les conflits de cache, etc., ainsi que des situations prévisibles.

• Tout comme la prélecture, il ne modifie pas le modèle de cohérence de la mémoire car il ne réorganise pas les accès dans un thread.

• Alors que les techniques précédentes visent à masquer la latence d'accès à la mémoire, le multithreading peut potentiellement masquer la latence de tout événement à longue latence tout aussi facilement, tant que l'événement peut être détecté au moment de l'exécution. Cela inclut également la synchronisation et la latence des instructions.

Cette tendance pourrait changer à l'avenir, car les latences sont de plus en plus longues par rapport aux vitesses du processeur. Également avec des microprocesseurs plus sophistiqués qui fournissent déjà des méthodes qui peuvent être étendues pour le multithreading, et avec de nouvelles techniques de multithreading en cours de développement pour combiner le multithreading avec le parallélisme au niveau des instructions, cette tendance semble certainement subir un certain changement à l'avenir.