Architectures systoliques pour le traitement du signal : bilan et perspectives

60 Architectures systoliques pp. 60-68

Yves ROBERT**

Architectures systoliques pour le traitement du signal.

bilan et perspectives*

R6sum~

L'article prdsente bridvement l'~volution des architectures systoliques, ~ travers l'exemple de la r~solution d' un probldme aux moindres carr(s tout particulidrement important en traitement du signal. On s'attache d mon- trer les avantages et les limites du moddle, et on d~crit quelques r~alisations architecturales. Une bibliographic comment~e conclut l'article.

Mots cl6s �9 Traitement signal, Architecture systolique, Article synth~se, MCthode moindre carr6.

Systolic architectures for digital signal processing : an assessment

and future trends

Abstract

In this paper we briefly survey systolic algorithms and architectures through the example of the least square solution of a beamforming problem. We show the ad- vantages and the limits of the systolic model of computation. We describe some existing systolic architectures. Finally, we provide the reader with an annotated list of references.

Key words : Signal processing, Systolic architecture, Review, Least square method.

Sommaire

I. Introduction. II. D~composition aux moindres carr~s.

III. Les contraintes du moddle.

IV. Quelques r(alisations architecturales. V. Bilan et perspectives.

VI. Bibliographic comment~e. Bibliographic (51 r(f).

I. I N T R O D U C T I O N

On pr6sente dans ce texte l '6volution de la recherche et des r6alisations dans le domaine des architectures systoliques au cours de la derni~re d6cennie. On tente 6galement de d6gager quelques perspectives.

Les r6seaux systoliques sont des processeurs int6gr6s sp6cialis6s. Deux caract6ristiques dominantes : un pa- rall61isme massif, et un mode op6ratoire synchrone. La complexit6 des circuits int6gr6s disponibles h l 'heure ac- tuelle rend possible la r6alisation hun faible cofit de tels syst~mes parall~les. Deux restrictions cependant :

�9 il s'agit de processeurs specialists que l 'on adjoint h un processeur h6te de type classique;

�9 la classe d'application est bien d61imit6e : les probl~mes o/1 le volume de calculs ~t effectuer prime largement sur les transferts de donn6es h r6aliser.

Une architecture systolique est agenc6e en forme de r6seau, qui se compose d 'un grand nombre de cellules 616mentaires identiques et localement interconnect6es. Chaque cellule reqoit des donn6es en provenance des cellules voisines, effectue un calcul simple, puis transmet les r6sultats, toujours aux cellules voisines, un temps de cycle plus tard. Pour fixer un ordre de grandeur, disons que chaque cellule a la complexit6, au plus, d 'un petit microprocesseur. Les cellules 6voluent en parall~le, sous le contr61e d 'une horloge globale (synchronisme total) : plusieurs calculs sont effectu6s simultan6ment sur le r6seau, et on peut pipeliner la r6solution de plusieurs

* Ce travail a 6t6 soutenu par le Projet de recherches coordonn6es C3 du CNRS et par le projet Esprit basic research action 3280 NANA de la Communaut6 6conomique europEenne.

** Laboratoire LIP-IMAG Ecole normale sup6rieure de Lyon, 46, all6e d'Italie, F-69364 Lyon Codex 07, France.

ANN. TELE, COMMUN., 46, n ~ 1-2, 1991 1/9

Y. ROBERT. - ARCHITECTURES SYSTOLIQUES POUR LE TRAITEMENT DU SIGNAL 61

instances du m~me problhme sur le r6seau. Notons que l'aspect synchrone, qui a donn6 son nom au modhle *, n'est pas essentiel : un mode de fonctionnement asyn- chrone, rythm6 par les donn6es est parfaitement possible (on parle alors de r6seaux ~ front d'onde).

Le traitement du signal est 6videmment un domaine d'application privil6gi6 des architectures systoliques : le volume important des calculs ~ effectuer, les exigences temps r6el imposent un recours au parall61isme. D'autre part, la r6gularit6 et la localit6 des op6rations dans les algorithmes usuels (convolution 1D ou 2D, d6com- position aux moindres carr6s, transformation de Fourier discrhte,...) correspondent bien aux exigences du modhle systolique.

Au paragraphe suivant, nous pr6cisons, sur l'exem- pie de la d6composition aux moindres carr6s, le fonctionnement d'une architecture systolique. Nous revenons au paragraphe III sur les contraintes du modhle, et les problhmes aff6rents aux relations avec la structure h6te (techniques de partitionnement, d6bit d'entr6es/sorties,...). Le paragraphe IV fait le point sur quelques r6alisations architecturales. Le paragraphe V d6gage quelques perspectives. Enfin, le lecteur d6sireux d'en savoir plus trouvera au paragraphe VI une bibliographie comment6e.

triangulaire sup6rieure d'ordre n. Comme Q est orthogonale,

I I A x - bll = [ I Q ( A x - b)ll = Ilnx- Q~bll + IIQ2bll.

La solution x du probl~me aux moindres carr6s est la solution du syst~me ~t n 6quations Rx = Q1 b, et l'erreur r6siduelle est [IQ2bll. Le calcul de x proc~de donc en deux 6tapes :

a) triangularisation orthogonale de la matrice (A, b), b) r6solution du syst6me triangulaire r6sultant.

ILl Triangularisation orthogonale

Nous d6crivons ici le r6seau triangulaire de Gent- leman et Kung [GK], qui est certainement l'arch6type du r6seau systolique bidimensionnel. Rappelons tout d'abord l'algorithme de triangularisation bas6 sur des matrices d'61imination de Givens.

pour k := 1 h n - 1 faire

pour i := k + 1/l m faire

ligne i ) * - - M i k ( ligne ligne

II. DI~COMPOSITION AUX MOINDRES CARRIES

On s'int6resse dans ce paragraphe ~ la r6solution d'un probl~me aux moindres carrEs avec contraintes linEaires. Soit A une matrice rectangulaire de taille m • n, avec m > n (dans la pratique, on a m~me m >> n), et b u n vecteur h m composantes. Le syst~me lin6aire Ax = b a plus d'6quations que d'inconnues : le vecteur x a n composantes. On cherche alors h minimiser la norme euclidienne du vecteur IIAx- bll, c'est-h-dire la (racine de la) somme des carr6s de ses composantes (d'ofa le nom du probl~me).

Ce probl~me intervient classiquement en traitement du signal pour la reconstitution d'un signal h partir des 6missions en sortie des diff6rents canaux d'un system e d'antennes radar ** (Mc Whirter [McW], Ward et al. [WHM]). Pour une application typique, il s'agit de reconstituer le signal h partir d'une dizaine de signaux 6chantillonn6s ~ plusieurs m6gahertz, ce qui n6cessite une puissance de calcul de l'ordre du gigaflop *** !

Si on factorise orthogonalement A, on obtient

(0 * La d6nomination systolique provient d 'une analogie entre la circu- lation des riots de donn6es darts le r6seau et celle du sang humain, l'horloge qui assure la synchronisation globale constituant le ctrur du syst~me. ** C'est le probl~me de la "formation de voies", traduction de l'anglais "beam forming". *** flop : floating point operation; gigaflop : milliard d'op6rations par seconde.

o?a la matrice Mik est choisie de mani~re ~ annuler le

coefficient en position (i, k) : 0 a~k "

Classiquement, M i k = ( cos0 s i n 0 ) - s i n 0 cos0 '

avec 0 = arctan ( aik ] . Ainsi l'algorithme proc~de en \ akk /

n - 1 6tapes. A l'6tape k, la ligne k est la ligne pivot, que l'on combine avec toutes les lignes inf6rieures pour annuler les 616ments de la k-i~me colonne situ6s sous la diagonale. On comprend ainsi qu'apr~s l'6tape n - 1, le syst~me obtenu est bien triangulaire.

Gentleman et Kung utilisent un r6seau triangulaire de processeurs connect6s orthogonalement, reproduit fi-

gure 1. Le nombre total de cellules est 6gal g n(n + 3) 2

Le r6seau se compose de n lignes, la ligne k com- prenant n + 2 - k processeurs num6rot6s de gauche h droite Pk,1,... , Pk,n+2-k (voir figure 1). La matrice (A, b) rentre dans le r6seau colonnes par colonnes. Plus pr6cis6ment, le processeur Plk reqoit les coefficients de la colonne k, un nouvel 616ment h chaque top, h partir du temps t = k. Ce format d'entr6e est 6galement repr6sent6 figure 1.

D'une faqon informelle, disons que la ligne k du r6seau est destin6e ~t effectuer l'6tape k de l'algorithme. Pour cela, on proc~de en deux temps. D'abord, il faut stocker la k-i6me ligne de la matrice dans le rdseau, un coefficient dans le registre interne de chaque cellule. Les lignes suivantes traversent alors les processeurs Pkl , . . . , Pk,,~+2-k, et effectuent au passage une combi- naison avec la ligne pivot k. A cet effet, les matrices Mk+l,k, Mk+2,k . . . . . Mnk sont g6n6r6es par la cellule ronde et transmises ~ toutes les autres cellules de la ligne.

2/9 ANN. TI~LI~COMMUN., 46, n ~ 1-2, 1991

62 Y. ROBERT. - ARCHITECTURES SYSTOLIQUES POUR LE TRAITEMENT DU SIGNAL

givens

givens

givens

init

54

a44 b3

a43 a34 b2

a42 a33 a24 b 1

a41 a32 a23 a14

a31 a22 a ~a

821 a12 - -

a l l

Fro. 1. - Le r6seau de triangularisation (n -- 4).

The triangularisation array (n = 4).

Bien stir, on pipeline ces deux phases, si bien que la cellule Pkl g6nbre les premibres matrices Mik(i > k) alors que les derniers coefficients de la ligne pivot k ne sont pas encore stockds.

Examinons par exemple le fonctionnement de la premibre ligne du r6seau. Tout d'abord, la premibre ligne de la matrice (A, b) est stock6e dans les registres internes des cellules : l'616ment alk est stock6 dans le processeur Plk au temps t = k. Quand une ligne numdro i > 2 est lue par le rdseau, elle est combin6e avec la ligne 1 pour annuler l 'dl6ment ail . La matrice 2 x 2, Mil est gdndrde par la ceUule P l l a u temps t = i, puis elle est envoy6e aux autres cellules de la ligne. Plus pr6cis6ment, la cellule/~ k > 2, effectue au temps t = i + k - 1 la transformation (alk, aik) t := Mil �9 ( a l L , aik) t.

I1 y a deux types de cellules dans le rdseau, reprdsentds par des ronds et des carr6s sur la figure 1. Dans la k-i~me ligne du r6seau : - la cellule Pkl est une cellule ronde, qui g6nbre les

matrices Mik pour i > k. - toutes les autres cellules sont des cellules carr6es, qui

appliquent les transformations M~k. Le fonctionnement des eellules est d6crite figure 2.

On voit que le fonctionnement des processeurs est contr616e par une variable bool6enne appelde contr~le *.

* On utilise figure 2 l'identit6 s in(arctan( t ) ) = 1 x / i -~ r

ANN. 'I'I~L~OMMUN., 46, n ~ 1-2, 1991

contr61e ain

contr61e

contr61e

Instant t Instant t + l

r contrSle de init : { stocker ain } r := ain ; givens : { g(~ndrer une rotation } GENERER (Lain, c,s) ;

Procddure GENERER (x,y,c,s): { rotation de (x,y) pour annuler y }

s l y = 0 a lo rs d~but c := 1 ; s := 0 ; fin sinon

sl lyl > Ixl a lors d i tbut t := x/y ; s := 1 / ~ c := st ; fin sinon d~but t := y/x ; c := 1 / ~ s := ct ; fin ;

x := cx + sy ; y := nil ;

ain

contr61e contr61e

aout


ea$ contr61e do init : { stocker ain } r := ain ; fin ; givens : { appliquer la rotation (c,s) }

di tbut APPLIQUER (r,ain,c,s) ; aout := ain ; fin

Proc6dure APPLIQUER (x,y,c,s): { appliquer la rotation (c,s) au couple (x,y) }

u : = x ; v : = y ; X:=CU+SV ; y := -SU + CV ;

FIG. 2. - Fonctionnement des cellules pour la factorisation de Givens.

Program of the cells for Givens factorization.

On v6rifie facilement, h l 'aide de la figure 1, que le premier fonctionnement du processeur Pki a lieu au temps t = 3k+i - 3. C'est pourquoi la variable contr~le circule dans le r6seau ~t partir de/911, avec une vitesse 1 vers la droite et une vitesse 1/3 vers le bas.

Au top m + 2n - 1, le processeur Pn2 effectue le dernier calcul. A cette date, la matrice triangulaire (R, b ' ) , avec b ' = Q l b , est stockde darts le rdseau de la manibre suivante :

rio r12 r13 T14 b~] r22 r23 r24 /

r33 r34 b~| r44 b~]

11.2 R ~ s o l u t i o n d u s y s t ~ m e t r i a n g u l a i r e

I1 reste h r6soudre le systbme triangulaire R z = b'. Pour ce faire, nous utilisons le mSme r6seau que pr6cddemment, et nous effectuons une deuxibme phase de calcul (que nous pipelinons avec la premibre).

3/9


L'id6e pour cette deuxi~me phase eat de faire appel l'algorithme de diagonalisation de Jordan. Nous allons combiner les lignes pivot avec toutes les autres lignes, et non plus seulement avec celles d'indice sup6rieur. A l'6tape k, nous cr6ons ainsi des z6ros dans toute la k-i~me colonne, except6 bien stir sur la diagonale. Puis nous divisons les coefficients de la ligne pivot par l'616ment diagonal pour obtenir un syst~me avec la matrice identit6 : r6solution imm6diate !

Pour 61iminer un coefficient a~ ~ l'6tape k, il n'est plus possible d'utiliser des rotations de Givens si i < k (sous peine de d6truire les z6ros cr66s dans les colonnes pr6c6dentes). On utilise alors des matrices Mi~ d'61imination de Gauss qui ne modifient pas la ligne [10] p i v o t k : M i ~ = _aJ~ .

Prenons n = 4 comme ~ la figure 1, et examinons l'action de la cellule Pll (voir Fig. 3). De t --- 1 ~ t = 4, tout se passe comme pr~c6demment. A l'instant t = 1, P ~ re~oit le contr61e init et stocke la variable en entree dans son registre interne. De t = 2 ~ t = 4, P ~ re~oit le contr61e givens et g6n~re les matrices ]Viii qui vont servir ~ annuler les coefficients ~2~, a31, a4~. A t = 5, il re~oit

0,vC~176176 a'o

Instant t

~ - - - ~ (b~out, b~out)

k ~ ~ contrOleout gi ~NN'~nt r61e~

v--~ga~ss

Instant t+ 1

{ modifier le contr61e en entr(~e si le signal giv~gauss est prasent } sl (g iv~gauss at contr61ein = givens)

a lors ctrl := gauss a lnon ctrl := contr61ein ; cas ctrl de

init : { stocksr ain } r := ain ; givens : { gan~rer une rotation }

d&but GENERER (Lain, c,s) ; bout 1 := c ; bout2:= s ; f in ; gauss : { alimination de Gauss }

dabut bout1:= -ain / r ; bout2:= nil ; f in ; rasol : { normaliser la ligne pivot }

d6but bout 1 := 1 / r ; bout2:= nil ; f in ; { g4n4ration du contr61e en sortie } contr61eout := ctrl ;

ain

contrSle contr~le

aout,


cas contr61e de init : { stocker ain } r := ain ; givens : { appliquer la rotation (c,s) }

d6but APPLIQUER (r,ain,bin 1,bin 2) ; aout := ain ; bout I := bin 1 ; bout2:= bin 2 ; f in ;

gauss : { ~limination de Gauss } d , ibut aout := ain + r * bin 1 ; bout 1 := bin 1 ; bout2:= nil ; f in ;

rdsol : { n0rmaUser la ligne pivot } d6but aou t := r * bin I ; bout 1 := bin I ; bout2:= nil ; f in ;

FiG. 3. - Fonctionnement des cellules pour la r6solution complete du syst~me.

Program of the cells for solving the whole least squares problem.

le contr61e r~sol (pour r6solution) et envoie l'inverse de son registre interne vers la droite, afin de normaliser la premiere ligne de la matrice (R, b ') en cr6ant un 1 sur la diagonale.

De t --- 2 ~ t = 5, P12 agit comme pr6c6demment : stockage puis triangularisation. I1 re~oit l'instruction r~sol ~ t --- 6. I1 multiplie alors le contenu de son registre interne par l'inverse du pivot o~11 qu'il reqoit de la gauche, et transmet la nouvelle valeur de a12 P21. PI2 transmet 6galement l'instruction r~sol vers la droite, pour continuer la normalisation de la ligne.

A t = 4, P21 re~oit l'instruction init et stocke a22. P21 g6n~re les matrices de Givens M32 et M42 pour 61iminer a32 et a42, aux temps t --- 5 et t = 6 respectivement. I1 doit alors g6n6rer une matrice de Gauss Mr2 h t = 7 pour 61iminer a12. Ce qui explique que la demi~re instruction givens que lui a transmise Pi t doit ~tre chang6e en gauss. C'est le r61e du bool6en giv --~ gauss

qui circule h la vitesse 1/2 vers le bas (donc plus vite que le contr61e) et transforme la derni~re instruction givens

de chaque cellule ronde en instruction gauss. P l l reqoit ce bool6en ~ t = 5, en m~me temps que l'instruction r~sol.

La valeur finale de la premiere composante zl du vecteur solution est calcul6e au temps t = m + 2n par le processeur Pn2. Une nouvelle composante du vecteur solution est d61ivr6e tous les tops, portant le temps de r6solution total du syst~me aux moindres carr6s

m + 3n - 1 tops. L'int6r~t principal de cette approche bas6e sur un uni-

que r6seau qui re~oit en entr6e les donn6es du syst~me et fournit en sortie sa solution, est de ne n6cessiter aucun retour interm6diaire h l'ordinateur h6te.

III . LES CONTRAINTES DU MODI~LE

Telle qu'elle est d6finie plus haut, l'architecture systolique est tr~s int&essante. Tout d'abord, elle r6sout un probl~me complexe, oh les calculs sont de l'ordre de m n 2 op6rations, en temps lin6aire m + 3n. Ensuite, le r6seau est tr~s r6gulier, et utilise seulement deux types de cellules : le r6seau complet s'obtiendra tr~s facilement ~ partir du dessin VLSI des deux briques de base, dessin qu'on peut unifier si on est pr& h utiliser une arithm6tique de type Cordic.

Plusieurs questions se posent n6anmoins pour une r6alisation concrete. La premiere est li6e h la taille du r6seau implant6 : est-il raisonnable de fondre dans le silicium un r6seau de taille fixe ? La deuxi~me question est li6e aux entr6es-sorties : va-t-on pouvoir correctement alimenter le r6seau ?

III.1 Les techniques de partitionnement

La r6ponse ~ la premiere question est 6videmment li6e au contexte d'utilisation. Par exemple, la r6solu- tion du probl~me aux moindres carr4s pour certaines applications a6ronautiques embarqu6es n6cessite une machine sp6cialis4e, compacte et ~ faible consommation

4/9 ANN. T.~LI~COMMUN., 46, n ~ 1-2, 1991

6 4 Y. ROBERT. - ARCHITECTURES SYSTOLIQUES POUR LE TRAITEMENT DU SIGNAL

d'Energie. Une architecture systolique de taille ad hoc semble ~tre la seule rEponse possible dans ce contexte. Plus gEnEralement, rappelons que le premier crEneau des architectures systoliques se trouve justement dans des applications sp6cifiques en traitement du signal et de l'image.

Dans un contexte plus gEnEral, il peut s'avErer sou- haitable de concevoir un rEseau systolique de taille r pour la resolution d'un probl6me aux moindres carrEs de matrice A de taille M x N. Pour simplifier, concentrons- nous sur la phase de triangularisation. L'algorithme de Givens progresse par colonnes. Soient cl, c2 . . . . . ci . . . . . clv les colonnes de A. A l'Etape k, seules les N - k + 1 derni~res colonnes de la matrice sont h considErer. On traite la colonne k pour gEnErer les matrices d'Elimina- tion de Givens Mik,i>k, et on applique les transformations correspondantes aux colonnes restantes. Pour un traitement totalement parall~le de l'Etape k, il nous faut donc disposer d'un processeur (rond) pour la gEnEration des transformations, et de N - k processeurs (carrEs) pour appliquer celles-ci (fig. 4a). Nous venons de dEcrire la k-i~me ligne de cellules du rEseau prEcEdent ! A l'op- posE, si on dispose de deux processeurs, un rond et un carrE, il faut traiter sEquentiellement les colonnes restantes, et par consequent on doit stocker dans des registres temporaires les instructions gEnErEes par le processeur rond pour les renvoyer autant de fois que nEcessaire en entree du processeur carr6 (fig. 4b).

Ck Ck+l Ck+2 CN-1 CN

FIe. 4. - a) Phase k de l'61imination de Givens avec N - k + 1 processeurs.

a) Phase k for Givens elimination using N - k + 1 processors.

CN

Ck

Ck+2

Ck+l

tampon @ instructions

FIG. 4. - b) Phase k avec seulement 2 processeurs.

