CAP5_P3

7/21/2019 CAP5_P3

1/16

ARHITECTURA SISTEMELOR DE CALCUL

199

-nu se iniiaz un nou task, evoluia fiind identic cu cea din cazul c0=1-

se iniiaz un nou task. n acest caz se calculeaz un nou vector de coliziune(stare) printr-o funcie SAU ntre vectorul de coliziune iniial i vectorul de

coliziune deplasat cu o poziie. Vectorul de coliziune rezultat prin aceast funcieSAUncorporeaz n vectorul deplasat efectul noii iniieri (aportul noii iniieri lapotenialul de coliziune existent).

Figura 3.46. ilustreaz algoritmul de calcul al vectorului de coliziune atunci cndse iniiaz sau nu se iniiaz un nou task. Sunt posibile diverse strategii de iniiere a noilortask-uri. Una dintre acestea, numit strategia "greedy", presupune iniierea unui nou taskoride cte ori vectorul de coliziune permite. Din nefericire, strategia greedy nu reprezint ntoate cazurile strategia optim, dei este ntotdeauna aproape de optim, i uor deimplementat.

Fig. 5.46. Algoritmul de construcie a organigramei strilor

7/21/2019 CAP5_P3

2/16

Proiectarea procesoarelor pipeline

200

Diagrama strilor pentru vectorul de coliziune (10011) aferent tabelei de rezervaredin figura 5.45 b) este prezentat n figura 5.47.

Fig. 5.47. Organigrama strilor pentru vectorul de coliziune 10011(DA/NU refer blocul "se iniiaz un nou task" din figura 5.46)

n organigrama din figura 5.47. sunt incluse toate strile posibile (fie c se iniiaz,fie c nu se iniiaz un nou task). Aceast organigram devine n anumite cazuri foartecomplicat.

Organigrama poate fi simplificat dac se reprezint doar schimbrile de staregenerate de iniierile unor noi task-uri. Pentru a crea o astfel de organigram se pornete totde la starea iniial care este dat ntotdeauna de vectorul de coliziune iniial. Dac existun zero n poziia cia vectorului (vezi 5.7.1. B.), atunci iniierea unui nou taskeste permisdup i uniti de timp (perioade de tact). Figura 5.48. reprezint forma simplificat a

organigramei strilor din figura 5.47.Vectorul de coliziune iniial (10011) reprezint starea iniial. Starea iniial arezerouri pe poziiile 2 i 3. Prin urmare, un nou task poate fi iniiat dup dou sau treiperioade de tact. Pentru fiecare iniiere permis, vectorul de stare este deplasat la dreapta cuipoziii (n partea stng se introduc zerouri). Aceast deplasare echivaleaz cu trecerea a iuniti de timp (perioade de tact). Noua stare (vector de coliziune) se obine aplicnd ofuncie SAU ntre vectorul rezultat n urma deplasrii i vectorul de coliziune iniial.Funcia SAUeste necesar pentru c iniierea noului taskadaug noi constrngeri la stareacurent apipeline-ului. Ori de cte ori se obine un nou vector de coliziune (stare) dintr-unvector de stare curent, se va trasa un arc ntre cei doi vectori n organigram. Arcul va fietichetat cu latena i. Procesul de generare a noilor vectori de coliziune continu pn cndnu mai pot fi generai vectori noi.

7/21/2019 CAP5_P3

3/16


201

Fig. 5.48. Organigrama strilor (simplificat) pentru structurapipelinedin fig. 5.45

n organigrama strilor, toate arcele etichetate cu latene N+1vor realiza automato revenire la vectorul de coliziune iniial. Aceasta se datoreaz faptului c prin deplasarea ladreapta cuN+1poziii a vectorului de coliziune curent se va obine un vector cu toi biii pe

zero. O funcie SAUntre acest vector de zerouri i vectorul de coliziune iniial va avea carezultat chiar vectorul de coliziune iniial.

D. Latena medie

