Spekulation til simulering. Innovation i verifikation

Genudgivet af Platon

Abonnenter: 0

Dette er en interessant idé, der bruger hardware-understøttet spekulativ parallelisme til at accelerere simulering, med et twist, der kræver tilpasset hardware. Paul Cunningham (Senior VP/GM, Verification at Cadence), Raúl Camposano (Silicon Catalyst, iværksætter, tidligere Synopsys CTO og nu Silvaco CTO) og jeg fortsætter vores serie om forskningsideer. Som altid er feedback velkommen.

Spekulation til simulering

Innovation

Denne måneds valg er Chronos: Effektiv spekulativ parallelisme for acceleratorer. Forfatterne præsenterede papiret på 2020-konferencen om arkitektonisk støtte til programmeringssprog og operativsystemer og er fra MIT.

Udnyttelse af parallelitet ved hjælp af multicore-processorer er en mulighed for applikationer, hvor parallelisme er indlysende. Andre algoritmer er måske ikke så let opdelte, men kan drage fordel af spekulativ udførelse, der udnytter iboende parallelisme. Normalt afhænger spekulativ udførelse af cache-kohærens, et højt overhead specielt til simulering. Denne metode omgår behovet for sammenhæng og fysisk lokaliserer opgaveudførelsen for at beregne fliser efter mållæse-skriveobjekt, hvilket sikrer, at konfliktdetektering kan detekteres lokalt uden behov for global kohærensstyring. Opgaver kan udføres spekulativt parallelt; enhver opdaget konflikt kan udrulles fra en opgave gennem dens underordnede opgaver og derefter genudføres uden at skulle stoppe andre tråde.

Et andet bemærkelsesværdigt punkt her. Denne metode understøtter forsinkelsesbaseret simulering i modsætning til de fleste hardwareaccelerationsteknikker.

Pauls syn

Wow, hvilket vidunderligt højoktanpapir fra MIT! Når jeg bliver spurgt om parallel beregning, tænker jeg straks på tråde, mutexes og hukommelsessammenhæng. Det er selvfølgelig sådan moderne multi-core CPU'er er designet. Men det er ikke den eneste måde at understøtte parallelisering i hardware.

Dette papir foreslår en alternativ arkitektur til parallelisering kaldet Chronos, der er baseret på en ordnet kø af opgaver. Under kørsel udføres opgaver i tidsstempelrækkefølge, og hver opgave kan oprette nye underopgaver, der tilføjes dynamisk til køen. Udførelsen begynder med at sætte nogle indledende opgaver i køen og slutter, når der ikke er flere opgaver i køen.

