Executie neordonata si redenumirea registrelor - microprocesoare intel

Executie neordonata si redenumirea registrelor - microprocesoare intel

Procesoarele moderne sunt arhitecturi atat in banda de asamblare cat si superscalare, asa cum rezulta din figura 3. Aceasta inseamna, in general, ca exista o unitate de citire care citeste instructiuni din memorie inainte ca acestea sa fie necesare pentru a fi trimise unitatii de decodificare. Unitatea de decodificare trimite instructiunile decodificate unitatilor functionale adecvate pentru executie. In anumite cazuri, instructiuni individuale pot fi descompuse in micro-operatii (micro-ops) inainte de a le trimite unitatilor functionale in functie de ce sunt capabile sa faca unitatile functionale.

Proiectarea masinilor ar fi mai simpla daca toate instructiunile sunt executate in ordinea in care sunt citite (presupunand pentru moment ca algoritmul de predictie a ramificatiior nu greseste niciodata). Totusi, executia in ordine nu furnizeaza intotdeauna performanta optima din cauza dependentei intre instructiuni. Daca o instructiune necesita o valoare calculata de catre instructiunea precedenta, cea de-a doua instructiune nu isi poate incepe executia pana ce prima nu a produs valoarea necesara. In aceasta situatie, numita dependenta RAW-read after write, a doua instructiune trebuie sa astepte incheierea celeilalte. Exista, de asemenea si alte tipuri de dependenta, asa cum se va vedea in acest capitol.

Pentru abordarea acestor probleme si pentru a realiza o performamta superioara, unele UCP-uri permit sarirea unor instructiuni pentru a ajunge la instrutiunile urmatoare care nu sunt dependente. Bineinteles ca algoritmul intern de planificare a instructiunilor utilizat trebuie sa furnizeze acelasi efect ca si cand programul ar fi executat in ordinea scrisa. Aceasta insemna ca instructiunile trebuie retrase in ordinea din program. Executia neordonata si reordonarea instructiunilor va fi tratata pe baza unui exemplu.

Presupunem ca avem de-a face cu o masina care intotdeauna furnizeaza instructiuni in ordinea programului si de asemenea necesita terminarea executiei in ordinea programului. Masina din exemplul nostru are opt registre vizibile programatorului, de la R0 la R7. Toate instructiunilor aritmetice utilizeaza trei registre: doua pentru operanzi si unul pentru rezultat. Vom presupune ca daca o instructiune este decodificata in ciclul n, executia incepe in ciclul n+1. Pentru o instructiune simpla, cum ar fi o adunare sau o inmultire, scrierea in registrul destinatie se produce la sfarsitul ciclului n+2. Pentru o instructiune mai complicata, cum ar fi o inmultire, scrierea se produce la sfarsitul ciclului n+3. Pentru ca exemplul sa fie realitst, vom permite unitatii de decodificare sa lanseze in executie pana la doua instructiuni pe ciclu de ceas. UCP-urile superscalare comerciale adesea pot lansa in executie patru sau chiar sase instructiuni pe ciclu de ceas.

Secventa de executie din exemplul nostru este aratata in figura 7 [15]. Aici prima coloana furnizeaza numarul de cicluri si a doua coloana furnizeaza numarul instructiunii. A treia coloana listeaza instructiunea decodificata, a patra spune care instructiune este lansata in executie (cu un maxim de doua pe ciclul de ceas). A cincea coloana precizeaza care instructiune a fost retrasa (terminata). In acest exemplu exista cerinta det lansare in executie in ordine cat si terminare in ordine, astfel ca instructiunea k+1 nu poate fi lansata in executie pana cand instructiunea k nu a fost lansata in executie, iar instructiunea k+1 nu poate fi retrasa, intelegand prin aceasta efectuarea scrierii in registrul destinatie, pana ce instructiunea k nu a fost retrasa. Celelalte 16 coloane ale acestui exemplu vor fi discutate in continuare.