Latena medie se determin pentru un anumit ciclu din organigrama strilor. Unciclu n organigram este reprezentat de o secven alternant de vectori de coliziune iarce, C0, a1, C1, ..., an, Cn, n care fiecare arc aiconecteaz doi vectori de coliziune distinci(Ci-1i Ci), cu excepia primului i ultimului vector care sunt identici. Pentru simplificare,vom reprezenta ciclurile prin secvena de latene aferente arcelor ciclului. De exemplu, nfigura 5.48., ciclul C0, a1, C1, a2, C0, unde C0=(10011), C1=(10111), a1este arcul de la C0laC1 i a2 este arcul de la C1 la C0, este reprezentat sub forma C=(2,3), unde 2 i 3 suntlatenele arcelor a1i, respectiv, a2.

Latena medie a unui ciclu se determin nsumnd latenele (numrul de poziiideplasate la dreapta) aferente arcelor ce compun ciclul respectiv i mprind suma obinutla numrul de arce din cadrul ciclului. De exemplu, ciclul C=(2,3), din figura 5.48., va avealatena medie:

(2 + 3)/2 = 2,5

E. Latena medie minim

O structurpipelinepoate avea mai multe latene medii asociate diferitelor cicluridin organigrama strilor. Latena medie minim va fi dat de cea mai mic laten medie

7/21/2019 CAP5_P3

4/16


202

cuprins n lista latenelor medii asociat structurii respective. De exemplu, n organigramadin figura 5.48. se pot identifica 4 cicluri cu urmtoarele latene medii:

(2+3)/2 = 2,5 ; pentru ciclul C0, a1, C1, a2, C0

(2+5)/2 = 3,5 ; pentru ciclul C0, a1, C1, a2, C03/1=3 ; pentru ciclul C0, a3, C05/1=5 ; pentru ciclul C0, a3, C0

Prin urmare, latena medie minim (LMM) este 2,5. Dei ciclul cu latena medie minimmaximizeaz performanele structurii pipeline, uneori se opteaz pentru un ciclu mai puineficient n ideea reducerii complexitii blocului de control aferent structurii respective(compromis ntre performane i cost). De exemplu, ciclul C=(2,3) care are LMM=2,5,necesit un circuit de control care contorizeaz 3 perioade de tact, apoi 2, din nou 3 .a.m.d.Dac acceptm iniierea unui nou task la fiecare 3 perioade de tact (un ciclu C=(3))complexitatea circuitului de control va fi redus. n consecin, exist situaii n care estenecesar determinarea celei mai mici latene care poate fi utilizat pe un ciclu care iniiaztask-urile cu o periodicitate constant. Aceast laten se numete laten minim i poate fideterminat alegnd n organigrama strilor un ciclu de lungime 1 (un singur arc) i care

prezint cea mai mic laten. O alt metod de determinare a latenei minime const naflarea celui mai mic ntreg care nmulit cu un ntreg arbitrar genereaz un rezultatnemembru al listei latenelor interzise. Pentru structura din figura 5.45. care are listalatenelor interzise (4, 1, 0), latena minim poate fi determinat astfel:

Latena minim Multiplicare cu ntregul Valoare Produs RezultatParial Global

1 1 1 NU NU2 1 2 OK2 2 4 NU NU3 1 3 OK3 2 6 OK OK!4 1 4 NU NU

Latena minim pentru aceast structurpipelineeste deci 3.

5.7.2. Controlul structurilor dinamice

Structurile statice opereaz pentru o singur funcie. n acest caz trebuie evitatedoar coliziunile ntre datele succesive aplicate pe intrarea structurii, date care aparinaceleiai funcii. Structurilepipelinedinamice pot procesa mai multe funcii n acelai timp(n timp ce modulele finale proceseaz un set de date pentru o funcie, modulele iniialeproceseaz alt set de date pentru alt funcie). Drept consecin, trebuie luate n considerare

7/21/2019 CAP5_P3

5/16


203

i coliziunile dintre dou seturi succesive de date care aparin unor funcii diferite. Ca i ncazul structurilor statice proiectarea blocului de control aferent structurii dinamice ncepecu determinarea listelor strilor interzise (o list pentru fiecare funcie) i continu cudeterminarea vectorilor de coliziune i n final cu trasarea organigramei strilor.

