Redenumirea regiștrilor
Seria: arhitectura modernă a calculatoarelor

Mihai Budiu -- mihaib+@cs.cmu.edu
http://www.cs.cmu.edu/~mihaib/

18 iunie 1999

Subiect:
tehnici de creștere a performanței procesoarelor moderne: redenumirea regiștrilor (register renaming)
Cunoștințe necesare:
cunoștințe elementare despre arhitectura procesoarelor
Cuvinte cheie:
registru, redenumire, dependență


Cuprins

Cu cîtăva vreme în urmă am publicat în PC Report două articole despre arhitectura procesoarelor moderne, care se doreau a fi parte dintr-o suită despre acest subiect foarte generos. Din păcate (sau din fericire, depinzînd de perspectivă), m-am luat cu vorba despre Internet și alte lucruri, și nu am mai continuat pe acest subiect, deși unul dintre articole promitea ``demistificarea'' unei liste impresionante de termeni.

Articolul de față este o continuare a celor două anterioare. Pentru o tratare matură a subiectului rămîne valabilă referința oferită cu acea ocazie, Hennessy and Patterson ``Computer Architecture -- a Quantitative Approach'', Morgan Kaufmann, ediția II, 1995.

Performanță și compatibilitate

Intel este cea mai mare companie din domeniul hardware, cu un venit anual de 26 de miliarde de dolari în 1998. Într-un fel ar fi de așteptat ca cei care au inventat microprocesorul să fie și liderii din punct de vedere economic. Pe de altă parte, adesea, tehnologic vorbind, compania a fost depășită de altele în ceea ce privește performanța microprocesoarelor realizate. De fapt, multă vreme procesoarele 8086, 80386, Pentium, etc. au fost cu mult mai slabe în performanțe decît procesoare contemporane lor ale unor firme concurente. Atunci cum se explică succesul economic nemaipomenit al lui Intel? Probabil că nu există un răspuns simplu, dar cel puțin o fărîmă de răspuns stă în producția de masă. PC-urile sunt de departe cele mai răspîndite calculatoare acum, așa că, chiar în condițiile unor produse inferioare calitativ (dar cu prețuri mici) Intel a putut să cîștige mult mai mult decît celelalte companii. Cîștiguri care apoi au fost investite în cercetare și dezvoltare, care au dus la crearea lui Pentium II, care este un chip cu adevărat extraordinar.

De fapt avantajele și dezavantajele lui Intel provin din aceeași sursă, producția de masă. Producția de masă necesită compatibilitate între produse, pentru ca utilizatorii să poată beneficia de software-ul care a fost deja scris. Asta este un avantaj nemaipomenit, și este cert că relația strînsă cu Microsoft a însemnat enorm în succesul lui Intel (Microsoft fiind acum compania cea mai mare din lume, socotind cotația la bursă). Dar compatibilitatea a fost și blestemul lui Intel.

La începutul anilor '80, din laboratoarele de cercetare de la universitățile Stanford și Berkeley ieșea un concept complet nou de arhitectură a procesoarelor: procesorul RISC, încarnat în procesorul MIPS (actualmente în posesiunea lui Silicon Graphics). RISC-urile sunt procesoare care implementează instrucțiuni extrem de simple, dar care profită de această simplitate pentru a rula la viteze extreme, folosind un hardware foarte eficace. Aparent RISC-ul era sortit să fie învingător, și o sumă întreagă de companii au început să fabrice RISC-uri. Performanțele lor erau într-adevăr spectaculoase, comparat cu procesoarele de tip CISC, tradiționale.

Aceasta era și problema lui Intel: 8088 și toți descendenții lui sunt de la început compatibile unul cu altul, deci trebuie să implementeze același set de instrucțiuni. Dar setul de instrucțiuni x86 (cum este abreviată familia) a fost proiectat înaintea revoluției RISC (mai exact în 1978), deci nu putea beneficia de toate avantajele tehnologice care pot fi aplicate în cazul acestora. Intel era sortită să rămînă în urmă.

Salvarea a venit însă dintr-o direcție oarecum neașteptată: din tehnologie. Intel a reușit în ultimii ani să recupereze toate diferențele față de competitorii săi, și să livreze procesoare extrem de performante. Cum se explică acest lucru?

