Loop Unrolling

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, n döndü sayısı olmak üzere toplam cycle \text{T}_c=4+10n olur. n=32 için de \text{T}_c=4+10*32=324 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 \text{T}_c=4+37n olur. n=8 için (i 4'er 4'er arttırılıyor) toplam cycle bu sefer \text{T}_c=4+37*8=300 olur. Aradaki fark 324-300=24 cycle dir. 24 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; t toplam işlem sayısı, k ise her döngüde yapılan işlem sayısı olmak üzere:

\begin{align*}\text{T}_{fark}=4+10t-4-10\frac{t}{k}=10t\Bigg(1-\frac{1}{k}\Bigg)\end{align*}

ş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ı \text{T}_c=10+22n 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 \text{T}_c=169 cycle olarak hesaplayabiliriz. -O3 ve -Otime optimizasyonları ile \text{T}_{fark}=324-169=155 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.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.