Loopoptimalisering - Loop optimization
I kompilatorteori er loopoptimalisering prosessen med å øke utføringshastigheten og redusere omkostningene forbundet med løkker . Det spiller en viktig rolle i forbedring av cacheytelsen og effektiv bruk av parallelle prosesseringsmuligheter . Mest utføringstid av et vitenskapelig program blir brukt på løkker. som sådan er det utviklet mange kompilatoroptimaliseringsteknikker for å gjøre dem raskere.
innhold
Representasjon av beregning og transformasjoner
Siden instruksjoner inne i løkker kan utføres gjentatte ganger, er det ofte ikke mulig å begrense antallet instruksjonsutførelser som vil bli påvirket av en loopoptimalisering. Dette gir utfordringer når man resonnerer om korrektheten og fordelene ved en loopoptimalisering, spesielt representasjonene for beregningen som blir optimalisert og optimaliseringen (e) som blir utført.
Optimalisering via en sekvens av sløyfetransformasjoner
Loopoptimalisering kan sees på som anvendelsen av en sekvens av spesifikke sløyfetransformasjoner (listet nedenfor eller i Compiler-transformasjoner for høyytelsesberegning ) til kildekoden eller mellomrepresentasjonen , hvor hver transformasjon har en tilhørende test for lovlighet. En transformasjon (eller sekvens av transformasjoner) må generelt bevare den tidsmessige sekvensen av alle avhengigheter hvis den skal bevare resultatet av programmet (dvs. være en lovlig transformasjon). Evaluering av fordelen med en transformasjon eller sekvens av transformasjoner kan være ganske vanskelig innenfor denne tilnærmingen, ettersom anvendelsen av en gunstig transformasjon kan kreve forutgående bruk av en eller flere andre transformasjoner som i seg selv ville resultere i redusert ytelse.
Vanlige sløyfetransformasjoner inkluderer:
- Fisjon eller distribusjon - sløyfe-fisjon prøver å dele en løkke i flere løkker over samme indeksområde, men hver nye sløyfe tar bare en del av den opprinnelige sløyfens kropp. Dette kan forbedre referanselokaliteten , både dataene som nås i løkken, og koden i sløyfens kropp.
- Fusjon eller kombinering - dette kombinerer kroppene til to tilstøtende løkker som vil itere det samme antall ganger (om dette tallet er kjent på samlingen tid eller ikke), så lenge de ikke viser til hverandres data.
- Utveksling eller permutasjon - disse optimaliseringene utveksler indre løkker med ytre løkker. Når sløyfevariablene indekseres i en matrise, kan en slik transformasjon forbedre referanselokaliteten, avhengig av matrisens oppsett.
- Inversjon - denne teknikken endrer en standard mens loop til en do / while (aka gjenta / til ) sløyfe innpakket i en hvis betinget, og reduserer antall hopp med to for tilfeller der løkken blir utført. Hvis du gjør det, dupliserer du tilstandskontrollen (øker størrelsen på koden), men er mer effektiv fordi hopp vanligvis forårsaker en rørledning . Hvis den opprinnelige tilstanden er kjent på kompileringstidspunktet og er kjent for å være bivirkning- fri, kan den opprinnelige if- vakten hoppes over.
- Loop-invariant kodebevegelse - dette kan forbedre effektiviteten enormt ved å flytte en beregning fra innsiden av løkken til utsiden av den, beregne en verdi bare en gang før løkken begynner, hvis den resulterende mengden av beregningen vil være den samme for hver loop-iterasjon ( dvs. en sløyfe-invariant mengde). Dette er spesielt viktig med adresseberegningsuttrykk generert av løkker over matriser. For korrekt implementering må denne teknikken brukes med inversjon, fordi det ikke er sikkert at alle koder kan flyttes utenfor løkken.
- Parallellisering - dette er et spesielt tilfelle av automatisk parallellisering med fokus på løkker, omstrukturering av dem for å fungere effektivt på multiprosessorsystemer. Det kan gjøres automatisk av kompilatorer ( automatisk parallellisering ) eller manuelt (sette inn parallelle direktiver som OpenMP ).
- Tilbakeføring - en subtil optimalisering som reverserer rekkefølgen som verdiene blir tilordnet indeksvariabelen. Dette kan bidra til å eliminere avhengigheter og dermed aktivere andre optimaliseringer. Enkelte arkitekturer bruker løkkekonstruksjoner på monteringsnivå som bare teller i en enkelt retning (f.eks. Dekrement-jump-if-not-zero [DJNZ]).
- Planlegging - dette deler en løkke inn i flere deler som kan kjøres samtidig på flere prosessorer.
- Skewing - denne teknikken brukes på en nestet sløyfe som itererer over en flerdimensjonal matrise, der hver iterasjon av den indre sløyfen er avhengig av tidligere iterasjoner, og omorganiserer arrayadgangene slik at de eneste avhengighetene er mellom iterasjoner av den ytre sløyfen.
- Rørledning av programvare - en type out-of-order utførelse av loop-iterasjoner for å skjule latensene til prosessorfunksjonsenheter.
- Splitting eller peeling - dette prøver å forenkle en sløyfe eller eliminere avhengigheter ved å bryte den inn i flere løkker som har de samme kroppene, men gjentas over forskjellige deler av indeksområdet. Et spesielt tilfelle er looping peeling , som kan forenkle en loop med en problematisk første iterasjon ved å utføre den iterasjonen separat før du går inn i loopen.
- Flislegging eller blokkering - omorganiserer en løkke for å itereere over blokker med data som er tilpasset cachen.
- Vectorisering - forsøker å kjøre så mange av loop-iterasjoner som mulig på et SIMD- system.
- Opprulling - dupliserer kroppen til loopen flere ganger for å redusere antall ganger sløyfetilstanden er testet og antall hopp, noe som kan forringe ytelsen ved å svekke instruksjonsrørledningen. Fullstendig rulling av en sløyfe eliminerer all overhead (bortsett fra flere instruksjonshentinger og økt programbelastningstid), men krever at antall iterasjoner er kjent på kompileringstidspunktet (bortsett fra når det gjelder just-in-time-kompilering ). Det må også tas hensyn til at flere omberegninger av indekserte variabler ikke er et større overhead enn fremføring av pekere i den opprinnelige sløyfen.
- Unswitching - flytter en betinget fra inne i en løkke til utsiden av den ved å duplisere loopens kropp, og plassere en versjon av den inne i hver av hvis og annet klausuler om betinget.
- Seksjonering eller stripedrift - introdusert for vektorprosessorer , loop-seksjonering er en sløyfetransformasjonsteknikk for å aktivere SIMD (enkeltinstruksjon, flere data) -kodinger av løkker og forbedre minneytelsen. Dette innebærer at hver vektoroperasjon blir utført for en størrelse som er mindre enn eller lik den maksimale vektorlengden på en gitt vektormaskin.
Det unimodulære transformasjonsrammeverket
Den unimodulære transformasjonsmetoden bruker en enkelt unimodulær matrise for å beskrive det kombinerte resultatet av en sekvens av mange av de ovennevnte transformasjoner. Sentralt i denne tilnærmingen er visningen av settet med alle henrettelser av en uttalelse i n løkker som et sett med heltallspunkter i et n- dimensjonalt rom, hvor punktene blir utført i leksikografisk rekkefølge . For eksempel kan henrettelsene av en uttalelse som er reist inne i en ytre sløyfe med indeks i og en indre sløyfe med indeks j, være assosiert med parene med heltall . Bruken av en unimodulær transformasjon tilsvarer multiplikasjonen av punktene i dette rommet med matrisen. For eksempel tilsvarer utvekslingen av to løkker matrisen .
En unimodular transformasjon er lovlig hvis den bevarer den tidsmessige sekvensen av alle avhengigheter ; Det er vanskeligere å måle ytelsen til en unimodulær transformasjon. Ufullkomne nestede løkker og noen transformasjoner (som flislegging) passer ikke lett inn i denne rammen.
Det polyhedrale eller begrensningsbaserte rammeverket
Den polyhedrale modellen håndterer en bredere klasse med programmer og transformasjoner enn det unimodulære rammeverket. Satsen henrettelser av et sett med uttalelser i et muligens ufullkommen nestet sett med løkker, blir sett på som foreningen av et sett med polytoper som representerer henrettelsene av uttalelsene. Affinetransformasjoner brukes på disse polytoper, og gir en beskrivelse av en ny utførelsesrekkefølge. Grensene for polytopene, datavhengighetene og transformasjonene blir ofte beskrevet ved bruk av systemer med begrensninger, og denne tilnærmingen blir ofte referert til som en begrensningsbasert tilnærming til loopoptimalisering. For eksempel utføres en enkelt setning i en ytre sløyfe ' for i: = 0 til n ' og en indre sløyfe ' for j: = 0 til i + 2 ' en gang for hvert (i, j) par slik at 0 <= i <= n og 0 <= j <= i + 2 .
Nok en gang er en transformasjon lovlig hvis den bevarer den tidsmessige sekvensen av alle avhengigheter . Å estimere fordelene ved en transformasjon, eller finne den beste transformasjonen for en gitt kode på en gitt datamaskin, forblir gjenstand for pågående forskning fra og med tidspunktet for dette skrivet (2010).
