Fonctionnement d'un ordinateur/Les architectures parallèles exotiques

Un livre de Wikilivres.
Aller à la navigation Aller à la recherche

Les chapitres précédents ont abordé des architectures parallèles relativement courantes et assez bien connues par les programmeurs et électroniciens. Qu'il s'agisse des architectures multi-threadées, des processeurs SMID, des architectures vectorielles ou autres, tout cela n'était pas spécialement exotique. Beaucoup des techniques abordées jusque-là sont utilisées dans les ordinateurs personnels modernes. Mais de nombreuses autres architectures ont été envisagées par les chercheurs en architecture des ordinateurs. Beaucoup n'ont pas eu de succès et sont tombées dans l'oubli, pour des raisons très diverses : elles étaient trop spécialisées dans des tâches restreintes, elles étaient peu pratiques pour programmer dessus, elles étaient compliquées à concevoir, peu importe. Les architectures tombées dans l'oubli ou peu utilisées actuellement sont légion. Dans ce chapitre, nous allons voir ces architectures parallèles exotiques. Nous allons voir les architectures associatives, les architectures systoliques, les architectures en tiles et quelques autres.

Beaucoup des architectures exotiques sont composées d'éléments de calcul reliées entre elles par un réseau d'interconnexion plus ou moins complexe. Les architectures en question sont classées en fonction de la nature de l’élément de calcul et de la forme du réseau d'interconnexion.

Les éléments de calcul en question peuvent être très variés et dépendent beaucoup de l'architecture en question. Les éléments de calcul peuvent être programmables ou non, peuvent faire un nombre important de calcul ou au contraire une seule opération, avoir une capacité de mémorisation limitée à un registre ou avoir un cache/un local store, etc. Sur les processeurs en tile, ce sont des processeurs assez simples qui sont interconnectés par un réseau d'interconnexion complexe. Les éléments de calcul sont alors composés des processeurs en question, d'un cache (pour le processeur) et d'un commutateur (pour la communication avec le réseau). Pour les architectures systoliques, les éléments de calculs sont plus simples et ne sont pas programmables. Ce sont juste des unités de calcul couplées à quelques registres. Enfin, pour les architectures associatives, les éléments de calcul ressemblent beaucoup aux cases mémoires des mémoires associatives, avec quelques améliorations, comme nous le verrons en temps voulu.

Il en est de même pour le réseau d'interconnexions, qui peut être fixé une fois pour toutes, ou être reconfigurable. Dans les cas les plus simples, le réseau d'interconnexion est juste un ensemble de fils fixé une bonne fois pour toutes et n'est donc pas configurable. Le trajet des données entre éléments de calcul est donc toujours le même et est fixé une fois pour toutes. Dans d'autres cas, le réseau d'interconnexion est similaire à un commutateur, ou un réseau crossbar (vu dans le chapitre sur le matériel réseau). Certains processeurs ont même un véritable réseau de communication, au sens où tout élément de calcul peut être propagé de proche en proche jusqu’à arriver à destination. Pour résumer : les possibilités sont nombreuses et la classification compliquée.

Les architectures many core[modifier | modifier le wikicode]

La plupart des architectures exotiques sont des architectures dites many core, des processeurs avec un très grand nombre de cœurs, plus d'une cinquantaine, voire plusieurs centaines ou milliers. Les architectures many core sont une forme extrême d'architecture multicœurs. La différence est surtout une question de degré, mais aussi de but recherché. Les architectures multicœurs sont surtout conçues pour les ordinateurs personnels, éventuellement les serveurs. Elles recherchent un bon compromis entre un grand nombre de cœurs, et une bonne performance pour les programmes non-parallèles. En clair, elles évitent de sacrifier les performances pour les applications non-parallèles, ce qui fait que leurs cœurs sont généralement très puissants, avec beaucoup d'optimisations micro-architecturales. Les architectures many core font le compromis inverse : elles ont beaucoup de cœurs, mais ceux-ci ne sont pas très puissants, surtout pour les applications non-parallèles. Les cœurs des architectures many core sont généralement des cœurs sans exécution dans le désordre, sans prédiction de branchements, sans renommage de registres, voire sans pipeline ni parallélisme d'instruction.

Les réseaux sur puce (network on chip)[modifier | modifier le wikicode]

