Arhitecturi Paralele - Curs

1. Introducere în problematica microarhitecturilor cu executie

speculativa

Specialistii opineaza ca 65% din aceasta crestere exploziva a performantei se datoreaza progreselor arhitecturale si doar 35% celor tehnologice.

Din punct de vedere arhitectural si în special dupa modul de prelucrare a instructiunilor, se considera ca pâna la ora actuala au existat 3 generatii de (micro)procesoare comerciale de uz general, dupa cum urmeaza:

- generatia I caracterizata în principal prin executia secventiala a fazelor (ciclilor masina) aferente instructiunilor - masina. Pionierii acestei generatii sunt desigur inventatorii calculatorului numeric, inginerii Eckert si Mauchly, alaturi de cel care ulterior a teoretizat si a îmbogatit conceptul, în persoana marelui om de stiinta american John von Neumann

- generatia a II-a de procesoare, care exploata în principal paralelismul temporal aferent instructiunilor masina prin suprapunerea fazelor acestora (pipelining, overlapping). Primul reprezentant comercial a fost sistemul CDC-6600 (Control Data Company - 1964) proiectat de catre cel mai mare creator de calculatoare de înalta performanta si totodata unul dintre pionierii supercalculatoarelor, Seymour Cray. Înca de la începuturile anilor '80, microprocesoarele RISC(Reduced Instruction Set Computers) scalare au reprezentat aceasta generatie (J. Cocke de la IBM, D. Patterson de la Univ. Berkeley si J. Hennessy de la Univ. Stanford, fiind doar trei dintre pionierii promotori ai acestor idei). În plus, aceste microprocesoare au optimizat setul de instructiuni masina în vederea implementarii optimale a aplicatiilor de nivel înalt.

- generatia a III-a, cea curenta, este caracterizata de procesarea mai multor instructiuni independente simultan, prin exploatarea unui paralelism spatial la nivelul diverselor unitati functionale de procesare (Multiple Instruction Issues). Executia instructiunilor se face out of order, utilizând deci tehnici de reorganizare, dinamica sau statica, a instructiunilor în vederea minimizarii timpului global de executie [Hen02]. Pionierul comercial – un adevarat arhetip al acestei generatii - a fost sistemul anilor '60 IBM-360/91 (printre proiectanti Anderson, Sparacio, Tomasulo,Goldschmidt, Earle etc.), care, prin algoritmul lui Tomasulo implementat în unitatea de virgula mobila, a pus bazele executiei out of order a instructiunilor. De remarcat totusi ca procesul de dispatch (lansare a instructiunilor din buffer-ul de prefetch în statiile de rezervare) era de tip in order. La ora actuala generatia aceasta este reprezentata prin microprocesoarele superscalare în special, dar si prin cele care optimizeaza prin compilator fluxul de instructiuni, adica cele de tip VLIW (Very Long Instruction Word), EPIC (Explicitly Parallel Instruction Computers) etc.

De câtiva ani, în laboratoarele de cercetare se întrezaresc câteva solutii privind caracteristicile majore ale urmatoarei generatii arhitecturale, cea de a IV-a, Din multitudinea realizarilor existente, le-am ales pe acelea care mi s-au parut ca îmbina doua caracteristici oarecum opuse: revolutionarismul (performanta agresiva) cu evolutionismul (compatibilitatea cu paradigma actuala a microprocesorului de uz general). Dintre acestea, cele bazate pe reutilizarea dinamica a instructiunilor precum si cele bazate pe predictia valorilor si deci pe o executie super-speculativa a instructiunilor. Astazi, accentul principal nu se mai pune pe implementarea hardware, ci pe proiectarea arhitecturii. Se porneste de la o arhitectura de baza, care este modificata si îmbunatatita dinamic, prin simulari laborioase pe benchmark-uri reprezentative (pentru procesoarele de uz general Stanford, SPEC etc.).

