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

Les chapitres précédents ont abordé des architectures parallèles les plus courantes, les plus connues par les programmeurs et électroniciens. 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 compliquées à programmer, elles étaient compliquées à concevoir, peu importe. Les architectures tombées dans l'oubli ou peu utilisées actuellement sont légion.

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 é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.

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 systoliques

Les architectures 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 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

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 normal, 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 plus pertinente.

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

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 $x_{0},x_{1},x_{2},...,x_{n}$ ; et un ensemble de poids notés $p_{0},p_{1},p_{2},p_{3},...,p_{n}$. le produit de convolution calcule les moyennes pondérées suivante :

$y_{0}=x_{0}\times p_{0}+x_{1}\times p_{1}+x_{2}\times p_{2}+...+x_{n}\times p_{n}$

$y_{0}=0\times p_{1}+x_{0}\times p_{2}+x_{1}\times p_{2}+...+x_{n-1}\times p_{n}$

$y_{0}=0\times p_{0}+01\times p_{1}+x_{0}\times p_{2}+...+x_{n-2}\times p_{n}$

...

$y_{0}=0\times p_{0}+0\times p_{1}+0\times p_{2}+...+x_{0}\times p_{n}$

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.

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. 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

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. 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

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

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 une ALU sérielle, afin d'économiser des circuits. Pour rappel, une ALU sérielle traite ses opérandes 1 bit à la fois. Typiquement, elle prend trois bits en entrées et fournit un résultat de un bit en sortie, avec éventuellement une retenue mémorisée dans une bascule interne à l'ALU (pensez à l'additionneur sériel ou au comparateur sériel).

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

Les différents types d'architectures associatives

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.