Calculatoare ne-universale:
implementarea programelor în hardware

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

mai 2001

Subiect:
sintetizarea automată de calculatoare specifice unei aplicații
Cunoștințe necesare:
cunoștințe elementare despre arhitectura calculatoarelor și limbaje de programare, elemente de C
Cuvinte cheie:
hardware, hardware reconfigurabil, compilare, sinteza de circuite


Cuprins




Un excurs istoric

Primele calculatoare construite erau foarte diferite de cele de astăzi. Nu mă refer aici la dimensiuni și capacitate (care depind doar de tehnologie), ci la structura lor fundamentală. Acele calculatoare erau construite pentru a rezolva o singură problemă; nu erau universale. Ele constau dintr-o colecție de unități funcționale, care puteau face calcule simple. ``Programatorii'' aveau sarcina de a conecta unitățile funcționale între ele cu sîrme, pe care le înfigeau manual în tot felul de mufe. De exemplu, dacă vroiau să calculeze (a+b)2, programatorii luau o unitate care făcea adunări și una care făcea înmulțiri și le cuplau ca în figura 1.

Figura 1: Implementarea în hardware a expresiei (a+b)2. Variabilele devin sîrme, iar operațiile sunt executate de unități funcționale.
\begin{figure}\centerline{\epsfxsize=3cm\epsffile{binom.eps}}\end{figure}

În anii '40 în domeniul calculatoarelor intră în scenă un genial matematician, pe nume John von Neumann. von Neumann analizează starea de fapt a calculatoarelor și scrie în 1945 un raport intitulat ``First Draft of a Report on the EDVAC'' (Prima ciornă a unui raport despre EDVAC), în care sugerează o arhitectura revoluționară. În această arhitectură, programul nu mai este reprezentat de felul în care sunt cuplate unitățile funcționale, ci este stocat în memorie, fiind descris folosind un limbaj numit cod-mașină. În cod-mașină, operațiile de executat sunt codificate sub forma unor numere numite instrucțiuni. Programul de executat este descris printr-un șir de instrucțiuni, care se execută consecutiv.

Pe lîngă unitățile funcționale care fac operații aritmetice, calculatorul mai are o unitate de control, care citește instrucțiunile programului și care trimite semnale între unitățile funcționale pentru a executa aceste instrucțiuni. Rezultatele intermediare sunt stocate în memorie. Această arhitectură se numește ``von Neumann''. Dacă nu sunteți impresionați de această viziune radicală, este pentru că marea majoritate a calculatoarelor din ziua de azi sunt bazate pe această arhitectură; noțiunea de limbaj-mașină, și cea înrudită, de limbaj de programare, folosite pentru descrierea programelor, sunt concepte foarte naturale pentru toți cei care manipulează calculatoarele.

Se cuvine menționat faptul că ideea de a descrie un program folosind un limbaj (și nu prin conexiuni între unități funcționale) este mai veche; în 1936 Alan Turing folosise noțiunea de ``mașină Turing universală'' pentru a descrie un calculator universal, care poate executa orice program. Programele erau stocate în memoria calculatorului, reprezentate ca șiruri de numere.

Modelul spațial de calcul

Spuneam că marea majoritate a calculatoarelor digitale construite astăzi au o arhitectură von Neumann. Dar nu toate; există încă ``calculatoare'' bazate pe arhitectura veche, în care unitățile funcționale sunt legate între ele prin sîrme și nu există un program stocat în memorie.

Modelul von Neumann are o virtute excepțională: flexibilitatea. Folosind același hardware putem executa oricîte programe, toate diferite între ele. Prețul care trebuie însă plătit este performanța: unele operațiuni nu se pot descrie foarte eficient prin instrucțiunile disponibile, și s-ar putea implementa mult mai bine direct în hardware; figura 2 prezintă un astfel de exemplu extrem.

Figura 2: Implementarea unui program care pune biții dintr-un octet în ordine inversă, în software (în limbajul C) și respectiv hardware. Execuția în software necesită cîteva zeci de instrucțiuni, pe cînd cea în hardware se face practic instantaneu.
\begin{figure}\centerline{\epsfxsize=10cm\epsffile{inversare.eps}}\end{figure}