Diferența RISC-CISC este o diferență relativă; relativă la tehnologia curentă. Dimensiunea tranzistoarelor dintr-un circuit integrat în 1986, și deci numărul de tranzistoare care se puteau construi, era limitat la o valoare în jurul a 100 000. Cu atîtea tranzistoare puteai construi o mașinărie RISC eficace, dar nu și una CISC; puteai face CISC-uri doar lente, folosind micro-cod, pentru că sarcina decodificării și executării unui set de instrucțiuni complex cerea mai multe resurse. Dar avansul implacabil al tehnologiei și-a spus cuvîntul, dimensiunea și viteza circuitelor se dublează la fiecare 18 luni, deci în 1995 Intel a avut la dispoziție suficiente resurse pe pilula de siliciu pentru a lupta cot-la-cot cu RISC-urile, folosind propriile lor idei, cu Pentium II. Și, cel puțin deocamdată, Intel a cîștigat, ajutată fiind și de formidabila economie de masă a PC-ului.

Compatibilitatea și regiștrii

Desigur, asta este o poveste interesantă, dar ce are a face cu arhitectura modernă a calculatoarelor? Ei bine, deși partea economică este cu certitudine incitantă, cuvîntul cheie asupra căruia o să mă aplec pentru a construi acest articol este ``compatibilitatea''.

Pentium III poate încă executa cod scris pentru procesorul 8086. De fapt, majoritatea codului executat în lume pe procesoare Pentium a fost scris cu procesoare mai slabe decît 80286 în minte (la ora actuală cel mai rulat sistem de operare din lume este încă Windows 3.1). În plus, foarte multă lume scrie încă software pentru platforme vechi, pentru că baza instalată este uriașă, și altfel ar însemna să dai cu piciorul unei mulțimi de potențiali clienți. În plus, metoda obișnuită de distribuție a software-ului este în formă de programe executabile, gata compilate. Asta înseamnă că o mulțime de programe folosesc numai facilitățile vechi ale procesorului, chiar dacă acesta are acum cu mult mai multe resurse.

De pildă, în mod esențial numărul de regiștri de bază la Pentium este în continuare 4 (EAX, EBX, ECX și EDX), deși costul unui registru în hardware este nesemnificativ, iar performanța obținută din folosirea unui număr mare de regiștri este substanțială. Din motive de compatibilitate însă, Intel nu poate schimba radical setul de instrucțiuni, introducînd noi regiștri. Prin comparație, procesoarele moderne RISC au cel puțin cîte 32 de regiștri.

Regiștrii sunt foarte importanți pentru performanță pentru că accesul la datele din regiștri este foarte rapid (de fapt, ce sunt altceva regiștrii, decît o foarte mică memorie cache aflată chiar pe procesor; un cache al cărui management este făcut de compilator?). Odată cu miniaturizarea și creșterea vitezelor de ceas, diferența de durată între accesele la regiștri și cele la memorie crește îngrijorător (de exemplu am văzut într-un articol din PC Report niște măsurători pentru un sistem Pentium 266Mhz, la care accesul la memorie putea dura de 13 ori mai mult decît cel al un registru!). Diferența aceasta este de sute de cicli pentru cazul multi-procesoarelor, care au nevoie de mecanisme complicate de arbitrare a accesului la memorie.

Desigur, aici contrastăm viteza de acces la memoria principală, dar foarte adesea datele se vor afla de fapt în cache-ul microprocesorului. Chiar și așa, cache-urile moderne L1 nu sunt capabile să țină pasul cu viteza procesoarelor, oferind timpi de acces de ordinul a 2-4 cicli, timpi care vor crește în viitor (pentru că ciclul scade)1.

Dacă are mulți regiștri la dispoziție, un compilator poate aplica o serie mai largă de optimizări, și are mai multă libertate în plasamentul valorilor, putînd optimiza mai eficace programele. Un singur registru în plus poate însemna foarte mult pentru eficiența codului compilat. Vom vedea că un număr redus de regiștri forțează compilatorul să reutilizeze aceiași regiștri pentru lucruri diferite. Acesta reutilizare înseamnă dependențe între instrucțiuni, care la rîndul lor cauzează imposibilitatea de execuție a instrucțiunilor simultan.

