Vectorization (datamaskin)
Den vektorisering (innenfor parallell databehandling ), er et spesielt tilfelle av parallellitet , karakterisert ved at programvaren som utfører standard en operasjon av gangen på en enkelt tråd er modifisert for å utføre flere funksjoner samtidig.
Vektorisering er prosessen med å konvertere et dataprogram fra en skalarimplementering , som behandler et enkelt par operander om gangen, til en vektorimplementering som behandler en operasjon på flere par operander om gangen. Begrepet kommer fra konvensjonen om å sette operander i vektorer eller matriser .
Den vektoren Beregningen er en viktig funksjon for både konvensjonelle datamaskiner og super moderne, som kan utføre vektoroperasjoner som samtidig utføre operasjoner som for eksempel de følgende fire tilsetninger:
Men i de fleste programmeringsspråk skriver vi vanligvis sløyfer som utfører rekkefølger i rekkefølge. Her er et eksempel på en slik løkke, i C :
for (i=0; i<n; i++) c[i] = a[i] + b[i];Automatisk vektorisering er et viktig forskningsfag innen informatikk; den består i å lete etter metoder som lar en kompilator konvertere (uten menneskelig hjelp) skalarprogrammer til vektoriserte programmer.
Kontekst
Tidlige datamaskiner hadde generelt en logisk enhet som sekvensielt utførte en instruksjon på et par operander av gangen. Dataprogrammer og programmeringsspråk er derfor designet for å utføre instruksjoner sekvensielt. Moderne datamaskiner kan gjøre mange ting samtidig. Et stort antall optimaliserende kompilatorer utfører automatisk kodevektorisering: det er en funksjon av kompilatoren som gjør det mulig å transformere deler av sekvensielle programmer til tilsvarende parallelle programmer for å produsere kode som vil bli brukt godt av en vektorprosessor.
Garantier
Automatisk vektorisering, som loopoptimalisering eller annen kompilasjonsoptimalisering, må nøyaktig bevare oppførselen til programmet.
Dataavhengighet
Alle avhengigheter må overholdes ved kjøretid for å unngå feil resultater.
Generelt kan loop-invarianter og leksikalt avhengige avhengigheter lett vektoriseres, og ikke-scoped avhengigheter kan også vektoriseres, selv om det er vanskeligere. Men disse transformasjonene må gjøres trygt for å sikre avhengighet mellom alle erklæringer mens de forblir tro mot den opprinnelige koden.
Sykliske avhengigheter må behandles uavhengig av vektoriserte instruksjoner.
Datanøyaktighet
Den nøyaktighet av hel (binært format) må opprettholdes under utførelsen av vektoren instruksjon. Sistnevnte må velges riktig i henhold til størrelsen og oppførselen til de interne heltallene. Også med blandede heltallstyper må man være ekstra forsiktig med å promotere / degradere ordentlig uten tap av presisjon. Spesiell forsiktighet må utvises med skiltforlengelse (flere heltall pakkes i samme register) og under transformasjonsoperasjoner, eller bitbæringsoperasjoner som ville blitt tatt i betraktning.
Flyttall presisjon bør også opprettholdes, med mindre IEEE-754 compliance er ikke i kraft, i hvilket tilfelle operasjoner vil være raskere, men resultatene vil variere litt. Store variasjoner, selv ignorering av IEEE-754, betyr vanligvis programmeringsfeil. Programmereren kan også tvinge enkle presisjonskonstanter og sløyfevariabler (vanligvis to som standard) til å utføre dobbelt så mange operasjoner per instruksjon.
Teori
For å vektorisere et program, må kompilatoroptimalisereren først forstå avhengighetene mellom erklæringer og justere dem om nødvendig. Etter at avhengighetene er kartlagt, må optimalisereren ordne ordentlig instruksjonsimplementeringene til de aktuelle kandidatene til instruksjonsvektorer som opererer på flere dataelementer.
Bygg avhengighetsgrafen
Det første trinnet er å bygge avhengighetsgrafen, og identifisere deklarasjonene som avhenger av de andre erklæringene. Dette innebærer å undersøke hver påstand og identifisere hverandre av hvert dataelement som utsagnet får tilgang til. Den alias analyse kan anvendes for å bekrefte at de forskjellige variablene tilgang til den samme minnetildeling.
Avhengighetsgrafen inneholder alle lokale avhengigheter med en avstand mindre enn størrelsen på vektoren. Så hvis vektorregisteret er 128 bit, og arraytypen er 32 bit, er størrelsen på vektoren 128/32 = 4. Alle andre ikke-sykliske avhengigheter bør ikke ugyldiggjøre vektorisering, fordi den ikke gjør det, vil ikke være samtidig tilgang til samme vektorinstruksjon.
Anta at størrelsen på vektoren er den samme som fire heltall:
for (i = 0; i < 128; i++) { a[i] = a[i-16]; // 16 > 4, ignoré a[i] = a[i-1]; // 1 < 4, reste sur le graphe de dépendances }Gruppering
Ved hjelp av grafen kan optimalisereren deretter gruppere de sterkt tilkoblede komponentene (SCC) og de vektoriserbare setningene atskilt fra resten.
Tenk for eksempel på et programfragment som inneholder tre klynger av instruksjoner i en løkke: (SCC1 + SCC2), SCC3 og SCC4, i den rekkefølgen, der bare den andre klyngen (SCC3) kan vektoriseres. Det endelige programmet vil inneholde tre sløyfer, en for hver klynge, med bare den midterste som er vektorisert. Optimalisereren kan ikke bli med den første til den siste uten å bryte ordren for gjennomføring av instruksjonen, noe som vil ugyldiggjøre de nødvendige garantiene.
Idiomregistrering
Noen ikke-åpenbare avhengigheter kan optimaliseres videre basert på spesifikke uttrykk.
For eksempel kan følgende data selvavhengigheter vektoriseres fordi verdien av verdiene til høyre (RHS) blir hentet og deretter lagret på verdien til venstre, slik at dataene ikke kan endres i oppgaven.
a[i] = a[i] + a[i+1];Selvavhengighet av skalarer kan vektoriseres ved å eliminere variabler.
Generelle rammer
Det generelle rammeverket for løkkevektorisering er delt inn i fire trinn:
- Forspill: Når de uavhengige sløyfevariablene er klare til å brukes inne i sløyfen. Dette innebærer normalt å flytte dem til vektorregister med spesifikke mønstre som skal brukes i vektorinstruksjoner. Dette er også stedet å sette inn avhengighetskontrollen for kjøretid. Hvis kontrollen bestemmer at vektorisering ikke er mulig, gå til rengjøringstrinnet.
- Loop (s): alle vektoriserte sløyfer (eller ikke), atskilt av CSSC-klynger i rekkefølge etter utseende i den opprinnelige koden.
- Postlude: returnerer alle variablene til uavhengige sløyfer, induksjoner og reduksjoner.
- Opprydding: Bare implementer (ikke-vektoriserte) sløyfer for iterasjoner på slutten av en sløyfe som ikke er et multiplum av vektorstørrelsen eller for når kjøretidskontroller forbyr vektorbehandling.
Runtime vs kompilering
Noen vektoriseringer kan ikke bekreftes fullstendig på kompileringstidspunktet. Optimalisering av kompileringstid krever en eksplisitt indeks for matrise . Biblioteksfunksjoner kan også beseire optimalisering hvis dataene de behandler er levert av eksterne parametere. Selv i disse tilfellene kan kjøretidsoptimalisering fremdeles vektorisere løpende løkker.
Denne utførelseskontrollen gjøres i forspillstrinnet og leder strømmen til vektoriserte instruksjoner hvis mulig, ellers går vi tilbake til standardbehandling, avhengig av variablene som sendes på registerene eller skalarvariablene.
Følgende kode kan enkelt vektoriseres ved kompileringstidspunkt fordi den ikke har noen funksjoner som kaller eller er avhengig av eksterne parametere. I tillegg garanterer språket at det ikke vil okkupere samme minnetildeling som alle andre variable, som lokale variabler og lever bare i utførelsen stabelen .
int a[128]; int b[128]; // initialise b for (i = 0; i<128; i++) a[i] = b[i] + 5;På den annen side har koden nedenfor ingen informasjon om minneposisjoner fordi referansene er pekere og minnet der de er tildelt er dynamisk.
int *a = malloc(128*sizeof(int)); int *b = malloc(128*sizeof(int)); // initialise b for (i = 0; i<128; i++, a++, b++) *a = *b + 5; // ... // ... // ... free(b); free(a);En rask kjøretidskontroll på adressen til a og b, samt iterasjonssløyfeområdet (128) er tilstrekkelig til å fortelle om matriser overlapper eller ikke, og avslører dermed alle avhengigheter.
Det finnes verktøy for å dynamisk analysere eksisterende applikasjoner for å vurdere det latente potensialet som ligger i SIMD- parallellitet , som kan utnyttes gjennom utviklingen av kompilatoren og / eller ved manuelle kodeendringer.
Teknikker
Et eksempel kan være et program som multipliserer to vektorer med digitale data. En skalær tilnærming ville være omtrent som:
for (i = 0; i < 1024; i++) C[i] = A[i]*B[i];Det kan være vektorisert for å se slik ut:
for (i = 0; i < 1024; i+=4) C[i:i+3] = A[i:i+3]*B[i:i+3];Her representerer C [i: i + 3] de fire matriseindeksene fra C [i] til C [i + 3] og vektorprosessoren kan utføre fire operasjoner for en enkelt vektorinstruksjon. Fordi alle fire vektoroperasjonene er fullført omtrent samtidig med en skalarinstruksjon, kan vektortilnærmingen utføre opptil fire ganger raskere enn original kode.
Det er to forskjellige tilnærminger til kompilering: en basert på den klassiske vektoriseringsteknikken og den andre basert på sløyfeavvikling .
Automatisk vektorisering på sløyfenivå
Denne teknikken, brukt for klassiske vektormaskiner, prøver å finne og utnytte SIMD-parallellitet på sløyfenivå. Den består av to hovedetapper, som følger.
- Finn en indre sløyfe som kan vektoriseres;
- Transformer loop og generer vektorkoder;
I det første trinnet ser kompilatoren etter hindringer som kan forhindre vektorisering. En viktig hindring for vektorisering er en sann dataavhengighet kortere enn lengden på vektoren. Andre hindringer inkluderer funksjonssamtaler og korte iterasjonstall.
Når sløyfen er bestemt for å være vektoriserbar, blir sløyfen stripet av lengden på vektoren, og hver skalarinstruksjon i kroppen til sløyfen erstattes med den tilsvarende vektorinstruksjonen. Nedenfor vises komponenttransformasjonene i dette trinnet ved hjelp av eksemplet ovenfor.
- Etter strip-mining
- Etter å ha distribuert løkker ved hjelp av midlertidige matriser
- Etter utskifting med vektorkoder
Automatisk vektorisering på grunnleggende blokknivå
Denne relativt nye teknikken retter seg spesielt mot moderne SIMD-arkitekturer med korte vektorlengder. Selv om sløyfer kan vikles ut for å øke mengden SIMD-parallellisme i grunnleggende blokker, utnytter denne teknikken SIMD-parallellisme innenfor grunnleggende blokker i stedet for sløyfer. De to hovedetappene er:
- Den innerste sløyfen vikles ut av en faktor av lengden på vektoren for å danne et stort sløyfelegeme.
- Isomorfe skalarinstruksjoner (som utfører samme operasjon) er pakket i en vektorinstruksjon hvis avhengighetene ikke hindrer det i å gjøre det.
For å vise trinnvise transformasjoner av denne tilnærmingen, brukes det samme eksemplet som ovenfor.
- Etter å ha viklet ut løkkene (etter lengden på vektoren, antas det å være 4 i dette tilfellet)
- Etter emballasje
- Etter generering av kode
Her representerer sA1, SB1, ... skalarvariabler og VA, VB og Vc representerer vektorvariabler.
Kommersielle autovektor-kompilatorer bruker for det meste den konvensjonelle tilnærmingen på sløyfenivå med unntak av IBM XL-kompilatoren, som bruker begge deler.
I nærvær av kontrollflyt
Tilstedeværelsen av if i kroppen av sløyfen krever utførelse av utsagn i alle kommandobaner for å slå sammen flere verdier av en variabel. En generell tilnærming er å gå gjennom en sekvens av kodetransformasjoner: Predikasjon → vektorisering (ved hjelp av en av metodene ovenfor) → fjern predikater fra vektorer → fjern skalære predikater.
Følgende kode brukes som et eksempel for å vise disse transformasjonene:
for (i = 0; i < 1024; i++) if (A[i] > 0) C[i] = B[i]; else D[i] = D[i-1];- Etter forkynnelse
hvor (P) betegner et predikat som holder erklæringen.
- Etter vektorisering
- Etter å ha fjernet predikater fra vektorer
- Etter fjerning av skalære predikater
Reduksjon av merkostnadene ved vektorisering i nærvær av kontrollstrøm
Å måtte utføre instruksjonene i alle kontrollbaner i vektorkode har vært en av hovedfaktorene som bremser vektorkoden med hensyn til den skalære basen. Jo mer kompleks kommandostrømmen blir og jo flere instruksjoner blir avbøyd i skalarkoden, jo vanskeligere blir vektorisering. For å redusere overhead, kan vektorgrener settes inn for å omgå instruksjonsvektorer som ligner på hvordan skalargrener omgår skalarinstruksjoner. Nedenfor brukes AltiVec-predikater for å vise hvordan dette kan oppnås.
- Scalar base (original kode)
- Etter vektorisering i nærvær av kontrollstrøm
- Etter innsetting i vektorgrener
Det er to ting å merke seg i den endelige koden med vektorgrening. På den ene siden er predikatet som definerer instruksjonen for vPA også inkludert i kroppen til den eksterne vektorgrenen ved bruk av vec_any_gt. På den annen side avhenger lønnsomheten for indre vektorgrening for vPB av den betingede sannsynligheten for at vPB har falske verdier i alle felt, siden vPA har falske verdier i alle bitfelt.
Tenk på et eksempel der den eksterne forgreningen i skalarbunnen alltid tas utenom de fleste instruksjonene i kroppen. Det mellomliggende tilfellet ovenfor, uten vektorgrening, utfører alle vektorinstruksjoner. Den endelige koden, med vektorgrening, utfører både sammenligningen og forgreningen i vektormodus, og potensielt får ytelse over den skalære basen.
Se også
Referanser
- (no) Denne artikkelen er delvis eller helt hentet fra den engelske Wikipedia- artikkelen med tittelen " Vectorization_ (parallel_computing) " ( se forfatterlisten ) .
- http://dl.acm.org/citation.cfm?id=2254108
- S. Larsen og S. Amarasinghe , “ Proceedings of the ACM SIGPLAN conference on Programming language design and implementation ”, ACM SIGPLAN Notices , vol. 35, n o 5,2000, s. 145–156 ( DOI 10.1145 / 358438.349320 )
- " Kodeoptimalisering med IBM XL Compilers " ,Juni 2004(åpnet mai 2010 )
- J. Shin , MW Hall og J. Chame , “ Proceedings of the international symposium on Code generation and optimization ”, Superword-Level Parallelism in the Presence of Control Flow ,2005, s. 165–175 ( ISBN 0-7695-2298-X , DOI 10.1109 / CGO.2005.33 )
- J. Shin , " Proceedings of the 16. International Conference on Parallel Architecture and Compilation Techniques ", Introducing Control Flow into Vectorized Code ,2007, s. 280–291 ( DOI 10.1109 / PACT.2007.41 )