Les architectures many core sont des architectures à mémoire partagée, ce qui fait que les problématiques de cohérence des caches sont toujours là. Pour simplifier la gestion de la cohérence des caches, ces architectures n'utilisent pas de bus pour relier les cœurs et les caches, mais un réseau d'interconnexion. Le réseau d'interconnexion peut être très complexe, avec des connexions réseau, des commutateurs, et des protocoles d'échanges entre processeurs assez complexes basés sur du passage de messages. De telles puces utilisent un réseau sur puce (network on chip). Mais d'autres simplifient le réseau d'interconnexion, qui se résume à un réseau crossbar, voire à des mémoires FIFO pour faire l'interface entre les cœurs.

Les architectures en tile[modifier | modifier le wikicode]

Les architectures en tile sont des architectures many core composées d'un grand nombre de tiles connectées les unes aux autres par un réseau d'interconnexion. Chaque tile contient un cœur de processeur et un commutateur (switch). Le cœur est un cœur de processeur complet, avec une unité de calcul, des registres, un séquenceur, et tout ce qui va avec. Un cache est parfois présent, et il est plus ou moins compliqué suivant l'architecture. Enfin, le commutateur connecte chaque tile au réseau d'interconnexion.

Tile de base du Tile64.

Le réseau est souvent organisé en tableau, chaque tile étant connectée à plusieurs voisines. Dans le cas le plus fréquent, chaque tile est connectée à quatre voisines : celle du dessus, celle du dessous, celle de gauche et celle de droite. Précisons que cette architecture n'est pas une architecture distribuée dont tous les processeurs seraient placés sur la même puce de silicium. En effet, la comparaison ne marche pas pour ce qui est de la mémoire : tous les cœurs accèdent à une mémoire partagée située en dehors de la puce de silicium. Le réseau ne connecte pas plusieurs ordinateurs séparés avec chacun leur propre mémoire, mais plusieurs cœurs qui accèdent à une mémoire partagée.

Un bon exemple d'architecture en tile serait les déclinaisons de l'architecture Tilera. Les schémas du-dessous montrent l'architecture du processeur Tile 64. Outre les tiles, qui sont les éléments de calcul de l'architecture, on trouve plusieurs contrôleurs mémoire DDR, divers interfaces réseau, des interfaces série et parallèles, et d'autres entrées-sorties.

Architecture Tile64 du Tilera.

Les architectures systoliques[modifier | modifier le wikicode]

Les achitectures systoliques sont composées d'un grand nombre d’éléments de calcul identiques, très simples, non-programmables, connectés entre eux. Contrairement aux architectures many core, les éléments de calcul sont ici très simples et ne sont souvent pas programmables. Dans le cas le plus fréquent, ils se limitent à des circuits de calcul couplés à quelques registres. Le réseau d'interconnexion est très rarement reconfigurable, et s'il l'est, il se limite alors à un simple commutateur de type crossbar, guère plus. Dans la majorité des cas, cependant, c'est juste un ensemble de fils qui relie les éléments de calculs entre eux.

Un exemple classique de réseau systolique est illustré ci-dessous, si ce n'est que le signal d'horloge n'est pas indiqué. Dans cet exemple, l'architectures systolique est sont organisée en un tableau d'éléments de calcul. En soi, ce n'est pas obligatoire, d'autres organisations sont possibles, mais c'est l'organisation la plus conventionnelle. Le transfert des données entre les unités de calcul se fait de manière synchrone, c'est à dire cadencé par un signal d'horloge, ce qui fait qu'il y a des registres sur les entrées des éléments de calcul. De nouvelles données sont insérées sur les bords gauche et haut du tableau à chaque cycle d'horloge. Chaque élément de calcul reçoit des données provenant de deux autres éléments, et fournit un résultat à deux autres éléments. Le résultat final du calcul est disponible sur un des bords du tableau systolique, voire sur les deux bords du bas et de droite. Le résultat final n'est connu qu'après quelques cycles d'horloge, une fois que les données ont traversées le tableau de proche en proche, en traversant les éléments de calcul.

Tableau systolique.

Les éléments de calcul reçoivent des données en entrée, effectuent un calcul dessus, et renvoient un résultat qui est propagé aux éléments de calcul suivants. Contrairement à ce que l'on voit sur les autres architectures, le calcul est déclenché par l'arrivée de nouvelles données en entrée. Le calcul effectué est toujours le même, ce qui fait que les éléments de calcul sont encore plus simples que des unités de calcul d'un processeur. On pourrait plus les comparer avec un circuit de calcul, couplé à quelques registres qui mémorisent les données envoyées en entrée et qui servent à synchroniser les échanges entre éléments de calcul.

