Spekulation för simulering. Innovation In Verification

Återutgiven av Platon

anhängare: 0

Detta är en intressant idé, att använda hårdvarustödd spekulativ parallellism för att accelerera simulering, med en twist som kräver anpassad hårdvara. Paul Cunningham (Senior VP/GM, Verification at Cadence), Raúl Camposano (Silicon Catalyst, entreprenör, tidigare Synopsys CTO och nu Silvaco CTO) och jag fortsätter vår serie om forskningsidéer. Som alltid välkomnas feedback.

Spekulation för simulering

Innovation

Den här månadens val är Chronos: Effektiv spekulativ parallellism för acceleratorer. Författarna presenterade artikeln vid konferensen 2020 om arkitektoniskt stöd för programmeringsspråk och operativsystem och är från MIT.

Att utnyttja parallellism med flerkärniga processorer är ett alternativ för applikationer där parallellism är självklart. Andra algoritmer kanske inte är så lätta att partitionera men kan dra nytta av spekulativ exekvering som utnyttjar inneboende parallellism. Vanligtvis beror spekulativ exekvering på cachekoherens, en hög overhead speciellt för simulering. Denna metod kringgår behovet av koherens, fysiskt lokaliserar uppgiftsexekveringen för att beräkna brickor efter målläs-skrivobjekt, vilket säkerställer att konfliktdetektering kan upptäckas lokalt, utan behov av global koherenshantering. Uppgifter kan utföras spekulativt parallellt; alla upptäckta konflikter kan rullas upp från en uppgift genom dess underordnade uppgifter och sedan köras om utan att behöva stoppa andra trådar.

En annan punkt att notera här. Denna metod stöder fördröjningsbaserad simulering, till skillnad från de flesta hårdvaruaccelerationstekniker.

Pauls syn

Wow, vilket underbart högoktanigt papper från MIT! När jag frågas om parallell beräkning tänker jag genast på trådar, mutexer och minnessammanhang. Det är naturligtvis så moderna flerkärniga processorer är designade. Men det är inte det enda sättet att stödja parallellisering i hårdvara.

Detta dokument föreslår en alternativ arkitektur för parallellisering som kallas Chronos som är baserad på en ordnad kö av uppgifter. Under körning exekveras uppgifter i tidsstämpelordning och varje uppgift kan skapa nya deluppgifter som läggs dynamiskt till i kön. Utförandet börjar med att lägga in några initiala uppgifter i kön och slutar när det inte finns fler uppgifter i kön.

Uppgifter i kön flyttas ut till flera bearbetningselement (PE) parallellt – vilket innebär att Chronos spekulativt utför framtida uppgifter innan den aktuella uppgiften har slutförts. Om den aktuella uppgiften ogiltigförklarar eventuella spekulativt utförda framtida uppgifter så "ångras" åtgärderna för dessa framtida uppgifter och de ställs i kö igen. Att implementera detta koncept korrekt i hårdvara är inte lätt, men för den utomstående användaren är det vackert: du kodar bara din algoritm som om uppgiftskön exekveras seriellt på en enda PE. Du behöver inte koda några mutexes eller oroa dig för dödläge.

Författarna implementerar Chronos i SystemVerilog och kompilerar det till en FPGA. Mycket av uppsatsen ägnas åt att förklara hur de har implementerat uppgiftskön och all nödvändig utrullning i hårdvara för maximal effektivitet. Chronos är benchmarkad på fyra algoritmer som är väl lämpade för en uppgiftsköbaserad arkitektur. Varje algoritm implementeras på två sätt: först med en dedikerad algoritmspecifik PE, och för det andra med en 32-bitars inbäddad RISC-V CPU som PE. Chronos prestanda jämförs sedan med flertrådiga programvaruimplementeringar av algoritmerna som körs på en Intel Xeon-server med en prislapp som liknar den FPGA som används för Chronos. Resultaten är imponerande – Chronos skalar 3x till 15x bättre än att använda Xeon-servern. Men att jämföra tabell 3 med figur 14 gör mig lite orolig för att de flesta av dessa vinster kom från de algoritmspecifika PE:erna snarare än själva Chronos-arkitekturen.

