Réseau systolique

Dans les architectures informatiques parallèles, un réseau systolique est un réseau homogène d'unités de traitement de données (DPU) étroitement couplées appelées cellules ou nœuds. Chaque nœud ou DPU calcule indépendamment un résultat partiel en fonction des données reçues de ses voisins en amont, stocke le résultat et le transmet en aval. Les matrices systoliques ont été utilisées pour la première fois dans Colossus, qui était un des premiers ordinateurs utilisés pour casser les chiffrements allemands de Lorenz pendant la Seconde Guerre mondiale. Ils ont été redécouverts par H.T. Kung et Charles Leiserson qui ont décrit des réseaux pour de nombreux calculs d'algèbre linéaire dense (produit matriciel, résolution de systèmes d'équations linéaires, décomposition LU, etc.) pour les matrices à bandes. Les premières applications incluent le calcul des plus grands diviseurs communs d'entiers et de polynômes. Ils sont parfois classés comme architectures à données uniques à instructions multiples (MISD) selon la taxonomie de Flynn, mais cette classification est discutée plus loin dans cet article.

Les données d'entrée parallèles circulent à travers un réseau de nœuds de processeur câblés, qui combinent, traitent, fusionnent ou trient les données d'entrée en un résultat dérivé. Parce que la propagation des données à travers un réseau systolique ressemble au pouls du système circulatoire humain, le nom systolique a été inventé à partir de la terminologie médicale. Le nom est dérivé de la systole par analogie avec le pompage régulier du sang par le cœur.

Applications

Les 2014x systoliques sont souvent câblés pour des opérations spécifiques, telles que "multiplier et accumuler", pour effectuer des tâches d'intégration massivement parallèle, de convolution, de corrélation, de multiplication matricielle ou de tri de données. Ils sont également utilisés pour les algorithmes de programmation dynamique, et dans l'analyse de séquences d'ADN et de protéines.

Architecture

Un réseau systolique se compose généralement d'un grand réseau monolithique de nœuds informatiques primitifs qui peuvent être câblés ou configurés par logiciel pour une application spécifique. Les nœuds sont généralement fixes et identiques, tandis que l'interconnexion est programmable. Les processeurs à front d'onde plus généraux, en revanche, emploient des nœuds sophistiqués et programmables individuellement qui peuvent ou non être monolithiques, en fonction de la taille du réseau et des paramètres de conception. L'autre distinction est que les réseaux systoliques reposent sur des transferts de données synchrones, tandis que le front d'onde a tendance à fonctionner de manière asynchrone.

Contrairement à l'architecture Von Neumann plus courante, où l'exécution du programme suit un script d'instructions stockées dans la mémoire commune, adressées et séquencées sous le contrôle du compteur de programme (PC) du CPU, les nœuds individuels au sein d'un réseau systolique sont déclenchés par l'arrivée de nouvelles données et traitent toujours les données exactement de la même manière. Le traitement réel au sein de chaque nœud peut être câblé ou microcodé par bloc, auquel cas la personnalité du nœud commun peut être programmable par bloc.

Le paradigme du réseau systolique avec des flux de données pilotés par des compteurs de données est la contrepartie de l'architecture Von Neumann avec un flux d'instructions piloté par un compteur de programme. Étant donné qu'un réseau systolique envoie et reçoit généralement plusieurs flux de données et que plusieurs compteurs de données sont nécessaires pour générer ces flux de données, il prend en charge le parallélisme des données.

Objectifs et avantages

Un avantage majeur des réseaux systoliques est que toutes les données d'opérande et les résultats partiels sont stockés dans (passant par) le réseau. Il n'est pas nécessaire d'accéder aux bus externes, à la mémoire principale ou aux caches internes lors de chaque opération comme c'est le cas avec les machines séquentielles Von Neumann ou Harvard. Les limites séquentielles des performances parallèles dictées par la loi d'Amdahl ne s'appliquent pas non plus de la même manière, car les dépendances de données sont implicitement gérées par l'interconnexion de nœuds programmable et il n'y a pas d'étapes séquentielles dans la gestion du flux de données hautement parallèle.

Les réseaux systoliques sont donc extrêmement efficaces pour l'intelligence artificielle, le traitement d'images, la reconnaissance de formes, la vision par ordinateur et d'autres tâches que le cerveau des animaux accomplit particulièrement bien. Les processeurs de front d'onde en général peuvent également être très efficaces pour l'apprentissage automatique en implémentant des réseaux de neurones à auto-configuration en matériel.

Controverse sur la classification

Alors que les réseaux systoliques sont officiellement classés comme MISD, leur classification est quelque peu problématique. Étant donné que l'entrée est généralement un vecteur de valeurs indépendantes, le réseau systolique n'est certainement pas SISD. Étant donné que ces valeurs d'entrée sont fusionnées et combinées dans le(s) résultat(s) et ne conservent pas leur indépendance comme elles le feraient dans une unité de traitement vectoriel SIMD, il ne peut pas être classé comme tel. Par conséquent, il ne peut pas non plus être classé comme MIMD, car un MIMD peut être considéré comme une simple collection de petites machines SISD et SIMD.

Enfin, étant donné que les données sont transformée lorsqu'elles traversent le réseau de nœud en nœud, les nœuds multiples ne fonctionnent pas sur les mêmes données, ce qui rend la classification MISD impropre.

Malgré tout ce qui précède, les réseaux systoliques sont souvent proposés comme un exemple classique d'architecture MISD dans les manuels sur l'informatique parallèle et dans les cours d'ingénierie.

Les réseaux systoliques utilisent un graphe de flux de calcul prédéfini qui connecte leurs nœuds. Les réseaux de processus Kahn utilisent un graphe de flux similaire, mais il y a des files d'attente FIFO entre chaque nœud, et les nœuds ne sont pas synchronisés.

Description détaillée

Un réseau systolique est composé d'une matrice d'unités de traitement de données appelées cellules. Les unités de traitement de données (DPU) sont similaires aux unités centrales de traitement (CPU), (à l'exception de l'absence habituelle d'un compteur de programme, puisque l'opération est déclenchée par le transport, c'est-à-dire par l'arrivée d'un objet de données). Chaque cellule partage les informations avec ses voisines immédiatement après le traitement. Le réseau systolique est souvent rectangulaire où les données circulent à travers le réseau entre les DPU voisins, souvent avec des données différentes circulant dans des directions différentes. Les flux de données entrant et sortant des ports de la matrice sont générés par des unités de mémoire à séquençage automatique, les ASM. Chaque ASM comprend un Compteur de données. Dans les systèmes embarqués, un flux de données peut également être entré depuis et/ou sorti vers une source externe.

Un exemple d'algorithme systolique effectue la multiplication matricielle. Une matrice est alimentée une rangée à la fois à partir du haut du réseau et est transmise vers le bas du réseau, l'autre matrice est alimentée dans une colonne à la fois du côté gauche du réseau et passe de gauche à droite. Les valeurs fictives sont ensuite transmises jusqu'à ce que chaque processeur ait vu une ligne entière et une colonne entière. À ce stade, le résultat de la multiplication est stocké dans le réseau et peut maintenant être sorti une ligne ou une colonne à la fois, descendant ou traversant le réseau.

Les réseaux systoliques sont des réseaux de DPU qui sont connectés à un petit nombre de DPU voisins souvent suivant un maillage rectangulaire. Les DPU effectuent une séquence d'opérations sur les données qui circulent. Seules les applications avec des dépendances de données régulières peuvent être implémentées sur des réseaux systoliques classiques. Comme les machines SIMD, les réseaux systoliques calculent de façon synchronisée. Un réseau systolique bien connu est le processeur iWarp de l'Université Carnegie Mellon, qui a été fabriqué par Intel. Un système iWarp possède un processeur linéaire connecté par des bus de données allant dans les deux sens.

Histoire

Les réseaux systoliques ont été décrits pour la première fois par H.T. Kung et Charles E. Leiserson, qui ont publié le premier article décrivant les réseaux systoliques en 1979. Cependant, la première machine connue pour avoir utilisé une technique similaire était le Colossus Mark II en 1944.

Exemple d'application

Évaluation polynomiale

La règle de Horner pour évaluer un polynôme est :

$y=(\ldots (((a_{n}\cdot x+a_{n-1})\cdot x+a_{n-2})\cdot x+a_{n-3})\cdot x+\ldots +a_{1})\cdot x+a_{0}.$

Un réseau systolique linéaire dans lequel les processeurs sont disposés par paires : on multiplie son entrée par $x$ et passe le résultat à droite, le suivant ajoute $a_{j}$ et passe le résultat vers la droite.

Avantages et inconvénients

Avantages :

• Plus rapide que les processeurs à usage général
• Évolutif

Inconvénients :

• Cher, en raison de la faible économie d'échelle
• Un matériel hautement spécialisé et personnalisé est requis et souvent spécifique à l'application.
• Pas largement mis en œuvre
• Base de code limitée de programmes et d'algorithmes. (Tous les algorithmes ne peuvent pas être implémentés sous forme de réseaux systoliques. Souvent, des astuces sont nécessaires pour adapter l'algorithme afin de l'exécuter sur un réseau systolique. )

Implémentations

• Le processeur de réseau Cisco PXF est organisé en interne comme une matrice systolique.
• Le TPU de Google est également conçu autour d'un réseau systolique.
• Système de recherche de texte Paracel FDF4T TestFinder
• Paracel FDF4G GeneMatcher Système de recherche biologique (ADN et protéines)
• Puce d'inférence chez Amazon Web Services
• MIT Eyeriss est un accélérateur de réseau systolique pour les réseaux de neurones convolutifs.

Voir également

• MISD - Données uniques d'instructions multiples, exemple : réseaux systoliques
• iWarp – Ordinateur à matrice systolique, VLSI, Intel/CMU
• WARP (réseau systolique) – Ordinateur de réseau systolique, GE/CMU
• Tensor Processing Unit – accélérateur d'IA ASIC

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « systolic array » (voir la liste des auteurs).

Sources

• H. T. Kung, C. E. Leiserson: Algorithms for VLSI processor arrays; in: C. Mead, L. Conway (eds.): Introduction to VLSI Systems; Addison-Wesley, 1979
• S. Y. Kung: VLSI Array Processors; Prentice-Hall, Inc., 1988
• N. Petkov: Systolic Parallel Processing; North Holland Publishing Co, 1992

Annexes

Liens externes

• Instruction Systolic Array (ISA)
• 'A VLSI Architecture for Image Registration in Real Time' (Based on systolic array), Vol. 15, September 2007