Ca atare, atunci cînd este nevoie de performanță deosebită, sau cînd flexibilitatea nu este foarte importantă, inginerii construiesc în continuare calculatoare specializate. De exemplu, ruterele de mare viteză de pe coloana vertebrală a Internetului trebuie să proceseze pachetele cu informații la viteze uluitoare (au la dispoziție doar cîteva zeci de nano-secunde pentru fiecare pachet). Ca atare, unele din funcțiile de clasificare și manipulare ale pachetului sunt implementate direct în hardware, într-un algoritm fixat. Chiar dacă performanța nu este critică, atunci cînd algoritmul de procesare este foarte bine standardizat, este adesea mai ieftin de folosit un astfel circuit specializat, numit ASIC (Application-Specific Integrated Circuit). Chiar și într-un calculator obișnuit se găsesc de obicei multe astfel de circuite pentru manipularea perifericelor: plăci de rețea, controlere de magistrală, etc.

Hardware reconfigurabil

În articolul meu anterior din NetReport am discutat despre o posibilă evoluție a tehnologiilor electronice, nanotehnologiile, care ne vor permite să construim circuite digitale cu miliarde de porți logice. În acel articol am sugerat că aceste circuite imense vor putea fi folosite cel mai eficient sub formă de hardware reconfigurabil. Hardwareul reconfigurabil este un model de calcul foarte asemănător cu cel de acum cincizeci de ani: constă dintr-o ``mare'' de porți logice universale, care pot fi programate individual pentru a implementa orice funcție logică, și două rețele: una care leagă porțile între ele, și care poate fi configurată în felurite moduri pentru a lega și dezlega porțile, și una de configurație, care este folosită pentru a transporta informațiile de configurare spre porți și spre cealaltă rețea.

Folosind hardware reconfigurabil putem sintetiza circuite specifice fiecărei aplicații; de data asta, însă, în loc de a conecta unitățile funcționale manual, le cuplăm în mod electronic, schimbînd felul în care sunt cuplate porțile logice.

În articolul de față voi arăta discuta mai pe larg cum se poate transforma un program într-un circuit și ce fel de proprietăți are acest nou model de execuție.

Limbaje de descriere a hardware-ului (HDL)

Ideea de a descrie hardware folosind programe nu este de loc nouă; de fapt circuitele integrate digitale sunt construite chiar în acest fel: circuitul de construit este descris într-un limbaj special de programare, numit Hardware Description Language. Circuitul astfel descris este apoi prelucrat de o suită complicată de programe CAD (Computer-Aided Design), care optimizează circuitul, îl transformă în operații elementare, le plasează pe o suprafață plană și le conectează prin sîrme. În faza de proiectare, circuitul descris într-un HDL poate fi simulat, pentru testare și depanare.

La ora actuală există două limbaje foarte importante de descriere a hardware-ului, care au fiecare susținătorii lor aprigi; unul dintre ele se numește VHDL iar celălalt Verilog. VHDL este prescurtarea a două prescurtări: Vhsic HDL, unde VHSIC înseamnă ``Very High Speed Integrated Circuits''. Verilog vine de la ``VERifying LOGic'', dar limbajul este folosit nu numai pentru a simula și verifica circuite logice (cum a fost conceput inițial, și după cum arată numele său), ci și pentru a le proiecta și implementa (sinteza de hardware; hardware synthesis).

Cele două limbaje sunt relativ similare ca putere de expresie, dar incompatibile între ele. Sunt de asemenea destul de diferite de celelalte limbaje obișnuite de programare: în limbajele HDL programatorul exprimă un circuit ca o colecție de sub-circuite care operează în paralel (paralelismul este explicit în program). Variabilele sunt semnale electrice, iar operațiile descriu unități funcționale. Nu există funcții recursive, structuri de date complicate sau manipulare dinamică a memoriei (malloc/new/free).

Hardware din limbaje de nivel înalt

Verilog și VHDL sunt foarte potrivite pentru a descrie circuite, însă sunt puțin potrivite pentru felul în care gîndesc oamenii. În general, oamenii au probleme în a-și imagina mai multe procese care se petrec concurent și comunică între ele; din cauza asta calculatoarele paralele nu au avut prea mult succes, și tot din cauza asta programarea aplicațiilor cu mai multe fire de execuție (threads) este un exercițiu de disciplină și nervi de fier.