b) Phase k using only 2 processors.

posons N = nr. On divise la matrice A en n blocs de r colonnes : soit Ck le k-i~me bloc de r colonnes de la matrice A, formE des colonnes (k - 1)r + 1 ~ kr. Le premier rEseau systolique triangulaire T (jouant le r61e du processeur rond prEcEdent) gEn6re les instructions relatives au traitement des r colonnes du bloc Ck, et ces instructions, stockEes dans un tampon, sont envoyEes en entree du rEseau carrE pour le traitement des blocs suivants (fig. 4c).

Cn

Ck

( ~ tampon instructions

Ok+2

Ck+l

FIG. 4. - C) Partionnement pour l'61imination de Givens.

c) Partitioning the Givens elimination.

Soulignons un point essentiel : l'entr6e des coefficients de la matrice A du syst~me doit se faire par colonnes, puisque le partitionnement s'effectue selon les colonnes de la matrice. Si l 'un des r6seaux recevait ses entrees sous forme de lignes de la matrice, le traitement d'une colonne donnEe devrait s'effectuer en plusieurs passages, impliquant la nEcessitE de stocker et/ou de transmettre des informations internes au rEseau. A l'opposE dans un fomaat par colonnes, seules les varia- bles externes aux rEseaux (instructions et donnEes en sortie) doivent ~tre temporairement stockEes avant leur prochain traitement. Avec cette mEthode, pour une matrice de taille M • N, on obtient un temps de calcul

