Döngü değişimi - Loop interchange

İçinde derleyici teorisi, döngü değişimi iç içe geçmiş bir tarafından kullanılan iki yineleme değişkeninin sırasını değiştirme işlemidir. döngü. İç döngüde kullanılan değişken dış döngüye geçer ve bunun tersi de geçerlidir. Genellikle çok boyutlu unsurların olmasını sağlamak için yapılır. dizi hafızada bulundukları sırayla erişilir, referans yeri.

Örneğin, kod parçasında:

i için 0'dan 10'a, j için 0'dan 20'ye a [i, j] = i + j

döngü değişimi şunlarla sonuçlanır:

j için 0'dan 20'ye, i için 0'dan 10'a a [i, j] = i + j

Bazen böyle bir dönüşüm, daha fazla optimizasyon için fırsatlar yaratabilir. otomatik vektörleştirme dizi atamalarının.

Döngü değişiminin faydası

Satır ve sütun ana düzeninin çizimi

Döngü değişiminin temel amacı, CPU önbelleği dizi öğelerine erişirken. Bir işlemci bir dizi öğesine ilk kez eriştiğinde, bellekten önbelleğe kadar tüm bir veri bloğunu alır. Bu bloğun ilkinden sonra daha fazla ardışık eleman olması muhtemeldir, bu nedenle bir sonraki dizi elemanı erişiminde, doğrudan önbellekten getirilecektir (bu, yavaş ana bellekten almaktan daha hızlıdır). Önbellek eksik döngü içindeki bitişik olarak erişilen dizi öğeleri farklı bir önbellek bloğundan geliyorsa oluşur ve döngü değişimi bunu önlemeye yardımcı olabilir. Döngü değişiminin etkinliği, temeldeki donanım tarafından kullanılan önbellek modeline ve derleyici tarafından kullanılan dizi modeline bağlıdır ve dikkate alınmalıdır.

İçinde C programlama dili, aynı satırdaki dizi elemanları ardışık olarak bellekte saklanır (a [1,1], a [1,2], a [1,3]) - in ana satır sırası. Diğer taraftan, FORTRAN programlar, aynı sütundaki dizi öğelerini birlikte (a [1,1], a [2,1], a [3,1]) kullanarak depolar büyük sütun. Bu nedenle, ilk örnekteki iki yineleme değişkeninin sırası bir C programı için uygunken, ikinci örnek FORTRAN için daha iyidir.[1] Derleyicileri optimize etme programcılar tarafından yanlış sıralamayı tespit edebilir ve daha iyi önbellek performansı elde etmek için sırayı değiştirebilir.

Uyarı

Herhangi biri gibi derleyici optimizasyonu döngü değişimi daha kötü performansa yol açabilir çünkü önbellek performansı hikayenin sadece bir parçasıdır. Aşağıdaki örneği ele alalım:

 yapmak ben = 1, 10000   yapmak j = 1, 1000     a[ben] = a[ben] + b[j,ben] * c[ben]   bitirmek bitirmek

Bu örnekteki döngü değişimi, b (j, i) 'ye erişimin önbellek performansını artırabilir, ancak iki ekstra yük getirdiği için iç döngüde a (i) ve c (i)' nin yeniden kullanımını bozacaktır (a (için i) ve c (i) için) ve her yineleme sırasında fazladan bir mağaza (a (i) için). Sonuç olarak, döngü değişiminden sonra genel performans düşebilir.

Emniyet

İterasyon değişkenlerini, yürütülmeleri gereken sırayla ifadeler arasındaki bağımlılıklar nedeniyle değiştirmek her zaman güvenli değildir. Bir derleyicinin döngüleri güvenle değiştirip değiştiremeyeceğini belirlemek için, bağımlılık analizi gereklidir.

Ayrıca bakınız

Referanslar

  1. ^ "Döngü değişimi" (PDF). HP-UX Sistemleri için Paralel Programlama Kılavuzu. HP. Ağustos 2003.

daha fazla okuma