Ca atare, de multă vreme unele grupuri de cercetare încearcă să folosească limbaje mai simple și mai naturale (de genul Pascal/C) pentru a descrie hardware. (Dacă limbajele acestea nu vi se par naturale, înseamnă că nu ați încercat să descrieți un sistem complex în Verilog!).

Tentativa de a genera hardware din limbaje obișnuite de programare se lovește de mai multe obstacole. În primul rînd, tehnologia pentru extragerea paralelismului dintr-un program scris într-un limbaj ``secvențial'' (ca C sau Fortran) este nesatisfăcătoare; ori paralelismul este principalul avantaj al unui model de execuție în hardware.

În al doilea rînd, limbajele de genul C sau Fortran folosesc tot felul de construcții care nu au un corespondent direct în hardware, cum ar fi funcții recursive, memorie alocată dinamic, sau structuri de date complicate. În ce fel se pot traduce acestea în hardware într-un mod eficient este un subiect activ de cercetare.

În cele ce urmează voi ilustra cum se pot traduce în hardware operațiile fundamentale ale unui limbaj de programare.

O instrucțiune

Pentru a traduce o operațiune simplă în hardware, asociem variabilele cu ``sîrmele'', și operațiile cu unități funcționale, după cum am anticipat și mai devreme. Figura 1 ilustrează o astfel de transformare.

Un bloc de instrucțiuni

În limbajele de nivel înalt valorile sunt stocate în variabile; în codul mașină ele sunt atribuite unor regiștri, sau sunt stocate în memorie. Cînd avem de-a face cu un bloc de instrucțiuni consecutive care manipulează doar regiștri, le putem traduce în hardware transformînd fiecare registru într-o sîrmă, ca în figura 3.

Figura: Un bloc de instrucțiuni și circuitul corespunzător. Observați cum variabilele devin sîrme. Variabila b este folosită de două ori, deci devine două sîrme diferite, b și b’. Observați de asemenea cum operațiile & și + sunt executate simultan.
\begin{figure}\centerline{\epsfxsize=7cm\epsffile{bloc.eps}}\end{figure}

Instrucțiuni de control

În limbajele de nivel înalt avem construcții care selectează între diferite instrucțiuni care urmează să se execute, cum ar fi if-then-else. Pentru a le traduce pe acestea în hardware avem mai multe alternative. În figura 4 ilustrăm o posibilitate care exploatează la maximum paralelismul dintre instrucțiuni, executînd simultan părțile then și else, și selectînd doar rezultatele necesare.

Figura 4: Implementarea instrucțiunilor de control al execuției în mod speculativ: executăm simultan ramurile if, then și else și păstrăm numai rezultatul corect. Trapezul este un multiplexor, cu trei intrări: un selector, desenat în lateral, și două valori între care se selectează. Ieșirea multiplexorului este intrarea din stînga dacă selectorul este 0 și intrarea din dreapta dacă selectorul este 1.
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{control.eps}}\end{figure}

Acest gen de execuție se numește speculativă, pentru că execută mai mult decît este strict necesar și selectează numai ceea ce e necesar la sfîrșit. Și microprocesoarele moderne folosesc o formă de execuție speculativă, pe care am descris-o mai demult într-un articol din PC Report despre predicția salturilor.

Accese la memorie

Una dintre cele mai puternice trăsături ale limbajelor de nivel înalt este capacitatea de a manipula matrici, care se bazează pe posibilitatea de a adresa memoria în mod indirect. Cu alte cuvinte, citim conținutul unei celule de memorie a cărei adresă a fost calculată.

Accesele indirecte nu pot fi transformate pur și simplu în sîrme; trebuie să folosim memorii hardware pentru a stoca matrici. În plus, atunci cînd avem cod executat în mod speculativ, trebuie să fim atenți să nu executăm decît accesele la memorie corecte, pentru că altfel vom ``strica'' conținutul memoriei.

Figura 5: Pentru a implementa matrici folosim memorii în care adresăm cu indicele din matrice. Citirea din matrice este o citire din memorie, iar scrierea în matrice este o scriere în memorie.
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{memorie.eps}}\end{figure}

