Sistolni niz
U paralelnoj računarskoj arhitekturi, sistolni niz je homogena mreža čvrsta u sprezi obrade podataka jedinica (DPU) zvane ćelije ili čvorovi. Svaki čvor ili DPU nezavisno izračunava delimičan rezultat u funkciji podataka dobijenih od svojih suseda uzvodno, čuva rezultate u sebi i prosleđuje ih nizvodno. Sistoličke nizove su izmislili Rihard P. Brent i H. T. Kung koji su ih razvili da izračunaju najveće zajedničke delioce celih brojeva i polinoma.[1] Oni su ponekad klasifikovani kao višestruke instrukcije jednog podatka ( MISD ) arhitekture pod flinovom podelom, ali ova klasifikacija je pod znakom pitanja, jer jak argument može biti da se razlikuju sistolni nizove od bilo kojeg od Flinove četiri kategorije : SISD , SIMD , MISD , MIMD, kao što je objašnjeno kasnije u ovom članku .
Paralelni unos podataka protiče kroz mrežu kablom čvorova procesora, podseća na ljudski mozak koji kombinuju , proces, spajanje ili sortiranje ulaznih podataka u izvedenim rezultatima. Zato što prostiranje talasa nalik podacima kroz sistolni niz podseća na puls sistema krvotoka ljudi, ime sistolni je skovano iz medicinske terminologije. Ime je izvedeno iz sistole ( medicina) kao analogija sa redovnim pumpanjem krvi putem srca.
Aplikacije[uredi | uredi izvor]
Sistolički nizovi su često teško-priključeni za konkretne operacije , kao što su " umnožavanje i akumuliranje" , da izvrše masovnu paralelnu integraciju, konvolucija, korelaciju, množenje matrica ili sortiranja zadataka podataka.
Arhitektura[uredi | uredi izvor]
Sistolni niz obično se sastoji od velike monolitne mreže primitivnih računarskih čvorova koji mogu biti fiksirana ili konfigurisanog softvera za određenu aplikaciju. Čvorovi su obično fiksni i identični , dok se veza može programirati . Opštiji talasni front procesori , s druge strane, koriste sofisticirane i pojedinačno programirane čvorove koji mogu ili ne mogu biti monolitni , u zavisnosti od veličine niza parametara i dizajna. Druga razlika je da se sistolni nizovi oslanjaju na sinhroni prenos podataka, dok talasni front imaju tendenciju da rade asinhrono.
Za razliku od više zajedničke fon Nojmanove arhitekture , gde izvršenje programa sledi scenario instrukcija koji se čuvaju u zajedničkoj memoriji, adresirano i sekvencirano pod kontrolom centralne procesorske jedinice programskog brojača ( PS ) , pojedinačni čvorovi unutar sistolnog niza se aktiviraju dolaskom novih podataka i uvek obrađuju podatke na potpuno isti način. Stvarna obrada u svakom čvoru može biti teško snadbevena žicom ili blokirani mikroprogram, u tom slučaju zajednički čvor ličnosti može biti blok programiranja.
Sistolni niz paradigma sa tokovima podataka vođenim brojačem podataka, je pandan fon Nojmanove arhitekture sa uputstvom toka kojim je upravljao programski borjač. Jer sistoličko polje obično šalje i prima višestruke tokove podataka , i više brojača podataka je potrebno za proizvodnju ovih tokova podataka , koji podržavaju paralelizam podataka.
Stvarni čvorovi mogu biti jednostavni i fiksirani ili se sastojati od više sofisticiranih jedinica koristeći mikro kod, što može biti blok programiranja.
Ciljevi i prednosti[uredi | uredi izvor]
Najveća korist od sistolnih nizova je da su svi podaci operand i delimični rezultati čuvaju u ( prolaze kroz ) nizu procesora . Nema potrebe da pristupite spoljnim autobusima , glavna memorija ili unutrašnji keš tokom svake operacije kao što je to slučaj sa fon Nojmanom ili harvardskim uzastopnim mašinama . Konsekutivna ograničenja u paralelnom performansu diktira Amdalov zakon i ne primenjuju na isti način , jer podaci zavise od implicitnog upravljanja programabilnih povezanih čvorova i ne postoje uzastopni koraci u upravljanju visokog paralelnog protoka podataka .
Sistolički nizovi su stoga izuzetno dobri u veštačkoj inteligenciji, obradi slika, prepoznavanju oblika, kompjuterskoj viziji i drugim poslovima koje životinjski mozgovi rade tako posebno dobro. Bejfront procesori generalno mogu biti veoma dobri u mašinskom učenju primenom neuronske mreže konfigurisane u hardveru.
Klasifikacija kontroverze[uredi | uredi izvor]
Dok sistolni nizovi su zvanično klasifikovani kao MISD , njihova klasifikacija je donekle problematična. Pošto je ulaz obično vektor nezavisnih vrednosti , sistolni niz definitivno nije SISD. Od ove ulazne vrednosti su spojeni i kombinuju rezultat (e) i ne održavaju svoju nezavisnost kao što bi u SIMD vektorskim procesorskim jedinicama, niz ne može klasifikovati kao takav. Shodno tome, niz se ne može klasifikovati kao MIMD , jer MIMD se može posmatrati kao prikupljanje manjih SISD i SIMD mašina .
Na kraju , jer se roj podataka koji je transformisan dok prolazi kroz niz od čvora do čvora, višestruki čvorovi nisu u funkciji na istim podacima, što čini MISD klasifikaciju pogrešnom. Drugi razlog zašto sistolički niz ne treba kvalifikovati kao MISD je isti kao i onaj koji ga diskvalifikuje iz kategorije SISD : Ulazni podatak je obično vektor nijedna pojedinačna vrednost podataka, iako bi se moglo tvrditi da bilo koji dati ulazni vektor je jedan skup podataka.
Sve gore navedeno ne odoleva, sistolni nizovi često nude kao klasičan primer MISD arhitekturu u udžbenicima paralelnih obrada u inženjerskoj klasi. Ako se niz spolja posmatra kao atomski možda bi trebalo klasifikovati kao SFMuDMeR = jednu funkciju , višestrukih podataka , spojenih rezultata.
Detaljan opis[uredi | uredi izvor]
Sistolno polje se sastoji od matrice poput redova obrade jedinica podataka zvanih ćelije. Obrade podataka jedinice ( DPU ) su slične centralnim jedinicama za obradu ( CPU) , ( osim uobičajenog nedostatka IP procesora [2], od kada je operacija prevoza aktivirana, odnosno od dolaska objekta podataka ) . Svaka ćelija deli informacije sa svojim susedima odmah nakon obrade . Sistolno polje je često pravougaonog oblika , gde protok podataka preko niza između komšija DPU, često sa različitim podacima teče u različitim pravcima. Potoci podataka ulaze i izlaze iz nizova portova koji su generisani od strane auto sekvencioniranih memorijskih jedinica, ASMS. Svaki ASM sadrži brojač podataka. U ugrađenim sistemima podaci struja mogu takođe biti ulaz iz i/ili izlaz na spoljni izvor .
Primer sistolnog algoritma može biti dizajniran za matricu multiplikacije. Jedna matrica se dovodi u niz u vremenu od vrha niza i spušta se dole niz niz , druga matrica se dovodi u kolonu u vremenu sa leve strane niza i prolazi sleva nadesno. Lažne vrednosti su zatim prošle sve dok svaki procesor nije video jedan ceo red i jednu celu kolonu. U ovom trenutku , rezultat množenja se čuva u nizu i sada mogu da se emituju red ili kolona istovremeno, tečeći dole ili preko niza.[3]
Sistolički nizovi su nizovi DPU koji su povezani sa malim brojem najbližih suseda DPU u mrežama poput topologije . DPUs obavlja niz operacija na podacima koji teču između njih. Zato što su tradicionalne metode sinteze sistoličkog niza praktikovane algebarskim algoritmima, samo jedinstveni nizovi sa samo linearnim cevima se mogu dobiti , tako da su arhitekture iste u svim DPU. Posledica je , da samo aplikacije sa redovnim zavisnostima podataka se sprovodi na klasičnim sistolnim nizovima . Kao SIMD mašina , koja radi sistolne nizove izračunavanjem u " zaključanom-koraku" sa svakim procesorom preduzima alternativno računarstvo | komunicirane faze . Ali sistolni nizovi sa asinhronim rukovanja između DPU se zove talasni front nizovi. Jedan poznati sistolički niz je iVarp procesor, koji je proizvedena od strane kompanije Intel . IVarp sistem ima procesor sa linearnim nizom povezan sa podacima autobusa koji idu u oba smera.
Istorija[uredi | uredi izvor]
Sistolička polja ( <wavefront procesori ) , prvi put su ih opisali H. T. Kung i Čarls E. Leiserson , koji je objavio prvi papir koji opisuje sistolna polja 1978. Međutim , prva mašina poznata da je koristila sličnu tehniku je bila Kolos Mark II 1944. godine .
Primer primene[uredi | uredi izvor]
Primer aplikacije-evaluacija polinoma
Hornerovo pravilo za ocenjivanje polinoma je :
Linearno sistoličko polje u kojem su procesori raspoređeni u parovima : jedan umnožava svoj ulaz sa h i donosi rezultat nadesno , sledeći dodaje a_j i donosi rezultat nadesno :
Prednosti i mane[uredi | uredi izvor]
Prednosti
- Brže
- Skalabilnije
Protiv
- Skupo
- Visokospecijalizovan, običaj hardver je potrebna često specifična aplikacija.
- Nije široko implementiran
- Ograničen broj baza programa i algoritama
Implementacija[uredi | uredi izvor]
Cisko phf procesor mreže je interno organizovan kao sistolni niz.[4]
Vidi još[uredi | uredi izvor]
- MISD -Višestruko Uputstvo Slobodnog podatka , na primer: Sistolička polja
- iVarp -Sistoličko polje računara , VLSI , Intel/CMU
- VARP(sistolički polje)- Sistoličko polje računara GE/CMU
Napomene[uredi | uredi izvor]
- 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
Reference[uredi | uredi izvor]
- ^ http://www.eecs.harvard.edu/~htk/publication/1984-ieeetoc-brent-kung.pdf
- ^ The Paracel GeneMatcher series of systolic array processors do have a program counter.
- ^ Systolic Array Matrix Multiplication
- ^ Cisco 10000 Series Routers - Products & Services - Cisco