Une architecture pipelinée : la comparaison avec les autres architectures[modifier | modifier le wikicode]

Le flux des données dans un tableau systolique ressemble un petit peu au pipeline d'un processeur haute performance, mais fortement modifié. Là où un pipeline est une chaîne unidimensionnelle de circuits liés l'un à la suite de l'autre, les architectures systoliques utilisent une connectivité plus complexe, en deux dimensions. Une meilleure comparaison serait avec les unités de calculs d'un processeur vectoriel, qui sont organisées en pipeline. Mais il y a deux différences entre un tableau systolique et une ALU vectorielle. Premièrement, là où le pipeline d'une unité de calcul vectorielle est unidimensionnel, les tableaux systoliques sont un pipeline en deux dimensions. Deuxièmement, les étages d'une unité vectorielle sont différents, là où les étages d'une architecture systoliques sont tous identiques.

Précisons que le tableau d'éléments de calcul est secondé avec des circuits de contrôle qui insèrent les données adéquates dans le tableau et récupèrent les résultats sur la sortie. Sur beaucoup d'architectures systoliques, le tableau est en réalité l'équivalent d'une unité de calcul sur un processeur normale, le reste de l'architecture étant composé d'un séquenceur adapté aux besoins du tableau systolique. La comparaison avec les processeurs vectoriels n'en est que lus pertinente.

Les opérations adaptées aux architectures systoliques : la multiplication de matrices et le calcul du produit de convolution[modifier | modifier le wikicode]

La simplicité des éléments de calcul est autant un défaut qu’une qualité. Qualité car le circuit final est très simple, consomme peu d'énergie, très performant. Mais en contrepartie, les architectures systoliques sont très spécialisées. Elles sont utilisées pour certains calculs bien précis, qui se marient bien avec les architectures systoliques. Beaucoup de calculs ne sont pas implémentables sur les architectures systoliques, en raison de la non-programmabilité des éléments de calcul. Elles sont notamment adaptées pour les applications d'intelligence artificielles basées sur des réseaux de neurones logiciels, le traitement d'images, l'évaluation de polynômes, l'application de filtres audio/vidéo, les calculs de corrélation statistique, etc. Toutes ces applications recourent beaucoup à l'opération qui brille le plus par son adaptation aux architectures systoliques : la multiplication de matrices.

L'usage d'architectures systoliques pour multiplier des matrices est ancien, les premières architectures de ce type datant des années 70. Mais elles sont revenues en force avec les progrès en intelligence artificielle des années 2010-2020. La démocratisation du machine learning a amené sur le marché de nombreux accélérateurs matériels spécialement dédiés à l'accélération des calculs basés sur des réseaux de neurones logiciels. Sans rentrer dans le détail (nous verrons cela en détail dans le chapitre sur les architectures neuromorphiques), nous pouvons cependant dire que les algorithmes de machine learning font énormément de calculs matriciels, dont des multiplications de matrices. Les architectures systoliques sont alors revenues en force dans ce cadre.

Les algorithmes de machine learning sont basés sur un calcul de convolution, qui se base lui-même sur plusieurs multiplications de matrices dont les données sont partagées. Malgré son nom barbare, le produit de convolution est une simple moyenne glissante pondérée. Concrètement, le produit de convolution prend en entrée un ensemble de nombres notés  ; et un ensemble de poids notés . le produit de convolution calcule les moyennes pondérées suivante :

...

Comme on le voit, le calcul du produit de convolution demande de faire beaucoup d'additions et de multiplications en parallèle. Les architectures systoliques optimisées pour le calcul de convolution ont donc des éléments de calculs capables de faire une opération MAD (multiply and accumulate) et rien de plus. Les poids et les entrées sont stockées dans deux registres tampons, situés sur les entrées du tableau systolique. À chaque cycle, un nouveau calcul est effectué et une des moyennes pondérée est disponible sur la sortie, sur le bord bas ou droit du tableau.

Tableau systolique conçu pour les produits de convolution.
Tensor Processing Unit 3.0