Med tanke på att detta är en verifieringsblogg som jag naturligtvis zoomade in på simuleringsriktmärket på grindnivå. EDA-industrin har investerat mycket för att försöka parallellisera logisk simulering och det har visat sig vara svårt att se stora vinster utöver några specifika användningsfall. Detta beror främst på att prestandan för de flesta simuleringar i den verkliga världen domineras av laddnings-/lagringsinstruktioner som saknas i L3-cachen och går ut till DRAM. Det finns bara ett testcase som benchmarkerats i detta papper och det är en liten 32-bitars lagringsadderare. Om du läser den här bloggen och skulle vara intresserad av att göra lite mer grundlig benchmarking, låt mig veta – om Chronos verkligen kan skala bra på verkliga simuleringar skulle det ha ett enormt kommersiellt värde!

Raúls syn

Det huvudsakliga bidraget från denna tidning är Spatially Located Ordered Tasks (SLOT) exekveringsmodell vilket är effektivt för hårdvaruacceleratorer som utnyttjar parallellism och spekulation, och för applikationer som genererar uppgifter dynamiskt under körning. Stöd för dynamisk parallellism är oundvikligt för simulering och spekulativ synkronisering är ett tilltalande alternativ, men koherensoverheaden är för hög.

SLOT undviker behovet av koherens genom att begränsa varje uppgift att arbeta (skriva) på ett enda objekt och stöder ordnade uppgifter för att möjliggöra atomicitet med flera objekt. SLOT-applikationer är ordnade, dynamiskt skapade uppgifter som kännetecknas av en tidsstämpel och ett objekt-id. Tidsstämplar anger orderbegränsningar; objekt-id anger databeroendena, dvs. uppgifter är databeroende om och endast om de har samma objekt-id. (om det finns ett läsberoende kan uppgiften utföras spekulativt). Konfliktdetektering blir lokal (utan komplexa spårningsstrukturer) genom att mappa objekt-ID till kärnor eller brickor och skicka varje uppgift dit dess objekt-ID mappas.

Smakämnen Chronos Systemet implementerades i AWS FPGA-ramverket som ett system med 16 brickor, var och en med 4 applikationsspecifika bearbetningselement (PE), som körs på 125MHz. Detta system jämförs med en baslinje som består av 20-kärniga/40-trådiga 2.4 GHz Intel Xeon E5-2676v3, vald specifikt för att dess pris är jämförbart med FPGA-en (ca 2 USD/timme). Genom att köra en enda uppgift på en PE är Chronos 2.45 gånger snabbare än baslinjen. När antalet samtidiga uppgifter ökar, skalas Chronos-implementeringen till en självrelativ hastighet på 44.9x på 8 brickor, vilket motsvarar en 15.3x hastighetsökning jämfört med CPU-implementeringen. De jämförde också en implementering baserad på generella RISC-V snarare än tillämpningsspecifika PE:er; PE var 5 gånger snabbare än RISC-V.

Jag tyckte att uppsatsen var imponerande eftersom den täcker allt från ett koncept till definitionen av SLOT-exekveringsmodellen till implementeringen av hårdvara och den detaljerade jämförelsen med en traditionell Xeon CPU för 4 applikationer. Ansträngningen är betydande, Chronos är över 20,000 5.4 rader av SystemVerilog. Resultatet är en 4x genomsnittlig hastighet (av de XNUMX applikationerna) jämfört med programvaruparallella versioner, på grund av mer parallellism och mer användning av spekulativ exekvering. Uppsatsen är också läsvärd för tillämpning på icke-simuleringsuppgifter; tidningen innehåller tre exempel.

Dela det här inlägget via: