Slingoptimering
I kompilatorteorin är loopoptimering processen att öka exekveringshastigheten och minska de omkostnader som är förknippade med loopar . Det spelar en viktig roll för att förbättra cacheprestanda och effektivt använda parallellbearbetningsmöjligheter . Den största delen av genomförandetiden av ett vetenskapligt program läggs på loopar; som sådan har många kompilatoroptimeringstekniker utvecklats för att göra dem snabbare.
Representation av beräkningar och transformationer
Eftersom instruktioner inuti loopar kan exekveras upprepade gånger, är det ofta inte möjligt att ge en gräns för antalet instruktionskörningar som kommer att påverkas av en loopoptimering. Detta innebär utmaningar när man resonerar om riktigheten och fördelarna med en loopoptimering, specifikt representationerna av beräkningen som optimeras och optimeringen(erna) som utförs.
Optimering via en sekvens av looptransformationer
Loopoptimering kan ses som tillämpningen av en sekvens av specifika looptransformationer (listade nedan eller i kompilatortransformationer för högpresterande beräkningar ) på källkoden eller mellanrepresentationen , där varje transformation har ett associerat test för laglighet. En transformation (eller sekvens av transformationer) måste i allmänhet bevara den tidsmässiga sekvensen av alla beroenden om den ska bevara programmets resultat (dvs. vara en legal transformation). Att utvärdera fördelen med en transformation eller sekvens av transformationer kan vara ganska svårt inom detta tillvägagångssätt, eftersom tillämpningen av en fördelaktig transformation kan kräva att en eller flera andra transformationer i förväg används som i sig skulle resultera i minskad prestanda.
Vanliga looptransformationer inkluderar:
- Fission eller distribution – loop fission försöker bryta en loop i flera loopar över samma indexintervall, men varje ny loop tar bara en del av den ursprungliga loopens kropp. Detta kan förbättra referenslokaliteten , både för data som nås i slingan och koden i slingans kropp.
- Fusion eller kombinering – detta kombinerar kropparna av två intilliggande loopar som skulle iterera samma antal gånger (oavsett om det numret är känt vid kompileringstidpunkten eller inte), så länge de inte refererar till varandras data.
- Utbyte eller permutation – dessa optimeringar byter ut inre loopar med yttre loopar. När loopvariablerna indexeras till en array kan en sådan transformation förbättra referenslokaliteten, beroende på arrayens layout.
- Inversion – den här tekniken ändrar en standard while -loop till en do/while (aka repeat/tills ) loop insvept i en om villkorlig, vilket minskar antalet hopp med två för fall där loopen exekveras. Om du gör det dupliceras tillståndskontrollen (ökar storleken på koden) men är mer effektivt eftersom hopp vanligtvis orsakar en pipeline-stopp . Dessutom, om det initiala tillståndet är känt vid kompilering och är känt för att vara biverkningsfritt , kan det initiala if -guard hoppas över.
- Loop-invariant kodrörelse – detta kan avsevärt förbättra effektiviteten genom att flytta en beräkning från insidan av loopen till utsidan av den, beräkna ett värde bara en gång innan loopen börjar, om den resulterande kvantiteten av beräkningen kommer att vara densamma för varje loop-iteration ( dvs en loop-invariant kvantitet). Detta är särskilt viktigt med adressberäkningsuttryck som genereras av loopar över arrayer. För korrekt implementering måste denna teknik användas med inversion, eftersom inte all kod är säker att flytta utanför slingan.
- Parallellisering – detta är ett specialfall av automatisk parallellisering med fokus på slingor, omstrukturering av dem för att fungera effektivt på multiprocessorsystem. Det kan göras automatiskt av kompilatorer ( automatisk parallellisering ) eller manuellt (införande av parallella direktiv som OpenMP ).
- Reversering – en subtil optimering som omvänder ordningen i vilken värden tilldelas indexvariabeln. Detta kan hjälpa till att eliminera beroenden och därmed möjliggöra andra optimeringar. Vissa arkitekturer använder looping-konstruktioner på sammansättningsnivå som endast räknas i en enda riktning (t.ex. dekrementera-hopp-om-inte-noll [DJNZ]).
- Schemaläggning – detta delar upp en loop i flera delar som kan köras samtidigt på flera processorer.
- Skewing – den här tekniken tillämpas på en kapslad loop som itererar över en flerdimensionell array, där varje iteration av den inre slingan beror på tidigare iterationer och omordnar dess arrayåtkomster så att de enda beroenden är mellan iterationer av den yttre slingan.
- Programvarupipelining – en typ av urdriftkörning av loopiterationer för att dölja latenserna för processorfunktionsenheter.
- Splittring eller peeling – detta försöker förenkla en loop eller eliminera beroenden genom att dela upp den i flera loopar som har samma kroppar men itererar över olika delar av indexintervallet. Ett specialfall är loop peeling , vilket kan förenkla en loop med en problematisk första iteration genom att utföra den iterationen separat innan du går in i loopen.
- Sida eller blockering – omorganiserar en loop för att iterera över datablock som är dimensionerade för att passa i cachen.
- Vektorisering – försöker köra så många av loop-iterationerna som möjligt samtidigt på ett SIMD- system.
- Avrullning – duplicerar slingans kropp flera gånger för att minska antalet gånger som slingtillståndet testas och antalet hopp, vilket kan försämra prestandan genom att försämra instruktionspipelinen. Att helt rulla upp en loop eliminerar all overhead (förutom flera instruktionshämtningar och ökad programladdningstid), men kräver att antalet iterationer är känt vid kompileringstidpunkten (förutom i fallet med just-in-time kompilering ). Försiktighet måste också iakttas för att säkerställa att multipel omräkning av indexerade variabler inte är en större omkostnad än att flytta fram pekare inom den ursprungliga loopen.
- Unswitching – flyttar en villkorlig från insidan av en slinga till utanför den genom att duplicera slingans kropp och placera en version av den inuti var och en av om och annat - satserna i villkoret.
- Sektionering eller strip-mining – introducerad för vektorprocessorer , loop-sectioning är en loop-transformationsteknik för att möjliggöra SIMD (enkel instruktion, flera data)-kodningar av loopar och förbättra minnesprestanda. Detta innebär att varje vektoroperation utförs för en storlek som är mindre än eller lika med den maximala vektorlängden på en given vektormaskin.
Det unimodulära transformationsramverket
Den unimodulära transformationsmetoden använder en enda unimodulär matris för att beskriva det kombinerade resultatet av en sekvens av många av ovanstående transformationer. Centralt för detta tillvägagångssätt är synen på uppsättningen av alla exekveringar av en sats inom n loopar som en uppsättning heltalspunkter i ett n -dimensionellt utrymme, där punkterna exekveras i lexikografisk ordning . Till exempel kan exekveringen av en sats kapslad inuti en yttre slinga med index i och en inre slinga med index j associeras med paren av heltal ( . Tillämpningen av en unimodulär transformation motsvarar multiplikationen av punkterna inom detta utrymme med matrisen. Till exempel motsvarar utbytet av två slingor matrisen .
En unimodulär transformation är laglig om den bevarar den tidsmässiga sekvensen av alla beroenden ; det är svårare att mäta prestandaeffekten av en unimodulär transformation. Ofullständigt kapslade slingor och vissa transformationer (som kakelsättning) passar inte lätt in i detta ramverk.
Det polyedriska eller begränsningsbaserade ramverket
Den polyedriska modellen hanterar en bredare klass av program och transformationer än det unimodulära ramverket. Uppsättningen av exekveringar av en uppsättning satser inom en möjligen ofullständigt kapslad uppsättning slingor ses som föreningen av en uppsättning polytoper som representerar exekveringen av satserna. Affina transformationer appliceras på dessa polytoper, vilket ger en beskrivning av en ny exekveringsorder. Polytopernas gränser, databeroendena och transformationerna beskrivs ofta med hjälp av system av begränsningar, och detta tillvägagångssätt kallas ofta för en begränsningsbaserad metod för loopoptimering. Till exempel, en enstaka sats inom en yttre slinga ' för i := 0 till n ' och en inre slinga ' för j := 0 till i+2 ' exekveras en gång för varje (i, j) par så att 0 <= i <= n och O <= j <= i+2 .
Återigen är en transformation laglig om den bevarar den tidsmässiga sekvensen av alla beroenden . Att uppskatta fördelarna med en transformation, eller att hitta den bästa transformationen för en given kod på en given dator, är fortfarande föremål för pågående forskning när detta skrivs (2010).