Odmotavanje petlje
Odmotavanje petlje ili odvijanje petlje je tehnika transformacije petlje koja pokušava da optimizuje brzinu izvršenja programa nauštrb binarne veličine. Transformacije se može izvršiti ručno od programera ili preko optimizirajućeg komajlera.
Cilj odmotavanja petlje je uvećanje brzine programa smanjenjem ili eliminisanjem instrukcija koje kontrolišu petlju, kao što su aritmetički pokazivač i "end of loop" testovi za svaku iteraciju;[1] smanjenje grešaka granjanja; kao i "skrivene latencije, posebno, kašnjenje čitanja podataka iz memorije".[2] Da bi eliminisale ove troškove, petlje mogu biti ponovo napisane kao ponovljena sekvenca sličnih nezavisnih iskaza.[3]
Prednosti uredi
Troškovi u "tesnim" petljama se često sastoje iz instrukcija za inkrementiranje pokazivača ili indeksa do sledećeg elementa u nizu (aritmetički pokazivač), kao i "end of loop" testova. Ako je optimizirajući kompajler ili asebler u mogućnosti da izračuna ofsete za svaku individualno referenciranu promenjivu iz niza, one se mogu ugraditi u instrukcije mašinskog koda direktno, pa ne zahtevaju dodatne aritmetičke operacije tokom izvršenja (ovo nije slučaj u primeru dole).
- Smanjenjem izvršenih instrukcija kompenzuje se za umanjenje performansi uzrokovano povećanjem veličine programa.
- kazna grananja je minimizirana.
- Ako iskazi u petlji nisu zavisni jedan od drugog (gde iskazi koji se dešavaju ranije u petlji ne utiču na iskaze koje ih prate), iskazi se potencijalno mogu izvršiti paralelno.
- Može se implementirati dinamički ako je broj elemenata u nizu nepoznat u vreme izvršenja (kao u Dafovom uređaju).
Optimizirajući kompajleri će ponekad izvršiti odmotavanje automatski ili po zahtevu.
Mane uredi
- Veća veličina programskog koda, koja može biti neželjena, pogotovo za ugrađene sisteme.
- Takođe može izazvati povećanje u promašajima instrukcijskog keša, koje mogu loše uticati na performanse.
- Osim ako nije izvršeno transparentno i od strane optimizirajućeg kompajlera, kod može biti manje čitljiv.
- Ako kod u telu petlje sadrži pozive funkcija, možda neće biti moguće odmotovanje sa ekspanzijom u liniji, jer će povećanje u veličini koda biti preveliko. To može biti kompromis između dve optimizacije.
- Moguće povećanje korišćenja registra u jednoj iteraciji za skladištenje privremenih promenjivih, što može smanjiti performanse, iako će sve zavisiti od mogućih optimizacija.
- Osim veoma malih i jednostavnih kodova, odmotane petlje koje sadrže grananje su još sporije od rekurzija.
Ručno – manuelno odmotavanje petlje uredi
Ručno (ili statičko) odmotavanje uključuje programera koji alalizira petlju i interpretira iteracije u sekvencije instrukcija koje će smanjiti troškove petlje. Ovo je suprotno dinamičkom odmotavanju koje odrađuje kompajler.
Jednostavni ručni primer u C uredi
Sledi procedura u programu koja briše 100 stvari iz skupa. Ovo se normalno radi preko for – petlje koja poziva funkciju delete(item_number). Ako je ovo deo programa koji treba optimizirati, i troškovi petlje zahtevaju ozbiljne resurse u poređenju sa onim u delete(x) petlji, odmotavanje ga može ubrzati.
| Normalna pelja | Nakon odmotavanja petlje |
|---|---|
int x;
for (x = 0; x < 100; x++)
{
delete(x);
}
|
int x;
for (x = 0; x < 100; x+=5)
{
delete(x);
delete(x+1);
delete(x+2);
delete(x+3);
delete(x+4);
}
|
Kao rezultat ove modifikacije, novom programu treba samo 20 iteracija umesto 100. Posle, samo 20% skokova i kondicionalnog grananja moraju se obaviti, i reprezentuju, preko mnogo iteracija, potencijalno značajno uvećanje u administraciji troškova petlje. Da bi napravili optimalne beneficije, nijedna promenjiva se ne sme specifikovati u odmotanom kodu koji zahteva aritmetiku pokazivača. Ovo obično zahteva "base plus offset" adresiranje umesto indeksiranog referenciranja.
Sa druge strane, ovo odmotavanje širi izvorni kod sa 3 na 7 linija koje moraju da se naprave, provere i debaguju, i kompajler možda mora da alocira više registra za čuvanje promenjivih u proširenoj iteraciji petlje. Dodatno, promenjive kontrole petlje i broj operacija u strukturi odmotanoe petlje moraju se odabrati pažljivo tako da rezultat bude isti kao i originalni kod. Na primer, implikacije će biti velike ako ukupan broj iteracija nije deljiv sa 5. Ručne popravke postaju komplikovanije ako su promenjivi test uslovi.
Rana kompleksnost uredi
U prostom slučaju, kontrola petlje je administrativni trošak koji uređuje produktivne iskaze. Sama petlja ne doprinosi željenim rezultatima, što olakšava programeru da ne mora da reciplira kod stotine puta što se moglo uraditi pomoću generacija replikacija ili tekst editora. Slično, if iskazi i drugi iskazi kontrole toka se mogu zameniti kodnom replikacijom. Programi lako prate kombinacije, ali programerima je ovo ponavljanje dosadno i prave greške. Imajmo u vidu:
| Normalna petlja | Nakon odmotavanja petlje |
|---|---|
for i := 1:8 do
if i mod 2 = 0 then do_evenstuff(i)
else do_oddstuff(i);
next i;
|
do_oddstuff(1); do_evenstuff(2); do_oddstuff(3); do_evenstuff(4); do_oddstuff(5); do_evenstuff(6); do_oddstuff(7); do_evenstuff(8); |
Ali naravno, izvršeni kod ne mora da bude buđenje procedure, i sledeći primer uključuje indeksnu promenjivu u računanju:
| Normalna petlja | Nakon odmotavanja petlje |
|---|---|
x(1) := 1;
For i := 2:9 do
x(i) := x(i - 1)*i;
print i,x(i);
next i;
|
x(1) := 1; x(2) := x(1)*2; print 2,x(2); x(3) := x(2)*3; print 3,x(3); x(4) := x(3)*4; print 4,x(4); ...etc. |
što, ako se kompajlira, može napraviti mnogo koda (print iskazi su ozloglašeni) ali dalja optimizacija je moguća. Ovaj primer referencira samo x(i) i x(i - 1) u petlji (zadnji samo razvija novu vrednost x(i)) stoga, zbog toga što se kasnije ne pojavljuje referenca na niz x koji je razvijen ovde, korišćenje istog bi moglo biti zamenjeno promenjivom. Takva promena bi značila da prosta promenjiva čija vrednost je promenjena a ako ostane u nizu, kompajlerova analiza možda uvidi da su vrednosti u nizu konstantne, svaka izvedena iz prethodne konstante, i stoga kod postaje
print 2,2; print 3,6; print 4,24; ...etc.
Bilo bi pravi iznenađenje ako kompajler prepozna da je x(n) = Factorial(n).
Generalno, sadržaj petlje može biti veliki, uključujući zapetljano indeksiranje niza. Ove slučajeve je verovatno najbolje ostaviti za optimizujuće kompajlere. Repliciranje unutrašnjih petlji može dozvoliti mnogo mogućih optimizacija a da dobitak bude mali osim ako je n veliko.
Odmotavanje WHILE petlji uredi
Pseudokod WHILE petlje – sličan sledećem:
| Normalna petlja | Nakon odmotavanja petlje | Odmotana i sređena petlja |
|---|---|---|
WHILE (condition) DO
action
ENDWHILE
.
.
.
.
.
.
|
WHILE (condition) DO
action
IF NOT(condition) THEN GOTO break
action
IF NOT(condition) THEN GOTO break
action
ENDWHILE
LABEL break:
.
|
IF (condition) THEN
REPEAT {
action
IF NOT(condition) THEN GOTO break
action
IF NOT(condition) THEN GOTO break
action
} WHILE (condition)
LABEL break:
|
Odmotavanje je brže jer ENDWHILE (koji će se kompajlirati u jump na početku petlje) će biti izvršeno 66% manje.
Još bolje, sređeni pseudokod, koji se može izvršiti automatski nekoim oprimizujučim kompajlerima, eliminišući bezuslovne skokove potpuno.
Dinamičko odmotavanje uredi
Pošto su benefiti odmotavanja petlje često zavisni od veličine niza koji se možda i ne zna do početka izvršenja, JIT kompajleri (na primer) mogu da odrede da li da probude standardnu sekvencu petlje ili da umesto toga generišu relativno kratku sekvencu indivnidualnih instrukcija za svaki element. Ova fleksibilnost je jedna od prednosti JIT tehnika u kontrastu sa statičkim ili ručnim optimizacijama. U ovoj situaciji, često su male vrednosti 'n' gde su dobici korisni, rezultujući u veoma malom ili nikakvnom povećanju programa.
Programeri asemblerskog jezika (uključujući pisce optimizujućih kompajlera) su u beneficiji i od tehnike dinamičkog odmotavanja petlje, koristeći metod sličan korišćenom u efikasnim tablama grananja. Ovde je prednost najveća gde je maksimum ofseta koji se može specifirati mašinskom instrukcijom (koji će biti označeni zastavom ako je asembler prevaziđen). Primer ispod je za IBM/360 ili Z/Architecture asembelere i zauzima polje od 100 bajtova (na ofsetu 0) i koji treba kopirati iz niza 'FROM' u niz 'TO' – oba imaju dužine elemenata od 256 bajta sa 50 ulaza
* иницијализовати све регистре да показују на низове (R14 је адреса за повраћај)
LM R15,R2,INIT load R15= '16', R0=number in array, R1--> 'FROM array', R2--> 'TO array'
LOOP EQU *
SR R15,R0 узми 16 минус број у низу
BNP ALL ако је n > 16 треба урадити целу секвенцу, онда поновити
* (ако # уноса = 0, R15 ће и даље бити 16, па ће сви MVCови бити заобиђени)
* израчунај офсет (почни од MVC секвенце) за некондиционо гранање
MH R15,=AL2(ILEN) помножи дужином (MVC..) инструкције (= 6 у овом примеру)
B ALL(R15) индексирана инструкција гранања(до MVC са испуштањем)
ALL MVC 15*256(100,R2),15*256(R1) * помери 100 бајта 16ог уноса од низа 1 до низа 2
ILEN EQU *-ALL дужина (MVC...) инструкционе секвенце; у овом случају = 6
MVC 14*256(100,R2),14*256(R1) *
MVC 13*256(100,R2),13*256(R1) *
MVC 12*256(100,R2),12*256(R1) * свих 16 покретачких карактера инструкције користе base plus offset адресирање
MVC 11*256(100,R2),11*256(R1) * и сваки од-до офсета смањује за дужину једног елемента низа (256).
MVC 10*256(100,R2),10*256(R1) * овим се избегава да аритметика тражи да сваки елемет буде
MVC 09*256(100,R2),09*256(R1) * дозвољени максимални офсет унутар инструкције X'FFF'. Инструкције
MVC 08*256(100,R2),08*256(R1) * су у реду смањујућег офсета, па је први елемент у скупу померен на крај
MVC 07*256(100,R2),07*256(R1) *
MVC 06*256(100,R2),06*256(R1) *
MVC 05*256(100,R2),05*256(R1) *
MVC 04*256(100,R2),04*256(R1) *
MVC 03*256(100,R2),03*256(R1) *
MVC 02*256(100,R2),02*256(R1) *
MVC 01*256(100,R2),01*256(R1) помери 100 бајта другог уноса
MVC 00*256(100,R2),00*256(R1) помери 100 бајта првог уноса
*
S R0,MAXM1 смањи Count = остали уноси за процесуирање
BNPR R14 ... нема више, врати адресу на R14
AH R1,=AL2(16*256) повећај 'FROM' показивач регистра после првог скупа
AH R2,=AL2(16*256) повећај 'TO' показивач регистра после првог скупа
L R15,MAXM1 поново увези (макс MVCа) у R15 (који је уништен пређашњим рачунањем)
B LOOP изврши петљу поново
*
* ----- Дефиниши статичке константе и промењиве (они могу да прођу као параметри) --------------------------------- *
INIT DS 0A 4 адресе (показивача) за пре вађење са 'LM' инструкцијом
MAXM1 DC A(16) максимум MVCа
N DC A(50) број стварних уноса у низ (промењива постављена другде)
DC A(FROM) адреса почетка првог низа ("pointer")
DC A(TO) адреса почетка другог низа ("pointer")
* -----Дефиниши статичке низове (они могу бити динамички стечени) -------------------------------------------------- *
FROM DS 50CL256 низ од макс 50 уноса од којих је сваки 256 бајта
TO DS 50CL256 низ од макс 50 уноса од којих је сваки 256 бајта
U ovom primeru će optrilike 202 instrukcije zahtevati konvencionalnu petlju (50 iteracija) a gornji dinamički kod zahteva samo oko 89 instrukcija (ili čuvanje otprilike 56%). Ako se niz sastojao od samo 2 unosa, i dalje bi se izvršavao u isto vreme kao i originalna neodmotana petlja. Povećanje veličine koda od samo 108 bajta čak iako su hiljade unosa u nizu. Slične tehnike se mogu koristiti i ako se koriste više instrukcija, sve dok se kombinovane dužine instrukcija menjaju prema tome. Na primer u istom promeru, ako se zahteva da se očisti ostatak svakog unosa niza na nulu odmah nakon što je polje od 100 bajta kopirano, dodatna instrukcija za čišćenje, 'XC xx*256+100(156,R1),xx*256+100(R2)', se može dodati odmah nakon svake MVC u sekvenci (gde 'xx' odgovara vrednosti u MVC iznad njega).
Naravno, moguće je generisati gornji kod u jednoj liniji koristeći asemblerski makro iskaz, specifirajući samo 4 ili 5 operanada, što čini optimizaciju spremnom za neiskusne programere.
C primer uredi
Sledeći primer demonstrira dinamičko odmotavanje za jednostavni program napisan u C. Suprotno asemblerskom primeru iznad, pokazivač/indeks aritmetika se i dalje generišeu kompajleru u ovom primeru jer se promenjiva (i) i dalje koristi za adresiranje elementa iz niza. Potpuna optimizacija je moguća samo ako su apsolutni indeksi korišćeni u iskazima zamene.
#include<stdio.h>
#define TOGETHER (8)
int main(void)
{
int i = 0;
int entries = 50; /* укупан број за процесуирање */
int repeat; /* број понављања.. */
int left = 0; /* подсетник (process later) */
repeat = (entries / TOGETHER); /* број понављања */
left = (entries % TOGETHER); /* израчунај остатак */
/* одмотај петљу у осмице */
while( repeat-- > 0 )
{
printf("process(%d)\n", i );
printf("process(%d)\n", i + 1);
printf("process(%d)\n", i + 2);
printf("process(%d)\n", i + 3);
printf("process(%d)\n", i + 4);
printf("process(%d)\n", i + 5);
printf("process(%d)\n", i + 6);
printf("process(%d)\n", i + 7);
/* аптедјтуј индекс за количину процесуирану одједном */
i += TOGETHER;
}
switch (left)
{
case 7 : printf("process(%d)\n", i + 6); /* процесуирај и ослони се на пропуштање */
case 6 : printf("process(%d)\n", i + 5);
case 5 : printf("process(%d)\n", i + 4);
case 4 : printf("process(%d)\n", i + 3);
case 3 : printf("process(%d)\n", i + 2);
case 2 : printf("process(%d)\n", i + 1); /* још два */
case 1 : printf("process(%d)\n", i ); /* још један */
case 0 : ; /* није остао ниједан */
}
}
Reference uredi
- ^ Ullman, Jeffrey D.; Aho, Alfred V. (1977). Principles of compiler design. Reading, Mass: Addison-Wesley Pub. Co. str. 471–2. ISBN 0-201-10073-8.
- ^ Petersen, W.P.; Arbenz, P. (2004). Introduction to Parallel Computing. Oxford University Press. str. 10.
- ^ Nicolau, Alexandru (1985). „Loop Quantization: Unwinding for Fine-Grain Parallelism Exploitation”. Dept. of Computer Science Technical Report. Ithaca, NY: Cornell University. OCLC 14638257.
Litaratura uredi
- Kennedy, Ken; Allen, Randy (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 978-1-55860-286-1.
Spoljašnje veze uredi
- Chapter 7, pages 8 to 10, of Michael Abrash's Graphics Programming Black Book is about loop unrolling, with an example in x86 assembly.
- Generalized Loop Unrolling, gives a concise introduction.
- Optimizing subroutines in assembly language Agner Fog's optimizations handbook with the loop unrolling technique (2012)