Dupa decodificarea unei instructiuni unitatea de decodificare trebuie sa decida daca poate fi lansata in executie imediat sau nu. Pentru a lua aceasta decizie, unitatea de decodificare trebuie sa cunoasca starea tuturor registrelor. Daca, de exemplu, instructiunea curenta necesita un registru a carui valoare nu a fost inca calculata, instructiunea curenta nu poate fi lansata in executie si UCP trebuie sa se blocheze. Vom pastra informatii despre utilizarea registrelor folosind un dispozitiv numit tabela de scor (scoreboard), care a fost prima data prezent in masina CDC 6600. Tabela de scor are un numarator pentru fiecare registru indicand de cate ori este utilizat acel registru ca sursa de catre instructiunile aflate in executie. Daca maximum, sa zicem, 15 instructiuni se pot executa simultan atunci este necesar un contor de 4 biti. Cand este lansata in executie o instructiune, intrarile tabelei de scor pentru registrele sale cu operanzi sunt incrementate. Cand o instructiune este retrasa, intrarile sunt decrementate.

C = Ciclu; Iss = Lansata; Ret = Retrasa

Figura 7. Functionarea unei UCP superscalar cu lansare in executie in ordine si terminare in ordine.

Tabela de scor are de asemenea un numarator pentru fiecare registru, pentru a pastra informatii despre registrele utilizate ca destinatii. Deoarece se permite o singura scriere la un moment dat, aceste numaratoare pot fi de 1 bit. In figura 7 cele 16 coloane din dreapta indica aceasta tabela de scor.

In masinile reale, tabela de scor pastreaza si informatii despre utilizarea unitatilor functionale pentru a impiedica lansarea in executie unei instructiuni pentru care nu este disponibila nici o unitate functionala. Pentru simplitate, vom presupune ca intotdeauna exista o unitate functionala adecvata disponibila, asa ca nu vom arata unitatile functionale pe tabeta de scor.

Prima linie din figura 7 indica I1 (instructiunea 1), care inmulteste R0 cu R1 si depune rezultatul in R3. Deoarece nici unul din aceste registre nu este deocamdata folosit, instructiunea este lansata in executie si tabela de scor actualizata pentru a reflecta faptul ca R0 si R1 sunt citite si R3 este inscris. Nici una din instructiunile urmatoare nu va putea scrie in oricare din aceste registre sau nu va putea citi R3 pana cand I1 nu a fost retrasa. Deoarece aceasta instructiune este o inmultire despre care am spus ca dureaza trei cicluri, ea se va incheia la sfarsitul ciclului Valorile tabelei de scor aratate pe fiecare linie reflecta starea acestora dupa ce instructiunea de pe acea linie a fost lansata in executie. Intrarile care nu contin nimic sunt zerouri.

Deoarece exemplul prezentat este o masina superscalara care poate lansa in executie doua instructiuni pe ciclu, o a doua instructiune (I2) este lansata in executie in timpul ciclului 1. Aceasta este o adunare a doi registri, memorand rezultatul in R Pentru a vedea daca aceasta instructiune poate fi lansata in executie se aplica urmatoarele reguli:

1. Daca orice operand este in curs de inscriere, nu se va lansa in executie (dependenta RAW).

2. Daca registrul rezultat este in curs de citire, nu se va lansa in executie (dependenta WAR).

3. Daca registrul rezultat este in curs de scriere, nu se va lansa in executie (dependenta WAW).