Les Tensor Processing Units (TPU) de Google sont des accélérateurs matériels dédiés aux calculs de machine learning, basés sur une architecture systolique. La première version des TPU se basait sur un tableau systolique de 256 lignes et 256 colonnes, dont les éléments de calculs pouvaient multiplier deux entiers de 8 bits. Le tableau systolique est en réalité une unité de calcul, commandées par un séquenceur spécialisé. L'ensemble a une fréquence de 700 MHz et possède 28 mébioctets de mémoire intégré, avec 4 mébioctets de registres accumulateurs utilisés pour stocker les résultats fournis par le tableau systolique (256 × 256 = 4 mégas). Les versions suivantes ont augmenté le débit de la mémoire, ajouté le support des nombres flottants et augmenté les performances de manière générale, en augmentant le nombre de circuits de calcul. Une technologie équivalente existe sur les cartes graphiques NVIDIA suffisamment récentes, sous le nom de Tensor cores, et c'est sans compter sur des technologies équivalentes développées par Qualcomm, Amazon, Apple, Facebook, AMD, Samsung et d'autres entreprises.

Les architectures associatives[modifier | modifier le wikicode]

Il y a quelques chapitres, nous avons vu les mémoires associatives, aussi appelées mémoires CAM. Pour résumer, ces mémoires ont un fonctionnement totalement opposé aux mémoires adressables normales : au lieu d'envoyer l'adresse pour accéder à la donnée, on envoie la donnée pour récupérer son adresse. Nous avions vu que leur plan mémoire ressemblait à ce qui est illustré ci-dessous. Chaque case mémoire intègre un comparateur, lui-même relié au bus de donnée. Le comparateur compare la donnée envoyée en entrée sur le bus de donnée, avec le contenu de la case mémoire. Chaque comparateur fournit en sortie un bit qui indique si les deux sont identiques ou non. La sortie du plan mémoire est donc un ensemble de bits, qui indiquent quelle case mémoire contient la donnée d'entrée. Des mémoires associatives plus complexes ajoutent un circuit à chaque case mémoire, afin d'intégrer des opérations de masquage, mais c'est là un détail. Pour faire une mémoire associative, il faut ajouter un encodeur à ce plan mémoire, mais nous n'en parlerons pas plus que cela, vous comprendrez pourquoi après.

Plan mémoire d'une mémoire associative.

Les processeurs associatifs reprennent ce plan mémoire, mais modifient le comparateur pour en augmenter les capacités. Les mémoires associatives ne font que comparer la donnée d'entrée avec chaque case mémoire, la comparaison utilisée étant une comparaison d'égalité stricte. Mais on pourrait leur permettre de faire d'autres comparaisons, comme des comparaisons du type "supérieur ou égal", "inférieur ou égal", etc. De même, les mémoires associatives élaborées permettent d'appliquer un masque à chaque case mémoire, mais guère plus. Pourtant, il est possible d'ajouter d'autres opérations bit à bit au circuit sans trop de problèmes. On pourrait aussi remplacer le comparateur par une véritable unité de calcul, capable de faire des comparaisons, des opérations bit à bit, du masquage, mais aussi des additions/soustractions, voire d'autres calculs.

Les propositions précédentes permettent chacune d'obtenir un processeur associatif, un processeur qui permet d'appliquer des opérations simples dans toutes les cas mémoire simultanément, en parallèle. En général, les opérations disponibles sont assez simples, pour éviter d'utiliser trop de circuits. Traditionnellement, seules les opérations bit à bit sont possibles, ce qui inclut les opérations logiques (NON, ET, OU, XOR, ...), éventuellement des décalages, mais rarement plus. Les autres opérations sont plus rares, car autant les circuits de masquage sont simples et prennent peu de transistors, autant ce n'est pas le cas des autres opérations, beaucoup plus gourmandes en circuits.

La micro-architecture d'un processeur associatif[modifier | modifier le wikicode]

Les processeurs associatifs ne sont pas vraiment des mémoires associatives améliorées. Les similitudes s'arrêtent au plan mémoire, mais les autres circuits d'une mémoire associative ne sont pas repris. Une mémoire associative combine le plan mémoire décrit plus haut avec un encodeur à priorité et quelques autres circuits. Par contre, les processeurs associatifs n'ont généralement pas besoin de l'encodeur. Ils n'ont pas besoin de fournir l'adresse de la case mémoire qui matche l'entrée. Leur raison d'être est d'appliquer une même opération sur un grand nombre de données en même temps, en parallèle, ce qui ne donne aucun rôle à l'encodeur.