Vom vedea în acest articol o soluție foarte ingenioasă a acestei probleme; vom vedea cum, dînd iluzia programelor că au la dispoziție numai un număr foarte redus de regiștri, procesoarele sunt capabile să utilizeze intern mai multe, obținînd majoritatea beneficiilor descrise mai sus.

Paralelism și dependențe

Dacă 50% din cre'sterea 'in performan't'a a procesoarelor contemporane provine cu certitudine din aportul tehnologiei, care permite folosirea unor ceasuri din ce în ce mai rapide, cealaltă jumătate trebuie sa fie atribuită inovațiilor hardware, și mai cu seama, paralelismului exploatat.

Paralelism înseamnă că mai multe activități independente se desfășoară simultan. Nu prea este clar despre ce fel de paralelism poate fi vorba în cazul procesoarelor: acestea primesc doar un singur program, care este o secvență de instrucțiuni, pe care trebuie să-l execute. Ce se poate face în paralel atunci?

Există mai multe feluri de paralelism, de obicei categorisit după granularitatea sarcinilor executate în paralel. De pildă, un sistem de operare este capabil să execute simultan mai multe aplicații; acesta este paralelismul la nivel de aplicație. Procesoarele însă acționează la un nivel microscopic, privind doar la cîte o instrucțiune din program. Ele manipulează paralelism la o granularitate infimă, comparat cu paralelismul proceselor.

Chiar dacă programele scrise de noi denotă o suită de acțiuni care trebuie efectuate într-o anumită secvență, există o cantitate oarecare de libertate în ordinea în care acestea sunt îndeplinite. Dacă, de pildă, inițializăm mai multe variabile, adesea aceste operații pot fi executate în orice ordine, obținînd aceleași efecte.

Desigur, două instrucțiuni se pot executa simultan numai dacă nu depind una de alta. Două instrucțiuni ca ``f=1; g=f+2'' nu se pot executa simultan, pentru că a doua are nevoie de rezultatul primeia. Spunem atunci că a doua instrucțiune depinde de prima, sau că între ele există o dependență.

Atunci cînd programele sunt traduse în cod-mașină, între micile instrucțiuni rezultate adesea se găsesc unele care sunt independente, deci care se pot executa în orice ordine. Aceste instrucțiuni pot fi executate deci și în paralel, dacă avem resursele necesare la dispoziție. Acest gen de paralelism este extrem de important, și are propriul său nume: ``paralelism la nivel de instrucțiune'', sau Instruction Level Parallelism, ILP.

Procesoare superscalare și LIW

Majoritatea procesoarelor moderne exploatează ILP într-un mod foarte natural: au mai multe unități din fiecare fel, care le permit să execute mai multe instrucțiuni simultan. Astfel, ele trebuie să aibă mai multe unități care aduc instrucțiuni din memorie, care le decodifică, care le execută și care stochează rezultatele.

Există două categorii mari de procesoare care exploatează ILP executînd instrucțiuni în paralel; ele se deosebesc după felul în care se decide care instrucțiuni se pot simultaneiza.

LIW:

Prima mare categorie de procesoare lasă decizia în cîrca compilatorului; acesta are misiunea să indice care instrucțiuni sunt independente. Hardware-ul doar ia instrucțiunile indicate și le trimite unor unități separate. Hardware-ul este simplu, iar compilatorul este complicat. De fapt putem vedea compilatorul ca oferind hardware-ului niște ``super-instrucțiuni'', formate din mai multe instrucțiuni elementare; din cauza asta astfel de procesoare se numesc ``Long Instruction Word'' (LIW), sau cîteodată VLIW (Very LIW). De exemplu procesorul de semnal Texas Instruments TMS320C62x primește simultan pînă la 8 instrucțiuni.

Superscalare:

A doua clasă de procesoare calculează dependențele în întregime în hardware, și decide la fața locului care instrucțiuni pot fi lansate în paralel2. Pentium II de pildă citește, decodifică și încearcă să execute cîte două instrucțiuni la fiecare bătaie de ceas. Aceste procesoare se numesc superscalare.

