Slingbyte
I kompilatorteori är loop utbyte processen att byta ut ordningen av två iterationsvariabler som används av en kapslad loop . Variabeln som används i den inre slingan växlar till den yttre slingan och vice versa. Det görs ofta för att säkerställa att elementen i en flerdimensionell array nås i den ordning som de finns i minnet, vilket förbättrar referensplatsen .
Till exempel, i kodfragmentet:
för i från 0 till 10 för j från 0 till 20 a[i,j] = i + j
loop utbyte skulle resultera i:
för j från 0 till 20 för i från 0 till 10 a[i,j] = i + j
Ibland kan en sådan transformation skapa möjligheter att ytterligare optimera, såsom automatisk vektorisering av arraytilldelningarna.
Nyttan av loop utbyte
Huvudsyftet med loop-utbyte är att dra fördel av CPU-cachen vid åtkomst till array-element. När en processor kommer åt ett arrayelement för första gången kommer den att hämta ett helt datablock från minnet till cache. Det blocket kommer sannolikt att ha många fler på varandra följande element efter det första, så vid nästa arrayelementåtkomst kommer det att hämtas direkt från cachen (vilket är snabbare än att hämta det från långsamt huvudminne). Cachemissar uppstår om de kontinuerligt åtkomliga arrayelementen i slingan kommer från ett annat cacheblock, och loop-utbyte kan hjälpa till att förhindra detta. Effektiviteten av loop-utbyte beror på och måste beaktas i ljuset av cachemodellen som används av den underliggande hårdvaran och arraymodellen som används av kompilatorn.
I programmeringsspråket C lagras arrayelement i samma rad i rad i minnet (a[1,1], a[1,2], a[1,3]) - i rad-stor ordning . Å andra sidan FORTRAN- program arrayelement från samma kolumn tillsammans (a[1,1], a[2,1], a[3,1]), med kolumn-major . Således är ordningen för två iterationsvariabler i det första exemplet lämplig för ett C-program medan det andra exemplet är bättre för FORTRAN. Optimerande kompilatorer kan upptäcka felaktig ordning av programmerare och byta ut ordningen för att uppnå bättre cacheprestanda.
Varning
Liksom all kompilatoroptimering kan loop-utbyte leda till sämre prestanda eftersom cacheprestanda bara är en del av historien. Ta följande exempel:
do i = 1 , 10000 do j = 1 , 1000 a [ i ] = a [ i ] + b [ j , i ] * c [ i ] end do end do
Slingbyte i det här exemplet kan förbättra cacheprestandan för åtkomst till b(j,i), men det kommer att förstöra återanvändningen av a(i) och c(i) i den inre slingan, eftersom det introducerar två extra laddningar (för a( i) och för c(i)) och ett extra minne (för a(i)) under varje iteration. Som ett resultat kan den totala prestandan försämras efter slingbyte.
Säkerhet
Det är inte alltid säkert att utbyta iterationsvariabler på grund av beroenden mellan satserna för den ordning i vilken de måste köras. För att avgöra om en kompilator säkert kan byta slingor krävs beroendeanalys .
Se även
Vidare läsning
- Kennedy, Ken ; Allen, Randy (2002). Optimizing Compilers for Modern Architectures: A Dependence-Based Approach (2011 digitaltryck av 1:a upplagan). Academic Press / Morgan Kaufmann Publishers / Elsevier . ISBN 978-1-55860-286-1 . LCCN 2001092381 .