Loop Unrolling, programlamada yapılabilecek optimizasyon türlerinde biridir. Adından da anlaşılabileceği gibi döngünün açılması(uzatılması)dır. Örnek vermek gerekirse, aşağıdaki gibi bir döngümüz olsun.
int a[32], b[32], c[32]; for(int i = 0; i < 32; i++) { c[i] = a[i] + b[i]; }
Bu döngünün açılmış hali aşağıdaki gibidir:
int a[32], b[32], c[32]; for(int i = 0; i < 32; i += 4) { c[i] = a[i] + b[i]; c[i + 1] = a[i + 1] + b[i + 1]; c[i + 2] = a[i + 2] + b[i + 2]; c[i + 3] = a[i + 3] + b[i + 3]; }
Döngülerin bu şekilde açılmasının nedeni, döngünün başında ve sonunda yapılan işlemlerin gereksiz tekrarından kaçmaktır. Bunlar döngünün başlangıcında i değerinin koşulu sağlayıp sağlamadığının kontrol edilmesi ve döngünün sonunda i değerinin arttırılmasıdır. Optimizasyonun ne kadar fayda sağladığını derlenen assembly kodlarından anlayabiliriz. Unrolling yapılmamış döngünün assembly kodları aşağıdaki gibidir.
3: for(int i = 0; i < 32; i++) 4: { ;Döngünün baslangıcı için i(R0) değerine 0x00 yükle 0x0800041C 2000 MOVS r0,#0x00 ;i(R0) değerini koşula(i < 32) uyup uymadığını ;kontrol eden işleme(0x08000436) dallan 0x0800041E E00A B 0x08000436 5: c[i] = a[i] + b[i]; 6: } ;a dizisinin başlangıç adresini R1'e yükle 0x08000420 4907 LDR r1,[pc,#28] ; @0x08000440 ;Bu adresin i*4(R0<<2) ilerisindeki veriyi(a[i]) R1'e yükle 0x08000422 F8511020 LDR r1,[r1,r0,LSL #2] ;Aynı işlemi b içinde yap 0x08000426 4A07 LDR r2,[pc,#28] ; @0x08000444 0x08000428 F8522020 LDR r2,[r2,r0,LSL #2] ;a[i](R1) ve b[i](R2) değerlerini topla ve R1'e at 0x0800042C 4411 ADD r1,r1,r2 ;c dizisinin başlangıç adresini R2'ye yükle 0x0800042E 4A06 LDR r2,[pc,#24] ; @0x08000448 ;Bu adresin i*4(R0<<2) ilerisine R1'deki(a[i] + b[i]) veriyi yükle 0x08000430 F8421020 STR r1,[r2,r0,LSL #2] ;i'yi(R0) 1 arttır 0x08000434 1C40 ADDS r0,r0,#1 ;i'yi(R0) 0x20(32) ile karşılaştır 0x08000436 2820 CMP r0,#0x20 ;Eğer i(R0) 0x20(32) den küçükse 0x08000420 adresine dallan 0x08000438 DBF2 BLT 0x08000420 6: } ;i'ye(R0) 0 değerini yükle 0x0800043A 2000 MOVS r0,#0x00 ;lr'ye dallan 0x0800043C 4770 BX lr ;a, b, c'nin adresleri 0x0800043E 0000 DCW 0x0000 0x08000440 0000 DCW 0x0000 0x08000442 2000 DCW 0x2000 0x08000444 0080 DCW 0x0080 0x08000446 2000 DCW 0x2000 0x08000448 0100 DCW 0x0100 0x0800044A 2000 DCW 0x2000
Her komutun yürütülme(çalıştırılma) süresine 1 cycle dersek, döndü sayısı olmak üzere toplam cycle olur. için de olur. Unrolling yapılmış döngünün de açılımı aşağıdaki gibi olacaktır.
7: for(int i = 0; i < 32; i+=4) 8: { ;Döngünün baslangıcı için i(R0) değerine 0x00 yükle 0x0800041C 2000 MOVS r0,#0x00 ;i(R0) değerini koşula(i < 32) uyup uymadığını kontrol eden işleme(0x0800047E) dallan 0x0800041E E02E B 0x0800047E 9: c[i] = a[i] + b[i]; ;a dizisinin başlangıç adresini R1'e yükle 0x08000420 4919 LDR r1,[pc,#100] ; @0x08000488 ;Bu adresin i*4(R0<<2) ilerisindeki veriyi(a[i]) R1'e yükle 0x08000422 F8511020 LDR r1,[r1,r0,LSL #2] ;Aynı işlemi b içinde yap 0x08000426 4A19 LDR r2,[pc,#100] ; @0x0800048C 0x08000428 F8522020 LDR r2,[r2,r0,LSL #2] ;R1(a[i]) ile R2'yi(b[i]) topla ve bu toplamı R1'e at 0x0800042C 4411 ADD r1,r1,r2 ;c dizisinin başlangıç adresini R2'ye yükle 0x0800042E 4A18 LDR r2,[pc,#96] ; @0x08000490 ;Bu adresin i*4(R0<<2) ilerisine R1'deki(a[i] + b[i]) veriyi yükle 0x08000430 F8421020 STR r1,[r2,r0,LSL #2] ;Aynı işlemleri i+1 içinde yap 10: c[i + 1] = a[i + 1] + b[i + 1]; 0x08000434 4A14 LDR r2,[pc,#80] ; @0x08000488 ;R1' e R0+1(i+1) değerini at 0x08000436 1C41 ADDS r1,r0,#1 0x08000438 F8522021 LDR r2,[r2,r1,LSL #2] 0x0800043C 4B13 LDR r3,[pc,#76] ; @0x0800048C 0x0800043E F8531021 LDR r1,[r3,r1,LSL #2] 0x08000442 440A ADD r2,r2,r1 0x08000444 4B12 LDR r3,[pc,#72] ; @0x08000490 0x08000446 1C41 ADDS r1,r0,#1 0x08000448 F8432021 STR r2,[r3,r1,LSL #2] ;Aynı işlemleri i+2 içinde yap 11: c[i + 2] = a[i + 2] + b[i + 2]; 0x0800044C 4A0E LDR r2,[pc,#56] ; @0x08000488 0x0800044E 1C81 ADDS r1,r0,#2 0x08000450 F8522021 LDR r2,[r2,r1,LSL #2] 0x08000454 4B0D LDR r3,[pc,#52] ; @0x0800048C 0x08000456 F8531021 LDR r1,[r3,r1,LSL #2] 0x0800045A 440A ADD r2,r2,r1 0x0800045C 4B0C LDR r3,[pc,#48] ; @0x08000490 0x0800045E 1C81 ADDS r1,r0,#2 0x08000460 F8432021 STR r2,[r3,r1,LSL #2] ;Aynı işlemleri i+3 içinde yap 12: c[i + 3] = a[i + 3] + b[i + 3]; 13: } 0x08000464 4A08 LDR r2,[pc,#32] ; @0x08000488 0x08000466 1CC1 ADDS r1,r0,#3 0x08000468 F8522021 LDR r2,[r2,r1,LSL #2] 0x0800046C 4B07 LDR r3,[pc,#28] ; @0x0800048C 0x0800046E F8531021 LDR r1,[r3,r1,LSL #2] 0x08000472 440A ADD r2,r2,r1 0x08000474 4B06 LDR r3,[pc,#24] ; @0x08000490 0x08000476 1CC1 ADDS r1,r0,#3 0x08000478 F8432021 STR r2,[r3,r1,LSL #2] 7: for(int i = 0; i < 32; i+=4) 8: { 9: c[i] = a[i] + b[i]; 10: c[i + 1] = a[i + 1] + b[i + 1]; 11: c[i + 2] = a[i + 2] + b[i + 2]; 12: c[i + 3] = a[i + 3] + b[i + 3]; 13: } ;R0'ı(i) 4 arttır 0x0800047C 1D00 ADDS r0,r0,#4 ;R0'ı(i) 0x20(32) ile karşılaştır 0x0800047E 2820 CMP r0,#0x20 ;Eğer R0(i) 0x20(32) den küçükse 0x08000420 adresine dallan 0x08000480 DBCE BLT 0x08000420 14: } ;R0'a 0 değerini yükle 0x08000482 2000 MOVS r0,#0x00 ;lr'ye dallan 0x08000484 4770 BX lr ;a, b, c'nin adresleri 0x08000486 0000 DCW 0x0000 0x08000488 0000 DCW 0x0000 0x0800048A 2000 DCW 0x2000 0x0800048C 0080 DCW 0x0080 0x0800048E 2000 DCW 0x2000 0x08000490 0100 DCW 0x0100 0x08000492 2000 DCW 0x2000
Burada göze çarpan önemli şeylerden birisi kod alanının büyümesidir. Loop Unrolling'in dezavantajlarından birisi de budur. Yukarıda yaptığımız gibi toplam cycle bu sefer olur. için (i 4'er 4'er arttırılıyor) toplam cycle bu sefer olur. Aradaki fark cycle dir. cycle uygulamaya göre az bir zaman kazanımı olabilir ancak toplam işlem sayısı(bu örnekte 32 idi) ve döngü içinde yapılan işlem sayısı arttıkça bu fark daha da artacaktır. Bu zaman kazanımını hesaplamak istersek; toplam işlem sayısı, ise her döngüde yapılan işlem sayısı olmak üzere:
şeklinde hesaplanır.
Yukarıdaki assembly kodları dikkatlice incelenirse, derleyicinin iyi bir kod ürettiği söylenemez. Bunun nedeni derleyicinin -O0 optimizasyon seviyesinde kodları derlemesidir. Optimizasyon seviyesini -O2 yaparak 2. programın toplam cycle sayısı yapılabilir. Optimizasyon seviyesi arttırıldıkça derleyici kendi kendine Loop Unrolling işlemini de yapar. Aşağıda Loop Unrolling kullanılmadan -03 ve -Otime(işlemleri daha kısa sürede çalışacak şekilde ayarlayan bir optimizasyon) optimizasyonları ile derlenen bir programın assembly çıktısı vardır.
;R4-R9 registerlerini stack'e at 0x080003CC E92D03F0 PUSH {r4-r9} 7: for(int i = 0; i < 32; i+=1) 8: { ;a dizisinin başlangıç adresini R7'ye yükle 0x080003D0 4F15 LDR r7,[pc,#84] ; @0x08000428 ;R8'e R7+0x80 değerini yükle ;Burada R7+0x80, b dizinin başlangıç adresine denk geliyor ;Yani R8'e b dizisinin başlangıç değeri yüklenmiş oluyor 0x080003D2 F1070880 ADD r8,r7,#0x80 9: c[i] = a[i] + b[i]; 10: /*c[i + 1] = a[i + 1] + b[i + 1]; 11: c[i + 2] = a[i + 2] + b[i + 2]; 12: c[i + 3] = a[i + 3] + b[i + 3];*/ 13: } ;a[0] değerini R2'ye yükle 0x080003D6 683A LDR r2,[r7,#0x00] ;b[0] değerini R3'ye yükle 0x080003D8 F8D83000 LDR r3,[r8,#0x00] ;R9'a R7+0x100 değerini yükle ;Burada R7+0x100 c dizisinin başlangıç adresine denk geliyor ;Yani R9'a c dizisinin başlangıç değeri yüklenmiş oluyor 0x080003DC F5077980 ADD r9,r7,#0x100 ;R3'e R3+R2(a[0]+b[0]) değerini at 0x080003E0 4413 ADD r3,r3,r2 14: } ;R3(a[0]+b[0]) değerini R9'un(&c[0]) adreslediği konuma yaz 0x080003E2 F8C93000 STR r3,[r9,#0x00] ;a[1] değerini R4'e yükle 0x080003E6 687C LDR r4,[r7,#0x04] ;b[1] değerini R12'ye yükle 0x080003E8 F8D8C004 LDR r12,[r8,#0x04] ;R7(a) değerini R1'e, R8(b) değerini R0'a, R9(c) değerini R2'e 0x080003EC 4639 MOV r1,r7 0x080003EE 4640 MOV r0,r8 0x080003F0 464A MOV r2,r9 ;R3'e 0x0F(15) değerini yükle 0x080003F2 230F MOVS r3,#0x0F ;R1+0x08(a+0x08=&a[2]) adresindeki veriyi R5'e at ve adresi güncelle ;Bundan sonra R1, a[2] verisinin adres değerine sahip olacak 0x080003F4 F8515F08 LDR r5,[r1,#0x08]! ;R0+0x08(b+0x08=&b[2]) adresindeki veriyi R6'e at ve adresi güncelle 0x080003F8 F8506F08 LDR r6,[r0,#0x08]! ;R12 ye R12+R4(b[1]+a[1]) değerini at 0x080003FC 44A4 ADD r12,r12,r4 ;R12(a[1]+b[1]) deki değeri R2+0x04(c+0x04=c[1]) adresine yükle 0x080003FE F8C2C004 STR r12,[r2,#0x04] ;R4'e R1+0x04(&a[2]+0x04=&a[3]) adresindeki veriyi yükle 0x08000402 684C LDR r4,[r1,#0x04] ;R5'e R5+R6(a[2]+b[2]) değerini yükle 0x08000404 4435 ADD r5,r5,r6 ;R12'ye R0+0x04(&b[2]+0x04=&b[3]) adresindeki veriyi yükle 0x08000406 F8D0C004 LDR r12,[r0,#0x04] ;R5'e R2+0x08(c+0x08=&c[3]) adresindeki veriyi yükle ve adresi güncelle 0x0800040A F8425F08 STR r5,[r2,#0x08]! ;R3' den 1 çıkar 0x0800040E 1E5B SUBS r3,r3,#1 ;Eğer R3 0 değil ise 0x080003F4 adresine dallan 0x08000410 D1F0 BNE 0x080003F4 ;a[31] değerini R0'a yükle 0x08000412 6FF8 LDR r0,[r7,#0x7C] ;b[31] değerini R0'a yükle 0x08000414 F8D8107C LDR r1,[r8,#0x7C] ;R0'a R0+R1(a[31]+b[31]) değerini at 0x08000418 4408 ADD r0,r0,r1 ;R0(a[31]+b[31]) daki değeri R9+0x7C(c+0x7C=&c[31]) adresine yükle 0x0800041A F8C9007C STR r0,[r9,#0x7C] ;R4-R9 registerlerini stack'den çek 0x0800041E E8BD03F0 POP {r4-r9} ;R0'a 0x00 değerini at 0x08000422 2000 MOVS r0,#0x00 ;lr^ye dallan 0x08000424 4770 BX lr 0x08000426 0000 DCW 0x0000 0x08000428 0000 DCW 0x0000 0x0800042A 2000 DCW 0x2000 0x0800042C F04F7040 MOV r0,#0x3000000 0x08000430 EEE10A10 VMSR FPSCR, r0 0x08000434 4770 BX lr 0x08000436 0000 MOVS r0,r0 0x08000438 0448 DCW 0x0448 0x0800043A 0800 DCW 0x0800 0x0800043C 0000 DCW 0x0000 0x0800043E 2000 DCW 0x2000 0x08000440 07E0 DCW 0x07E0 0x08000442 0000 DCW 0x0000 0x08000444 01C4 DCW 0x01C4 0x08000446 0800 DCW 0x0800
Kodlar incelenirse derleyici önce c[0] = a[0] + b[0] işlemini yapıp daha sonra 2'li olarak yani Loop Unrolling yaparak 15 seferde c[n] = a[n] + b[n] ve c[n+1] = a[n+1] + b[n+1] işlemlerini yaptığı ve son olarak da c[31] = a[31] + b[31] işlemini yaptığı görülmektedir. İşlemin toplam cycle süresi ile ilgili kesin bir denklem yazamayız ama yukarıdaki işlemlerin toplam süresini cycle olarak hesaplayabiliriz. -O3 ve -Otime optimizasyonları ile cycle kazancımız olmuştur.
Sonuç olarak Loop Unrolling büyük döngülerde işlem zamanını azaltmak için uygulabilecek yararlı bir yöntemdir. En büyük dezavantajı kod alanının büyümesidir. Kod alanının sınırlı olmadığı ve hız gerektiren uygulamalarda gerekli optimizasyonlar ile büyük farklar yaratılabilir.