Pipelines (conducte)

Pe lîngă această metodă de a exploata ILP, există o alta foarte ingenioasă, numită ``banda de asamblare'', sau ``conductă''. Am scris un articol întreg despre acest subiect, dar iată ideile esențiale: dacă avem o suită de acțiuni de efectuat și mai multă forță de muncă, și dacă putem descompune fiecare acțiune în mai multe bucățele, atunci putem construi o bandă de asamblare, în care fiecare porțiune a benzii face o singură parte. La fel ca zidarii: unul ia cărămidă, unul o întinde, unul pune mortar și unul o înfige în perete.

La fel stau lucrurile și în cazul procesoarelor: citirea, decodificarea, execuția, stocarea rezultatelor, sunt tot atîtea micro-acțiuni, care pot fi executate simultan pentru instrucțiuni diferite: cînd o instrucțiune tocmai se termină, cea de după ea stochează rezultatele, următoarea tocmai și le calculează în timp ce a patra este decodificată, etc.

Acest gen de paralelism se numește paralelism de pipeline. La o vedere superficială paralelismul de pipeline nu este afectat de dependențe; în realitate acestea sunt la fel de importante ca și în cazul superscalarelor. Să ne gîndim un pic: dacă avem cele două instrucțiuni de mai sus, dependente, ``f=1; g=f+2'', atunci cînd f+2 vrea să citească valoarea lui f pentru a face calcule cu ea, valoarea de fapt încă nu a fost calculată, și nici stocată unde trebuie, pentru că instrucțiunea f=1 se află încă în stagiul de execuție. În analogia cu zidarii, este ca și cum un zidar fabrică chiar mortarul de care are nevoie unul dinaintea lui; cel care pune mortar nu are cum să acționeze înainte ca mortarul să existe.

Dependențele sub lupă

Dacă sunteți nerăbdători să aflați ce are asta a face cu redenumirea regiștrilor, o să fac aici o scurtă avanpremieră. Vom vedea că anumite dependențe sunt de fapt artificial introduse, din cauză că unii regiștri trebuie refolosiți pentru a stoca variabile complet diferite; dacă am avea mai mulți regiștri, ca să punem o variabilă în fiecare, aceste dependențe ar dispărea. Ei bine, redenumirea regiștrilor tocmai asta va face: va folosi o găleată cu regiștri ascunși, pe care-i va folosi în astfel de cazuri, eliminînd anumite dependențe și mărind gradul de paralelism de care procesorul poate profita.

În general între două instrucțiuni există o dependență dacă folosesc același registru sau aceeași adresă de memorie. Acesta însă nu este un criteriu suficient; contează și cum folosesc acest registru comun. De pildă dacă două instrucțiuni citesc dintr-un același registru, între ele nu există nici o dependență, pentru că acțiunea de citire lasă registrul neschimbat, deci ordinea instrucțiunilor nu influențează rezultatul. Dacă una din instrucțiuni însă scrie în registru, atunci avem o dependență. Dependențele se denotează cu 3 litere: Acțiune-După-Acțiune, de pildă Scrie-După-Citire. Denumirile tradiționale sunt în engleză:

RAW
Read after write. Avem o astfel de dependență în exemplul anterior, reprodus și în figura 1.

Figura 1: O dependență RAW: f este citit de instrucțiunea 2 după ce ce este scris de către instrucțiunea 1.
\begin{figure}\centerline{\epsfxsize=3cm\epsffile{raw.eps}}\end{figure}

A doua instrucțiune citește valoarea lui g după ce prima o scrie. Această dependență se mai numește și ``dependență adevărată'' (true dependence).

WAR
apare cînd o instrucțiune scrie într-un registru care tocmai a fost citit, cum ilustrează și figura 2.

Figura 2: O dependență WAR: b este scris de instrucțiunea 2, după ce a fost citit de instrucțiunea 1.
\begin{figure}\centerline{\epsfxsize=10cm\epsffile{war.eps}}\end{figure}

Din nou, nu putem schimba ordinea instrucțiunilor, sau nu putem risca să le executăm în paralel, pentru că, dacă a doua se termină înainte ca prima să citească valoarea, rezultatul primeia va fi greșit. O astfel de dependență se mai numește anti-dependență.