O idee interesanta bazata pe descentralizarea resurselor are în vedere implementarea mai multor asa numite "Instruction Windows" (IW) - un fel de buffer-e de prefetch si statii de rezervare multiple. Lansarea în executie a instructiunilor se face pe baza determinarii celor independente din fiecare IW. Desigur ca trebuie determinate si dependentele inter - IW- uri. Ideea principala consta în executia paralela a mai multor secvente de program aflate în IW - uri diferite, bazat pe mai multe unitati functionale (multithreading). În esenta un procesor cu executii multiple ale instructiunilor este compus din doua mecanisme decuplate: mecanismul de aducere (fetch) a instructiunilor, pe post de producator si respectiv mecanismul de executie a instructiunilor, pe post de consumator. Separarea între cele doua mecanisme (arhitectura decuplata) se face prin buffer-ele de instructiuni si statiile de rezervare, ca în figura 1.2. Instructiunile de ramificatie si predictoarele hardware aferente actioneaza printr-un mecanism de reactie între consumator si producator.Astfel, în cazul unei predictii eronate, buffer-ul de prefetch trebuie sa fie golit macar partial iar adresa de acces la cache-ul de instructiuni trebuie si ea modificata în concordanta cu adresa la care se face saltul.

Pe baze statistice se arata ca un basic-block contine, pe programele de uz general, doar 4-6 instructiuni în medie, ceea ce înseamna ca rata de fetch a instructiunilor este limitata la cca. 6, aducerea simultana a mai multor instructiuni fiind inutila (fetch bottleneck sau Flynn’s bottleneck ).

Desigur, aceasta limitare fundamentala ar avea consecinte defavorabile si asupra consumatorului,care ar limita principial si rata medie de executie a instructiunilor (IR - Issue Rate) la aceasta valoare. Progresele semnificative în algoritmii de lansare în executie impun însa depasirea acestei bariere. În acest sens, cercetarile actuale insista pe îmbunatatirea mecanismelor de aducere a instructiunilor prin urmatoarele tehnici:

• predictia simultana a mai multor ramificatii / tact rezultând deci rate IR sporite

• posibilitatea accesarii si aducerii simultane a mai multor basic- block-uri din cache, chiar daca acestea sunt nealiniate, prin utilizarea unor cache-uri multiport

• pastrarea unei latente reduse a procesului de aducere a instructiunilor, în contradictie cu cele 2 cerinte anterioare

Alti factori care determina limitarea ratei de fetch a instructiunilor (FR- Fetch Rate) sunt:

largimea de banda limitata a interfetei procesor - cache, miss-urile în cache, predictiile eronate ale

ramificatiilor etc.

În contextul urmatoarei generatii arhitecturale de microprocesoare de înalta performanta, cea de a 4-a, se întrevede de asemenea implementarea unor mecanisme de aducere de tip out of order a instructiunilor, în plus fata de cele deja existente în executia instructiunilor. Aceste instructiuni fiind independente de conditia de salt, pot fi chiar lansate în executie. Când predictia se va fi realizat sau pur si simplu când adresa destinatie a ramificatiei va fi cunoscuta, procesorul va relua aducerea instructiunilor de la adresa destinatie a ramificatiei. Asadar o rafinare a conceptelor de executie speculativa a instructiunilor masina, bazata pe predictie sau pe concepte avansate de tip multiflow.

Evident, executia instructiunilor se va face out of order, pe baza dezvoltarii unor algoritmi de tip Tomasulo, mult mai agresivi însa. Statiile de rezervare aferente unitatilor de executie, vor trebui sa aiba capacitati de peste 2000 de instructiuni.

Pentru a evita falsele dependente de date (WAR – Write After Read, WAW – Write After Write),procesoarele vor avea mecanisme de redenumire dinamica a registrilor logici. Desigur, tehnicile de scheduling static vor trebui îmbunatatite radical pentru a putea oferi acestor structuri hardware complexe suficient paralelism Se estimeaza atingerea unor rate medii de procesare de 12-14 instr. /tact, considerând ca se pot lansa în executie maximum 32 instr. / tact. La ora actuala, cele mai avansate procesoare, cu un potential teoretic de 6 instr. / tact, ating în realitate doar 1.2-2.3 instr. /tact .Aceste rate mari de procesare, impun executia paralela a cca. 8 instructiuni Load/ Store.