Dependentele RAW au mai fost intalnite. Acestea apar atunci cand o instructiune trebuie sa utilizeze ca sursa un rezultat pe care o instructiune precedenta inca nu l-a produs. Celelalte doua dependente sunt mai putin grave. Ele reprezinta de fapt conflicte de resurse. Intr-o dependenta WAR (Write After Read - scriere dupa citire), o instructiune incearca sa suprainscrie un registru pe care o instructiune precedenta poate nu a terminat inca sa-l citeasca. O dependenta WAW (Write After Write - scriere dupa scriere) semnifica acelasi lucru. Astfel de dependente pot fi evitate prin plasarea rezultatelor celei de-a doua instructiuni undeva in alta parte, eventual intr-un registru temporar. Daca nici una din cele trei dependente de mai sus nu exista si daca unitatea functionala necesara este disponibila, instructiunea este lansata in executie. In cazul din exemplul prezentat, I2 utilizeaza un registru (R0) care este in curs de citire de catre o instructiune in desfasurare, dar aceasta suprapunere este permisa deci I2 este lansata in executie. Asemanator, I3 este furnizata in timpul ciclului 2. In ceea ce privesteI4, aceasta necesita utilizarea lui R Asa cum rezulta din linia 3 registrul R4 este in curs de scriere. Exista deci o dependenta RAW, asa ca unitatea de decodificare se blocheaza pana cand R4 devine disponibil. Cat timp este blocata, aceasta nu va prelua instructiuni de la unitatea de citire a instructiunilor. Cand tampoanele interne ale unitatii de citire se incarca integral, se va opri citirea instructiunii in avans.

Urmatoarea instructiune in ordinea programului, I5 nu are conflicte cu nici una din instructiunile in desfasurare. Ar fi putut fi decodificata si lansata in executie In ciclul 2, dar nu este posibil caci in variant de lucru prezentata initial este necesara lansarea instructiunilor in executie in ordine.

In timpul ciclului 3. I2, fiind o adunare cu o durata de doua cicluri, se incheie la sfasitul ciclului 3. Din nefericire, ea nu poate fi retrasa eliberand astfel R4 pentru I Motivul il constituie faptul ca am presupus ca acesta varianta de lucru necesita, de asemenea, retragerea in ordine. Merita de vazut care este motivul pentru care I4 nu poate fi terminata acum prin memorarea rezultatului in R4 si marcarea acestuia ca disponibil. Pentru aceasta sa presupunem ca instructiunile se pot termina in ne-ordine. Atunci, daca apare o intrerupere, ar fi foarte dificil sa se salveze starea masinii, astfel incat sa fie restabilita ulterior. In particular nu ar fi posibil sa se spuna ca toate instructiunile pana la o anumita adresa au fost executate si toate instructiunile de dupa aceasta nu. Aceasta este numita intrerupere precisa (precise interrupt) si este o caracteristica de dorit intr-o UCP. Retragerea in ne-ordine face intreruperile imprecise, motiv pentru care unule masini necesita terminarea in ordine a instructiunilor.

Revenind la exemplul dat, la sfarsitul ciclului 4 toate cele trei instructiuni in desfasurare pot fi retrase, astfel ca in ciclul 5 I4 poate fi in sfarsit lansata in executie, alaturi de ultima instructiune decodificata I5. Ori de cate ori o instructiune este retrasa unitatea de decodificare trebuie sa verifice daca exista o instructiune blocata care poate fi acum lansata in executie.

In ciclul 6, I6 se blocheaza pentru ca trebuie sa scrie in R1, iar R1 este ocupat. Ea este lansata abia in ciclul 9. Intreaga secventa de opt instnictiuni consuma in total pentru terminare 15 cicluri datorita numeroaselor dependente, chiar daca hardware-ul este capabil sa lanseze in executie doua instructiuni in fiecare ciclu. Se observa, citind de coloana Issued din figura 7, ca toate instructiunile au fost lansate in executie in ordine. In acelasi fel, coboana Retrasa arata ca instructiunile au fost retrase de asemenea in ordine.

O alta solutie ar putea fi executia in ne-ordine. In aceasta solutie instructiunile pot fi lansate in executie in alta ordine si pot fi retrase de asemenea in alta ordine decat cea din program. Aceeasi secventa de opt instructiuni este aratata in figura 8, numai ca acum sunt permise lansarea in executie si retragerea in ne-ordine.