Figura 5 ilustrează implementarea unei bucăți de cod care conține accese la memorie.

Bucle

Lucrurile devin mai interesante atunci cînd avem de executat bucle. Circuitul pe care-l implementăm nu mai este un simplu circuit combinatorial, în care semnalul se propagă într-un singur sens. El devine un circuit secvențial, cu o buclă de feed-back. Bucla de feed-back trebuie să fie întreruptă de un registru controlat de un ceas, care sincronizează propagarea tuturor semnalelor din buclă.

Figura 6: Implementarea (ușor simplificată) a unei bucle. Un registru citește noua valoare a lui i la fiecare tact de ceas și o memorează pînă la următorul tact. Bucla este pornită în execuție punînd semnalul de inițializare pe 0 (după aceea semnalul trebuie să rămînă 1 pînă la terminarea buclei). Semnalul de terminare a buclei indică momentul cînd toate iterațiile s-au terminat.
\begin{figure}\centerline{\epsfxsize=12cm\epsffile{bucla.eps}}\end{figure}

Figura 6 ilustrează o posibilă implementare a unei bucăți de cod care conține o buclă.

Apeluri de procedură

Cînd avem un program compus din mai multe proceduri, fiecare procedură poate fi implementată ca un circuit separat. Procedura curentă, în curs de execuție, corespunde circuitului activ. Controlul este transmis între proceduri prin semnale care activează procedura chemată.

O problemă ceva mai complicată este că atunci cînd procedura chemată se termină, trebuie să sară la o bucată de cod diferită de fiecare dată (la chemătorul ei). Acest lucru poate fi realizat în mai multe feluri; de exemplu, fiecare procedură primește un parametru suplimentar, care este chemătorul său; pentru terminarea procedurii, se poate sintetiza o bucată de hardware care selectează dintre toți chemătorii posibili bazat pe valoarea acestui parametru și-i trimite un mesaj cînd procedura curentă și-a terminat execuția.

Această implementare nu funcționează pentru procedurile recursive, care mai au nevoie și de o stivă; deocamdată nu avem la-ndemînă o soluție eficientă pentru a trata astfel de cazuri.

Rezultate preliminare

Pentru a estima impactul unui asemenea model de calcul asupra performanței am făcut un studiu preliminar, care face o mulțime de asumpții simplificatoare. Sperăm că modelul real de calcul nu va da rezultate substanțial diferite de idealizarea noastră.

Cel mai ``idealizat'' aspect al analizei noastre constă în cantitatea de informație pe care am folosit-o despre program și zonele de memorie pe care le folosește: am presupus că știm exact ce adrese de memorie vor fi accesate de fiecare instrucțiune de citire și scriere din memorie. Această informație a fost colectată executînd programul modificat pentru a colecta informații despre propria sa comportare (un astfel de program se numește instrumentat).

Un program desfășurat

Figura 7 arată un astfel de program desfășurat și așezat în plan.

Figura 7: Un program așezat în plan. Fiecare pătrat reprezintă 100 de unități, unde o instrucțiune aritmetică simplă sau un cuvînt de memorie ocupă 1 unitate. Un pătrat verde conține numai memorie, iar un pătrat alb conține numai instrucțiuni. Nuanțe intermediare indică mixturi de instrucțiuni și memorie. Liniile roșii indică transfer de control între blocuri consecutive de instrucțiuni, iar liniile albastre indică accese la memorie. Grosimea unei linii este proporțională cu logaritmul frecvenței cu care acea linie este utilizată. De exemplu, o linie de 10 ``pixeli'' a fost utilizată de program de 210 = 1024 de ori. Liniile groase sunt deci mult mai importante decît cele subțiri.
\begin{figure}\centerline{\epsfxsize=10cm\epsffile{graf.eps}}\end{figure}

Fiecare program este reprezentat sub forma unui graf, în care nodurile sunt instrucțiuni sau memorii și în care muchiile sunt transfer de execuție între instrucțiuni sau accese la memorie. Toate programele pe care le-am analizat1 au trăsături foarte similare:

