Speculation For Simulation. Innovation In Verification

Republicat de Platon

Urmaritori: 0

Aceasta este o idee interesantă, folosind paralelismul speculativ suportat de hardware pentru a accelera simularea, cu o întorsătură care necesită hardware personalizat. Paul Cunningham (Senior VP/GM, Verification at Cadence), Raúl Camposano (Silicon Catalyst, antreprenor, fost CTO Synopsys și acum Silvaco CTO) și continuăm seria noastră despre idei de cercetare. Ca întotdeauna, feedback binevenit.

Speculații pentru simulare

Inovația

Alegerea din această lună este Chronos: Paralelism speculativ eficient pentru acceleratoare. Autorii au prezentat lucrarea la Conferința din 2020 privind suportul arhitectural pentru limbaje de programare și sisteme de operare și sunt de la MIT.

Exploatarea paralelismului folosind procesoare multicore este o opțiune pentru aplicațiile în care paralelismul este evident. Alți algoritmi ar putea să nu fie partiționați atât de ușor, dar ar putea beneficia de execuția speculativă exploatând paralelismul intrinsec. De obicei, execuția speculativă depinde de coerența cache-ului, o suprasarcină mare în special pentru simulare. Această metodă ocolește nevoia de coerență, localizând fizic execuția sarcinii pentru a calcula plăcile prin obiectul de citire-scriere țintă, asigurând că detectarea conflictelor poate fi detectată local, fără a fi nevoie de managementul coerenței globale. Sarcinile se pot executa în mod speculativ în paralel; orice conflict detectat poate fi derulat dintr-o sarcină prin sarcinile sale secundare, apoi re-executat fără a fi nevoie să blocați alte fire.

Un alt punct de remarcat aici. Această metodă acceptă simularea bazată pe întârziere, spre deosebire de majoritatea tehnicilor de accelerare hardware.

punctul de vedere al lui Paul

Uau, ce minunată hârtie cu octanism ridicat de la MIT! Când sunt întrebat despre calculul paralel, mă gândesc imediat la fire, mutexuri și coerența memoriei. Desigur, așa sunt proiectate procesoarele moderne multi-core. Dar nu este singura modalitate de a sprijini paralelizarea în hardware.

Această lucrare propune o arhitectură alternativă pentru paralelizare numită Chronos, care se bazează pe o coadă ordonată de sarcini. În timpul execuției, sarcinile sunt executate în ordinea marcajului de timp și fiecare sarcină poate crea noi sub-sarcini care sunt adăugate dinamic la coadă. Execuția începe prin introducerea unor sarcini inițiale în coadă și se termină când nu mai există sarcini în coadă.

Sarcinile din coadă sunt împărțite la mai multe elemente de procesare (PE) în paralel – ceea ce înseamnă că Chronos execută în mod speculativ sarcini viitoare înainte ca sarcina curentă să fie finalizată. Dacă sarcina curentă invalidează orice sarcini viitoare executate în mod speculativ, atunci acțiunile acelor sarcini viitoare sunt „anulate” și sunt puse din nou în coadă. Implementarea corectă a acestui concept în hardware nu este ușoară, dar pentru utilizatorul exterior este frumoasă: doar codificați algoritmul ca și cum coada de sarcini ar fi executată în serie pe un singur PE. Nu este nevoie să codificați niciun mutex sau să vă faceți griji cu privire la blocaj.

Autorii implementează Chronos în SystemVerilog și îl compilează într-un FPGA. O mare parte a lucrării este dedicată explicării modului în care au implementat coada de sarcini și orice derulare necesară în hardware pentru o eficiență maximă. Chronos este evaluat pe patru algoritmi potriviti unei arhitecturi bazate pe cozi de sarcini. Fiecare algoritm este implementat în două moduri: mai întâi folosind un PE dedicat algoritmului, iar al doilea utilizând un procesor RISC-V încorporat pe 32 de biți, ca PE. Performanța Chronos este apoi comparată cu implementările software multi-threaded ale algoritmilor care rulează pe un server Intel Xeon cu un preț similar cu cel al FPGA utilizat pentru Chronos. Rezultatele sunt impresionante – Chronos se adaptează de 3x la 15x mai bine decât folosind serverul Xeon. Cu toate acestea, compararea Tabelului 3 cu Figura 14 mă face să mă îngrijoreze puțin că majoritatea acestor câștiguri provin din PE-urile specifice algoritmului, mai degrabă decât din arhitectura Chronos în sine.