WAW
este ultimul tip, în care o două instrucțiuni scriu în aceeași valoare; vedeți figura 3.

Figura 3: O dependență WAW apare cînd două instrucțiuni au aceeași destinație.
\begin{figure}\centerline{\epsfxsize=10cm\epsffile{waw.eps}}\end{figure}

Aceste dependențe se mai numesc și output dependences.

Aparent dependențele WAW nu trebuie să apară în programe: de ce compilatorul ar indica o instrucțiune al cărei efect să fie imediat distrus? De ce și-ar bate proiectantul procesorului capul cu astfel de instrucțiuni? În realitate dependențele WAW pot apărea în mai multe contexte:

  1. Între instrucțiuni nu neapărat consecutive, cum este ilustrat în figura 4. Aici avem o dependență WAW între prima și a treia instrucțiune;

    Figura 4: O dependență WAW și una RAW la care participă o singură valoare.
    \begin{figure}\centerline{\epsfxsize=3cm\epsffile{waw-ex.eps}}\end{figure}

  2. Pe de altă parte, nu e treaba procesorului să decidă dacă un program are sau nu sens; poate cineva scrie de mînă un astfel de program; procesorul tot trebuie să dea rezultatele corecte;

  3. Un alt caz de acest gen poate apărea dacă apare o întrerupere; deși nu există nicăieri în program două scrieri consecutive în același registru, saltul la rutina de întrerupere poate cauza apariția unei astfel de secvențe;

  4. În fine, procesoarele moderne folosesc o altă tehnică, numită execuție speculativă: execută cod chiar ne-necesar, pentru că nu sunt sigure ce trebuie să facă, deci mai bine să facă ceva, orice, care s-ar putea dovedi util, decît să stea degeaba (intenționez să consacru un articol întreg acestui subiect). Ei bine, dacă ai executat cod speculativ și ai observat că de fapt nu trebuia, atunci poate vei dori să ștergi efectele codului speculativ; în acest caz pot apărea din nou dependențe WAW.

Încă o dată: studiul dependențelor este important, pentru că existența lor reduce posibilitatea de execuție paralelă a mai multor instrucțiuni din program (fie prin paralelism superscalar, VLIW ori pipelined). Din fericire, în anumite, cazuri putem face ceva pentru a ameliora situația.

Redenumirea regiștrilor

În realitate numai dependențele ``adevărate'' (RAW) sunt de ne-evitat. De celelalte putem scăpa redenumind regiștri. Observația cheie este că programele în final vor stoca toate rezultatele în memorie; pentru utilizator conținutul regiștrilor nu este important. Dacă programul folosește registrul x sau y, nu are nici o importanță atîta vreme cît obținem același rezultat.

Figurile 5 și 6 arată cum putem rescrie dependențele WAR și WAW de mai sus, obținînd același efect. Vom presupune că avem la dispoziție în fiecare caz cîte un registru nefolosit.

Figura 5: Dependența WAR este eliminată înlocuind aparițiile lui b cu un registru nou (f).
\begin{figure}\centerline{\epsfxsize=10cm\epsffile{war-r.eps}}\end{figure}

Figura 6: Dependența WAW este eliminată înlocuind aparițiile lui f cu un registru nou (a).
\begin{figure}\centerline{\epsfxsize=10cm\epsffile{waw-r.eps}}\end{figure}

Observați că ambele aceste programe produc exact același rezultat ca programele inițiale.

Cred că acum începe să devină clar de fapt ce se întîmplă în miezul procesorului:

  1. Microprocesorul are intern foarte mulți regiștri, dar expune programatorului numai cîțiva;

  2. Cînd procesorul execută cod, detectează dependențele care se pot rezolva (anti- și output-). Atunci cînd găsește astfel de dependențe, în cazul în care posedă un registru intern liber, folosește acest registru în locul celui care provoca dependența.

  3. În felul acesta procesorul transformă instrucțiuni dependente în instrucțiuni independente, care se pot apoi executa în paralel, mărind performanța execuției.

  4. Procesorul ține minte regiștrii redenumiți, și aparițiile lor ulterioare sunt de asemenea redenumite.