N 2 M Egal h ~ (le temps de stockage et de communica-

tion avec l'h6te est nEgligE). Le temps d'exEcution est bien divisE par un facteur de l'ordre de r 2 relativement au temps sEquentiel.

Nous renvoyons h [Mol, Hel, QR] pour une Etude plus complete. Notons simplement que ce qui a facilitE l'approche sur notre exemple est l'absence de cycles dans le graphe de communication du rEseau [CH, Kla, HC] ... une caractEristique importante Egalement pour la conception de rEseaux resistant aux pannes [HA, JA].

III.2 Les entr~es/sorties Apr~s ex6cution compl6te de la phase k, les deux

processeurs peuvent ~tre r6utilis6s pour l'6tape k + 1. Bien stir, un tel dispositif n'est pas directement efficace, mais il contient en germe l'idEe-cl6 qui sous-tend les techniques de partitionnement : si on remplace chacun des deux processeurs par un r6seau systolique de taille r, on gagne un facteur de r 2 sur le temps d'ex6cution. Supposons sans perte de g6n6ralit6 N divisible par r, et

Le probl6me des entr6es/sorties se d6compose en deux sous-probl6mes : un probl~me pratique de r6alisa- tion, li6 aux nombres de pattes disponibles sur un boitier, et un probl~me de d6bit, lid h l'alimentation en donn6es du r6seau systolique par la structure h6te.

Consid6rons le r6seau triangulaire pr6c6dent, avec r = 4. I1 faut connecter la structure h6te en entr6e des 4 cellules de la premiere ligne, et en sortie des 4 cellules de

ANN. T~LI~COMMUN., 46, n ~ 1-2, 1991 5/9


la demi~re colonne, soit 8 mots de donn6es. N6gligeant tout contr61e, horloge, alimentation et autres d6tails, on obtient 512 pattes pour une entr6e parall~le de 8 mots de 64 bits. Impossible! Cette contrainte technologique a conduit les concepteurs ~ mettre en oeuvre deux types de techniques :

(i) utiliser des entr6es bit s6rie, et par suite d6velopper des algorithmes pipeline sp6cifiques pour ce mode de fonctionnement. Les progr~s r6cents en arithm6tique en ligne permettent de telles r6alisations [Erc, DHM] ;

(ii) utiliser une carte interface extr~mement perfec- tionn6e, capable de multiplexer et rediriger les entr6es d'un circuit vers un autre h chaque pulsation du syst~me.

Le probl~me de l'alimentation du circuit est bien stir li6 au mode op~ratoire bit s6rie ou bit parall~le. Mais dans les deux cas, les demandes en d6bit sont consid6ra- bles. C'est certainement cette contrainte qui a conduit au d6veloppement d'architectures systoliques lin6aires, dont seules les deux cellules extr6mit6s communiquent avec le monde ext6rieur.

Reprenons notre r6seau triangulaire : on peut facilement simuler l'op6ration des cellules sur un r6seau lin6aire de processeurs. L'id6e la plus simple est d'al- louer les calculs effectu6s par les cellules de la j-i~me colonne du r6seau au j-i~me processeur. C'est d'ailleurs la m6thode employ6e par Ho et al [HLL] pour r6sou- dre notre probl~me aux moindres carr6s sur la machine W A R P . Une difficult6 cependant : la capacit6 m6moire des processeurs doit maintenant d6pendre de la taille du probl~me, et les techniques de partitionnement sont plus difficiles/t mettre en oeuvre.

IV. QUELQUES RI~ALISATIONS ARCHITECTURALES

On peut distinguer 3 t.ypes de r6alisations : les r6seaux sp6cialis6s, les r6seaux microprogrammables, et les r6seaux h usage g6n6ral. Sans entrer dans les d6tails, nous consacrons un paragraphe ~ chacune de ces cat6go- ries, renvoyant aux r6f6rences cit6es pour plus d'infor- mation.

IV.1 Les r6seaux sp6cialis6s

Le premier cr6neau commercial des architectures systoliques, celui des op6rateurs int6gr6s monoalgorithme, s'est r6v616 porteur, et de nombreuses r6alisations ont vu le jour. Le lecteur trouvera une large liste de r6alisa- tions dans les conf6rences [BKS, KWK, MMS, MMU] et dans le num6ro sp6cial de Computer [Com]: op6rateurs de convolution [Chr], de corr61ation, FFT ([Swa], produit matrice-vecteur, r6seaux de dgcomposition aux moindres carr6s, filtres de Kalman [Yeh]. Citons un d6veloppe- ment r6cent qui consiste h utiliser les r6seaux systoliques (comme le produit matrice-vecteur) comme briques de base pour des op6rateurs connexionistes ("r6seaux

de neurones") d'apprentissage et de reconnaissance de formes [BM, KSY2].

IV.2 Un r~seau microprogrammable : le GAPP

Nous citons ici le GAPP (Geometric Arithmetic Paral- lel Processor), conqu par Martin Marietta [Clo] et com- mercialis6 par NCR [NCR]. "Le premier processeur parall~le monochip h architecture systolique" (pour repren- dre les termes de la documentation") se pr6sente sous la forme d'un circuit VLSI h 8 4 broches, contenant une grille rectangulaire de 6 x 12 microprocesseurs 1 bit, dont chaque 616ment peut communiquer avec ses quatre voisins Nord, Est, Sud et Ouest, ainsi qu'avec l'ext6rieur. Chaque processeur est compos6 d'une UAL, d'une RAM de 128 bits, et de quatre registres 1 bit. Trois sont af- fect6s aux entr6es de I'UAL, et le quatri~me permet la transmission d'entr6es/sorties/l travers la grille sans in- terf6rer avec I'UAL. Toutes les op6rations arithm6tiques et logiques de base sont r6alis6es en un seul cycle. Cha- que processeur reqoit ses instructions par mots de 13 bits.

Bien que r6alis6s en technologie de pointe (CMOS double m6tallisation), les 616ments pris individuellement ne sont pas particuli~rement rapides : il faut 25 cycles pour additionner deux nombres de 8 bits. Mais en additionnant les 72 processeurs d'un GAPP, on obtient une puissance de calcul de 28 millions d'additions de 8 bits par seconde. De plus, le GAPP est modulaire, et des zones de processeurs de taille arbitraite peuvent ~tre constitu6es par multiples de 6 • 12 616ments.

Le GAPP trouve imm6diatement son application dans le traitement de signaux utilisant de tr~s grandes puis- sances de calcul, comme la reconnaissance des formes, et surtout le traitement d'images, domaine pour lequel il a 6t6 originellement con~u. Si chaque pixel est af- fect6 hun processeur, une grille de taille 48 x 48 (soit 32 GAPPS) peut prendre en compte jusqu'h 60 millions de pixels par seconde, soit 6 fois le rythme temps r6el standard des syst~mes de synth~se vid6o classiques.

Chaque cellule du G A P P dispose d'une ligne de communication directe avec l'ext6rieur, ce qui confere/l l'ensemble une caract6ristique SIMD. Mais la d6nomination systolique semble incontestable (c'6tait lh un point fort de la publicit6 de NCR).

Le successeur du GAPP est en cours de r6alisation chez Martin Marietta. I1 s'agit d'ASAP II (Advanced Systolic Array Processor) [HG], un ensemble modulaire de cartes VME capable de surpasser la Connection Machine...

IV.3 Une machine/~ usage g6n6rai : le WARP

La machine WARP, dont la conception a d6but6 en 1984 ~t Carnegie Mellon University, est compos6e de trois parties : l'h6te, l'unit6 d'interface, et un r6seau lin6aire de processeurs (fig. 5).

Le WARP est une machine complexe, capable de simuler un r6seau lin6aire bidirectionnel ou encore un r6seau

6/9 ANN. TFLI~COMMUN., 46, n ~ 1-2, 1991


I hSte I

d'interface

........ admsses, contr(51e - - donn6es

FIG. 5. - La machine WARP.

The WARP machine,

deux dimensions. Un langage de bas niveau (microins- tructions) a 6t6 d6velopp6 pour les cellules et l'unit6 d'interface. Un syst~me de d6monstration de 10 cellules WARP, totalement int6gr6es dans un syst~me, fonction- nait en 1987 h Carnegie Mellon, avec une performance de pointe de 100 Mflops [AAG, KHT3]. La compagnie General Electric commercialise la machine. De nom- breux algorithmes de traitement du signal et de l'image ont pu ~tre implant6s sur la machine, grace h l'utilisation d'un langage de programmation de haut niveau compil6 de fa~on tr~s performante.

Le successeur du WARP est annonc6 pour le dernier trimestre 1990. Le iWARP, d6velopp6 avec Intel, est un processeur monochip pouvant servir de brique de base hun r6seau lin6aire ou bidimensionnel [BCC]. Le d6bit de communication interprocesseur est de 40 Mo/s sur chacun des 4 liens bidirectionnels, et chaque processeur peut d61ivrer 20 Mflops (fig. 6). Une cellule du iWARP a donc une puissance de calcul comparable h celle du microprocesseur i860, par exemple. L'int6r& principal de la machine r6side en son potentiel extraordinaire de communication (mode systolique local, mais aussi routage "wormhole" comme pour les hypercubes de deuxi~me g6n6ration). La r6ussite de ce projet permettrait ~ coup stir de d6passer largement les meilleures performances jamais obtenues pour les algorithmes usuels du traite-

m@moire locale

'5 E

E unita de calcul

.~=

I unit~ de communication

EG. 6. - Une cellule du iWARP.

/WARP cell.

ment du signal comme la convolution ou la transformation de Fourier rapide.

V. BILAN ET PERSPECTIVES

V.1 Quelques 61~ments d'appr6ciation

La qualit6 du bilan d6pend bien stir des pr6ten- tions affich6es h l'origine. Donnons quelques 616ments d'appr6ciation :

�9 Recherche : la recherche sur les architectures systoliques se porte bien. L'auteur de cet article a largement plus de 1000 r6f6rences sur le sujet dans sa biblioth~que, et cela ne repr6sente qu'un petit pourcentage de la litt6ra- ture existante. La communaut6 des "systoliciens" a cependant 6prouv6 r6cemment le besoin d'61argir son ac- tivit6, comme en t6moigne la modification du titre de la conf6rence internationale annuelle Systolic arrays en Application specific array processors.

�9 Projets : plusieurs projets europ6ens (Esprit) et am6ricains (sponsoris6s par les grandes agences gouver- nementales) sont en cours.

�9 R6alisations commerciales : encore une fois, la phi- losophie du modble s'est impos6e pour les op&ateurs sp6cialis6s. Par exemple, il semble inconcevable aujour- d'hui de dessiner un circuit de convolution sans exami- ner la solution systolique. Bien stir, cette solution systolique "pure" sera certainement remanife en fonction du cahier des charges de l'application (ajout d'un bus de chargement, par exemple), mais les paradigmes de lo- calit6 et modularit6 sous-tendront toujours la d6marche du concepteur. En ce qui concerne les machines plus g6n6rales, le pronostic est encore incertain, mais le fait que le iWARP ait 6t6 choisi avec la Connection Machine par la Darpa comme l'une des deux machines de la d6cennie est de bon augure ?

Les perspectives sont nombreuses. Citons deux axes de recherche importants :

�9 algorithmique : les probl~mes de partitionnement et de relation machine systolique/h6te ont fait comprendre l'importance des r6seaux lin6aires, modulaires, microprogrammables, sans cycles;

�9 synth~se : les m6thodologies de synth~se de r6seaux progressent chaque jour, et surpassent souvent la conception manuelle. La classe des algorithmes qu'on salt synth6tiser s'61argit 6galement. On est proche d'une chatne complete, qui partant d'un algorithme exprim6 en langage applicatif de haut niveau, g6n6rera une entr6e directement ufilisable par un compilateur de silicium,

I1 est difficile, dans le cadre de cette pr6sentation d'ensemble, d'entrer dans le d6tail des deux axes de recherche pr6c6dents : la technicit6 des articles systoliques a beaucoup progress6 en 10 ans! Pour donner un seul exemple, revenons sur le r6seau de la figure 1 qui triangularise une matrice de taille n x (n + 1) en temps 3n - 1, avec n(n + 3)/2 cellules. Plusieurs questions naturelles se posent :

ANN. 'I"~II~COMMUN., 46, n ~ 1-2, 1991 7/9


�9 ce temps est-il optimal ? Le plus difficile est de prEciser les hypoth6ses qui caractErisent la classe des rEseaux considErEs;

�9 quel est le Hombre minimal de processeurs nEces- saire pour un rEseau optimal en temps ?

�9 peut-on trouver des mEthodes systEmatiques pour la construction de tels rEseaux ?

Voici des rEponses partielles : �9 le temps 3n - 1 est optimal duns la classe des

rEseaux obtenus par ordonnancement puis allocation d'un graphe de dependance rendu uniforme * ;

�9 il est possible de construire un rEseau optimal en temps et qui n'utilise que n2/4 cellules environ (moiti6 moins que le rEseau initial [BR]);

�9 des mEthodes de synth~se sont en cours de dEve- loppement (voir par exemple [CMP]).

V.2 Le projet europEen NANA

�9 un ouvrage gEnEral sur les algorithmes et architectures systoliques de Quinton et Robert [QR],

�9 le numEro special de Computer [Com] sur les rEseaux systoliques,

�9 les articles de synthEse suivants : [FoK, KuA, Qui, Rob].

En ce qui conceme les applications du modEle systolique au traitement du signal :

�9 l'ouvrage de S.Y. Kung [KSY1], �9 les articles de synthEse suivants : [CS1, FiK, KHT1,

KY, SK], �9 les articles plus spEcialisEs : [ADM, CS2, Del,

WCY, Yeh]. Enfin, la communautE des chercheurs darts le do-

