Investigații asupra limitelor de paralelismOptimizatoarele de cod (schedulere) destinate arhitecturilor avansate de microprocesoare (superscalare, VLIW) reușesc performanțe medii de 1- 2 instrucțiuni / tact, încă modeste având în vedere forța hardware a acestor mașini. Până unde am putea spera să ajungem prin schedulere mai performante? Ce determină actualele optimizatoare să obțină doar performanțele menționate? Unde ar trebui acționat în viitor pentru apropierea realului de idealul posibil? Acest articol încearcă să răspundă, fie și parțial, câtorva asemenea întrebări.
Această prezentare încearcă să răspundă la o problemă, credem noi, fundamentală, și anume: mai putem spera la rezultate spectaculoase de la acest domeniu al exploatării paralelismului la nivel de instrucțiuni în cadrul hard-soft al microprocesoarelor avansate (ILP- Instruction Level Parallelism)? Altfel spus, mai există potențial de performanță neexploatat relativ la schedulingul (rearanjarea instrucțiunilor programului obiect în vederea execuției sale optimale) static? După cum se va vedea, pe o bază de simulare cantitativă, răspunsul meu va fi unul optimist. În ultimii ani, se manifestă un interes deosebit pe plan mondial în dezvoltarea unor metode și algoritmi de scheduling static global pentru arhitecturile MEM (Mașini cu Execuții Multiple ale instrucțiunilor mașină). Aceste schedulere - unele chiar integrate în compilatoare [Hwu95] - asamblează în așa-numite grupuri, instrucțiuni independente din program, în scopul execuției simultane a instrucțiunilor aparținând aceluiași grup. Această investigație realizată de grupul de arhitecturi avansate de la Universitatea din Hertfordshire, UK, condus de profesorul Gordon B. Steven, împreună cu autorul acestui articol, se bazează pe arhitectura HSA (Hatfield Superscalar Arhitecture). Arhitectura HSA dezvoltată la Universitatea din Hertfordshire, U.K., reprezintă o arhitectură microprocesor superscalară- VLIW ( Very Long Instruction Word) hibridă, care aduce anticipat din cache-ul de instrucțiuni (I-CACHE), instrucțiuni multiple într-un buffer de prefech. În fiecare tact, logica de decodificare trimite In-Order spre execuție, din bufferul de prefech, cât mai multe instrucțiuni independente pentru a fi executate în paralel. Optimizarea programelor se face static, după compilare, printr-un scheduler special conceput, deosebit de complex- conține cca. 65.000 linii sursa de C [Col95, Ste96] ! Scopul acestei cercetări este de a măsura gradul de ILP existent în benckmark-urile Stanford, compilate special pentru arhitectura HSA utilizând compilatorul GNU CC de sub Unix [Col95]. Aceste 8 benchmark-uri au fost scrise în C și propuse de către profesorul John Hennessy de la Universitatea din Stanford, U.S.A., cu scopul de a constitui numitorul comun în evaluarea performanțelor arhitecturilor ILP. Ele sunt considerate deosebit de reprezentative pentru aplicațiile de uz general (non-numerice) și realizează aplicații generale precum: sortări (bench-urile bubble, tree și sort), aplicații puternic recursive (bench-urile: perm, puzzle, tower-problema turnurilor din Hanoi), și alte aplicații clasice (matrix- procesări de matrici, queens - problema de șah a celor 8 regine). În urma compilării acestor benchmark-uri C, s-au obținut programe asamblare HSA (*.ins). Principiul metodei utilizate în investigare se bazează pe implementarea unui simulator TDS (Trace Driven Simulator), care să lucreze pe trace-urile HSA (*.trc) ale bench-urilor Stanford. Aceste trace-uri, reprezentând în principiu toate instrucțiunile mașină HSA dintr-un program, scrise în ordinea execuției lor și memorate într-un fișier, s-au obținut pe baza simulatorului HSA dezvoltat anterior [Col95]. Acest simulator procesează benchmark-urile Stanford gata asamblate și generează parametrii compleți aferenți procesării, precum și trace-urile în diverse forme. De precizat că trace-urile utilizate conțin între cca 200.000 și 900.000 de instrucțiuni mașină HSA. În principiu, TDS analizează secvențial toate instrucțiunile dintr-un anumit trace HSA. Fiecărei instrucțiuni i se asociază un parametru numit PIT (Parallel Instruction Time), semnificând numărul impulsului de tact în care instrucțiunea respectivă poate fi lansată în execuția propriu-zisă. Aceasta înseamnă că în acel moment, operanzii sursă aferenți instrucțiunii respective sunt disponibili. Dacă o instrucțiune următoare este dependentă RAW (Read After Write) printr-un registru sau printr-o variabilă de memorie de instrucțiunea curentă, atunci ei i se va aloca un nou PIT dat de relația: PITnou = PITvechi + L, unde: L = latența instrucțiunii curente Acest proces de alocare PIT continuă în mod similar până la finele trace-ului. Instrucțiuni arbitrar plasate în trace pot avea același PIT, semnificând deci faptul că- teoretic cel puțin- pot fi executate în paralel. Se consideră că arhitectura are resurse (unități funcționale, regiștri, etc.) infinite, astfel încât, oricât de multe instrucțiuni independente pot fi executate în paralel la un moment dat. De asemenea, se ignoră hazardurile false de tip WAR (Write After Read) și WAW (Write After Write), considerându-se deci un renaming perfect, analiză anti-alias perfectă a adreselor instrucțiunilor Load/ Store și o predicție perfectă a branch-urilor (model ORACLE). În final se obține gradul teoretic de paralelism disponibil: IRteoretic = N/ PITmax, unde N = numărul total de instrucțiuni din trace. De remarcat că dacă un asemenea model idealizat ar deține mecanisme de forwarding prin implementarea unor algoritmi de tip Tomasulo [Vin97], s-ar reduce la maximum posibil citirile din seturile de regiștri. Astfel, s-ar diminua deci hazardurile structurale la regiștri. Acest indicator este esențial întrucât va lămuri dacă există suficient paralelism în programele de uz general care să justifice în continuare cercetările în scheduling, întrucât realizările actuale cele mai performante comunică rate de procesare de până la 1.2-2.4 instr./tact, pe procesoare capabile teoretic la 6-8 instr./tact [Col95]. După cum se va vedea, răspunsul va fi unul pozitiv. O altă problemă, implicată de cele prezentate până acum, este următoarea: de ce nu se obține IRteoretic în practică? Răspunsul este: datorită unor limitări fundamentale, obiective, dar și datorită unor limitări artificiale. O limitare fundamentală se referă la chiar conceptul de scheduling static. Acesta este nevoit să fie uneori, inevitabil, conservator, datorită informațiilor necunoscute în momentul compilării programului [Fra92, Col95]. Dintre celelalte limitări fundamentale amintim: hazardurile structurale, de date și de control. Limitările artificiale sunt date de conservatorismul, teoretic evitabil, al schedulerelor actuale și după cum vom arăta, limitează serios performanța acestora. De exemplu, buclele (loops) constituie o astfel de limitare. Multe schedulere forțează execuția serială a iterațiilor unei bucle de program, deși ar fi posibilă paralelizarea acestor iterații prin tehnici deja cunoscute precum cele de loop unrolling sau software pipelining [Vin97]. De asemenea, majoritatea schedulerelor actuale nu permit execuția instrucțiunilor dintr-o buclă până când toate instrucțiunile precedente buclei nu s-au executat. Analog, la ieșirea din buclă. O limitare similară cu cea introdusă de bucle o introduc procedurile. Un alt exemplu îl constituie reorganizarea statică (execuția Out of Order) a instrucțiunilor LOAD/STORE. Schedulerele actuale nu permit sau permit în limite foarte strînse acest lucru, întrucât problema dezambiguizării (analiză antialias) referințelor la memorie nu este încă pe deplin rezolvată [Hua94]. Această problemă constă în determinarea adreselor de acces aferente instrucțiunilor LOAD/ STORE, înaintea execuției lor. Dacă, de exemplu, s-ar ști că adresa unui LOAD diferă întotdeauna de cea a unui STORE, ele s-ar putea executa în afara ordinii normale, cu mari beneficii asupra timpului global de execuție al programului respectiv. Din păcate un scheduler pur static nu poate distinge întotdeauna dacă două referințe la memorie sunt permanent diferite pe timpul execuției programului. În fine, o altă limitare de acest tip o constituie latența mare a unor instrucțiuni sau memorii care se așteaptă să fie reduse în viitor prin progrese arhitecturale sau/și tehnologice. În cele ce urmează, se vor cuantifica pierderile de performanță introduse prin aceste limitări, demonstrând totodată că există suficient potențial în acest domeniu, în care cercetările sunt doar la început. Se menționează că există câteva referințe bibliografice care abordează această problematică [Lam92, Wall91]. Din păcate, concluziile obținute nu concordă între ele datorită unor metodologii de lucru foarte diferite. Astfel, de exemplu, Wall consideră că rata maximă de procesare pe un procesor superscalar nu poate depăși 7 instr./tact. Acest lucru se datorează faptului că, în modelul său, schedulingul este exclusiv dinamic, realizându-se de fapt exclusiv prin hardware. Având în vedere capacitatea limitată a bufferului de prefetch, rezultatul obținut este absolut normal. Alții, pe modele mai agresive și prin scheduling static comunică potențiale mult mai optimiste cuprinse între 90 și 158 instr./tact [Lam92]. Astfel de ex. în [Lam92] se abordează problematica gradului de paralelism posibil, prin prisma relaxării constrângerilor determinate de instrucțiunile de ramificație. Se examinează aportul cantitativ asupra gradului ILP adus de trei tehnici: execuția speculativă cu predicție a instrucțiunilor de ramificație, analiza dependențelor impuse de ramificații și respectiv multithreading-ul. Execuția speculativă se referă la execuția în paralel cu instrucțiunea de salt, sau chiar anterior acesteia, a unei instrucțiuni situată în program după instrucțiunea de salt. O tehnică relativ uzuală constă în execuția speculativă a instrucțiunilor situate pe calea ce mai probabilă (trace-ul cel mai probabil) în a fi executată. Fetch-ul speculativ al instruc'iunilor poate mări de asemenea considerabil gradul de paralelism. Desigur, în cazul predicțiilor eronate ale instrucțiunilor de salt, efectele instrucțiunilor executate speculativ trebuie înlăturat. Analiza dependențelor ramificațiilor se referă la faptul că toate instrucțiunile executate speculativ în cazul unei ramificații greșit predicționate, se anulează. Această constrângere este uneori redundantă, conducând la acțiuni inutile, consumatoare de timp. De exemplu în cazul următor, asignarea c=2; nu depinde de salt și ca urmare poate fi executată speculativ în orice caz (saltul se face ori nu). if (a<0) b=1; c=2; Chiar dacă prin hardware este mai dificil, totuși compilatorul (scheduler-ul) ar putea detecta aceaste independențe de control și ca urmare, elimina această ineficiență. În caz contrar, efectul asignării c=2 trebuie anulat, ceea ce e evident inutil, în cazul proastei predicții a saltului condiționat (if). Mai mult, printr-o analiză serioasă, execuția speculativă în acest caz s-ar putea face peste mai multe ramificații. Multithreading-ul se referă la capacitatea unei mașini de a executa în paralel fluxuri distincte, independente, de instrucțiuni (procese) din cadrul unei aplicații. Să considerăm secvența: for (i=0; i<100; i++) if (A[i]>0) flux1(); flux2(); Într-un uniprocesor MEM va fi dificil și oarecum impropriu de exploatat la maximum paralelismul buclei flux1() împreună cu a procesului flux2(), chiar dacă cele 2 procese sunt independente de date. Acest lucru s-ar putea preta perfect însă pe o mașină MIMD (multiprocesor) unde s-ar putea crea 2 perechi independente de tip procesor- proces. În continuare, autorii evaluează gradul de paralelism disponibil în
programele de uz general pe baza unei metodologii tipice, de tip trace
driven simulation. Evaluările se fac pe mai multe mașini abstracte,
dintre care amintim următoarele tipuri reprezentative: BASE - mașină MEM convențională, caracterizată de faptul că o instrucțiune
nu se execută până când ramificația care o precede nu s-a încheiat.
Instrucțiunile de salt se vor executa secvențial, câte una pe ciclu
(tact). Pentru exemplificare, în figura Secvența de program și trace-ul aferent se prezintă o secvență de program cu 7 instrucțiuni independente de date, precum și trace-ul aferent execuției. Instrucțiunile 1, 2, și 5 sunt ramificații (BR- Branch). Se presupune că ramificațiile 2b și 5c din trace sunt predicționate greșit in trace, deci acestea nu ar permite execuții speculative. În figura Execuțiile trace-ului pe modele se prezintă execuțiile aferente acestui trace pe cele 4 modele anterior prezentate. Dacă pe modelul BASE, execuția trace-ului s-ar face în 8 tacte, pe modelul CD+MF se face in 5 tacte iar pe modelul SP în doar 3 tacte. Simularea acestor modele pe benchmark- urile SPEC '92 a condus la grade medii (armonice!) de paralelism [instr./tact], prezentate în tabel. Modelul ORACLE este unul perfect, în care singurele restricții sunt
date de dependențele de date de tip Read After Write între instrucțiuni
(în rest, se consideră predicție perfectă a salturilor, resurse hardware
infinite, bandă de fetch oricât de mare, etc.). Gradul teoretic IPL și limităriGRADUL TEORETIC DE PARALELISM În continuare se prezintă o investigație cantitativă asupra potențialului de ILP existent în aplicațiile uzuale, la care a contribuit și autorul. S-a considerat un procesor HSA cu resurse infinite, predictor de branch-uri perfect, renaming perfect al regiștrilor și dezambiguizare perfectă (model ORACLE). Așadar, timpul de execuție este restricționat doar de către dependențele reale de date (RAW), singurele care impun execuția serializată. Latența tuturor instrucțiunilor este de un tact, cu excepția celor de tip DIV care este 32 tacte și respectiv MUL, 3 tacte. Așadar, pe un model hibrid superscalar- VLIW idealizat, media armonică a ratelor de procesare (IR - Issue Rates) este de 19.45 instr./tact (media aritmetică ar fi de 55 instr./tact, mai optimistă). Toate raportările ulterioare se vor face relativ la acest model de bază. INSTRUCȚIUNI COMBINATE În [Vas93] se arată că s-a reușit proiectarea și implementarea în tehnologie CMOS a unor unități ALU complexe cu 3 intrări și care nu impun mărirea perioadei de tact a procesorului comparativ cu o unitate ALU clasică, având 2 intrări. Acest fapt a condus la ideea unor instrucțiuni ALU combinate care să conțină trei operanzi sursă în loc de doar doi. Așadar, ar cădea în sarcina schedulerului să combine 2 instrucțiuni ALU dependente RAW într-una singură combinată. Mai precis, o secvență de 2 instrucțiuni dependente RAW printr-un registru (R1), ca mai jos: ADD R1, R2, R3 ADD R5, R1, R9 va fi transformată de către scheduler în-tr-o instrucțiune combinată, care va avea același timp de execuție: ADD R5, R2, R3, R9. Această tehnică, posibil de aplicat atât prin hardware (combinarea instrucțiunilor în bufferul de prefetch), cât și prin software (scheduling), ar putea fi deosebit de agresivă întrucât ar acționa asupra unei limitări considerată până acum fundamentală și deci imposibil de depășit: dependența de date RAW. Se prezintă în continuare câteva evaluări cantitative ale acestei tehnici noi, pe arhitectura HSA și trace-urile Stanford. Modelarea s-a bazat pe atribuirea aceluiași PIT pentru 2 instrucțiuni dependente RAW din trace și care se pot combina conform unor reguli predefinite. După cum era de așteptat, instrucțiunile combinate generează o creștere semnificativă a performanței, mai precis cu 60% față de modelul precedent, obținându-se o medie armonică de 31.27 instr./tact. Consider acest câștig ca fiind suficient de ridicat, încât ideea instrucțiunilor combinate, implementabilă atât prin scheduler static, cât și prin hardware, să prindă teren în viitor [Vin98]. În continuare, se vor determina pierderile cantitative de performanță pe care diversele limitări artificiale le implică și vom analiza aceste rezultate. Cu alte cuvinte, vom măsura mai multe neputințe hard-soft actuale și vom vedea cu cât ne îndepărtează ele, concret, de aceste idealuri stabilite anterior. O LIMITARE: LATENȚA UNOR INSTRUCȚIUNI Se va determina deci creșterea de performanță, în ipoteza că toate instrucțiunile mașină ar avea latența de un tact. Cu alte cuvinte, se va încerca să se răspundă la următoarea întrebare: vor aduce viitoarele progrese în eficiența algoritmilor de înmulțire și împărțire, progrese semnificative? Răspunsul cantitativ la această întrebare este dat de următoarea figură, obținută pe baza metodei de analiză și a simulatorului implementat în acest scop. S-a obținut o medie armonică de 20.57 instr./tact, deci constatăm o creștere cu doar 5.7% față de modelul de bază, ceea ce arată clar că reducerea latenței instrucțiunilor DIV și MUL nu va putea aduce creșteri spectaculoase de performanță în execuția programele de uz general. Desigur, în cazul aplicațiilor cu un puternic caracter numeric, influența unor asemenea instrucțiuni ar fi importantă. LIMITĂRI DATORATE BUCLELOR DE PROGRAM Se va încerca să se determine cantitativ, degradarea ratei de procesare ideală anterior obținută, atunci când există simultan două limitări, specifice schedulerelor actuale: instrucțiunile dintr-o buclă nu se vor lansa în execuție până când toate instrucțiunile anterioare nu se vor fi terminat și respectiv instrucțiunile care urmează unei bucle nu se vor lansa în execuție până când toate instrucțiunile din buclă nu s-au lansat deja în execuție. Cu această restricție, am obținut următoarele rezultate: În continuare, se va determina degradarea de performanță introdusă de fiecare componentă: limitarea la intrarea în buclă și respectiv, la ieșirea din buclă, pentru a analiza contribuția fiecăreia în parte la degradarea ratei de procesare. Se constată că ratele medii armonice sunt cvasiegale în ambele cazuri, adică 9.61 respectiv 9.19 instr./tact, ceea ce arată că ambele restricții sunt practic la fel de importante. O altă limitare ar consta în forțarea execuției seriale a tuturor iterațiilor unei bucle, așadar ignorarea paralelizărilor în interiorul buclei prin tehnici de tip Loop Unrolling și Software Pipelining [Vin97]. Rezultatele obținute în acest caz se vor prezenta în continuare (Fig.10). Scăderea de performanță devine acum realmente dramatică, întrucât de la o rată ideală de 19.45 instr./tact s-a ajuns la una de 2.84 instr./tact, ceea ce înseamnă o degradare a performanței cu 584%! Această degradare se datorează exclusiv serializării execuției buclelor. Adevărul este că aici progresele au fost semnificative, paralelizarea în cadrul buclelor de program fiind oarecum satisfăcătoare la acest moment . LIMITAREA TOTALĂ A DEZAMBIGUIZĂRII REFERINȚELOR LA MEMORIE Se dorește aici, să se determine degradarea de performanță relativă la modelul de bază, pe care o implică o execuție In Order a instrucțiunilor de tip LOAD și STORE. Aceasta este o caracteristică a majorității schedulerelor actuale. Cu alte cuvinte, am modelat o procesare a instrucțiunilor, fără nici un mecanism de dezambiguizare (antialias) a referințelor la memorie, deci cu forțarea execuției In Order a instrucțiunilor LOAD, respectiv STORE. Menționez că majoritatea schedulerelor actuale nu au implementate mecanisme de dezambiguizare. Din nou se observă o scădere de performanță extrem de ridicată, de la 19.45 la doar 4.00 instr./tact, deci o reducere a performanței cu 380%. Se impun deci clar metode mai puternice de dezambiguizare a referințelor la memorie, comparativ cu cele deja existente, această provocare fiind una dintre cele mai importante în viitorul apropiat. MACROINSTRUCȚIUNI SAU PROCEDURI? Se știe că procedurile implică salvări/restaurări laborioase de contexte și totodată sunt mari consumatoare de timp. In lining-ul acestora ar mări semnificativ lungimea codului, dar ar micșora timpul de execuție. În cele ce urmează, prezentăm rezultatele obținute pentru un in- lining perfect al tuturor procedurilor. Acest model ignoră în simulare toate instrucțiunile de salvare/restaurare asociate procedurilor existente în programele benchmark utilizate. Rezultatele obținute prin simularea acestei idei sunt prezentate în figura 12. Se constată o creștere a gradului de paralelism de la 19.45 la 28.24 instr./tact, adică cu 45% mai mult, ceea ce este semnificativ. Concluzia autorului este că trebuiesc găsite aici soluții de compromis de tip in lining selectiv, pe baze euristice, întrucât se pare că beneficiile asupra performanței ar putea să fie majore. O euristică relativă la această selecție ar trebui să țină cont, în opinia mea, de lungimea procedurii și de cât de des este ea apelată. De asemenea, în același sens, este important dacă procedura respectivă mai apelează la rândul ei alte proceduri. În concluzie, în concordanță cu aceste investigații, performanța arhitecturilor
MEM poate fi serios îmbunătățită în opinia autorului, și nu numai prin
dezvoltarea următoarelor tehnici: tehnici agresive de paralelizare a buclelor de program ; Așadar, cred că ne putem aștepta în continuare la performanțe semnificative în domeniul microprocesoarelor avansate și datorate în primul rând unor îmbunătățiri ale compilatoarelor (schedulerelor) respective. Limitările actuale sunt în primul rând datorate nouă, minților noastre, domeniul ILP fiind încă departe de a fi epuizat, după peste 17 ani de cercetări asidue... în alte țări. Situația este oarecum similară în domeniul arhitecturilor cu paralelism masiv. Este încă o dovadă, dacă mai era necesară, că progresele ingineriei calculatoarelor sunt tributare mai întâi sărăciei ideilor (algoritmilor de procesare) și abia mai apoi lipsei unor tehnologii (hardware) puternice. Poate că o înțelegere mai profundă și mai complexă a acestui fapt la noi în țară, în mediile academice în primul rând, coroborată cu un management adecvat al cercetării prin instituționalizarea acesteia, ar putea naște proiecte și rezultate de primă mărime în știința și ingineria calculatoarelor, pe plan mondial chiar. BIBLIOGRAFIE BYTE România - martie 1998
(C) Copyright Computer Press Agora |