O provocare pentru promoția 2009: arhitecturi multicore și

manycore

Curs festiv, Promoţia “Calculatoare”, 20 mai, 2009

Prof. Lucian VINȚAN

Catedra de calculatoare, Universitatea “Lucian Blaga”, Str. Emil Cioran, Nr. 4, 550025-Sibiu, România

lucian.vintan@ulbsibiu.rohttp://webspace.ulbsibiu.ro/lucian.vintan/

http://acaps.ulbsibiu.ro/research.php

Geneza Power Wall; Câțiva GHz sute de W/cm2 on-chip;

Pd=kCV2f saturarea frecvenței tactului – Frequency Wall

ILP Wall (super-pipeline, out of order, branch prediction, I-Trace-Cache, procesări speculative, scheduling static)

Memory Wall (DRAM-microprocesor)

Compromisul optimal între performanța procesării (Instructions Per Cycle – IPC) și complexitatea arhitecturală (puterea consumată, disipația termică, aria de integrare și bugetul de tranzistori) - tot mai greu de stabilit pe monoprocesoare

Soluția?! ...MultiCores Performance = (Cores * F)

Monoprocesoarele vor exploata paralelismul la nivel fin din cadrul aplicațiilor cu secvențialitate intrinsecă (scrise în limbaje secvențiale).

Sisteme multicore și manycore

Latențele miss-urilor mult mai mici-SMP, lărgimea de bandă a bus-urilor de interconectare mai mare-SMP etc. Performanța/Watt mai bună decât la sistemele monoprocesor

Exploatează paralelismul thread-urilor TLP reduc Memory Wall

Provocări: Minimizarea acceselor la datele aflate în afara memoriilor locale. Optimizarea balansării, a comunicațiilor și a sincronizărilor

Necesara o nouă proiectare a algoritmilor în vederea mapării lor optimale pe sistemele de tip multicore

Metricile succesului: productivitatea programării și performanța aplicatiei.

În anul 2015 se așteaptă microprocesoare comerciale de uz general cu 256 de nuclee. La 30 nm se pot integra 1000-1500 de nuclee simple (actualmente INTEL utilizează tehnologii la 45 nm).

Anyway… ne vor face viata (si mai) grea!

Arhitecturi multicore omogene vs.

eterogene Viitorul este cel al unor sisteme multicore

eterogene adaptare dinamică la caracteristicile programelor

f=0.1; [N=100 omogene simple] vs. [N=90 omogene + nucleu OoO (= 10 omogene)]

S’ = 1 / (0.1/2 – 0.9/90) = 16.7

Necesare simulări complexe