maine systolique, et plus gEnEralement des machines VLSI spEcialisEes, se rEunit lors d'une conference annuelle depuis 1986 [MMU, BKS, MMS, KSF]. Tout ce que vous avez toujours voulu savoir sur le systolique se trouve l~t !

Pour illustrer les axes de recherche cites, dEcrivons briEvement le projet Esprit basic research action 3280 "NANA : Novel parallel algorithms for new real-time VLSI architectures" de la Communaut6 6conomique eu- ropEenne **

L'objectif est le dEveloppement d'algorithmes pa- rallEles et d'architectures VLS! temps reel pour le traitement du signal multidimensionnel (MDSP) et les intEgrer dans un environnement de synthEse assistEe par ordinateur. La premiere partie du projet est axle sur la conception d'algorithmes parallEles devant s'exEcuter sur des architectures VLSI temps reel :

�9 noyaux algorithmiques pour le traitement du signal multidimensionnel,

�9 mEthodes de valeurs propres et decomposition SVD, EtudiEes d'un point de vue de leur robustesse numErique et de leur complexitE pour une integration VLSI,

�9 problEmes de modElisation (ElEments finis, lancer de rayons).

La deuxiEme partie conceme les methodologies architecturales de synthEse :

�9 architectures microprogrammEes (gestion mEmoire, allocation),

