Döngü açma

Döngü açma (İngilizcesi loop unwinding veya loop unrolling), bir programın çalışmasını hızlandıran döngü dönüştürme yöntemlerinden biridir. Bu yöntem yazılan programın kod satır sayısını arttırmaktadır. Döngülerdeki dönüşüm manuel olarak programcı tarafından yapılabileceği gibi kodlar derleyiciler tarafından da düzenlenebilmektedir.Döngü açmanın amacı, döngülerdeki kontrol buyruklarını (örnek: gösterge aritmetiği ya da "döngü sonu" testleri) azaltarak ya da tamamen ortadan kaldırarak programın çalışmasını hızlandırmaktır. Döngüler, birbirini tekrarlayan ve bağımsız kod satırları eklenerek tekrar yazılır, bunun sonucunda da döngülerde harcanan fazla zaman yükü ortadan kaldırılır."Sıkı" döngülerdeki fazla zaman yükü, "döngü sonu" testleri ile olabileceği gibi, bir dizinin sonraki elemanına geçmeyi sağlayan gösterge indisini arttırma işlemi (gösterge aritmetiği) sebebiyle olur. Optimizasyon sağlayan bir derleyici ya da çevirici her ayrı ayrı referanslanmış dizi değişkeninin değerini hesapladığı takdirde, kodları direkt olarak makine dili buyruklarına çevirir ve böylece yürütme zamanında fazladan aritmetik operasyon yapılmasına gerek kalmaz.Yürütülen buyrukların azalmasından kaynaklanan çalışma hızındaki artış, programın uzunluğundaki fazlalaşmadan kaynaklanan yavaşlamayı dengelediği takdirde başarımda büyük ölçüde artış gözlenmektedir.Döngüdeki kod satırlarının birbirinden bağımsız olması durumunda bu satırlar paralel işleme ile çalışabilir.Optimizasyon sağlayan derleyiciler çoğunlukla döngü açma işlemini otomatik olarak ya da isteğe bağlı olarak yapabilmektedir.Derleme zamanında dizideki elemanların sayısı bilinmiyor ise dinamik olarak gerçekleştirimi yapılabilir.Tek iterasyonda geçici değişkenleri saklamak için gereken yazmaç sayısında artış olma ihtimali vardır, ki bu durum başarımı etkilemektedir.Kod uzunluğundaki artış, buyruk önbelleğinde isabetsizliklere yol açabilir, ki bu durum başarımı olumsuz etkilemektedir.Optimizasyon yapabilen derleyiciler tarafından yapılmadığı takdirde kodun okunabilirliğinde azalmalar olabilir.Aşağıda bir koleksiyondan 100 adet item silen bir bilgisayar programı vardır. Bu normalde delete(item_number) fonksiyonunu çağıran bir for-döngüsü tarafından yapılmaktadır. Eğer programın bu kısmı optimize edilecek olursa ve fazladan oluşan zaman yükü programdaki önemli kaynakları elinde barındırıyorsa, zaman yükü yok edildiğinde bu döngünün açılması programın hızlandırılması için kullanılabilir.Bu değişiklik sayesinde yeni programın 100 yerine 20 iterasyon yapması gerekir. Bu sayede atlamaların ve koşullu dallanmaların sadece %20'si yapılacak ve döngüde fazladan oluşan zaman yükü önemli ölçüde azalır. Eğer optimizasyon yapan derleyici otomatik olarak fonksiyonu çağıran satır yerine fonksiyonun içeriğini kullanırsa daha da büyük bir başarım artışı sağlanır. Çünkü 100 adet fonksiyon çağrımı yapan kod satırı da derleyici tarafından silinecektir. İyileştirmeyi en uygun hale getirmek için, açılan döngüde gösterge ile tanımlanmış değişken bulunmaması gerekmektedir. Bu da genellikle indis tabanlı referans yerine, "taban adresi + konum" şeklindeki adresleme ile yapılır.Öte yandan bu şekilde manuel olarak yapılan döngü açma işlemi kaynak kod boyutunu 3 satırdan 7 satıra çıkarmaktadır. Bu da daha fazla satırın derleyici tarafından kontrol edilmesine ve işlenmesine sebep olacaktır. Derleyici kodu bu şekilde derlemek için daha fazla yazmaç kullanabilir.Açılmamış olan döngü daha hızlıdır. Bu kodda ENDWHILE (derlendiğinde döngünün ilk satırına bir "atla" kodu ekler) satırı %66 daha az çalışacaktır.Daha da iyi olanı ince ayar yapılmış olan kod parçasıdır. Bazı derleyiciler otomatik olarak ince ayarı gerçekleştirir ve koşulsuz olan atlamaları elimine eder.Döngü açmanın faydaları programda kullanılan dizinin büyüklüğüne bağlı olduğu için çoğunlukla yürütme zamanından önce bilinememektedir. JIT (Just-in-time compilation) yapan derleyiciler döngülerin standart bir şekilde çalıştırılmasına veya ayrı ayrı buyrukları sıralayarak farklı bir kod oluşturup döngülerin açılmasına karar verebilirler. Bu esneklik just-in-time derlemenin statik veya manuel olarak döngülerin açılmasına göre büyük üstünlük sağladığını gösterir.Assembly dili programcıları da verimli dallanma tablolarında kullanılan tekniğe benzer bir teknik kullanarak dinamik döngü açma tekniğinden faydalanabilmektedir. Aşağıdaki örnek IBM 360 veya Z mimarisini kullanan çevirici kodlarıyla yazılmıştır. 256 baytlık ve 50 elemanlı 2 dizi olan FROM ve TO dizilerinde, 'FROM' dizisinin 100 baytını 'TO' dizisine kopyalama işlemi gerçekleştirilmektedir.LM    R15,R2,INIT                       load R15= '16', R0=number in array, R1--> 'FROM array', R2--> 'TO array'MH    R15,=AL2(ILEN)                    multiply by length of (MVC..) instruction (=6 in this example)* Assignment (move) table - (first entry has maximum allowable offset with single register = X'F00' in this example)ALL      MVC   15*256(100,R2),15*256(R1)         * move 100 bytes of 16th entry  from array 1 to array 2 (with drop through)ILEN     EQU   *-ALL                                         length of (MVC...) instruction sequence; in this case =6MVC   12*256(100,R2),12*256(R1)         * All 16 of these 'move character' instructions use base plus offset addressingMVC   11*256(100,R2),11*256(R1)         * and each to/from offset decreases by the length of one array element (256).MVC   10*256(100,R2),10*256(R1)         * This avoids pointer arithmetic being required for each element up to aMVC   09*256(100,R2),09*256(R1)         * maximum permissible offset within the instruction of X'FFF'. The instructionsMVC   08*256(100,R2),08*256(R1)         * are in order of decreasing offset, so the first element in the set is movedL     R15,MAXM1                         re-load (maximum MVC's) in R15 (destroyed by calculation earlier)* ----- Define static Constants and variables (These could be passed as parameters) ---------------------------------  *INIT     DS    0A                                4 addresses (pointers) to be pre-loaded with a 'LM' instructionN        DC    A(50)                             number of actual entries in array (a variable, set elsewhere)* ----- Define static Arrays (These could be dynamically acquired) --------------------------------------------------  *Bu örnekte, klasik döngü kullanımıyla 50 iterasyonluk bir döngü ile yaklaşık 202 buyruk çalıştırılacakken, dinamik kod ile 89 buyrukta tamamlanabilecektir. Dizi 2 girdi ile yapılsaydı yaklaşık olarak yine normal, açılmamış döngüde harcanan zamana denk olacaktı. Koddaki artış ise 108 bayt kadar olup, binlerce girdi ile denense bile aynı sonucu verecekti. Tabii ki benzer yöntemler birden fazla buyruk işin içine katıldığında da birleşik buyruk uzunluğu ayarlanarak kullanılabilir. Örneğin yukarıdaki kod parçasında kopyalanan 100 bayttan hemen sonra kopyaladığımız kısımları silmek istersek fazladan temizleme buyruğu her MVC buyruğu çağırıldıktan sonra eklenebilir.'Aşağıdaki örnek C programlama dilinde yazılmış bir döngü açma programıdır. Yukarıdaki assembler örneğinin aksine, gösterge/indis aritmetiği compiler tarafından kullanılmaktadır. Bunun sebebi dizinin adreslenmesinde kullanılan (i) değişkenidir. Tam optimizasyon için indislerin gerçek değerlerinin (i) değişken değeriyle değiştirilmesi gerekmektedir.case 7 : printf("process(%d)\n", i +6);           /* process and rely on drop through drop through */case 2 : printf("process(%d)\n", i +1);          /* two left                                      */case 1 : printf("process(%d)\n", i   );          /* just one left to process                      */case 0 :                                         /* none left                                     */