# Fonctionnement d'un ordinateur/Les architectures systoliques

Les architectures systoliques ont un chemin de données très particulier, qui est composé d'un grand nombre d’unité de calcul identiques, interconnectées via un réseau en deux dimensions non-configurable. Un exemple classique de réseau systolique est illustré ci-dessous. Dans cet exemple, l'architecture systolique est organisée en un tableau à deux dimensions d'unités de calcul. D'autres organisations sont possibles, mais c'est l'organisation la plus conventionnelle. C'est pour cela que l'on parle aussi de tableaux systoliques, qui est synonyme d'architecture systolique.

## Le flot des données dans une architecture systolique

Les carrés sont notés DPU pour Data Processing Unit. Dans le premier schéma, les flèches entre DPU donnent le sens de déplacement des opérandes et non des résultats des unités de calcul ! Les résultats des calculs ne sortent pas de l'unité de calcul. Le transfert des opérandes sur les interconnexions (les flèches) se fait de manière synchrone, c’est-à-dire cadencé par un signal d'horloge, qui commande la mise à jour des registres. Les unités de calcul sont donc associées à deux registres d'entrée : un par opérande entrant.
Les DPU (Data Processing Unit) ne sont rien de plus que des unités de calcul couplées à un registre accumulateur. À chaque cycle, elles effectuent une opération sur les deux opérandes entrants et additionnent le tout au contenu du registre accumulateur. Les éléments de calcul reçoivent des données en entrée, effectuent un calcul dessus, et mémorisent le résultat dans un registre accumulateur. À la fin du calcul, le résultat final est disponible dans les différents accumulateurs.
De nouveaux opérandes sont insérées sur les bords gauche et haut du tableau à chaque cycle d'horloge. Les données insérées ainsi parcourent le tableau d'un rang à chaque cycle. Les opérandes insérés à gauche parcourent le tableau de gauche à droite, en restant sur la même ligne. Celles insérées en haut le parcourent de haut en bas, en restant sur la même colonne. Le flot des données a été comparé au flot du sang dans le corps, avec la propulsion par les battements du cœur. D'ailleurs, le terme "systolique" est l'adjectif associé au nom "systole" qui désigne les battements du cœur. Plus précisément, il désigne une partie du battement du cœur, où le cœur se contracte pour pousser le sang dans les artères.
Pour exploiter le tableau systolique, il faut insérer les opérandes dedans au rythme d'un opérande par cycle pour chaque ligne/colonne. Pour cela, chaque ligne et colonne est reliée à une mémoire FIFO qui contient les opérandes à insérer, dans leur ordre d'insertion. À chaque cycle, un opérande est retiré de la FIFO et insérée dans le tableau systolique.
Le tableau systolique est secondé avec des circuits de contrôle qui insèrent les opérandes dans le tableau à chaque cycle. 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

Beaucoup de calculs ne sont pas implémentables sur les architectures systoliques, en raison de la non-programmabilité des éléments de calcul. Dans les faits, l'opération qui brille le plus par son adaptation aux architectures systoliques est la multiplication de matrices.
Pour rappel, une matrice est un tableau rectangulaire de nombres, organisé en lignes et colonnes. Les nombres sont appelés des éléments. Ils sont doublement numérotés, dans le sens où on leur attribue un numéro de ligne et un numéro de colonne, qui sont notés i et j respectivement. Par exemple, l’élément noté A42 appartient à la matrice A, est dans la 4ème ligne et sur la 2nd colonne.
Il est possible de multiplier des matrices. La multiplication de deux matrices prend deux matrices, qu'on notera A et B, pour fournir une matrice C. Pour simplifier les explications nous partons du principe que les matrices sont des matrices avec autant de lignes que de colonnes, appelées matrices carrées'. Avec des matrices carrées, le produit de deux matrices carrées de même dimension est une troisième matrice carrée, aux dimensions identiques aux deux matrices de base. La multiplication d'une matrice n'a rien de complexe, mais les formules deviennent rapidement compliquées, aussi nous allons expliquer le tout autrement.
Pour simplifier, le produit de deux matrices se calcule élément par élément du résultat. Pour obtenir le résultat dans une case du tableau, on regarde sa position dans le tableau : sa ligne et sa colonne. On prend alors la même ligne de la première matrice opérande et la même colonne dans la seconde matrice opérande. Et on multiplie les deux. Pour multiplier une ligne et une colonne, on procède comme suit : on prend le premier élément de la ligne et de la colonne, et on les multiplie. On fait pareil avec les seconds éléments, les troisièmes, etc. Et on additionne tous les produits calculés.
Le produit de deux matrices demande de faire beaucoup d'additions et de multiplications en parallèle. Prenons une matrice carrée de n lignes/colonnes. Calculer une case de la matrice finale demande de multiplier une ligne par une colonne et additionner le tout. Donc, calculer une case du résultat demande de faire $n^{2}$ produits et presque autant d'additions. A multiplier par le nombre de cases, ce qui donne $n^{4}$ multiplications et autant d'additions. Et les produits sont tous différents niveau opérandes, ce qui réduit fortement les optimisations possibles.

### L'usage des tableaux systoliques pour multiplier des matrices

Multiplier deux matrices demande de faire beaucoup d'opérations. N'espérez pas implémenter le tout avec $n^{4}$ multiplieurs et autant d'additionneurs. Il faut trouver une autre solution, qui réduit le nombre de multiplieurs/additionneurs utilisés, tout en gardant un temps de calcul acceptable. Pour cela, les tableaux systoliques sont tout indiqués. Les architectures systoliques incorporent pour cela des DPU capables de faire une opération MAD (multiply and accumulate), rien de plus. En tout, elles intègrent $n^{2}$ multiplieurs et autant d'additionneurs, mais le temps de calcul est proportionnel à n.
Et le mouvement des opérandes dans une architecture systolique colle parfaitement avec la multiplication de matrice. Pour rappel, une opérande traverse une ligne ou une colonne. Or, dans une multiplication de matrice, chaque opérande est utilisée dans tous les produits d'une ligne, ou dans tous les produits d'une colonne. L'idée est donc d'insérer une ligne/colonne case par case dans le tableau systolique. Pour multiplier deux matrices sur une architecture systolique, les deux matrices doivent être insérées dans le tableau comme suit :
Voici une vidéo qui montre comment se déroule la multiplication de deux matrices avec un tableau systolique :
    Systolic array, how matrices are multiplied?
Il faut noter qu'un tableau systolique a une taille fixe. par exemple, un tableau systolique 64 par 64 contient 4096 DPU, ce qui permet de multiplier des matrices carrées de 64 par 64. Mais il ne peut pas multiplier des matrices plus grandes. Cependant, il faut savoir que ce n'est pas un problème si on utilise des algorithmes de multiplication de matrices adaptés. De tels algorithmes subdivisent une matrice en plusieurs sous-matrices plus petites. Ils multiplient les sous-matrices entre elles et combinent les résultats pour obtenir la matrice finale. La subdivision est même récursive, à savoir que les sous-matrices sont elles-mêmes subdivisées, et ainsi de suite, jusqu'à obtenir des matrices très petites, que le hardware peut gérer. De tels algorithmes sont dit de type divide and conquer.

## Leur utilisation dans les accélérateurs d'intelligence artificielle

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 n'ont pas eu beaucoup de succès. 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 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. 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.