Având în vedere că acesta este un blog de verificare, am mărit în mod natural comparația de simulare la nivel de poartă. Industria EDA a investit masiv pentru a încerca să paralelizeze simularea logică și s-a dovedit dificil de a observa câștiguri mari dincolo de câteva cazuri de utilizare specifice. Acest lucru se datorează în principal performanței majorității simulărilor din lumea reală, fiind dominată de instrucțiunile de încărcare/stocare care lipsesc în cache-ul L3 și care ies în DRAM. Există un singur test de referință în această lucrare și este un mic adăugator de salvare pe 32 de biți. Dacă citiți acest blog și ați fi interesat să faceți o analiză comparativă mai amănunțită, vă rugăm să-mi spuneți - dacă Chronos poate scala cu adevărat bine pe simulările din lumea reală, ar avea o valoare comercială uriașă!

Viziunea lui Raul

Principala contribuție a acestei lucrări este Model de execuție a sarcinilor ordonate localizate spațial (SLOT). care este eficient pentru acceleratoarele hardware care exploatează paralelismul și speculațiile și pentru aplicațiile care generează sarcini dinamic în timpul execuției. Suportul paralelismului dinamic este inevitabil pentru simulare, iar sincronizarea speculativă este o opțiune atrăgătoare, dar coerența generală este prea mare.

SLOT evită nevoia de coerență prin restricționarea fiecărei sarcini pentru a opera (scrie) pe un singur obiect și acceptă sarcini ordonate pentru a permite atomitatea cu mai multe obiecte. Aplicațiile SLOT sunt sarcini ordonate, create dinamic, caracterizate printr-un marcaj de timp și un id de obiect. Marcajele de timp specifică constrângerile de ordine; ID-urile obiectelor specifică dependențele de date, adică sarcinile sunt dependente de date dacă și numai dacă au același id de obiect. (dacă există o dependență de citire, sarcina poate fi executată în mod speculativ). Detectarea conflictelor devine locală (fără structuri complexe de urmărire) prin maparea ID-urilor obiectelor la nuclee sau tile și trimiterea fiecărei sarcini acolo unde este mapat id-ul obiectului său.

Chronos sistemul a fost implementat în cadrul AWS FPGA ca un sistem cu 16 plăci, fiecare cu 4 elemente de procesare specifice aplicației (PE), rulând la 125MHz. Acest sistem este comparat cu o linie de bază formată din Intel Xeon E20-40v2.4 cu 5 de nuclee/2676 fire de 3 GHz, ales special pentru că prețul său este comparabil cu cel FPGA (aproximativ 2 USD/oră). Rulând o singură sarcină pe un singur PE, Chronos este de 2.45 ori mai rapid decât linia de bază. Pe măsură ce numărul de sarcini concurente crește, implementarea Chronos crește până la o accelerare autonomă de 44.9x pe 8 piese, corespunzând unei accelerații de 15.3x față de implementarea CPU. Ei au comparat, de asemenea, o implementare bazată pe RISC-V cu scop general, mai degrabă decât pe PE specifice aplicației; PE-urile au fost de 5 ori mai rapide decât RISC-V.

Am găsit lucrarea impresionantă pentru că acoperă totul, de la un concept la definirea modelului de execuție SLOT până la implementarea hardware-ului și comparația detaliată cu un procesor tradițional Xeon pentru 4 aplicații. Efortul este substanțial, Chronos are peste 20,000 de linii de SystemVerilog. Rezultatul este o accelerare medie de 5.4x (din cele 4 aplicații) față de versiunile software-paralele, datorită mai multor paralelism și mai multă utilizare a execuției speculative. Lucrarea merită, de asemenea, citită pentru aplicare la sarcini non-simulare; lucrarea include trei exemple.

Distribuie această postare prin: