Optimizacija petlje

U teoriji kompajlera, optimizacija petlje je proces povećanja brzine izvršenja i smanjenja troškova vezanih za petlju. On igra važnu ulogu u poboljšanju keš performanse i efektivnom korišćenju paralelnog procesa mogućnosti. Veći deo vremena izvršenja računarske nauke se troši na petlje ; mnoge tehnike optimizacije kompilatora su razvijene da ih prave brže.

Predstavljanje obračuna i transformacija

Pošto se instrukcije unutar petlje mogu ponovo izvršavati , često nije moguće dati granicu o broju instrukcija izvršenja koja će biti pod uticajem od strane optimizacije petlje. Ovo predstavlja izazove kada se razmatra ispravnost i beneficije optimizacije petlje, posebno predstave izračunavanja koje se optimiziraju i optimizacija (e) koje se obavljaju.

Optimizacija preko niza petlji transformacija

Optimizacija petlje može da se posmatra kao primena niza specifičnih petlji transformacije (navedeno ispod ili u ) izvornog koda ili međujezika, sa svakom transformacijom koja ima upitni test za zakonitost. Transformacija (ili niz transformacija) generalno mora da čuva vremensku sekvencu svih zavisnosti podataka ako je očuvanje rezultat programa (tj. da bude ispravna transformacija). Procena koristi od transformacije ili niza transformacija može biti prilično teška u okviru ovog pristupa, kao i primena jedne korisne transformacije može zahtevati prethodno korišćenje jedne ili više drugih transformacija koje, same po sebi, mogu dovesti do pada performansi.

Zajedničke transformacije petlji

• fisija / raspodela : fisija petlje pokušava da podeli petlju u više petlji u istom opsegu indeksa ali tako da svaka uzima samo deo tela glavne petlje. Ovo može poboljšati lokalnost reference, oba podataka koji pristupaju petlji i kodu u telu glavne petlje. 
• fuzija / kombinovanje: Druga tehnika koja pokušava da smanji petlje iznad glave. Kada bi dva susedna petlje ponoviti isti broj puta (bez obzira da li taj broj je poznata po kompajliranja), njihova tela mogu se kombinovati sve dok se ne pominju jedni druge podatke.
• razmena / permutacija: Ove optimizacije razmenjuju unutrašnje petlje sa spoljnim petljama. Kada je indeks promenljive petlje u nizu, takva transformacija može da poboljša lokalnost referenci, u zavisnosti od rasporeda niza celine.
• inverzija: Ova tehnika menja standard dok petlja u do/while (takođe poznato i kao repeat/until) petlju umotanu kao if uslovno, smanjenje broja skokova sa dva za slučajeve u kojima se izvršava petlja. Na taj način duplira proveru stanja (povećanje veličine koda), ali je efikasnija, jer skokovi obično uzrokuju gubitak brzine cevovoda . Pored toga, ako je početno stanje poznato u kompajliranju vremenu i zna se da nema nuspojava, if stražar može biti preskočen.
• kretanje invarijantne petlje :  Ako se količina računa unutar petlje tokom svakog ponavljanja, a njena vrednost je ista za svaku iteraciju, to mnogo može poboljšati efikasnost da ga izbaci ispred petlje i izračuna njegovu vrednost samo jednom pre nego što počne petlja. Ovo je posebno važno sa adresom-proračuna izraza koje generišu petlje preko nizova. Za pravilnu implementaciju, ova tehnika se mora koristiti pomoću inverzne petlje, jer nisu svi kodovi sigurni da mogu biti isticani izvan petlje.
• paralelizacija: Poseban slučaj za automatsku paralelizaciju fokusiranja na petljama, restrukturiranje istih kako bi efikasno radile na multiprocesorskim sistemima. To može biti automatski urađeno pomoću kompajlera (nazvano automatska paralelizacija) ili ručno (ubacivanje paralelnih zadataka kao OpenMP ).
• Preokret: Preokret petlje obrće redosled kojim su vrednosti dodeljene indeksima promenljivih. To je suptilna optimizacija što može da pomogne eliminaciji zavisnosti i na taj način omogući druge optimizacije. Takođe, pojedine arhitekture koriste petlje konstrukcije na nivou Asemblera koji računa u jednom pravcu (npr. dekrementirani skok ako nije nula (DSNO)).
• raspored petlji : Paspored petlje deli petlju u više delova koji se mogu istovremeno raditi na više procesora.
• krivljenje medijuma : Krivljenje medijuma petlje uzima grupisanje petlji po korenu iteracije preko multidimenzionalnog niza, gde svaki niz iteracija unutrašnje petlje zavisi od ranijih iteracija, i uređuje njegov niz pristupa, tako da su samo zavisnosti između ponavljanja spoljašnje petlje.
• deoba softvera : Tip vanrednog izvršavanja iteracija petlje kako bi se sakrila kašnjenja u funkciji procesorskih jedinica.
• cepanje / piling : Razdvajanje petlje pokušava da pojednostavi petlju ili eliminiše analizu zavisnosti od razbijanja petlje u više petlji koje imaju isto telo, ali ponavlja više različitih i susednih delova opsega indeksa. Koristan i poseban slučaj je piling petlja, koja može pojednostaviti petlje sa problematičnom prvom iteraciji vršeći tu iteraciju odvojeno pre ulaska u petlju.
• pločice / blokiranje : Pločice petlje reorganizuju petlju da ponavlja više blokova podataka takve veličine da se uklapaju u keš.
• vektorizacija : Vektorizacija pokušava da pokrene što više iteracija petlje što je moguće u isto vreme na sistemu sa više procesora.
• odmotavanje petlje: Duplira telo petlje više puta, kako bi se smanjio broj puta koliko je uslov petlje testiran i broj skokova, što može smanjiti performanse i ugroziti instrukcije cevi. Potpuno odmotavanje petlje eliminiše sve iznad vrha petlje (osim ako više uputstava nađu i povećaju vreme učitavanja programa), ali zahteva da broj iteracija bude poznat u  vremenu kompajliranja (osim u slučaju JIT kompajlera). Mora se voditi računa da višestruko ponovno izračunavanje indeksiranih promenljivih nije veće od napredovanje pokazivača u originalu petlje.
• prebacivanje: Prebacivanje pomera uslovno unutar petlje van nje umnožavanjem tela petlje, i stavljanjem verzije toga unutar svakog od if i else klauzula kondicionala.

