HATFIELD SUPERSCALAR SCHEDULER

6Organizarea i proiectarea microarhitecturilor

MODALITI DE EVALUARE A PERFORMANTEI SISTEMELOR DE CALCULTOPICI de urmrit n cadrul cursului

METRICI DE EVALUARE A SISTEMELOR DE CALCUL

ALEGEREA METRICILOR.LEGEA LUI AMDAHL

SIMULATOARE SOFTWARE DEDICATE MICROARHITECTURILOR DE CALCUL.METODOLOGII DE SIMULARE.TOOLS-URI SI BENCHMARK-URI STANDARDIZATE.ECUATIA DE STABILIRE A PERFORMANEI PROCESORULUI (CPU)METRICI DE EVALUARE A SISTEMELOR DE CALCUL: PERFORMANA DE PROCESARECa i architect de microprocesoare scopul principal l constituie realizarea unor compromisuri ntre urmtoarele METRICI: Performan de procesare, Putere disipat, Arie de integrare, Complexitate, Cost, Suportul oferit aplicaiei, Funcionalitate, Compatibilitate ntre modele aparinnd aceleai clase, Fiabilitate

Odat cu stabilirea unui set de cerine funcionale ale sistemului, arhitectul de microprocesoare trebuie s optimizeze procesul de proiectare. Optimalitatea n proiectare depinde de metrica aleas. Modificrile realizate n ultima decad n spaiul aplicaiilor cu sisteme de calcul au influenat n mod dramatic rolul metricilor. Sistemele desktop sunt analizate (msurate) prin prisma utilizatorilor individuali urmrindu-se optimizarea raportului cost-performan. Procesoarele sistemelor desktop sunt complexe, cu execuie out-of-order i speculativ a instruciunilor. Serverele sunt optimizate din punct de vedere al fiabilitii, scalabilitii i al raportului cost - performan global msurat n tranzacii (operaii) per unitate de timp (secund, or) Sistemele dedicate sunt optimizate din punct de vedere al costului i al puterii consumate. Procesoarele embedded sunt mai simple, cu execuie in-order a instruciunilor, dedicate n general aplicaiilor de timp real. Nu conin structuri de predicie a ramificaiilor de program => nu exist execuie speculativ, nu (prea) conin cache-uri, trebuie evitat Worst Case Execution Time (sau s fie egal cu cazul general), conin anumite instruciuni sqrt, dedicate multimedia, etc. n acest sens se va urmri ulterior n cadrul acestui curs diferenele specifice dintre benchmark-urile de uz general (suita SPEC) i benchmark-urile embedded (suita EEMBC).Un sistem desktop (X) este mai performant dect altul (Y) dac execut acelai program ntr-un timp (TX) mai mic dect cel de-al doilea (TY). se urmrete reducerea timpului de execuie (sau de rspuns timpul scurs ntre nceputul i sfritul unui eveniment). Timpul de execuie (latena) reprezint inversul (reciproca) performanei de procesare Dac (X) este de n ori mai performant dect (Y) atunci:

Un server (SX) este mai performant dect altul (SY) dac execut mai multe tranzacii (operaii, programe tasks, jobs) n acelai interval de timp. Cantitatea de tranzacii (operaii, programe tasks, jobs, work) efectuat ntr-un interval de timp bine stabilit se definete throughput sau performana sistemelor server. n cazul serverelor nu se urmrete reducerea timpului de execuie ci creterea performanei (execuia unui numr mai mare de operaii n acelai interval de timp). Throughput (taskuri/secund) vs. Latena (secunde/pentru un task)Cea mai direct definiie a timpului de execuie o reprezint latena de terminare a unui task, incluznd accesele la disc, la memorie, activiti cu dispozitive periferice, alte interaciuni cu sistemul de operare. n cadrul sistemelor server, caracterizate de multiprogramare, procesorul (CPU) poate executa un alt program n timp ce ateapt finalizarea operaiilor de I/O (citire / scriere din fiier, etc) nefiind necesar n acest caz minimizarea timpului de execuie al task-ului principal. CPU_time timp folosit exclusiv de procesor pentru calcul intern dintr-un singur task, neincluznd timpul de ateptare pentru finalizarea operaiilor I/O sau pentru execuia altor task-uri. CPU_time nu este sesizat de utilizatorul sistemului. Acesta vede ntreg timpul de execuie.

CPU_time poate fi descompus n:

User_CPU_time = timp petrecut cu instruciunile programului. Focalizarea se face pe aceast metric n evaluarea i optimizarea microarhitecturilor de calcul de pe parcursul acestui curs. System_CPU_time = timp petrecut n cadrul sistemului de operare pentru execuia diverselor rutine solicitate prin program (accese la periferice, memoria video, ntreruperi software, etc). Depinde de fiecare SO pe care se execut task-ul respectiv. Poate reprezenta pna la 35% din CPU_time.METRICI DE EVALUARE A SISTEMELOR DE CALCUL: DISPONIBILITATEA, FIABILITATEA, DEPENDABILITATEAFor many years, most computer architects have pursued one primary goal: performance. Architects have translated the ever-increasing abundance of ever-faster transistors provided by Moores law into remarkable increases in performance. Recently, however, the bounty provided by Moores law has been accompanied by several challenges that have arisen as devices have become smaller, including a decrease in dependability due to physical faults.

The goal of a fault-tolerant computer is to provide safety and liveness, despite the possibility of faults.

A safe computer never produces an incorrect user-visible result. If a fault occurs, the computer hides its effects from the user. Safety alone is not sufficient, however, because it does not guarantee that the computer does anything useful. A computer that is disconnected from its power source is safe it cannot produce an incorrect user-visible result yet it serves no purpose.A live computer continues to make forward progress, even in the presence of faults. Ideally, architects design computers that are both safe and live, even in the presence of faults. However, even if a computer cannot provide liveness in all fault scenarios, maintaining safety in those situations is still extremely valuable.It is preferable for a computer to stop doing anything rather than to produce incorrect results. An often used example of the benefits of safety, even if liveness cannot be ensured, is an automatic teller machine (ATM). In the case of a fault, the bank would rather the ATM shut itself down instead of dispensing incorrect amounts of cash. DISPONIBILITATEA fraciunea din timpul total n care sistemul este disponibil pentru execuia oricrei aplicaii:

