Mihai Budiu -- mihaib+@cs.cmu.edu
http://www.cs.cmu.edu/~mihaib/
18 iunie 1999
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.
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.
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.
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.
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.
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.
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ă:
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).
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ță.
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:
Î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.
Î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.
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:
Î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.
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ă!
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.
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.
Î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ă.