Pour construire un processeur associatif, il faut donc prendre le plan mémoire d'une mémoire associative, remplacer les comparateurs par des unités de calcul plus ou moins puissantes, et ajouter des circuits annexes. Le plan mémoire obtenu en remplaçant les comparateurs par des unités de calcul ne donne pas un processeur associatif complet, mais seulement le chemin de données du processeur. Ce plan associatif est configurable, comme tout chemin de données, les signaux de commande étant assez nombreux. Pour obtenir un processeur associatif complet, il faut rajouter un séquenceur, qui prend en entrée une instruction à appliquer sur toutes les cellules mémoire et configure le plan associatif pour exécuter l'instruction. L'op-code de l'instruction est distribué à toutes les cellules mémoires, à toutes les unités de calcul pour être précis.

Les architectures associatives sérielles et parallèles[modifier | modifier le wikicode]

Il existe plusieurs manières de classer les processeurs associatifs, mais la plus simple distingue les architectures totalement parallèles des architectures sérielles. Dans les deux cas, chaque case mémoire est associée à un circuit dédié aux calculs, appelé l'unité de calcul. Mais ses capacités et sa complexité ne sont pas les mêmes suivant que l’on parle d'une architecture sérielle ou totalement associative.

Sur les processeurs totalement parallèles, chaque case mémoire est associée à une unité de calcul capable de traiter tous les bits du mot d'un seul coup. Elle prend plusieurs nombres en entrée : l'entrée provenant du bus de donnée, la case mémoire, parfois d'autres données annexes.

Case mémoire d'un processeur associatif totalement parallèle.

Sur les architectures dites sérielles, l'ALU est castrée pour économiser des circuits, ce qui fait qu'elle ne peut plus traiter qu'un nombre limité de bits. Typiquement, elle prend trois bits en entrées et fournit un résultat de un bit en sortie. Une bascule est ajoutée au circuit, ce qui est la norme pour toute ALU sérielle (pensez à l'additionneur sériel ou au comparateur sériel). Sur ces architectures, les opérations comme l'addition ou la soustraction sont parfois implémentées. La raison est qu'un additionneur sériel ne demande que quelques portes logiques et une bascule pour gérer la retenue, comme on l'a vu il y a quelques chapitres.

Case mémoire d'un processeur associatif bit serial avec une bascule.

Les différents types d'architectures associatives[modifier | modifier le wikicode]

Une autre classification différencie les architectures associatives en fonction des possibilités de communication entre les unités de calcul. Plus haut, nous avions juste dit que les comparateurs étaient remplacés par des unités de calcul. Sur les architectures associatives proprement dit, c'est tout. Mais d'autres architectures ajoutent un circuit d'interconnexions, qui permettent aux unités de calcul d’échanger des informations. La présence de ce système d'interconnexions permet d'appliquer une instruction différente pour chaque unité de calcul, ce qui en fait des architectures MIMD. En comparaison, les processeurs associatifs normaux appliquent une même instruction sur toutes leurs données, ce qui en fait des processeurs SIMD. La connectivité des unités de calcul varie fortement d'un processeur associatif à l'autre. Il est rare que chaque unité de calcul soit connectée à toutes les autres, le nombre d'interconnexion serait juste trop important pour être réaliste.

Sur les processeurs associatifs de type array, appelés associative array processors en anglais, chaque unité de calcul est connectée à un petit nombre d'unités proches, généralement 4 ou plus. Les cellules sont organisées en tableau organisé en ligne/colonne, avec une unité de calcul et une case mémoire à l'intersection de chaque cellule. Chaque cellule est alors connectée à quatre voisines : celle du dessus, celle du dessous, celle de gauche, et celle de droite. D'autres organisations sont possibles. La classification des associative array processors se fait en fonction de la manière dont les cellules sont interconnectées, en fonction de la topologie du circuit d'interconnexion.

Une autre possibilité est d'organiser les unités de calcul en ligne, chaque unité étant connectée à deux voisines. Typiquement, chaque cellule est connectée à la suivante et à la précédente. Les données peuvent traverser la ligne dans un sens, de gauche à droite, en passant d'une cellule à la suivante. Un circuit d'interconnexion général, qui relie toutes les cellules, est souvent ajouté. Cette organisation peut sembler quelque peu contre-intuitive, mais elle prend tout son sens quand on sait comment s'appellent les processeurs de ce type. On les appelle des associative string array processor : string signifie chaîne de caractère, ce qui trahit leur utilité. De tels processeurs sont conçus pour manipuler des chaînes de caractères, à savoir du texte, des suites de caractères placés les uns à côté des autres. Le fait de relier les cellules ainsi fait que l'on peut faire passer une chaîne de caractère de gauche à droite à travers la chaîne, en effectuant des traitements divers au passage.