A. Listele strilor interzise

n cazul structurilor dinamice, numrul de liste de stri interzise va fi egal cuptratul numrului de funcii care partajeaz structura pipeline respectiv. Structura dinfigura 5.49. proceseaz dou funcii, A i B, i va avea un numr de 4 liste de stri interzisepe care le vom nota AA, AB, BA i BB.

Fig. 5.49. Structurpipelinedinamic partajat de dou funcii

cu tabelele de rezervare b), c).

Listele AA, AB, BA i BB corespund celor 4 combinaii posibile n care se pot aflacele 2 funcii iniiate la intrarea structurii:

AA - funcia A urmat de o alt funcie AAB - funcia A urmat de o funcie BBA - funcia B urmat de o funcie ABB - funcia B urmat de o alt funcie B

t0 t1 t2 t3 t4Modul 1 A AModul 2 A AModul 3 A

b)

t0 t1 t2 t3 t4Modul 1 B BModul 2 BModul 3 B B

c)

a)

7/21/2019 CAP5_P3

6/16


204

De exemplu, dac lista AB conine numrul k, atunci un set de date aferent funciei B nupoate fi aplicat la intrarea structurii pipelinen momentul t + k, dac treprezint momentulanterior n care un alt set de date asociat funciei A a fost aplicat pe intrarea aceleiaistructuri. Listele AA i BB se obin ca n cazul structurilor statice. Listele AB i BA se

obin simplu prin combinarea celor dou tabele de rezervare din figura 5.49. Tabelacombinat se prezint n figura 5.50. Se obin urmtoarele liste de stri interzise:

AA = (3,0) , AB = (2,1,0) , BA = (4,2,1,0) , BB = (3,2,0)

Fig. 5.50. Tabel combinat pentru funciile A i B

B. Vectori de coliziune i matrici de coliziune

Vectorii de coliziune sunt determinai aplicnd procedeul prezentat pentrustructurile statice. Un bit de 0 n vector reprezint o laten permis iar un bit de 1

reprezint o laten interzis. Pe baza celor 4 liste de stri interzise se obin cei 4 vectori decoliziune:

CAA= (01001) CBA= (10111)CAB= (00111) CBB= (01101)

Vectorii de coliziune afereni funciei A formeaz matricea de coliziuneMA:

=

=

00111

01001

AB

AAA

C

CM

7/21/2019 CAP5_P3

7/16


205

Vectorii de coliziune afereni funciei B formeaz matricea de coliziuneMB:

=

=

01101

10111

BB

BAB

C

CM

C. Organigrama strilor

Dei se obine ntr-o manier similar cu cea prezentat n cazul structurilorstatice, organigrama strilor pentru structurile dinamice este mult mai complicat datoritnumrului mare de coliziuni posibile. Pentru exemplificare, considerm organigramaaferent structuriipipelinedin figura 5.49. pe care o redm n figura 5.51.

Fig. 5.51. Organigrama strilor aferent unei structuripipelinedinamice

Considerm ca punct de start matricea MA. Exist dou tipuri de coliziuni:

-o funcie A intr n coliziune cu o alt funcie A anterioar (vectorul CAA)-o funcie B intr n coliziune cu o funcie A anterioar (vectorul CAB)

7/21/2019 CAP5_P3

8/16


206

Dac alegem prima laten permis din vectorul CAA(latena 1), ntreaga matriceMA(ambiivectori) se deplaseaz la dreapta cu o poziie (din partea stng intr cifre zero). O funcieSAU se aplic apoi ntre matricea rezultat n urma deplasrii i matricea de coliziuneiniial MA, rezultnd astfel noua matrice de coliziune. Aceast nou matrice nglobeaz

efectul celor 2 funcii A lansate succesiv la intervalul de un ciclu. n mod analog seproceseaz i celelalte latene permise din vectorul CAA (latenele 2 i 4, 5, 6,....); diferdoar numrul de poziii cu care se deplaseaz la dreapta matricea MA.