�9 architectures systoliques (transformations formelles, algorithmes, interfaces),

�9 architectures h front d'onde.

VI. BIBLIOGRAPHIE COMMENTI~E

Pour une initiation au module systolique, on peut conseiller

�9 les deux articles fondateurs de Kung [KHT2] et Kung-Leiserson [KLe],

* Nous demandons pardon ~t tousles lecteurs non spEcialistes du sujet ]ui pourraient trouver cette phrase quelque peu sibylline !

Voici la liste des 6quipes membres du projet : Coordinateur : IMEC Louvain (F. Catthoor). Partenaires : TU Delft (E. Deprettere, P. Dewilde), ESAT Louvain (J. Vandewalle), IRISA Rennes (P. Quinton), LIP-IMAG Lyon (Y. Robert).

REMERCIEMENTS

Nous remercions vivement le relecteur, dont les com- mentaires ont permis d'am~liorer la presentation et le contenu de l'article.

BIBLIOGRAPHIE

[AAG] ANNARATONE (M.), ARNOULD (E.), GROSS (T.), KUNG (H.T.), LAM (M.), MENZILCIOGLU (O.), WEBB (J.A.). The Warp computer : architecture, implementation and performance, IEEE Trans. Computers (1987), 36, n ~ 12, pp. 1523-1538.