The availability of a system at time t is the probability that the system is operating correctly at time t.

FIABILITATEA The reliability / dependability of a system at time t is the probability that the system has been operating correctly from time zero until time t. Reliability is perhaps the best-known metric, and a well-known word, but it is rarely an appropriate metric for architects. Unless a system failure is catastrophic (e.g., avionics), reliability is a less useful metric than availability. Pentru servere este la fel de important disponibilitatea ca i performana. Pierderea financiar a unei companii cotate la burs n urma indisponibilitii serverelor proprii este de peste $6,450,000 / or. Mean Time Between Failures (MTBF) msoar timpul mediu ntre dou cderi succesive ale sistemului (ct timp serverul este utilizabil) Pentru harddiscul unui sistem desktop, uzual MTBF=500.000 de ore.

Mean Time to Repair (MTRR)

msoar timpul mediu necesar revenirii dintr-o cdere a sistemului

Pentru un server cu sarcini multe MTRR(0 ore (datorit redundanei oferite prin dublarea numrului de hardiscuri i copierea informaiei n dou locuri diferite)

Soluii pentru creterea fiabilitii sistemelor Redundana

informaional date de verificare suplimentar: check bits (paritate, coduri corectoare de erori)

hardware Mecanisme de check-pointing (salvarea strii sistemului la un moment dat i reluarea execuiei din acest punct) DEPENDABILITATEA n aplicaiile inginereti dependabilitatea reprezint o metric a disponibilitii, fiabilitii i suportului de mentenan a sistemelor. De asemenea, aceasta poate cuprinde i mecanisme menite s menin i s creasc fiabilitatea sistemelor. Prin cuvinte simple, sistemele dependabile (dependable systems) sunt sisteme de securitate critice. Se numesc astfel ntruct viaa noastr poate depinde de acestea. n cazul sistemelor de securitate critice timpul maxim de execuie al unei operaii trebuie s fie limitat i cunoscut, astfel nct timpul de reacie poate fi asigurat atunci cnd sunt necesare aciuni critice. Dependabilitatea poate fi analizat cunoscnd trei categorii de elemente:

Atribute Modaliti de evaluare a dependabilitii unui sistem Disponibilitatea efecturii corecte a unui serviciu Fiabilitatea continuitatea unui serviciu care funcioneaz corect

Siguran - absence of catastrophic consequences on the user(s) and the environment

Integritate - absence of improper system alteration

Mentenabilitate - ability for a process to undergo modifications and repairs Ameninri (pericole) - are things that can affect a system and cause a drop in Dependability. There are three main terms that must be clearly understood: Defecte: A fault (which is usually referred to as a bug for historic reasons) is a defect in a system. The presence of a fault in a system may or may not lead to a failure. For instance, although a system may contain a fault, its input and state conditions may never cause this fault to be executed so that an error occurs; and thus that particular fault never exhibits as a failure.

Erori: An error is a discrepancy between the intended behaviour of a system and its actual behaviour inside the system boundary. Errors occur at runtime when some part of the system enters an unexpected state due to the activation of a fault. Since errors are generated from invalid states they are hard to observe without special mechanisms, such as debuggers or debug output to logs.

Avarie (pan, rateu, insucces): A failure is an instance in time when a system displays behaviour that is contrary to its specification. An error may not necessarily cause a failure, for instance an exception may be thrown by a system but this may be caught and handled using fault tolerance techniques so the overall operation of the system will conform to the specification.

Mijloace de mbuntire a dependabilitii sistemelor - Ways to increase a system's dependability. Since the mechanism of a Fault-Error-Chain is understood it is possible to construct means to break these chains and thereby increase the dependability of a system. Four means have been identified so far: Prentmpinare Eliminare (ndeprtare) Predicie (Anticipare) Toleran la defectriMETRICI DE EVALUARE A SISTEMELOR DE CALCUL: PUTEREA DISIPAT Consumul de putere i disiparea termica a energiei au devenit obstacole importante n design-ul procesoarelor moderne cu performane ridicate. further increasing the clock frequency is also getting more and more difficult because (i) of heat problems and (ii) of too high energy consumption. The latter is not only a technical problem for both server farms and mobile systems, but in the future, it is also going to become a marketing weapon targeted at the growing number of environmentally aware consumers and companies in search of a greener computer.

Environment Protection Agency (EPA): computers consume 10% of commercial electricity consumption (2008) This include peripherals, possibly also manufacturing A Department of Energy (DOE) report suggested this percentage is much lower (3.0(3.5%)

Internet Data center growth was cited as a contribution to the 2000/2001 California Energy Crisis

Challenges about power consumption Understand where and why power is dissipated

Think about ways to reduce it at all levels of computing hierarchy (circuit level [Sch02], microarchitecture level e.g. Alpha EV8 processor integrated a huge hibrid branch predictor structure that costs 340Kbytes, consuming 10% of whole processor power). Procesoarele calculatoarelor portabile i cele constrnse energetic (durata scurt de via a bateriilor) se ateapt s produc performane similare cu procesoarele sistemelor desktop de mare performan.

Din ce n ce mai multe procesoare sunt integrate n dispozitive dedicate n care memoria disponibil este limitat, cum ar fi PDA-urile i sistemele mobile. Limitrile dimensiunii memoriei rezult din consideraii cum ar fi spaiul, greutatea, consumul de putere si costul de producie. Cercetrile au artat c viteza circuitelor (cu implicaii asupra performanei de procesare) se mbuntete cu aproximativ 2% pentru o reducere a temperaturii din cip cu 10(C [Sch02](if T(P( 10(C ( IPC ( 2%).

Metrici folosite:

P = [W]SI watt puterea medie instantanee = puterea medie disipat ntr-un ciclu de tact procesor

E = [J] SI joule energia = produsul dintre putere i timpul total de execuie: E = P * t. Aceast metric este n strns legtur cu timpul de via al bateriei sistemului dedicat

Sistemul de calculNumr nuclee per cipFrecvena de procesarePuterea medie instantanee

Server de ultim generaie~130170W

Desktop de ultim generaie

~70100W

Laptop de ultim generaie~30W

Laptop cu baterie optimizat~310W

Procesoare dedicate~0.51W

Procesoare de semnal (DSP)~100mW

Microcontrollere~10mW

Procesoare multicoreAMD Opteron X4 (Barcelona)42.5 GHz120W

Intel Nehalem42.5 GHz100W

IBM Power 624.7 GHz100W

Sun

Ultra SPARC T2

(Niagara 2)81.4 GHz94W

Tabelul 1. Consumul de putere pentru fiecare tip de sistem de calculPuterea dinamic reprezint principala surs de putere disipat n microprocesoarele realizate n tehnologie CMOS i este definit astfel:

,

Unde,

C este capacitatea circuitului ([nF]SI). Depinde de lungimea firelor, dimensiunea tehnologiei. Vdd (tensiunea de alimentare 2.2V) i f (frecvena procesorului) sunt determinate de procesul tehnologic cu toate c multe decizii de proiectare microarhitectural conduc la diminuarea frecvenei.

a factorul de activitate (numrul mediu de scrieri sau numrul de tranziii din 0 n 1 i invers) aferent fiecrei componente microarhitecturale.

Unde T reprezint timpul total de simulare / execuie msurat n perioade de tact iar P este puterea dinamic (Pd)Puterea static incepe s aib un aport tot mai mare la puterea total consumat.Puterea static este puterea consumat ntr-un sistem n absena oricrei comutaii si este definit ca produsul dintre tensiunea de alimentare i curentul static. Aceast pierdere este datorat dispozitivelor conectate la condensatori, cum ar fi tranzistori sau diode care, chiar dac sunt inchise conduc o cantitate mic de curent. Chiar dac acest current este foarte mic el poate descrca lent condensatorul. Imperfeciunile nedorite ale unor materialele dielectrice folosite n condensatori pot contribui la puterea static consumat. Materialul dielectric nefiind un izolator perfect permite circularea unui curent static (de pierdere) mic care va descrca lent condensatorul. Contribuia puterii statice la totalul de putere consumat intr-un sistem este preconizat s creasc in tehnologiile viitoare datorit cresterii exponeniale a curentului static pierdut odat cu scalarea tehnologiei. International Technology Roadmap for Semiconductors (ITRS 2006) [http://public.itrs.net/] anticipeaz c puterea static poate ajunge si la 50% din totalul de putere n urmtoarea generaie de procesoare.

Temperatura ajunge pn la 83(C (se pot gti ochiuri linitit). Cipul are 2.5x2.5 cm2Inductorii nu au o rezisten stabil n timp precum conductorii.

Variaia tensiunii instantanee (Vdd/Gnd Bounce calea direct a curentului ntre VDD i GND cnd ambii tranzistori NMOS i PMOS conduc) determin pentru cei 20 de ciclii de tactCPU apariia unui curent de scurgere.

LEGEA LUI AMDAHL (Legea scalabilitii totale)

Ideal ar fi ca un SMM dotat cu N procesoare s proceseze un program de N ori mai rapid dect un sistem monoprocesor, cerin numit scalabilitate complet. n realitate, acest deziderat de scalabilitate nu se realizeaz din multiple motive. n privina scalabilitii, aceasta este mai uor de realizat pe un sistem cu resurse distribuite dect pe unul avnd resurse centralizate, ntruct acestea din urm constituie un factor de strangulare a activitii.

Dintre cauzele care stau n calea unei scalabiliti ideale, se amintesc:

1. Gradul de secvenialitate intrinsec al algoritmului executat. Aa de exemplu, exist n cadrul unui algoritm operaii secveniale dependente de date i deci imposibil de partajat n vederea procesrii lor paralele pe mai multe procesoare.

100% = secvenial

------------------------------------------------------------------------------------------

(1-f)100%=paralelizabil

------------------------------------------------------------------------------------------

Accelerarea S pentru un SMM cu N procesoare este, prin definiie:

unde:

Ts = timpul de execuie pentru cel mai rapid algoritm secvenial care rezolv problema pe un monoprocesor (SISD)

TN = timpul de execuie al algoritmului paralel executat pe un SMM cu N (procesoare.

Dac notm cu f = fracia (procentajul) din algoritm care are un caracter eminamente secvenial, f([0,1], putem scrie:

adic

sau:

Legea lui G. Amdahl, 1(S(N (scalabil)

Legea lui G. Amdahl sugereaz c un procentaj (fx100%) orict de sczut de calcule secveniale impune o limit superioar a accelerrii (1/f) care poate fi obinut pentru un anumit algoritm paralel pe un SMM, indiferent de numrul N al procesoarelor din sistem i topologia de interconectare a acestora.

Se presupune, spre ex., ca f=10% din timp un program nu poate fi accelerat prin paralelizare pe un sistem cu N=100 de procesoare. Se consider c pentru a rula aceast parte secvenial de dou ori mai rapid decat pe un procesor simplu, este nevoie de un procesor complex (Out-of-Order) care are de 10 ori mai multe resurse (complexitate) decat procesorul simplu. Aplicand legea lui Amdahl, accelerarea obtinuta pe un sistem omogen cu 100 de nuclee simple este:S=1/[f+(1-f)/N]=1/[0,1+0,9/100]=9.17Daca utilizam N=90 procesoare omogene si un procesor OoO (echivalentul a zece procesoare omogene, i care ruleaz partea secventiala de doua ori mai rapid decat pe un procesor simplu) vom obtine urmatoarea accelerare (pe sistem eterogen):

S=1/[0,1/2+0,9/90]=16.67Totusi, superioritatea sistemelor eterogene fata de sistemele omogene va trebui dovedita mult mai convingator prin simulari complexe, atat pe benchmark-uri secventiuale cat si paralelizate (IPC, energie consumata, buget tranzistori, arie integrare etc.). De altfel, chiar si actualele multiprocesoare comerciale sunt neomogene, avand un nucleu superscalar out of order foarte puternic (IBM Cell BEA, Intel IXP procesoare de retea etc.) Dintre metricile succesului in cadrul dezvoltarii sistemelor multicore se amintesc:

productivitatea programrii

performana aplicaiei.

minimizarea acceselor la datele aflate n afara memoriilor locale optimizarea balansrii ncrcrii procesoarelor optimizarea comunicaiilor i sincronizrilorSIMULATOARE SOFTWARE DEDICATE MICROARHITECTURILOR DE CALCUL.

Simulatorul. Ce este? Este necesar simularea?

Istoria procesoarelor contrapune dou paradigme pentru creterea performanei, bazate pe software i respectiv pe hardware.

n procesul de proiectare al procesoarelor, aferent generaiilor viitoare, accentul principal nu se mai pune pe implementarea hardware, ci pe proiectarea arhitecturii n strns legtur cu aplicaiile poteniale. Se pornete de la o arhitectur de baz (generic), puternic parametrizat, care este modificat i mbuntit dinamic, prin simulri laborioase pe programe de test (benchmark-uri) reprezentative.

Simulator dedicat unei arhitecturi de calcul instrument software (aplicaie/program) utilizat n exploatarea / cercetarea / i mbuntirea performanelor unei microarhitecturi. De obicei funcionarea microarhitecturii se simuleaz la nivel de ciclu main permind vizualizarea tuturor resurselor hardware la finele fiecrui ciclu.

Provocari majore legate de metodologia de simulare si tehnologia software folosita in dezvoltarea simulatoarelor

Proiectarea si implementarea software Interfata cu utilizatorul si crearea resurselor. Nucleul functional al simulatorului.

Metodologia de simulare. Benchmark-uri. Optimizatoare de cod obiect (schedulere statice). Distribuirea simularii pe mai multe resurse hardware (arhitectura client server in retea) sau simularea pe o singura statie serial cate o configuratie microarhitecturala una dupa alta.

Modelarea capabilitatilor de simulare in functie de metricile urmarite Nucleul de procesare al microarhitecturii (unitati executie, statii rezervare, structura pipeline) Nivelul ierarhic de memorie: cache-uri de instructiuni / date L1, L2 sau chiar L3, DRAM Structuri de predictie implementate Arhitecturi ILP, TLP, monocore / multicore

Reducerea timpului de executie aferent unei simulari Sample simulation gasirea unui nucleu de instructiuni care aproximeaza executia intregului benchmark Implementarea unui Automatic Design Space Exploration Metode de cercetare euristica in spatiul tuturor parametrilor arhitecturii, compilatorului si al aplicatiilor pentru gasirea optimului din punct de vedere multicriterial (performanta de procesare, putere consumata, temperatura disipata, numar nuclee, etc.) Algoritmi de cautare locali (in vecinatatea unei configuratii microarhitecturale) de tip hill climbing, simulated annealing Metode avansate de invatare automata (machine learning), algoritmi genetici, algoritmi stigmergici bazati pe miscarea coloniilor de furnici, etc.

Simularea este necesar pentru c:

Dupa mai bine de douazeci de ani de preocupari in proiectarea si exploatarea arhitecturilor de calcul cercetatorii au ajuns la concluzia ca simulatoarele au devenit instrumente primordiale in cercetarea si dezvoltarea din domeniul stiintei calculatoarelor. Principalele avantaje ale simulatoarelor comparativ cu procesoarele reale sunt: costul de implementare si timpul de dezvoltare mai mic, flexibilitatea si extensibilitatea care permit arhitectului de microprocesoare sa evalueze mai rapid performanta unei plaje largi de arhitecturi si sa cuantifice eficienta fiecarei imbunatatiri (inovatii microarhitecturale sau optimizari la nivelul compilatorului). Cu toate acestea, timpul indelungat de simulare (zeci de ore pentru doar o singura configuratie arhitecturala) si acuratetea scazuta a rezultatelor simularii (sau imposibilitatea cautarii, analizei si simularii complete in spatiul enorm al tuturor parametrilor arhitecturii, compilatorului si al aplicatiilor) limiteaza eficienta simulatoarelor. Probabil cel mai important impediment ntlnit se datoreaz constrngerilor temporale; optimizarea unei arhitecturi dovedindu-se un proces lent care necesit putere de calcul considerabil. Pe langa importanta dovedita in domeniul cercetarii stiintei calculatoarelor in general si al arhitecturilor de calcul in special, in ultimul timp, simulatoarele au devenit instrumente pedagogice valoroase care permit studentilor s modifice interactiv parametrii configuraiilor hardware i s observe efectele lor ntr-o manier mult mai accesibil, sa vizualizeze componentele microarhitecturale si interactiunea dintre acestea, sa inteleaga si sa utilizeze mai bine principiile si conceptele teoretice din domeniu.Joshua J. Yi, David J. Lilja Simulation of Computer Architectures: Simulators, Benchmarks, Methodologies, and Recommendations, IEEE TRANSACTIONS ON COMPUTERS, VOL. 55, NO. 3, MARCH 2006.METODOLOGIA DE SIMULARE poate fi de dou (trei, dar a treia reprezint un hibrid ntre cele dou fundamentale) tipuri:

Execution driven simulation caracterizat de cunoaterea n fiecare moment (ciclu "pipe") a coninutului resurselor arhitecturale (regitri, locaii de memorie, uniti funcionale).

Simularea se face foarte detaliat, la nivel de ciclu de execuie al procesorului.

Outputs: - coninutul resurselor, gradul de ncrcare al acestora, rate de procesare, de hit etc.

Fiiere trace care conin toate instruciunile main ale programelor de test n ordinea n care se execut.

Trace driven simulation analizeaz secvenial toate instruciunile din trace-urile generate de simulatorul bazat pe execution driven, cu scopul de a determina instana optimal a arhitecturii - procesorul ce urmeaz a fi implementat n hardware. TDS se preteaz la simularea cache-urilor de date i instruciuni, mecanismelor de memorie virtual etc., datorit faptului c ofer pattern-uri reale de adrese, n urma execuiei unor programe reprezentative.

Figura 1. Etapele de simulare, comparare i determinare efectiv ale unei arhitecturi optime, pornind de la sursa HLL (High Level Languages) a programelor de test i pn la implementarea hardware a arhitecturii

Simulatoarele determina: performanta de procesare + model de putere (CACTI, WATCH) ( estimare putere /energie consumata + configuratie termica && configuratie microarhitecturala spatiala (Quilt, HotSpot) ( hotspots ( identificare DTM (manager termal dinamic).

Figure 0.2. The structure of the power consumption simulator

Figure 0.3. The thermal map of the Alpha 21364 architecure

Figure 0.4. The thermal map of the Alpha 21364 architecture enhanced with RB and LVPT

Din perspective tehnologiei software de implementare a simulatoarelor se disting platforme:

monolitice (SimpleScalar). Avantaje: disponibilitate gratuita, flexibilitate, portabilitate, extensibilitateDezavantaje: dificultatea depanarii si a reutilizarii codului la dezvoltarea unei arhitecturi noiExecution driven (cycle level) monocore: Simulatorul de cache-uri (sim-cache), de profil (sim-profile)

Predictorul de salturi (sim-bpred)

Simulatorul superspeculativ de complexitate ridicat out of order (sim-outorder)

Simulatorul TLP (cu paralelism simultan la nivelul firelor de executie msim)

Trace driven (trace level):

Simulatorul de (hotspot)

Execution driven (cycle level) multicore

Simulatorul TLP (cu paralelism simultan la nivelul firelor de executie multi2sim, msim-cmp)

modulare (UniSim).

Avantaje: permite simularea multicore-urilor

mediu de simulare modular (se pot dezvolta separat, crete ncrederea n implementare module mai mici, uor de testat)

interfee de comunicare standardizate intre module

metodologii diferite de simulare: Cycle level / Transaction level posibilitatea de a introduce simulatoare existente (wrapere), de a lega alte module (gen CACTI pentru consum de putere)

orientat obiect duce la reutilizare, dezvoltare facil a unei arhitecturi noiDezavantaje: dificultatea depanarii si complexitate ridicata la arhitecturi cu numar mare de core-uri, foarte instabil, documentaia redusa (inexistenta) a coduluiExecution driven (cycle level) monocore / multicore: procesor ARM cu un singur nucleu (arm-score) procesor PowerPC405 cu mai multe nuclee (ppc-mcore). procesor PowerPC405 cu un singur nucleu i care are integrat componenta de consum de putere (ppc-score_power_estimation). procesor PowerPC405 cu suport pentru thread-uri (se pot scrie benchmark-uri care pornesc fire de execuie, care sunt schedulate de procesor pe fiecare nucleu, pot fi sincronizri ntre aceste fire, se poate simula un comportament mult mai real al aplicaiilor i a dependenelor care exist ntre acestea)/opt/public/components/CycleLevel/simulators/ppc-pthread/cmpSimularea la nivel tranzactional in sistemele multiccore / many-core.

Apare datorita lipsei de productivitate din programarea paralela (in care este necesara pastrarea atomicitatii a variabilelor partajate prin sectiuni critice un singur procesor scrie la un moment dat o variabila) Modelarea la nivel de tranzacii = separarea comunicrii dintre module (hardware sau software) de implementarea lor (procesul computaional din sistem) Metodologia TLM este util n modelarea unor arhitecturi care executa programe paralele bogate in sectiuni critice (ex.: implementarea lock-unlock, bariere) si le inlocuiesc cu alternative checkpoint, commit, rollback specific tranzactiilor din bazele de date. procesor PowerPC cu doua nuclee (PowerPC-TLM)Alte instrumente software utile in analiza si proiectarea microarhitecturilor

Asambloare, link-editoare, debuggere. Cross-compilatoare

Creterea n performan i complexitate a microprocesoarelor moderne datorate tehnicilor avansate gen pipelining, execuie out-of-order , predicie i execuie speculativ, presupune un efort suplimentar de proiectare i verificare pentru dezvoltarea i implementarea de produse viabile. Pentru depirea acestor probleme, proiectanii de microarhitecturi au explorat diverse modaliti de transfer de funcionalitate la nivelul compilatorului. ncepnd cu procesoarele RISC VLIW i continund cu cele EPIC versiunile 1 i 2 de procesoare Intel Itanium, compilatorul a jucat un rol important n simplificarea arhitecturii la nivel hardware meninnd totodat tendinele curente de cretere a performanei.Asambloare i Link-editoare:./configure --host=i386-*-linux --target=sslittle-na-sstrix --with-gnu-as --with-gnu-ldDebuggere:gcc c g O *vpred.c

makegdb

Cross-compilatoare:crosstool-ppc405-4.1.1.tar.gzcrosstool-ppc750.tar.gzcrosstool-arm.tar.gzcrosstool-mips.tar.gz

ALEGEREA PROGRAMELOR REPREZENTATIVE PENTRU DETERMINAREA PERFORMANEI DE PROCESARECele mai bune soluii, n ordine descresctoare, sunt: ideal utilizatorul dorete simularea aplicaiilor reale, care sunt executate pe un sistem (compilatoare, procesoare de text, calcul tabelar, emulatoare de sisteme de operare, baze de date, jocuri, procesare de imagine / sunet). Aplicaiile reale au intrri / ieiri i diverse opiuni de selecie n momentul rulrii. Principal dezavantaj: lipsa portabilitii acestora (dependena de sistemul de operare i/sau de compilator). Sporirea portabilitii presupune modificarea codului surs i/sau eliminarea anumitor seciuni de gen grafic interactiv, etc, transformnd n final aplicaia. Folosirea programelor de test standardizate (benchmark-uri SPEC, SYSMARK). Benchmark-urile SPEC sunt programe reale modificate n vederea creterii portabilitii i minimizrii efectului dispozitivelor I/O asupra performanei. Un avantaj major al folosirii suitelor de benchmark-uri l reprezint faptul c slbiciunea oricrui benchmark este atenuat de prezena celorlalte programe de test. Orice concluzie se trage de pe urma simulrii ntregii suite. Simularea unor nuclee (kernels) ale aplicaiilor reale (Linpack, Bucle Livermore). Buclele Livermore reprezint o colecie de 24 structuri repetitive DO-loops implementate n Fortran. Constituie o mixtur de bucle vectorizabile i nevectorizabile care testeaz capabilitile de calcul ale sistemului hardware i abilitile software n compilarea eficient a codului n vederea vectorizrii buclelor de program. LINPACK reprezint o colecie de subroutine scrise n Fortran care analizeaz i rezolv sisteme de ecuaii liniare i probleme de complexitate cel puin ptratic. Nucleul LINPACK constituie o msur a puterii de calcul a unui sistem ce opereaz n virgul mobil. Toy Programs programe simple de test avnd pn la 100 de linii de cod i care produc rezultate apriori cunoscute de ctre utilizator. Exemple: Ciurul lui Eratostene, Quicksort, Puzzle, Hanoi, suita de benchmark-uri Stanford. Folosirea unor programe sintetice (dedicate) care imit din punct de vedere statistic comportamentul (frecvena operaiilor i a operanzilor, etc) a unui larg set de aplicaii. Sunt similare n filozofie cu benchmark-urile de tip kernel i utilizate de ctre proiectanii de compilatoare. Exemple: Whetstone, Dhrystone.BENCHMARK-URI STANDARDIZATE.

Benchmark-urile reprezint seturi de aplicaii dezvoltate pentru evaluarea celor mai importante metrici (performan, consum de putere, etc.) ale sistemelor de calcul (desktop, server, embedded, reele) i pot fi folosite pe diverse platforme (procesor + Sistem de Operare): UNIX, Linux i Microsoft Windows (dezvoltate de Microsoft).Benchmark-urile SPEC (Standard Performance and Evaluation Corporation) au fost dezvoltate de SPECs Open Systems Group (OSG), care nglobeaz peste 30 de productori de calculatoare, integratori de sisteme, autori si consultani din ntreaga lume.BAPCo (Business Applications Performance Corporation) reprezint un consoriu non-profit avnd ca scop principal dezvoltarea i distribuia unui set de benchmark-uri performante bazate pe aplicaii de uz general dar i pe sisteme de operare standardizate folosite n industrie. Rolul benchmark-urilor BAPCo este de a evalua tehnologiile implementate pe diferite platforme. Din BAPCo fac parte: AMD, Apple, ARCintuition, CNET, Dell, Hewlett-Packard, Intel, Lenovo, Microsoft, NVIDIA, Sony, Toshiba, VIA Technologies, ZDNet and Ziff Davis Media.TPC (Transaction Processing Council) a fost creat prin mijlocul anilor 1980 de ctre un grup de ingineri productori de calculatoare, integratori de sisteme. Scopul lor era de a crea un set de benchmark-uri realiste pentru procesarea tranzaciilor (msoar abilitatea sistemului de a manipula tranzacii, constnd n principiu n accese / interogri, actualizri ale bazelor de date). Performana este raportat n tranzacii per secund.SYSmark 2007 reprezint cea mai recent versiune de benchmark-uri BAPCo. Reflect patern-uri de aplicaii (Video creation, E-learning, 3D Modeling, Office Productivity) ale utilizatorilor (clieni) din domeniul economic. Caracterizeaz performana economic a unui client (aplicaii software dedicate sectorului economic pe platform Microsoft Windows Vista).

SPEC CPU2006 este a 5-a versiune major a seturilor de benchmark-uri SPEC CPU, care, n 1989 a devenit primul standard acceptat la scar larg pentru compararea performanelor la calcul intensiv pe o varietate de arhitecturi.

Tehnologia sistemelor de calcul se dezvolt aa de repede, nct trebuie s oferim noi pachete de benchmark-uri, pentru a asigura un mediu de testare adecvat. Benchmark-urile standardizate, trebuie s reflecte mbuntirile tehnologice aferente microprocesoarelor, noi compilatoare, aplicaii multimedia i transmisii de semnal audio/video/GSM, care s-a fcut n ultimii 6 ani.(adaptare dup Kaivalya M. Dixit, preedinte SPEC 19902002).CLASIFICAREA BENCHMARK-URILOR. SUITE REPREZENTATIVE

Benchmark-uri desktop CPU intensive (SPEC CPU2006 CINT2006, CFP2006) grafic intensive (cu toate c multe aplicaii grafice includ calcul intensiv i din partea CPU) SPECviewperf (benchmark-uri care se bazeaz pe biblioteci OpenGL), SPECapc (Pro/Engineer, SolidWorks 99, Unigraphics V15) aplicaii care folosesc din abunden primitive grafice. Benchmark-uri server (TPC-C, TPC-H, TPC-R, TPC-W, SPECjbb). Benchmark-uri dedicate (embedded) EEMBC (embassy), SPECjvm2008, SoftFloat, MediaBenchTPC-C simuleaz un mediu complex de interogri. Se bazeaz pe servere de baze de date standardizate: Oracle, Microsoft SQL.TPC-H modeleaz un sistem de decizii ad-hoc n care nu se ine cont de patern-ul anterior de interogri (neexistnd legturi ntre acestea) pentru optimizarea interogrilor viiitoare; ( timpul de execuie al anumitor interogri poate fi foarte mare = dezavantaj.

TPC-R simuleaz un sistem de decizii pentru afaceri n care utilizatorii ruleaz un set standard de interogri. n TPC-R, se ine cont de informaiile privind interogrile anteriore pentru optimizarea interogrilor viiitoare.TPC-W simuleaz activitile unui server web dedicat tranzaciilor unei companii din domeniul economic.

SPEC CPU2006 cuprinde 2 seturi de benchmark-uri: CINT2006 pentru msurarea performanelor n cazul calculului intensiv cu numere ntregi i CFP2006 pentru performanele n cazul calculului intensiv n virgul flotant. Cele 2 seturi msoar performanele procesorului, arhitecturii memoriei i compilatorului unui calculator.Setul CINT2006 cuprinde 12 benchmark-uri bazate pe aplicaii, scrise n limbajele C (9) i C++ (3), iar CFP2000 cuprinde 17 benchmark-uri care realizeaz operaii n virgul mobil, scrise n FORTRAN (6), C++ (4), C (3) i 4 ntr-un amestec de C i Fortran.

n ultima decad, substaniale mbuntiri au avut loc n tehnologia compilatoarelor pentru extragerea i valorificarea paralelismului la nivelul instruciunilor (ILP). Aceste aplicaii nu cuprind toate elementele eseniale ale aplicaiilor multimedia i de comunicaie.

SPEC2006 programs and the evolution of the SPEC benchmarks over time, with integer programs above the line and floating-point programs below the line.The figure shows all 70 of the programs in the 1989,1992,1995,2000, and 2006 releases. Only 3 integer programs and 3 floating-point programs survived three or more generations.Note that all the floating-point programs are new for SPEC2006. Although a few are carried over from generation to generation, the version of the program changes and either the input or the size of the benchmark is often changed to increase its running time and to avoid perturbation in measurement or domination of the execution time by some factor other than CPU time.

ECUAIA DE STABILIRE A PERFORMANEI PROCESORULUI (CPU)

Performana unui program (executat de un procesor) depinde de o combinaie de factori:

Eficiena algoritmilor utilizai n program (optimizai / neoptimizai din punct de vedere al referinelor la memorie i din punct de vedere al timpului de execuie) Componente software utilizate pentru a crea i translata codul surs al programului n instruciuni main (compilatoare, translatoare, reorganizatoare de cod - scheduler, asambloare, etc) Capacitatea sistemului de calcul de a executa eficient aceste instruciuni, care pot include operaii de intrare / ieire (I/O) mari consumatoare de timp.Componenta hardware sau software a sistemului de calculModul n care aceasta afecteaz performana

Algoritmul (sortare, cutare binar, folosirea tehnicilor de divide et impera, etc)Determin numrul de enunuri / instruciuni / comparaii la nivel de cod surs precum i numrul de operaii de intrare / ieire executate.

Limbajul de programare, Compilatorul i Arhitectura Setului de InstruciuniDetermin numrul de instruciuni asamblare / main corespunztoare fiecrui enun de la nivel de cod surs.

Interfaa dintre procesor i sistemul ierarhic de memorieStabilete ct de repede vor fi executate instruciunile main.

Dispozitivele periferice (I/O) i interfaarea operaiilor de intrare / ieire cu Sistemul de Operare prin ntreruperi softwareDetermin ct de repede vor fi executate operaiile de intrare / ieire.

Prima metric (M1 numrul de instruciuni din program) depinde de program, de limbajul n care este implementat aplicaia, de ISA procesorului (programul poate fi scris n limbaj de asamblare) n final el fiind translatat n cod main i executat, i evident de compilator. A doua metric (M2 numrul de ciclii n care se execut o instruciune) poate depinde de scheduler (component a compilatorului) dac se ncearc optimizarea i execuia n paralel a mai multor instruciuni independente, dar depinde n mod cert de microarhitectur (adncimea structurii pipeline, gradul de superscalaritate; proiectarea anumitor instruciuni flotante nmulire/mprire/radical poate fi optimizat). Dac primele dou metrici erau arhitecturale, a treia (M3 numrul de ciclii de tact procesor dintr-o secund) este tehnologic i depinde de fizicieni, electroniti, proiectani de circuite logice / secveniale n vederea creterii frecvenei de comutaie a tranzistorilor i de minimizare a timpului de execuie a fiecrei faze de procesare ( decodificare / execuie etc.) i a perioadei de tact a procesorului.IRETLICURI ARHITECTURALE UZUALE

Lungimea programului este constant.

Se simuleaz n mod repetat aceleai benchmark-uri, folosindu-se de acelai compilator Uneori pot fi variate opiuni de compilare pentru observarea impactului asupra performanei a tehnicilor arhitecturale propuse i n ce msur ctigul se datoreaz compilatorului.

Perioada de tact este constant (secund / ciclii de tactCPU).

Asftel, n majoritatea colectivelor de cercetare academic, prin simulare execution-driven se determin performana de procesare prin focalizarea pe studiul ciclilor / instruciune. n consecin, se modific configuraia microarhitectural pentru calculul IPC (instruciuni / ciclu de tactCPU) optim.UTILIZAREA MEDIEI ARMONICE N EVALUAREA VITEZEI DE EXECUIE A PROGRAMELOR (HM) Se consider c fiecare program execut O operaii

Se consider c n programe execut cele nO operaii n Ti Viteza (rata) de execuie a sistemului (P) este n acest caz dat de relaia:

P = nO/ Ti = n/ (Ti/O) = n/ 1/Piunde 1/Pi este inversul vitezei de execuie a programului i. Viteza de execuie a unui sistem (msurat n IPC instruciuni per ciclu de tactCPU) care ruleaz n benchmark-uri este egal cu media armonic a performanelor individuale de procesare a fiecruia dintre cele n benchmark-uri. HM elimin vrfurile (cazurile extreme care ar denatura rezultatul n cazul unei medii aritmetice) conducnd la interpretri greite a rezultatelor. Se recomand calculul HM mai ales c fiecare benchmark n parte are un numr diferit de instruciuni i evident un timp diferit de execuie.Probleme:

1. Se consider dou calculatoare desktop numite CSA avnd ISA de procesor MIPS i care execut instruciuni la o frecven de 2.5 GHz, respectiv CSB avnd ISA de procesor x86 i care execut instruciuni la o frecven de 3 GHz. n medie, programele executate pe arhitectur MIPS au o lungime mai mare, de 1.5 ori dect aceleai programe scrise i executate pe arhitectur x86.Se cere:

a) tiind suplimentar c pentru execuia programului P1, o instruciune pe CSA dureaz 2 perioade de tact (CPICSA=2) i instruciunile aceluiai program P1 executat pe CSB necesit 3 perioade de tact (CPICSB=3), care sistem de calcul execut mai rapid programul P1? Care este accelerarea (speed-up-ul) sistemului mai performant?b) Dac ns, pentru execuia programului P2, o instruciune pe CSA dureaz 1 perioad de tact (CPICSA=1) i instruciunile aceluiai program P2 executat pe CSB necesit 2 perioade de tact (CPICSB=2), care sistem de calcul execut mai rapid programul P2? Care este accelerarea (speed-up-ul) sistemului mai performant?Indicaie:

1a) Se consider c programul P1 dac se execut pe CSB cu arhitectur x86 (CISC) are n instruciuni. Rezult c acelai program P1 impune execuia pe pe CSA cu arhitectur MIPS (RISC) a 1.5n instruciuni. Calculm timpul de execuie aferent programului P1 pe cele dou sisteme de calcul CSA i CSB. Astfel:TCSB(P1) = n instr * Ciclii de procesare per instruciune * Perioada de tact procesorCSB = = n * 3 * 1/(3*109) [s] = n [ns - nanosecunde]

TCSA(P1) = 1.5n instr *Ciclii de procesare per instruciune * Perioada de tact procesorCSA =

= 1.5n * 2 * 1/(2.5*109) [s] = 1.2n [ns - nanosecunde]

Astfel, rata de procesare IRCSB = n instr. / n [ns] = 1 instr. / 1[ns] i

rata de procesare IRCSA = n instr. / 1.2n [ns] = 1 instr. / 1.2[ns] i

rezult Speed-up=IRCSB / IRCSA = 1.2x => programul P1 se execut de 1.2 ori mai rapid pe CSB dect pe CSA.

Verificai n aceeai manier, dar n condiiile de la punctul b) care dintre cele dou sisteme de calcul este mai rapid.

2. Se consider c dintre instruciunile unui program executat pe un procesor MIPS 10% sunt instruciuni de mprire. Toate celelalte instruciuni (care nu sunt de mprire) necesit 1 ciclu de tact pentru execuie. Instruciunile de mprire se execut n 50 de ciclii de tact (se mai numesc mari consumatoare de timp). Ce observai i cum interpretai n doar dou propoziii dup ce rezolvai cerinele de la a) la f)?a) Determinai care este metrica CPI aferent programului executat pe acest tip de procesor? (n ci ciclii de tact se execut n medie un astfel de program)

b) Ce procent de timp se pierde doar cu operaiile / instruciunile de mprire?c) Care este speed-up-ul obinut dac mbuntim performana de procesare a instruciunilor de mprire de 2 ori (numrul de ciclii de execuie pentru o instruciune de mprire se reduce la jumtate)?d) Care este speed-up-ul obinut dac mbuntim performana de procesare a instruciunilor de mprire de 5 ori (numrul de ciclii de execuie pentru o instruciune de mprire se reduce de 5 ori)?e) Aceeai ntrebare ca la punctele anterioare c) i d) dac mbuntim performana de procesare a instruciunilor de mprire de 10 ori respectiv de 50 de ori?

f) Ct va deveni speed-up-ul dac instruciunile de mprire vor deveni de un infinit de ori mai rapide (timp execuie(0 tacte de procesare)?Bibliografie[Sch02] Schmidt R., Notohardjono B. D., High-end server low-temperature cooling, IBM Journal of Research and Development, Volume 46 Issue 6, November 2002, Pages 739 - 751.

Legea scalabilitii totale sau ntlnit i sub denumirea legea randamentelor n scdere (diminishing returns)

Pentium P4 Extreme Edition consum 135W

Presupunem c simulm o microarhitectur cu 10 parametrii (FR, IBS, Irmax, SizeIC, SizeDC, latentaDRAM, ROBsize, RenBuffersize, optimizri_compilator), fiecare parametru putandu-se afla in 4 stari diferite (410=220=1048576 configuraii distincte de simulat * 24h de simulare per configuraie pe un sistem monoprocesor ( 2872 de ani (Se reamintete c pe n digii se pot reprezenta n baza b un bn numere: de la 00.00b) pn la (b-1)(b-1).(b-1)(b-1)b( de la 0 la valoarea maxim (b-1)*b0+(b-1)*b1+(b-1)*b2+.+(b-1)*bn-1=(bn -1) deci bn numere.

Simularea la nivel de tranzactii se bazeaz pe limbaje de programare de nivel nalt, aa cum este SystemC, un limbaj derivat din C++ pentru modelarea la nivel de sistem hardware-software (vezi HYPERLINK "http://www.systemc.org/" http://www.systemc.org/ ) i pune n eviden conceptul de separare a comunicaiei, fa de procesul computaional din cadrul sistemului. n abordarea la nivel transactional (TLM), componentele sunt modelate ca i module care pot executa o mulime de procese concurente, care calculeaz i le reprezint comportamentul. Aceste module comunic prin mesaje sub form de tranzacii folosind canale de comunicaie abstracte. Interfeele TLM sunt implementate n cadrul canalelor de comunicaie pentru a ncapsula protocoale de comunicaie. Pentru a putea comunica, un proces trebuie doar s acceseze aceste interfee, prin porturile pe care le are modulul cu care se dorete comunicarea.

Pentru detalii suplimentare legate de instrumente software utile n analiza i proiectarea microarhitecturilor a se vedea capitolul 3 din lucrarea 4 Predicia dinamic a valorilor n microprocesoarele generaiei urmtoare din bibliografia obligatorie prezentat n cursul introductiv i n fia disciplinei.

Tehnici de reorganizare a codului de tip: loop unrolling, software pipelining, mov merging, mov reabsorption, immediate merging, loop interchange, function inlining, merging array, etc contribuie la optimizarea programelor n vederea creterii paralelismului la nivelul instruciunilor.

Efectul hazardurilor de ramificaie (predicia greit a instruciunilor de salt) este senzitiv la microarhitectur, afectnd performana de procesare. O structur pipeline cu 20 de faze de procesare cum are Intel Pentium 4 i un factor de superscalaritate de 4, sau chiar 8 instruciuni, determin ca n execuie s se gseasc un numr de instruciuni de ordinul sutelor chiar miilor. Avnd n vedere c uneori pot trece i 100 de TCPU pn cnd se soluioneaz o instruciune de salt, rezult necesitatea evacurii tuturor instruciunilor procesate pe calea greit i reluarea de pe calea corect, cu implicaii negative asupra performanei de procesare i a energiei disipate.

Dezvoltarea unor structuri de reutilizare a rezultatelor instruciunilor anterior executate incluznd i cazul instruciunilor triviale.

Computer Science and Electrical EngineeringAdrian FLOREA

_1037564130.unknown

_1299562988.unknown

_1299650554.unknown

_1266754243.unknown

_1038174454.unknown

_1037563925.unknown

_1037564052.unknown

_1037563701.unknown

_959665274.unknown