Dac se alege prima laten permis din vectorul CAB(latena 3), ntreaga matriceeste deplasat la dreapta cu 3 poziii (din partea stng vor intra cifre zero). O funcie SAUse va aplica ntre matricea rezultat n urma deplasrii i matricea de coliziune MB.Matricea rezultat va ngloba efectul celor 2 funcii, A i B, lansate succesiv la intervalul de3 ciclii. Operaiile de deplasare i compunere prin funcie SAU vor continua lund nconsiderare toate latenele permise obinndu-se, n final, organigrama complet.

5.7.3. Reducerea latenei medii minime (LMM) prin inserarea unor ntrzieri

Uneori este posibil modificarea tabelei de rezervare aferent unei structuri

pipelineastfel nct structura n ansamblu rmne nemodificat, dar performanele ei cresc(LMMse reduce). Tabela poate fi modificat prin inserarea unor ntrzieri (module simple"delay"). Orice structurpipelinesincron este format dintr-un numr de module (uniti)de procesare separate prin registre intermodulare. Inserarea unei ntrzieri n tabela derezervare se poate obine prin introducerea unui registru suplimentar n cascada pipeline.Figura 5.52. evideniaz modificarea unei tabele de rezervare prin introducerea n structurapipelinea unui registru de ntrziere Rd.

a)

b)

Fig. 5.52. Modificarea structuriipipelinei a tabelei de rezervare aferenteprin inserarea unei ntrzieri

a) nainte de inserare b) dup inserare

7/21/2019 CAP5_P3

9/16


207

n general, o structur pipeline conine un numr de module i fiecrui modul icorespunde un rnd n tabela de rezervare. Pe fiecare rnd putem contoriza un numr desemne * i, n general, acest numr difer de la un rnd la altul. Fie nmaxnumrul de semne* de pe rndul cel mai populat cu semne *. Latena medie minim este ntotdeauna mai

mare sau egal cu nmax:LMM nmax

nmax reprezint limita minim pe care o poate atinge latena i aceast afirmaiepoate fi demonstrat astfel: lund n considerare o singur iniiere (lansarea unui singur taskn structura pipeline), nmaxreprezint numrul de cicluri (perioade de tact) n care cel maiutilizat modul din structur este ocupat. Fie tnumrul de coloane pe care le conine tabelade rezervare; tva reprezenta, de asemenea, numrul de cicluri (perioade de tact) necesareprocesrii unui taskn structur.Numrul maxim de iniieri va fi limitat superior de cel mai utilizat modul, care va putea fiutilizat numai de o iniiere (un task) pe fiecare perioad de tact. Deci:

Numrul maxim de iniieri = t/nmax

Latena minim = t/(numrul maxim de iniieri) = nmax

n concluzie:nmaxLMM (latena medie a ciclului greedy)

(numrul de bii 1 din vectorul de coliziune iniial)

n anumite cazuri, prin introducerea unor ntrzieri n cascada pipeline, LMMpoate fi redus pn la limita nmax.

Presupunnd c toate suboperaiile (semnele *) din tabela de rezervare suntdependente de suboperaiile anterioare, prezentm urmtorul algoritm care indic locul ncare vor fi plasate ntrzierile pentru a reduceLMMla valoarea n=nmax:

1. Pornind de la tabela de rezervare iniial vom considera tabela revizuit.Copiem primul semn * din tabela iniial pe aceiai poziie n tabela revizuit.Pornind de la acest prim semn * spre dreapta (pe rndul respectiv) marcm

fiecare a n- a csu cuI(interzis). Marcarea cuIindic rezervarea csuelorrespective pentru urmtoarele iniieri; urmtoarele task-uri vor fi iniiateperiodic la intervale de nperioade de tact (ncicluripipe).

2.

Se repet operaia 1, succesiv, pentru toate semnele * din tabela iniial pncnd un semn * "cade" ntr-o csu notat cu I. Semnul * respectiv va fintrziat (mutat spre dreapta) una sau mai multe poziii, poziionndu-se nprima csu liber gsit. Se marcheaz toate poziiile (csuele) ntrziate cuD (delay). Aceeai ntrziere (deplasare) se aplic tuturor semnelor *urmtoare. Aplicarea acestei ntrzieri tuturor semnelor * care urmeaz ntabela iniial este impus de ipoteza de la care am pornit: toate suboperaiiledin tabela de rezervare sunt dependente de suboperaiile anterioare.