Druge optimizacije petlji

• sekcionisanje: Prvi put predstavljeno za vektorske procesore, petlja-sekcionisanje (takođe poznata kao otvoreno kopanje) je tehnika petlja-transformacija za omogućavanje SIMD-kodiranja petlji i poboljšanja performansi memorije. Ova tehnika podrazumeva svaki vektor operacija koji se napravi za veličinu manju ili jednaku sa maksimalnim trajanjem vektorske dužine na datoj vektorskoj mašini.[2] [3]

Unimodularna transformacija okvira

Unimodularni pristup transformacija koristi jednu unimodularnu matricu da opiše kombinovani rezultat jedne sekvence od mnogih gornjih transformacija. U centru ovog pristupa je pogled na skup svih pogubljenja jednog uspeha u okviru petlje n kao skup celih bodova u n-dimenzionalnom prostoru, sa tačke koja se vrši u cilju leksikografskog reda. Na primer, pogubljenja u saopštenju smeštena unutar spoljašnje petlje sa indeksom i  i unutrašnje petlje sa indeksom j može biti povezana sa parovima brojeva ( i, j). Primena unimodularne transformacije odgovara umnožavanju tačaka u okviru ovog prostora od strane matrice. Na primer, razmena dve petlje odgovara matrici $\left[{\begin{array}{cc}0&1\\1&0\end{array}}\right]$.

Unimodularna transformacija je ispravna ako čuva vremenski redosled svih zavisnosti podataka; merenje uticaja na performanse od strane unimodularne transformacije je teže. Nesavršeno ugnežđene petlje i neke transformacije (kao što je pločica) se ne uklopaju lako u tom okviru.

Poliedar ili ograničenje zasnovano na okviru

Model mnogogranika rukuje širom klasom programa i transformacija nego unimodularni okvir. Skup izvršenja skupa iskaza u okviru eventualno nesavršeno umetnutog skupa petlji se vidi kao zajednica skupa poliedra i predstavlja izvršenje izjava. Transformacija preslikavanja se primenjuje na ove poliedre, proizvodeći opis novog izvršenja naloga. Granice poliedara, zavisnost podataka, kao i transformacije često opisane korišćenjem sistema ograničenja, i ovaj pristup se često naziva kao ograničenje pristupa zasnovanog na optimizaciji petlje. Na primer, jedan iskaz unutar spoljašnje petlje  'for i := 0 to n' i jedna unutrašnja petlja 'for j := 0 to i+2' se izvršava jednom za svaki (i, j) par kao da je 0 <= i <= n   i   0 <= j <= i+2.

Još jednom, transformacija je ispravna ako čuva vremenski redosled svih zavisnosti podataka. Procena prednosti transformacije, ili pronalaženje najbolje transformacije za dati kod na datom računaru, i dalje je predmet u toku istraživanja, kao u vreme pisanja ovog teksta.

Vidi još

• Optimizacija gnezda petlje
• Model poliedra
• Skalabilni paralelizam
• Skalabilna lokalnost