Loop fission och fusion
Inom datavetenskap är loop fission (eller loop distribution ) en kompilatoroptimering där en loop bryts upp i flera loopar över samma indexintervall där var och en endast tar en del av den ursprungliga loopens kropp . Målet är att bryta ner en stor slingkropp i mindre för att uppnå bättre utnyttjande av referensorten . Denna optimering är mest effektiv i flerkärniga processorer som kan dela upp en uppgift i flera uppgifter för varje processor .
Omvänt är loop fusion (eller loop jamming ) en kompilatoroptimering och looptransformation som ersätter flera loopar med en enda. Loop fusion förbättrar inte alltid körhastigheten. På vissa arkitekturer kan två loopar faktiskt fungera bättre än en loop, eftersom det till exempel finns en ökad datalokalitet inom varje loop. En av huvudfördelarna med loop fusion är att det tillåter att tillfälliga allokeringar undviks, vilket kan leda till enorma prestandavinster i numeriska datorspråk som Julia när man gör elementvisa operationer på arrays (Julias loop fusion är dock inte tekniskt sett en kompilatoroptimering , men en syntaktisk garanti för språket).
Andra fördelar med loop fusion är att det undviker overhead av loopkontrollstrukturerna, och även att det tillåter loopkroppen att parallelliseras av processorn genom att dra fördel av instruktionsnivå parallellism . Detta är möjligt när det inte finns några databeroenden mellan de två slingornas kroppar (detta står i skarp kontrast till den andra huvudsakliga fördelen med loopfusion som beskrivs ovan, som bara uppträder när det finns databeroenden som kräver en mellanliggande allokering för att lagra resultat). Om loop fusion kan ta bort redundanta allokeringar kan prestandaökningarna bli stora. Annars finns det en mer komplex kompromiss mellan datalokalitet, parallellitet på instruktionsnivå och loop-overhead (förgrening, inkrementering, etc.) som kan göra loopfusion, loopfission eller ingetdera, den föredragna optimeringen.
Fission
Exempel i C
0
int i , a [ 100 ], b [ 100 ]; för ( i = ; i < 100 ; i ++ ) { a [ i ] = 1 ; b [ i ] = 2 ; }
är ekvivalent med:
0
0
int i , a [ 100 ], b [ 100 ]; för ( i = ; i < 100 ; i ++ ) { a [ i ] = 1 ; } för ( i = ; i < 100 ; i ++ ) { b [ i ] = 2 ; }
Fusion
Exempel i C++ och MATLAB
Tänk på följande MATLAB-kod:
0
x = : 999 ; % Skapa en matris med tal från 0 till 999 (intervallet är inklusive) y = sin ( x ) + 4 ; % Ta sinus av x (elementvis) och lägg till 4 till varje element
Du kan uppnå samma syntax i C++ genom att använda funktion och operatörsöverbelastning:
0
0
0
0
0
0
#include <cmath> #include <cassert> #include <memory> #include <iostream> class Array { size_t length ; std :: unik_ptr < float [] > data ; // Intern konstruktor som producerar en oinitierad array Array ( size_t n ) : längd ( n ), data ( new float [ n ]) { } public : // Fabriksmetod för att producera en array över ett heltalsintervall (den övre //-gränsen är exklusivt, till skillnad från MATLABs sortiment). static Array Range ( size_t start , size_t end ) { assert ( end > start ) ; size_t length = slut - start ; Array a ( längd ); för ( storlek_t i = ; i < längd ; ++ i ) { a [ i ] = start + i ; } returnera en ; } // Grundläggande arrayoperationer size_t size () const { return length ; } float & operator []( size_t i ) { returnera data [ i ]; } const float & operator []( size_t i ) const { returnera data [ i ]; } // Deklarera en överbelastad additionsoperator som en fri vänfunktion (denna //-syntax definierar operator+ som en fri funktion som är en vän till denna //-klass, trots att den visas som en medlemsfunktionsdeklaration). vän Arrayoperator + ( const Array & a , float b ) { Array c ( a . size ()) ; för ( storlek_t i = ; i < a . storlek (); ++ i ) { c [ i ] = a [ i ] + b ; } returnera c ; } // På liknande sätt kan vi definiera en överbelastning för sin()-funktionen. I praktiken // skulle det vara otympligt att definiera alla möjliga överbelastade matematikoperationer som // vänner i klassen så här, men detta är bara ett exempel. vän Array sin ( const Array & a ) { Array b ( a . storlek ()); för ( storlek_t i = ; i < a . storlek (); ++ i ) { b [ i ] = std :: sin ( a [ i ]); } returnera b ; } }; int main ( int argc , char * argv []) { // Här utför vi samma beräkning som MATLAB-exemplet auto x = Array :: Range ( , 1000 ); auto y = sin ( x ) + 4 ; // Skriv ut resultatet - bara för att se till att optimeraren inte tar bort // allt (om det är smart nog att göra det). std :: cout << "Resultatet är: " << std :: endl ; för ( storlek_t i = ; i < y . storlek (); ++ i ) { std :: cout << y [ i ] << std :: endl ; } returnera ; }
Men exemplet ovan allokerar i onödan en temporär array för resultatet av sin(x) . En mer effektiv implementering skulle allokera en enda array för y och beräkna y i en enda slinga. För att optimera detta skulle en C++-kompilator behöva:
- Infoga funktionsanropen
sinochoperator+ . - Slå ihop slingorna till en enda slinga.
- Ta bort de oanvända lagren i de temporära arrayerna (kan använda ett register eller stackvariabel istället).
- Ta bort den oanvända tilldelningen och frigör.
Alla dessa steg är individuellt möjliga. Även steg fyra är möjligt trots att funktioner som malloc och gratis har globala bieffekter, eftersom vissa kompilatorer hårdkodar symboler som malloc och gratis så att de kan ta bort oanvända allokeringar från koden. Men från och med clang 12.0.0 och gcc 11.1 sker inte denna loopfusion och borttagning av redundant allokering - inte ens på den högsta optimeringsnivån.
Vissa språk som är specifikt inriktade på numerisk beräkning som Julia kan ha konceptet loopfusion inbyggt på en hög nivå, där kompilatorn kommer att lägga märke till närliggande elementvisa operationer och smälta samman dem till en enda loop. För närvarande, för att uppnå samma syntax i allmänna språk som C++, sin och operator+ pessimistiskt allokera arrayer för att lagra sina resultat, eftersom de inte vet vilket sammanhang de kommer att anropas från. Det här problemet kan undvikas i C++ genom att använda en annan syntax som inte förlitar sig på kompilatorn för att ta bort onödiga temporära tilldelningar (t.ex. att använda funktioner och överbelastningar för operationer på plats, som operator+= eller std :: transform ) .