Un exemplu

În loc de a prezenta algoritmul detaliat folosit pentru a redenumi regiștri, voi ilustra funcționarea sa cu un exemplu. Figurile 7-14 arată ``filmul'' execuției unui progrămel mic de 5 instrucțiuni pe un procesor superscalar care poate executa simultan adunări și înmulțiri. Presupunem că operația de adunare se poate efectua în 1 ciclu de ceas, iar cea de înmulțire în 2. Ilustrăm și structurile de date menținute de procesor pentru a ține cont de redenumiri. Acest exemplu este adaptat după un exemplu al domnului Randy Bryant, prezentat la un curs de arhitectura calculatoarelor în toamna anului 1998 la Carnegie Mellon.

Vom presupune că procesorul nostru poate executa instrucțiuni în orice ordine, dacă sunt independente.

Dacă urmăriți filmul cu atenție, veți observa că numai dependențele adevărate apar, celelalte fiind eliminate de redenumire. Veți vedea marcate instrucțiuni care așteaptă una după alta datorită dependențelor.

Figura 7: Programul de executat, valorile inițiale ale regiștrilor, regiștrii ascunși și cozile de instrucțiuni gata de execuție. Observați că săgețile pentru dependențe merg mereu în același ``sens'': WAW pe verticală, RAW de la stînga spre dreapta, WAR de la dreapta spre stînga. Cîmpul valid indică dacă acest registru ascuns are o valoare corectă în interior.
\begin{figure}\centerline{\epsfxsize=13cm\epsffile{film.eps}}\end{figure}

Figura 8: Ciclul 1: instrucțiunea a își redenumește destinația din r5 în x1, iar instrucțiunea b își redenumește destinația x2. Instrucțiunea de înmulțire așteaptă rezultatul din registrul x1 (fostul r5, acum redenumit), pentru a putea începe: avem aici o dependență RAW, care nu poate fi eliminată. Observați că r5 a fost deja redenumit de 2 ori. Numele de x2 este stocat pentru r5, pentru ca următoarele instrucțiuni care au nevoie de r5 să ia de fapt de aici valorile lor.
\begin{figure}\centerline{\epsfxsize=13cm\epsffile{film1.eps}}\end{figure}

Figura 9: Ciclul 2: instrucțiunea a s-a terminat, și a scris rezultatul în destinația ei, x1. Instrucțiunea de înmulțire poate începe, pentru că acum registrul x1 este valid. Instrucțiunea d este gata de execuție, dar instrucțiunea c nu a primit încă operandul din registrul x2, care este calculat de înmulțire. Instrucțiunea c și-a redenumit destinația în x3, iar instrucțiunea d în x4.
\begin{figure}\centerline{\epsfxsize=13cm\epsffile{film2.eps}}\end{figure}

Figura 10: Ciclul 3: instrucțiunea a s-a terminat complet; cu toate acestea nu a schimbat registrul r5, pentru că acum acesta este redenumit în x2. Instrucțiunea b își începe execuția pentru că are toate valorile necesare, dar termină numai primul din cei doi cicli necesari pentru execuție. Instrucțiunea d o ia înaintea lui c. Instrucțiunea e este pregătită pentru execuție și își redenumește destinația din r5 în x1. Observați ca valoarea din x1 a fost distrusă; ea nu mai era necesară, datorită output-dependenței. Puteam observa acest lucru, deoarece nici o instrucțiune nu mai avea nevoie de registrul x1 ca sursă, și nici un registru nu mai era redenumit în x1.
\begin{figure}\centerline{\epsfxsize=13cm\epsffile{film3.eps}}\end{figure}

Figura 11: Ciclul 4: instrucțiunea de înmulțire b se termină și oferă valoarea necesară executării instrucțiunii c. Instrucțiunea c începe execuția. Instrucțiunea d nu poate fi considerată terminată, pentru că este posibil ca instrucțiunea dinaintea ei, x să genereze o excepție, deci nu avem voie să stocăm încă rezultatele lui d.
\begin{figure}\centerline{\epsfxsize=13cm\epsffile{film4.eps}}\end{figure}