Prima deosebire apare in ciclul 3. Chiar daca I4 s-a blocat, se poate decodifica si lansa I5 pentru ca nu este in conflict cu nici o instructiune in desfasurare. Sarirea peste executia unei instructiuni genereaza o noua problema. Sa presupunem ca I5 a utilizat un operand calculat de instructiunea peste care s-a sarit, I Acest lucru nu poate fi remarcat cu tabela curenta de scor. In consecinta trebuie extinsa tabela de scor pentru a retine informatii despre memorarile facute de instructiunile peste care s-a sarit. Aceasta se poate face adaugand un al doilea plan de biti, un bit pentru fiecare registru, pentru a retine informatii despre memorarile facute de instructiunile blocate. Aceste contoare nu sunt aratate in figura 8. Acum regula pentru lansarea instructiunilor in executie trebuie extinsa pentru a evita lansarea oricarei instrutiuni cu un operand planificat sa fie modificat de o instructiune care a sosit mai inainte, dar a fost sarita.

Daca revenim la I6, I7 si I8 din figura 7, se observa ca I6 calculeaza o valoare in R1 care este apoi utilizata de I7. De asemenea, vedem si ca valoarea nu este utilizata din nou pentru ca I8 suprainscrie R1. Nu exista nici un motiv real sa se utilizeze R1 ca loc de pastrare a rezultatului lui I6. Mai rau, R1 este o alegere de registru intermediar foarte proasta, desi perfect rezonabila pentru un compilator sau programator obisnuit cu ideea executiei secventiale fara suprapunere de instructiuni.

Figura 8 prezinta o noua tehnica pentru rezolvarea acestei probleme ce poarta numele de redenumirea registrelor (register renaming). Unitatea inteligenta de decodificare schimba utilizarea lui R1 in I6 pe durata ciclulului 3 si I7 pe durata ciclului 4 intr-un registru secret, S1, invizibil programatorului. Acum I6 poate fi lansata concurent cu I5. UCP-urile moderne au adesea zeci de astfel de registre secrete folosite pentru redenumirea registrelor. Aceasta tehnica poate elimina adesea dependentele WAR si WAW.

Pentru instructiunea I8 seutilizeaza din nou redenumirea registrelor. De aceasta data R1 este redenumit in S2 asa ca adunarea poate fi lansata inainte ca R1 sa fie liber, la sfarsitul ciclului 6. Daca apare necesitatea ca de aceasta data rezultatul sa fie chiar in R1, continutul lui S2 poate fi oricand copiat acolo la timp. Mai mult, toate instructiunile urmatoare care au nevoie de el pot avea sursele lor redenumite la registrul unde este intr-adevar memorat.

Pe multe masini reale redenumirea este strans legata de modul in care sunt organizate registrele. Exista registre secrete si o tabela care pune in corespondenta registrele vizibile programatorului in registre secrete. Astfel registrul real utilizat pentru, sa spunem, R0 este localizat urmarind intrare 0 a acestei tabele de corespondenta. In acest fel, nu exista registru real R0, ci numai o legatura intre numele R0 si unul dintre registrele secrete. Aceasta legatura se schimba frecvent in timpul exectiei pentru a evita dependentele.

C = Ciclu; Iss = Lansata; Ret = Retrasa

Figura 8. Functionarea unei UCP superscalar cu lansare in ne-ordine si terminare in ne-ordine.

Din figura 8, cand se citeste de sus in jos coloana Issue=Lansata, rezulta cainstrutiunile nu au fost lansate in ordine. Nici nu au fost retrase in ordine dupa cum rezulta din coloana Retired. Concluzia acestui exemplu este ca utilizand executia in neordine si redenumirea registrelor exista posibilitatea de a mari viteza calculatorului printr-un factor de pana la doi. Pe cazul exemplului prezentat, daca programul in conditiile lansarii in ordine si a retragerii in ordine a durat 15 cicluri, in cazul executiei in ne-ordine si al redenumirii registrelor a durat 9 cicluri.