miniatura|Matriu sistòlica (figura dibuixada per mi mateix Rainier3 13:34, 14 de març de 2007 (UTC)) En les arquitectures d'ordinadors paral·lels, una matriu sistòlica és una xarxa homogènia d'unitats de processament de dades (DPU) estretament acoblades anomenades cel·les o nodes. Cada node o DPU calcula independentment un resultat parcial com a funció de les dades rebudes dels seus veïns aigües amunt, emmagatzema el resultat dins seu i el passa aigües avall. Els principis del flux de dades de tipus sistòlic es van veure per primera vegada a Colossus, que va ser un dels primers ordinadors utilitzats per desxifrar els xifrats de Lorenz alemanys durant la Segona Guerra Mundial. A causa de la naturalesa classificada de Colossus, van ser inventats independentment per HT Kung i Charles Leiserson, que van descriure matrius per a molts càlculs densos d'àlgebra lineal (producte matricial, resolució de sistemes d'equacions lineals, descomposició LU, etc.) per a matrius bandejades. Les primeres aplicacions inclouen el càlcul del màxim comú divisor d'enters i polinomis. Avui dia, es poden trobar en NPU i acceleradors de maquinari basats en dissenys espacials. De vegades es classifiquen com a arquitectures de dades individuals de múltiples instruccions (MISD) segons la taxonomia de Flynn, però aquesta classificació és qüestionable perquè es pot fer un argument sòlid per distingir les matrius sistòliques de qualsevol de les quatre categories de Flynn: SISD, SIMD, MISD, MIMD, com es discuteix més endavant en aquest article.
Les dades d'entrada paral·leles flueixen a través d'una xarxa de nodes de processador connectats directament, que combinen, processen, fusionen o classifiquen les dades d'entrada en un resultat derivat. Com que la propagació ondulatòria de les dades a través d'una matriu sistòlica s'assembla al pols del sistema circulatori humà, el nom sistòlic es va encunyar a partir de la terminologia mèdica. El nom deriva de la sístole com a analogia al bombament regular de sang pel cor.
Aplicacions Les matrius sistòliques sovint estan cablejades per a operacions específiques, com ara multiplicar i acumular, per fer tasques d'integració massivament paral·lela, convolució, correlació, multiplicació de matrius o classificació de dades. També s'utilitzen per a algorismes de programació dinàmica, utilitzats en l'anàlisi de seqüències d'ADN i proteïnes.
Arquitectura Una matriu sistòlica consisteix normalment en una gran xarxa monolítica de nodes de computació primitius que es poden connectar directament o configurar per programari per a una aplicació específica. Els nodes solen ser fixos i idèntics, mentre que la interconnexió és programable. Els processadors de front d'ona més generals, en canvi, utilitzen nodes sofisticats i programables individualment que poden ser o no monolítics, depenent de la mida de la matriu i els paràmetres de disseny. L'altra distinció és que les matrius sistòliques es basen en transferències de dades síncrones, mentre que els de front d'ona tendeixen a funcionar asíncronament.
A diferència de l'arquitectura més comuna de Von Neumann, on l'execució del programa segueix un guió d'instruccions emmagatzemades a la memòria comuna, adreçades i seqüenciades sota el control del comptador de programa (PC) de la CPU, els nodes individuals dins d'una matriu sistòlica s'activen amb l'arribada de noves dades i sempre processen les dades exactament de la mateixa manera. El processament real dins de cada node pot ser connectat per cable o microcodificat per blocs, en aquest cas la personalitat del node comú pot ser programable per blocs.
El paradigma de matriu sistòlica amb fluxos de dades controlats per comptadors de dades és la contrapart de l'arquitectura de Von Neumann amb un flux d'instruccions controlat per un comptador de programa. Com que una matriu sistòlica normalment envia i rep múltiples fluxos de dades, i es necessiten múltiples comptadors de dades per generar aquests fluxos de dades, admet el paral·lelisme de dades.
Objectius i beneficis Un avantatge important de les matrius sistòliques és que totes les dades dels operands i els resultats parcials s'emmagatzemen dins de la matriu del processador (passant per ella). No cal accedir a busos externs, memòria principal o memòries cau internes durant cada operació, com és el cas de les màquines seqüencials de Von Neumann o Harvard. Els límits seqüencials del rendiment paral·lel dictats per la llei d'Amdahl tampoc s'apliquen de la mateixa manera, perquè les dependències de dades es gestionen implícitament mitjançant la interconnexió del node programable i no hi ha passos seqüencials en la gestió del flux de dades altament paral·lel.
Per tant, les matrius sistòliques són extremadament bones en intel·ligència artificial, processament d'imatges, reconeixement de patrons, visió per computador i altres tasques que els cervells animals fan particularment bé. Els processadors de front d'ona en general també poden ser molt bons en l'aprenentatge automàtic implementant xarxes neuronals autoconfigurables en maquinari.
Controvèrsia de classificació Tot i que les matrius sistòliques es classifiquen oficialment com a MISD, la seva classificació és una mica problemàtica. Com que l'entrada és normalment un vector de valors independents, la matriu sistòlica definitivament no és SISD. Com que aquests valors d'entrada es fusionen i es combinen en el(s) resultat(s) i no mantenen la seva independència com ho farien en una unitat de processament vectorial SIMD, la matriu no es pot classificar com a tal. En conseqüència, la matriu tampoc es pot classificar com a MIMD, perquè MIMD es pot veure com una simple col·lecció de màquines SISD i SIMD més petites.
Finalment, com que l'eixam de dades es transforma a mesura que passa per la matriu de node a node, els múltiples nodes no operen amb les mateixes dades, cosa que fa que la classificació MISD sigui un nom inadequat. L'altra raó per la qual una matriu sistòlica no hauria de qualificar-se com a MISD és la mateixa que la que la desqualifica de la categoria SISD: les dades d'entrada solen ser un vector, no un únic valor de dades, tot i que es podria argumentar que qualsevol vector d'entrada determinat és un únic element de dades.
Malgrat tot l'anterior, les matrius sistòliques sovint s'ofereixen com a exemple clàssic d'arquitectura MISD en llibres de text sobre computació paral·lela i en classes d'enginyeria. Si la matriu es veu des de fora com atòmica, potser s'hauria de classificar com a SFMuDMeR = funció única, dades múltiples, resultat(s) fusionat(s).
Les matrius sistòliques utilitzen un gràfic de flux computacional predefinit que connecta els seus nodes. Les xarxes de processos de Kahn utilitzen un gràfic de flux similar, però es distingeixen perquè els nodes treballen en cadena a la matriu sistòlica: en una xarxa de Kahn, hi ha cues FIFO entre cada node.
Descripció detallada Una matriu sistòlica està composta per files matricials d'unitats de processament de dades anomenades cel·les. Les unitats de processament de dades (DPU) són similars a les unitats centrals de processament (CPU) (excepte per la manca habitual d'un comptador de programa, ja que l'operació es desencadena pel transport, és a dir, per l'arribada d'un objecte de dades). Cada cel·la comparteix la informació amb els seus veïns immediatament després del processament. La matriu sistòlica sovint és rectangular on les dades flueixen a través de la matriu entre les DPU veïnes, sovint amb dades diferents que flueixen en diferents direccions. Els fluxos de dades que entren i surten dels ports de la matriu es generen mitjançant unitats de memòria d'autoseqüenciació, ASM. Cada ASM inclou un comptador de dades. En els sistemes integrats, un flux de dades també es pot introduir i/o sortir a una font externa.
Un exemple d'algorisme sistòlic es podria dissenyar per a la multiplicació de matrius. Una matriu s'introdueix fila rere fila des de la part superior de la matriu i es passa cap avall, l'altra matriu s'introdueix columna rere columna des del costat esquerre de la matriu i passa d'esquerra a dreta. A continuació, es passen valors fictius fins que cada processador ha vist una fila sencera i una columna sencera. En aquest punt, el resultat de la multiplicació s'emmagatzema a la matriu i ara es pot generar fila o columna rere fila, fluint cap avall o a través de la matriu.
Les matrius sistòliques són matrius de DPU connectades a un petit nombre de DPU veïnes més properes en una topologia de tipus malla. Les DPU realitzen una seqüència d'operacions sobre les dades que flueixen entre elles. Com que els mètodes tradicionals de síntesi de matrius sistòliques s'han practicat mitjançant algorismes algebraics, només es poden obtenir matrius uniformes amb només canonades lineals, de manera que les arquitectures són les mateixes en totes les DPU. La conseqüència és que només es poden implementar aplicacions amb dependències de dades regulars en matrius sistòliques clàssiques. Com les màquines SIMD, les matrius sistòliques amb sincronització computan en "pas de bloqueig" amb cada processador realitzant fases de càlcul i comunicació alternatives. Però les matrius sistòliques amb handshake asíncron entre DPU s'anomenen matrius de front d'ona . Una matriu sistòlica ben coneguda és el processador iWarp de la Universitat Carnegie Mellon, que ha estat fabricat per Intel. Un sistema iWarp té un processador de matriu lineal connectat per busos de dades que van en ambdues direccions.
Història Les matrius sistòliques (també conegudes com a processadors de front d'ona) van ser descrites per primera vegada per HT Kung i Charles E. Leiserson, que van publicar el primer article que descrivia les matrius sistòliques el 1979. Tanmateix, la primera màquina que es coneix que va utilitzar una tècnica similar va ser la Colossus Mark II el 1944. Colossus utilitzava registres de desplaçament paral·lels per impulsar dades, cosa que és funcionalment similar a una matriu sistòlica, però li faltaven els "elements de processament" (PE) interconnectats que defineixen l'arquitectura Kung-Leiserson de 1978.
La primera màquina dissenyada explícitament com a matriu sistòlica va ser l'ordinador WARP el 1984.
Exemples Avaluació polinòmica La regla de Horner per avaluar un polinomi és:
Una matriu sistòlica lineal en què els processadors estan disposats en parelles: un multiplica la seva entrada per i passa el resultat a la dreta, el següent suma i passa el resultat a la dreta.
Convolució Considereu una cadena d'elements de processament (PE), cadascun dels quals realitza una operació de multiplicació-acumulació. Processa dades d'entrada () i pesos () sistòlicament, és a dir, que les dades flueixen a través de la matriu de manera regular i rítmica. Els pesos romanen estacionaris dins de cada PE, mentre que les dades d'entrada i les sumes parcials ( ) es mouen en direccions oposades.
Cada PE realitza la següent operació: on:
són les dades d'entrada. és la suma parcial entrant. és el pes emmagatzemat al PE. són les dades de sortida (passades al següent PE). és la suma parcial actualitzada.
Des de l'esquerra, el flux d'entrada és , i des de la dreta, el flux de sortida és Si introdueixi el PE més a la dreta simultàniament i, a continuació, les sortides del PE més a l'esquerra Aquesta és la convolució unidimensional. De la mateixa manera, la convolució n-dimensional es pot calcular mitjançant una matriu n-dimensional d'elements de pes (PEs).
Hi ha moltes altres implementacions de les convolucions 1D disponibles, amb fluxos de dades diferents.
Vegeu la Figura 12 per a un algorisme que realitza mínims quadrats sobre la marxa utilitzant matrius sistòliques unidimensionals i bidimensionals.
Ordenació