[ADM] AHMED (H.M., DELOSME (J.M.), MORE (M.). Highly concurrent computing structures for matrix arithmetic and signal processing, Computer (1982), 15, n ~ 1, pp. 65-82.

[BCC] BORKAR (S.), COHN (R.), COX (G.), GROSS (T.), KUNG (H.T.), LAM (M.), LEVINE (M.), MOORE (B.), MOORE (W.), PETERSON (C.), SUSMAN (J.), SUTI'ON (J.), URBANSKI (J.), WEBB (J.). Supporting systolic and memory communication in iWarp, in Proc. 1EEL 17th Annual Syrup. on Computer Architecture, Computer Society Press (1990), pp. 70-81.

[BKS] BROMLEY (K.), KUNG (S.Y.), SWARTZLANDER (E.) 6diteurs. In- ternational Conference on Systolic Arrays, IEEE Computer Society Press 0988).

[BM] BLAYO (F.), MARCHAL (P.). A generic systolic VLSI chip for cellular automata, in [MMS], pp. 655-664.

[BR] BENAINI (A.), ROBERT (Y.). Spacetime-minimal systolic arrays for Gaussian elimination and the algebraic path problem, Parallel Computing (1990), 15, pp. 211-225.

[Chr] CHRISTIE (R.D.). The MA7170 systolic correlator, architecture and applications, in [MMU], pp. 113-122.