Analizînd graful din figură am descoperit că una dintre cele două stele este în corpul funcției memcpy. Dacă ne gîndim puțin, vom realiza că acest lucru este foarte natural: toate structurile de date ale programului care sunt copiate vor fi atinse de această funcție.

Modelul computațional

Dacă am luat un program și l-am ``întins'' pe o suprafață, întrebarea următoare este: ``cît de repede merge''? Pentru a putea răspunde, trebuie să precizăm alte cîteva lucruri despre modelul nostru computațional:

Duplicarea codului

Pornind de la acest model am evaluat performanța programelor. Rezultatele au fost amestecate. Am căutat apoi metode de a îmbunătăți performanța prin transformări simple.

Primul obiectiv asupra căruia ne-am îndreptat atenția au fost ``stelele''; acestea sunt detrimentale performanței, pentru că, avînd mulți vecini, unii dintre aceștia vor fi în mod necesar plasați la distanță mare de centru, deci vor fi accesați foarte greu.

Ne-am întrebat: nu am putea cumva să ``spargem'' o stea în bucăți, în așa fel încît să facem două stele mai mici? Răspunsul este: da, și chiar foarte simplu. Tot ce trebuie făcut pentru programul din figură este să duplicăm codul funcției memcpy și să aranjăm ca din locuri diferite să fie chemate copii diferite. O tehnică foarte simplă pentru a realiza acest lucru se numește în compilatoare ``inlining'', în care funcția chemată este inserată textual în codul chemătorului.

După ce am aplicat această transformare, am obținut graful din figura 8.

Figura 8: Programul din figura 7 după ce corpul funcției memcpy a fost duplicat prin inlining. Observați cum stelele sunt mult mai mici și mai bine plasate.
\begin{figure}\centerline{\epsfxsize=10cm\epsffile{graf-inline.eps}}\end{figure}

Performanță

Rezultatele au fost destul de interesante. Am comparat performanța acestor programe cu execuția lor pe un microprocesor Alpha 21164 la 500 Mhz. Am presupus că în implementarea spațială vom putea executa o operație pe ciclu de ceas și că vom putea folosi aceeași frecvență de ceas cu Alpha.

În medie programele noastre funcționează ceva mai puțin de 2 ori mai încet decît pe Alpha, dar unele dintre ele merg mai rapid, după cum se vede în figura 9, în stînga. Graficul din dreapta arată cum își petrece timpul fiecare din programe.

Figura 9: În stînga este raportul dintre timpul de execuție al programului executat pe un microprocesor Alpha și pe un model spațial de calcul. Valoarea zero indică egalitatea timpului de execuție. O valoare negativă indică execuție mai rapidă în hardware, pe cînd o valoare pozitivă indică execuție mai rapidă pe Alpha. În dreapta este ilustrat timpul de execuție al fiecărui program. Culoarea verde indică timp petrecut așteptînd ca citiri din memorii de la distanță să returneze rezultatul. Albastru este pentru timp în care se execută calcule utile. Negru arată timpul petrecut transferînd control între blocuri consecutive, și galben măsoară timpul de transfer al datelor între blocuri consecutive. Porțiunile verde și negru pot fi probabil reduse prin optimizări mai agresive, cum ar fi folosirea de cache-uri și respectiv execuție speculativă.
\begin{figure}\centerline{\epsfxsize=16cm\epsffile{performanta.eps}}\end{figure}

Cercetări viitoare

Acest text ilustrează cercetările noastre preliminare în domeniul modelului spațial de execuție; foarte multe lucruri mai rămîn de făcut. Rezultatele noastre sunt însă încurajatoare: avem o metodologie care ne permite să compilăm programe destul de complicate iar performanța nu este substanțial degradată față de modelele de calcul convenționale.

Va trebui însă să dezvoltăm o grămadă de tehnici noi, plecînd de la construcția hardware-ului reconfigurabil însuși, trecînd prin metode de compilare și scule de simulare mai sofisticate, care iau în considerare mai multe detalii despre arhitectura reală a unui astfel de sistem.

Alte surse de informație



Note

... analizat1
Am analizat o serie de programe reprezentative scrise în limbajul C.
... 10)2
Numărul de muchii într-un graf poate fi pătratic în cel de noduri.