7/21/2019 CAP5_P3

10/16


208

ToateD-urile din tabela revizuit indic unde trebuie plasate registre de ntrziere(Rd) n structurapipeline.

S reconsiderm structura pipeline static din figura 5.45. a crei organigram

simplificat (fig. 5.48) o redm n figura 5.53.

Fig. 5.53. Organigrama strilor i tabela de rezervare aferenteunei structuripipelinestatice (LMM = 2,5)

LMMeste 2,5 i corespunde ciclului C0a1C1a2C0. Tabela de rezervare din figura5.53. are parametrul nmax=2. n consecin, vom ncerca mbuntirea performaneloracestei structuri prin inserarea unor ntrzieri. Performane maxime vom obine pentruLMM=nmax=2. Vom aplica algoritmul anterior pentru latena 2. Tabela de rezervarerevizuit i organigrama aferent sunt prezentate n figura 5.54. Tabela revizuit arat c osingur ntrziere este necesar i aceasta trebuie plasat ntre modulele 3 i 1.

Fig. 5.54. Tabela revizuit i organigrama strilor aferent (LMM = 2)

Modul 1 * *Modul 2 * *Modul 3 *

Modul 1 * D *Modul 2 * *Modul 3 *

Lista latenelor interzise: F=(5,1,0)

Lista latenelor interzise: F=(4,1,0)

7/21/2019 CAP5_P3

11/16


209

LMM corespunztoare tabelei revizuite este 2 i corespunde ciclului C0a1C1a2C1. Figura 5.55. indic poziia ntrzierii (registrului Rd) n structura pipelinerevizuit.

a) b)

Fig. 5.55. ReducereaLMMprin inserare de ntrzieria) Structura iniialb) Structura revizuit prin introducerea unei ntrzieri (Rd)

5.8. Procesareapipelinen calculatoarele vectoriale

Pe lng instruciunile "scalare" care proceseaz operanzi scalari, calculatoarelevectoriale includ n seturile lor de instruciuni i instruciuni vectoriale care proceseazoperanzi vectoriali. Un vector este constituit dintr-un ir de elemente scalare de o anumitlungime:

X= (x1, x2, x3, ....,xn)

Elementele vectorului (xi) sunt fie numere ntregi, fie numere flotante. Este posibil ovarietate de instruciuni vectoriale care implementeaz cele mai diverse operaii:

V operaie V V , V operaie S V , VV , VS

V- mulimea operanzilor vectorialiS- mulimea operanzilor scalari

7/21/2019 CAP5_P3

12/16


210

Supercalculatoarele conin de regul, att procesoare scalare ct i procesoare vectoriale.Operanzii vectoriali pot fi locai n registre vectoriale ( ca n cazul calculatoarelor Cray-1, -2, -X-MP, -Y-MP) sau n memorie (ca n cazul calculatorului Cyber 205). Cele mai

multe sisteme recurg la registre vectoriale. Caracteristica de baz a unei instruciunivectoriale este aceea c repet aceeai operaie aritmetico-logic asupra tuturor elementelorvectorului operand, respectiv vectorilor operanzi. Dac aceste operaii aritmetico-logice seimplementeaz n tehnic pipeline performanele procesorului vectorial cresc spectaculos.Arhitectura general este distribuit aa cum indic figura 5.56.

Fig. 5.56. Procesarea vectorilor n tehnicpipeline

Procesorul vectorial recepioneaz instruciuni vectoriale pe care le distribuieunitilor funcionale corespunztoare pentru execuie. Pentru obinerea unor performanesuperioare unitile de execuie pot fi nlnuite i sincronizate. Pentru exemplificare vomlua n considerare urmtoarea secven de instruciuni vectoriale:

ADD RV1, RV2, RV3 ; RV1 = RV2 + RV3MUL RV5, RV4, RV1 ; RV5 = RV4 * RV1