2.9)100/9.01.0/(1

N

f)(1f

1S

Exploatarea sinergică a tipurilor de

paralelism

Paralelismul programelor: Pipeline (faze) ILP (instrucțiuni, inclusiv MLP – disambiguation!) TLP (threads și micro-threads, resurse partajate/distincte - SMT) Multi & Many-Cores (tasks, procesoare distincte)

Chip-ul multicore eterogen dispozitivul universal de calcul

Exemplu: Exploatarea eterogenității multicore prin virtualizare. 2 stagii de compilare

Paralelismul datelor (SIMD) – (bit – vectori)

TLP – da, MLP – nu...

Sinergism: TLP si MLP deopotriva!

Ierarhia de memorie - provocari Ierarhia de cache-uri - neperformantă cca. 50%

din datele blocurilor sunt nefolosite! (Analog in Virtual Memory – VM...)

Exploatarea mai agresivă a “localităților” (vecinătăților) spațiale, temporale și... de ce nu?... chiar ale valorilor instructiunilor

Necesară adaptarea dinamică a dimensiunii blocului din cache la caracteristicile aplicației (VM)

Coerența variabilelor partajate: snooping (MSI, MESI, MOESI etc.) și directory-based sunt nescalabile noi scheme de coerență, mai scalabile

Tehnologii de integrare de tip 3 D. Integrarea on-chip a DRAM nu mai implica multiplexarea adreselor scăderea semnificativă a Tacc. Largime de banda mai mare.

Modele relaxate de consistența

Un program paralel trebuie să specifice ordinea operațiilor de scriere-citire. Consistența secvențială (CS): In_Proc[data-flow] AND Inter_Pr[Arbitrary]

Problemă: în ce moment trebuie să vadă un procesor că o anumită variabilă a fost modificată de un altul?

CSforţarea fiecărui procesor care scrie o variabilă partajată de a-şi întârzia această scriere până în momentul în care toate invalidările se vor fi terminat.

CS simplă, dar reduce performanţa dezvoltarea unor noi modele, mai relaxate, de consistenţă

(P1)A=0;- - -

A=1;L1: if(B==0)...

(P2)B=0;- - -

B=1;L2: if(A==0)...

Rețele de interconectare

Necesare rețele de interconectare (RIC) cu lărgime de bandă ridicată și memorie partajată on-chip, scalabilă. Low latency, power and cost

Necesară eficientizarea sub-sistemului de cache-uri scăderea presiunii asupra rețelelor de interconectare și a memoriei principale partajate și distribuite (NUMA)

Cercetări novatoare în arhitectura memoriilor DRAM. Processing In Memory – PIM interleaving. O rețea de procesoare PIM se numește arhitectură celulară (ex. IBM BlueGene).

Probabil că cercetările RIC se vor inspira din rețelele de interconectare ale supercomputerelor actuale.

IBM BlueGene. 65536 noduri interconectate 3 D Torus. Un nod: 80 CPU 2 SMT PIM, conectate

Crossbar

Un nod: IBM Cyclops 64 Multicore

Alte tipuri de RIC

Modele de programare paralelă

Productivitatea actualelor paradigme de programare paralelă (shared memory respectiv message passing) este una scazută. Creare_thread, sincronizare_threads, alocare Shared_Mem, Excl_Mut (Lock/UnLock) etc.

Actualmente aceste modele sunt nesatisfăcătoare, conducând la o programare, testare și depanare extrem de dificile.

Nu iau în considerare eterogenitatea arhitecturii... iar scalabilitatea acestor modele este una scăzută.

Modele productive, performante dar și simple (!) de programare paralelă pe sisteme multicore și manycore

Metode de evidențiere a paralelismelor la nivelul limbajelor de programare. Să se pună în evidență paralelismele inter-thread-uri, alocările de memorie, accesul la zonele de date partajate și modurile de sincronizare.

Gradul de abstractizare al modelului în baza compromisului productivitate – eficiență. Dificil!

Modele de programare paralela. Transactional Memory (TM) - I

Tranzacţia constituie o secvenţă de cod care execută în mod speculativ, mai multe citiri şi scrieri la nivelul unei memorii partajate. Tranzacţia este atomică (se execută dpdv logic în totalitate sau deloc), consistentă (dpdv al variabilelor partajate inter-tranzacții) și durabilă (odată începută, nu mai poate fi abortată).

Speculativ Rularea programului nu ține cont de secțiunile critice. Dacă apar conflicte pe variabilele partajate se vor detecta firele violate își vor relua execuția tranzacțiilor - roll-backs (checkpoints).

TM simplifică mult tehnicile de excluziune mutuală din programarea paralelă.

Modele de programare paralela. Transactional Memory (TM) - II

Avantajul principal nu îl constituie atât performanța rulării, cât corectitudinea acesteia, chiar și în condițiile în care programatorul (compilatorul) efectuează în mod eronat paralelizarea aplicației.

Productivitatea și facilizarea programării constituie alte obiective importante asociat acestui concept.

Stanford Transactional Memory Coherence and Consistency, o memorie tranzacțională implementată în hardware Protocoalele de coerență se implementează la nivelul tranzacțiilor și nu la nivelul scrierilor individuale.

Consortiul FP7 NoE HiPEAC implementează conceptul TM in GCC (www.hipeac.net).

Diagnosticare și depanare Depanarea unor sisteme multi-core cu sute de

thread-uri si cu procesări în limbaje native diferite problemă deschisă

Necesar suport hardware pentru programarea paralelă, inclusiv pentru depanarea programelor paralele, prin monitorizarea execuțiilor.

O sesiune a depanării trebuie să vizualizeze toate instrucțiunile mașină, informații legate de variabile și funcții, erorile de comunicație între module dar și a erorilor locale etc.

Evitarea violărilor de timing în cazul sistemelor în timp real având constrângeri tari (Worst Case Execution Time) și a erorilor de execuție având cauze incerte (Heisenbugs), constituie provocări majore.

Paralelizarea aplicațiilor

Paralelizarea automată obiectiv maximal, vizat de vreo 40 de ani de cercetări asidue

Realizări notabile îndeosebi în paralelizarea automată a programelor numerice scrise în limbaje orientate pe vectori (Fortran, Matlab etc.)

Realizări notabile și pentru arhitecturi omogene cu memorie partajată, în special din lumea embedded (CUDA – NVIDIA GPU).

Ele trebuie extinse la tipuri cât mai diverse de aplicații, la limbaje bazate pe pointeri, sisteme multiprocesor eterogene cu diferite modele de memorie.

Necesare în special tehnici statice novatoare de analiză a programelor scrise în limbaje bazate pe pointeri. Dificil!

Transmiterea de către compilator a unor informații de semantică a aplicației HLL către sistemul multicore pe care aceasta va rula optimizări semnificative în procesarea aplicației

Simularea - instrument primordial de R & D

(I)

Timpul enorm de simulare pe multicores. Stapânirea complexității cercetării-dezvoltării sistemelor multicore. Proiectarea hardware-software integrată - hardware-software co-design

[Simularea ciclu cu ciclu (acuratețe)] vs. [Simularea tranzacțională (viteză) – comunicațiile între modulele componente]

Simulare bazată pe eșantioane reprezentative ale benchmark-urilor - sampling simulation

Extragerea caracteristicilor reprezentative ale benchmark-urilor benchmark-uri sintetice având aceleați caracteristici, dar fiind mai scurte - statistical simulation

Metode analitice, hibride…

Simularea - instrument primordial de R & D (II)

Paralelizarea simulatorului și rularea lui pe sisteme multicore performante (ex. IBM Cell BE)

Simularea întregului sistem de calcul, inclusiv a sistemului de operare - full-system simulation

Simulatoarele monolitice sunt înlocuite cu simulatoare modulare (POO) maparea facilă a blocurilor hardware pe modulele software

Automatic Design Space Exploration

Necesare metode de căutare euristică în spațiul enorm(!) al parametrilor aplicațiilor – compilatorului – arhitecturii.

Problema: optimizare multicriterială – [performanță] vs. [energie, disipație termică, arie de integrare, buget tranzistori etc.]

ADSE Magellan - Illinois at Urbana-

Champaign Algoritmul Steepest Ascent Hill Climbing

(SAHC) căutarea în vecinătatea celui mai bun k-procesor curent. Dezavantaje complexitatea exponenţială cu numărul de core-uri + eșuarea în extreme locale

Annealing search SAHC + alegere random

Algoritmi genetici – Op_Reproducere vecinul cel mai bun (SAHC). OP_Crossover + OP_Mutație

Algoritmii stigmergici - ant colony optimizations. Marcare feromoni / Evaporare feromoni

Soluții de cel puțin 3800 de ori mai rapide decât căutarea exhaustivă ȘI cu maximum 1% mai puţin performante!

Un exemplu ADSE: FP7 HiPEAC

ArchExplorer - http://archexplorer.org/

Platformă web oarecum independentă de simulator. Abordare holistică arhitectură - compilator

Oferă o explorare continuă a spațiului stărilor pe clustere de servere dedicate

FP7 MultiCube - http://www.multicube.eu

Exemplu de cautare: scheme de partajare a L1 si L2-cache într-un dual-core

Arhitecturi multicore cu procesări anticipativ-speculative

Arhitectura SMT cu selective DIR & Val_Pred 23,6% IPC și 34,5% EDP - http://acaps.ulbsibiu.ro/research.php

Aceste tehnici anticipative vor reduce semnificativ accesele la rețeaua de interconectare în vederea comunicării prin variabile partajate. Legea lui Amdahl nu mai este valabilă aici!

Între predicția valorilor și problema consistenței cache-urilor în sistemele multiprocesor există legături subtile, neexplorate înca în mod aprofundat.

A prezice valoarea unei instrucțiuni și apoi, a verifica predicția, nu este întotdeauna suficient erori de consistență ale variabilelor partajate, chiar corect predicționate!

Dynamic Instruction Reuse, Memoization - complet nestudiat în contextul multicores!

N

f)-(1p)-f(1

1Svp(N)

Un exemplu de inconsistență a predicției

Putere consumată, disipație termică

Necesare consum de putere și disipație termică reduse. Simulatoarele Wattch & HotSpot (Floorplan, Pd/modul, frecvență, tehnologie) API-uri la simulator

Proiectarea unui adaptive run-time thermal manager (adaptarea tensiunii de alimentare sau a frecvenței tactului funcție de temperatură, mutarea calculului în module de rezervă etc.)

Un exemplu: harti termice comparative (Superscalar vs. Superscalar_DIR_VPred)

Concluzii (I) Exploatarea integratoare, sinergică, a

paralelismelor de tip fine grain și coarse grain, atât la nivel static cât și dinamic

Instrumente de stapânire a complexității proiectării hardware-software integrate

Noi metode de simulare, care să permită compromisuri optimale între acuratețe și viteză.

Metode euristice de DSE bazate pe Machine Learning Optimizări multicriteriale în spațiul enorm al caracteristicilor. Abordarea trebuie să aibă în vedere întreg ansamblul: aplicații HLL – compilator – sistem de operare – arhitectură.

Concluzii (II) Ierarhii de memorii scalabile care să

exploateze agresiv vecinătățile temporale și spațiale. Analog pentru protocoalele de coerență. Sisteme relaxate de asigurare a consistenței variabilelor partajate

Modele de programare productive, performante dar și simple. Memoria tranzacțională – o promisiune!

Metode de diagnoză și depanare avansate, bazate pe informații de profiling

Predicția și speculația reprezintă metode de procesare agresive, neexplorate încă suficient.

Fără o abordare holistică, integratoare, cercetarea-dezvoltarea în ingineria calculatoarelor

nu mai poate avansa!