Figura 12: Ciclul 5: Instrucțiunea b s-a terminat, dar din nou, r5 nu este schimbat. Datorită celei de-a doua dependențe WAW, valoarea calculată este nu mai trebuie stocată. Încă nu putem termina d, pentru că c nu e gata. c tocmai se termină.
\begin{figure}\centerline{\epsfxsize=13cm\epsffile{film5.eps}}\end{figure}

Figura 13: Ciclul 6: În fine, instrucțiunea c se termină, și ca atare se poate termina și d. Regiștrii ascunși își copiază valorile înapoi în regiștrii reali, iar ultima instrucțiune intră în execuție.
\begin{figure}\centerline{\epsfxsize=13cm\epsffile{film6.eps}}\end{figure}

Figura 14: Ciclul 7: Ultima instrucțiune s-a terminat, iar rezultatul ei este preluat dintr-un registru ascuns în cel real.
\begin{figure}\centerline{\epsfxsize=13cm\epsffile{film7.eps}}\end{figure}

Desigur, exemplul acesta este pedagogic, pentru că de fapt șirul instrucțiunilor nu se termină niciodată; acest algoritm incîlcit este executat fără osteneală de procesor, de 500 de milioane de ori pe secundă!

De ce apar dependențe inutile

Din moment ce procesorul are mulți regiștri, și din moment ce unele dependențe pot fi evitate, de ce apar ele totuși în program? Răspunsul este același: din motive de compatibilitate.

Setul de instrucțiuni al unui procesor trebuie să ofere vederi compatibile asupra procesorului, chiar dacă măruntaiele acestuia se schimbă foarte mult în timp.

De pildă, x86 are în continuare doar 4 regiștri fundamentali; compilatorul nu are cum să folosească regiștri diferiți pentru valori diferite, pentru că nu are destui regiștri la dispoziție. Din cauza asta va re-folosi regiștri, cauzînd apariția unor dependențe.

O problemă și mai mare a arhitecturii x86 este faptul că regiștrii ei sunt asimetrici! La x86, majoritatea operațiilor aritmetice trebuie să aibă registrul eax ca destinație, chiar dacă ceilalți regiștri sunt liberi. Din cauza asta compilatorul este forțat să facă și mai multe jonglerii cu regiștrii; probabil ca intern Pentium este implementat ca un RISC simetric, în care toții regiștrii pot fi destinația unei valori, și ca folosește din plin redenumirea regiștrilor pentru a lansa în execuție mai multe instrucțiuni aritmetice simultan.

Un panaceu?

Trebuie să înțelegem că, deși salvează din performanță în mod substanțial, redenumirea regiștrilor nu este un panaceu pentru a rezolva problema lipsei de regiștri. Ce se întîmplă: să zicem că la un moment dat compilatorul are de manipulat 5 valori pentru un sistem x86, care are doar 4 regiștri fundamentali.

Ei bine, atunci compilatorul nu are altceva de făcut decît să ``verse'' (spill) o variabilă în memorie, de unde să o încarce într-un registru cînd e necesar. Pentru astfel de cazuri, mecanismul de redenumire este inutil.

Concluzii

În acest text am văzut cum tensiunea dintre compatibilitate și tehnologie împinge arhitecții microprocesoarelor la soluții disperate, cum ar fi redenumirea regiștrilor. Această tehnică permite procesorului să mențină valori diferite în regiștrii săi ascunși disponibili, chiar dacă compilatorului aceștia îi sunt invizibili. Făcînd acest lucru, procesorul reduce numărul dependențelor dintre instrucțiuni, și face execuția paralelă a instrucțiunilor fezabilă, mărind productivitatea.

S-ar zice că Intel s-a săturat de problemele lui x86; în viitoarea arhitectură anunțată (de foarte, foarte multă vreme), IA64, Intel va implementa un procesor RISC cu 128 de regiștri. Să-i ajungă.



Note

... scade)1
Despre cache-uri am scris cu mai mult timp în urmă în PC Report mai multe articole ample.
... paralel2
Pentru o comparație sumară între expresivitatea metodelor statice (compilarea) și a celor dinamice vedeți și articolul meu din PC Report din luna iunie 1999, despre debugger-e.