[CH] CHUANG (H.Y.H.), HE (H.). Design of problem-size independent systolic arrays systems, in Int. Conf. Computer Design ICCD 84, IEEE Press (1984), pp. 152-156.

[Clo] CLOUD (E.). The geometric arithmetic parallel processor, in Proc. 2nd Symposium on the Frontiers of Massively Parallel Computation, R. Mills ed., Computer Society Press (1988), pp. 373-381.

[CMP] CLAUSS (P.), MONGENET (C.), PERRIN (G.R.). Calculus of space- optimal mappings of systolic algorithms on processor arrays, in [KSF!, pp. 4-18

[Com] Computer, numEro special Systolic arrays, 20, n ~ 7. [CS 1] CAPPELLO (ER.), STEIGLITZ (K.). Digital signal processing appli-

cations of systolic algorithms, in VLSl Systems and Computations, H.T. Kung et al. eds., Computer Science Press (1981), pp. 245-254.

[CS2] CAPPELLO (ER.), STmGLrrZ (K.). Completely pipelined architectures for digital signal processing, IEEE Trans. ASSP (1983), 31, n o 4, pp. 1016-1023.

[Dell DELOSME (J.M.). Algorithms for finite shift-rank processes, Ph. D. Thesis, Electrical Engineering Department, Rapport Technique M735-22, Stanford electronics laboratories (1982).

8/9 ANN. T~LI~COMMUN., 46, n ~ 1-2, 1991


[DHM] DUPRAT (J.), HERREROS (Y.), MULLER (J.M.). Some results about on-line computations of functions, in Proc. IEEE Syrup. on Computer Arithmetic ARITH, Computer Society Press (1989), 9, pp. 112-118.

[Erc] ERCEGOVAC (M.D.). On-line arithmetic : an overview, Real-time signal processing VII, in Proc. SPIE (Society of photo-optical instrumentation engineers) (1984), 495, pp. 86-93.

[FiK] FISHER (A.L.), KUNG (H.T.). Special-purpose VLSl architectures : general discussions and a case study, in [KWK], pp. 153-169.

[FoK] FOSTER (M.J.), KUNG (H.T.). The design of special-purpose VLSl chips, Computer (1980), 13, l, pp. 26-40.

[FRT] FOGELMAN-SOULIE (F.), ROBERT (Y.), TCHUENTE (M.). Automata Networks in Computer Science, Manchester Univ. Press (1987).

[GK] GENTLEMAN (W.M.), KUNG (H.T.). Matrix triangularisation by systolic arrays, 298, Proceedings SPIE (1981), Real-time Signal Processing IV, pp. 19-26.

[HA] HUANG (K.H.), ABRAHAM (J.A.). Algorithm based fault-tolerance for matrix operations, IEEE Trans. Computers (1984), 33, n ~ 6, pp. 518-528.

[HC] HWANG (K.), CHENG (Y.H.). Partitioned matrix algorithm for VLSl arithmetic systems, IEEE Trans. Computers (1982), 31, n ~ 12, pp. 1215-1224.

[Hel] HELLER (D.). Partitioning big matrices for small systolic arrays, in VLSl and Modern Signal Processing [S.Y. Kung et al. eds.] (1985), pp. 185-199.

[HG] HAUG (A.), GRAYBILL (R.). The Martin Marietta advanced systolic array processor, Proc. 2nd Symposium on the Frontiers of Massively Parallel Computation [R. Mills ed.], Computer Society Press (1988), pp. 367-372.

[HLL] Ho (T.V.), LAW (M.K.), LITVA (J.). Application of the Warp processor to adaptive beamforming, in [MMS], pp. 13-20.

[JA] Jou (J.Y.), ABRAHAM (J.A.). Fault-tolerant matrix arithmetic and signal processing on highly concurrent computing structures, Proceedings of the lEEE (1986), 74, n ~ 5, pp. 732-741.

[KHT1] KUNG (H.T.). Special-purpose devices for signal and image processing : an opportunity in VLSl, real-time signal processing III, Proc. SPIE (1980), 241, pp. 76-84.

[KHT2] KUNG (H.T.). Why systolic architectures, Computer (1982), 15, n ~ l, pp. 37-46.

[KHT3] KUNG (H.T.). WARP experience : we can map computations onto a parallel computer efficiently, Proc. 1988 Int. Conf. on Supercomputing, ACM Press (1988), pp. 668-674.

[KLa] KUNG (H.T.), LAM (M.S.). Fault-tolerance and two-level pipeli- ning, in VLSl systolic arrays, J. Parallel and Distributed Computing (1984), 1, n ~ 1, pp. 32-63.

[KLe] KUNG (H.T.), LEISERSON (C.E.). Systolic arrays for (VLSl), in [MC], chapitre 8.3.

[KSF] KUNG (S.Y.), SWARTZLANDER (E.E. Jr.), FORTES (J.A.B.), PRZYTULA (K.W.). Application specific array processors, 1EEL Computer Society Press (1990).

[KSY1] KUNG (S.Y.). VSLI array processors, Prentice Hall (1988). [KSY2] KUNG (S.Y.). VLSI array processors for signal/image proces-

sing, in Parallel processing for supercomputers and Al, [K. Hwang and D.G. Groot eds.], McGraw-Hill (1988), pp. 561-608.

[KuA] KUNG (S.Y.), ANNEVELINK (J.). VLSI design for massively parallel signal processors, Microprocessors and Microsystems (Special issue on signal processing devices) (1983), 7, n o 4, pp. 461-468.

[KWK] KUNG (S.Y.), WHITEHOUSE (H.J.), KAILATH (Z.). VLSI and modern signal processing, Prentice Hall (1985).

[KY] KULKARNI (A.V.), YEN (D.W.L.). Systolic processing and an implementation for signal and image processing, IEEE Trans. Computers (1982), 31, n ~ 10, pp. 1000-1009.

[McW] MC WHIRTER (J.). Recursive least-squares minimization using a systolic array, Real-time Signal Processing VI, Proc. SPIE (1983), 431, pp. 105-112.

[MC] MEAD (C.A.), CONWAY (L.A.). Introduction to VLSl systems, Addison-Wesley (1980).

[MMS] McCANNY (J.), McWHIRTER (J.), SWARTZLANDER (E.E.). Sys- tolic array processors, Prentice Hall (1989).

[MMU] MOORE (W.), McCABE (A.), URQUHART (R.). Systolic arrays, Adam Hilger (1987).

[Mol] MOLDOVAN (D.I.). Mapping an arbitrarily large QR algorithm into fixed size systolic arrays, IEEE Trans. Computers (1986), 35, n ~ l, pp. 1-12.

[NCR] NCR Note commerciale 45CG72, GAPP : Geometric Arithmetic Parallel Processor, NCR, GB (1984).

[QR] QUINTON (P.), ROBERT (Y.). Algorithmes et architectures systoliques, Masson (1989).

[Qui] QUINTON (E). The systematic design of systolic arrays, in [FRT], pp. 229-260.

[Rob] ROBERT (Y.). Systolic algorithms and architectures, in [FRT], pp. 187-228.

[SK] SCHREIBER (R.), KUEKES (E), Systolic linear algebra machines in digital signal processing, in [KWK], pp. 389-405.

[Swa] SWARTZLANDER (E.E.). Systolic FFT processors, in [MMU], pp. 133-140.

[WCY] WILLEY (T.), CHAPMAN (R.), YOHO (H.), DURRANI (T.S.), PREIS (D.). Systolic implementations for convolution, DFT and FFT, Proceedings of the IEEE (1985), 132, n ~ 6, pp. 466-479.

[WHM] WARD (C.R.), HAZON (S.C.), MASSEY (D.R.), URQUHART (A.J.), WOODWARD (D.G.). Practical realizations of parallel adaptive beamforming systems, in [MMS], pp. 3-12.

[Yeh] YEH (H.G.). YEH, Kalman filtering and systolic processors, in Proc. lEEE Int. Conf. ICASSP 86, Tokyo (1986), pp. 2139-2142.

BIOGRAPHIE

Yves ROBERT est Professeur d'informatique ~ l'6cole normale sup~Srieure de Lyon. I1 dirige l'6quipe TIPAS : Traitement d'images en parall~le et architectures sp6cialis6es du Laboratoire LIP-IMAG, URA CNRS n ~ 1398. Ses th~mes de recherches concement les architectures systoliques et les algorithmes parall~les pour le traitement d'images sur machine i~ m6moire distribu6e.

ANN. ~I~COMMUN., 46, n ~ 1-2, 1991 9/9

Documents

Architectures systoliques pour le traitement du signal : bilan et perspectives