Pentru execuia celor 2 instruciuni procesorul vectorial va activa 2 uniti deexecuie: P1 - structurpipelinede adunare i P2 - structur pipelinede nmulire. Secvenapoate fi executat:

a) fr cascadarea i sincronizarea structurilorpipeline(fig. 5.57)

Vectorul rezultat obinut pe ieirea structurii P1 se memoreaz n registrulvectorial RV1 care va furniza apoi unul din operanzi pentru structura P2. Structura P2 nu va

7/21/2019 CAP5_P3

13/16


211

putea starta procesarea dect n momentul n care operandul este disponibil n RV1, adicdup ce structura P1 a ncheiat procesarea celor 2 vectori i a memorat rezultatul (hazardRAW).

a) Schema de principiu

b) Caracteristica spaiu - timp

Fig. 5.57. Procesarea vectorilor fr cascadarea i sincronizareaunitilor de execuiepipeline

b) cu cascadarea i sincronizarea structurilorpipeline(fig. 5.58)

Cele 2 structuri pipeline vor fi sincronizate i vor funciona cu acelai tact.Componentele vectoriale obinute pe ieirea structurii P1 se vor aplica direct pe intrareastructurii P2. Figura 5.58. b) evideniaz suprapunerea n timp a activitilor celor 2structuri. Economia de timp este evident i este cu att mai nsemnat cu ct vectorii suntmai lungi.

7/21/2019 CAP5_P3

14/16


212

a) schema de principiu

b) caracteristica spaiu-timp

Fig. 5.58. Procesarea vectorilor cu cascadarea i sincronizareaunitilor de execuiepipeline

Un compilator performant poate detecta situaiile n care se poate aplicacascadarea i sincronizarea structurilor pipeline. O alt problem delicat care cade nsarcina compilatorului ar fi vectorizarea programelor scrise n limbaje de nivel nalt(compilarea programelor utiliznd ct mai multe instruciuni main vectoriale).Compilatorul trebuie s detecteze secvenele care pot fi vectorizate. Cele mai serioasecandidate la vectorizare sunt buclele din programele scrise n limbaje de nivel nalt. O buclcare se parcurge de n ori, n general, poate fi vectorizat rezultnd o instruciune sau osecven de instruciuni main vectoriale cu operanzi vectoriali de lungime n. Exist nsi bucle nevectorizabile (de exemplu buclele recurente) i, n consecin, la nivelulcompilatorului trebuie implementat un algoritm de recunoatere a buclelor vectorizabile.

7/21/2019 CAP5_P3

15/16


213

Dac procesorul vectorial lucreaz cu operanzi locai n registre vectoriale (registreCPU) atunci maina vectorial are o arhitectur load-store. Cele dou instruciunivectoriale "load " i "store" vor asigura transferul vectorilor ntre registrele vectoriale imemorie. Comunicaia cu memoria trebuie s aib o lrgime de band suficient de mare

(memorie cu adresare ntreesut). Lrgimea de band este dependent de pasul vectorului.Pasul hardeste reprezentat de diferena dintre adresele de memorie la care sunt memoratedou componente vectoriale succesive. Dintr-un vector V(i)se poate construi un subvectorV'(j) cuj =ki; kreprezint pasulsoftaferent subvectorului V'(j).

p = s L

p - pasul hards - pasulsoft

L - lungimea componentei vectoriale (numrul de locaii de memorie pe care leocup o component vectorial)

n general, dac pasulpi factorul de ntreesere (numrul de module care apar n structuramemoriei cu adresare ntreesut) sunt prime ntre ele se asigur o lrgime de band

maxim la nivelul comunicaiei cu memoria. Cea mai defavorabil situaie apare atuncicnd pasulpeste egal cu factorul de ntreesere deoarece toate componentele vectorului vorfi localizate fizic n acelai modul de memorie. Pentru eliminarea problemelor generate depasul vectorilor, la nivelul memoriei cu adresare ntreesut trebuie aplicate soluiiarhitecturale mbuntite.

7/21/2019 CAP5_P3

16/16


214

CAP5_P3

Documents

Transcript of CAP5_P3