Opgaver i køen er farmet ud til flere behandlingselementer (PE'er) parallelt - hvilket betyder, at Chronos spekulativt udfører fremtidige opgaver, før den aktuelle opgave er fuldført. Hvis den aktuelle opgave ugyldiggør eventuelle spekulativt udførte fremtidige opgaver, bliver handlingerne for disse fremtidige opgaver "fortryddet", og de sættes i kø igen. Det er ikke let at implementere dette koncept korrekt i hardware, men for den eksterne bruger er det smukt: du koder bare din algoritme, som om opgavekøen udføres serielt på en enkelt PE. Ingen grund til at kode mutexes eller bekymre dig om dødvande.

Forfatterne implementerer Chronos i SystemVerilog og kompilerer det til en FPGA. Meget af papiret er afsat til at forklare, hvordan de har implementeret opgavekøen og enhver nødvendig udrulning i hardware for maksimal effektivitet. Chronos er benchmarked på fire algoritmer, der er velegnede til en opgave-kø-baseret arkitektur. Hver algoritme implementeres på to måder: For det første ved at bruge en dedikeret algoritme-specifik PE, og for det andet ved at bruge en off the shelf open source 32-bit indlejret RISC-V CPU som PE. Chronos-ydeevnen sammenlignes derefter med multi-threaded softwareimplementeringer af algoritmerne, der kører på en Intel Xeon-server med en lignende pris som den FPGA, der bruges til Chronos. Resultaterne er imponerende – Chronos skalerer 3x til 15x bedre end at bruge Xeon-serveren. Men at sammenligne tabel 3 med figur 14 gør mig lidt bekymret over, at de fleste af disse gevinster kom fra de algoritmespecifikke PE'er snarere end selve Chronos-arkitekturen.

Da dette er en bekræftelsesblog, zoomede jeg naturligvis ind på simuleringsbenchmark på gateniveau. EDA-industrien har investeret kraftigt for at forsøge at parallelisere logisk simulering, og det har vist sig vanskeligt at se store gevinster ud over nogle få specifikke use cases. Dette skyldes hovedsageligt, at ydeevnen af de fleste simuleringer i den virkelige verden er domineret af load/store-instruktioner, der mangler i L3-cachen og går ud til DRAM. Der er kun én testcase benchmarked i dette papir, og det er en lillebitte 32-bit carry save adder. Hvis du læser denne blog og ville være interesseret i at lave noget mere grundig benchmarking, så lad mig det vide - hvis Chronos virkelig kan skalere godt på simuleringer fra den virkelige verden, ville det have enorm kommerciel værdi!

Raúls syn

Hovedbidraget fra dette papir er Spatially Located Ordered Tasks (SLOT) eksekveringsmodel som er effektiv til hardwareacceleratorer, der udnytter parallelitet og spekulation, og til applikationer, der genererer opgaver dynamisk under kørsel. Dynamisk parallelisme-understøttelse er uundgåelig til simulering, og spekulativ synkronisering er en tiltalende mulighed, men kohærensoverhead er for høj.

SLOT undgår behovet for sammenhæng ved at begrænse hver opgave til at operere (skrive) på et enkelt objekt og understøtter ordnede opgaver for at muliggøre multi-objekt atomicitet. SLOT-applikationer er ordnede, dynamisk oprettede opgaver karakteriseret ved et tidsstempel og et objekt-id. Tidsstempler angiver ordrebegrænsninger; objekt-id'er angiver dataafhængighederne, dvs. opgaver er dataafhængige, hvis og kun hvis de har samme objekt-id. (hvis der er en læseafhængighed, kan opgaven udføres spekulativt). Konfliktdetektion bliver lokal (uden komplekse sporingsstrukturer) ved at kortlægge objekt-id'er til kerner eller fliser og sende hver opgave, hvor dens objekt-id er kortlagt.

Chronos systemet blev implementeret i AWS FPGA-rammeværket som et system med 16 fliser, hver med 4 applikationsspecifikke behandlingselementer (PE), der kører ved 125MHz. Dette system sammenlignes med en baseline bestående af 20-kerne/40-tråds 2.4 GHz Intel Xeon E5-2676v3, valgt specifikt fordi dets pris er sammenlignelig med FPGA-en (ca. $2/time). Chronos kører en enkelt opgave på én PE og er 2.45 gange hurtigere end basislinjen. Efterhånden som antallet af samtidige opgaver stiger, skalerer Chronos-implementeringen til en selv-relativ hastighed på 44.9x på 8 fliser, svarende til en 15.3x hastighed i forhold til CPU-implementeringen. De sammenlignede også en implementering baseret på generelle formål RISC-V snarere end applikationsspecifikke PE'er; PE'er var 5 gange hurtigere end RISC-V.

Jeg fandt papiret imponerende, fordi det dækker alt fra et koncept til definitionen af SLOT-udførelsesmodellen til implementeringen af hardware og den detaljerede sammenligning med en traditionel Xeon CPU til 4 applikationer. Indsatsen er betydelig, Chronos er over 20,000 linjer af SystemVerilog. Resultatet er en 5.4x gennemsnitlig (af de 4 applikationer) fremskyndelse i forhold til software-parallelle versioner, på grund af mere parallelitet og mere brug af spekulativ eksekvering. Papiret er også værd at læse til anvendelse på ikke-simuleringsopgaver; papiret indeholder tre eksempler.

Del dette opslag via: