Loop Interchange — ichma-ich sikllarning bajarilish tartibini, masalan i tashqi va j ichki holatdan j tashqi va i ichki holatga almashtirish transformatsiyasi. U xotira lokaliteti va parallelizmni yaxshilash uchun ishlatiladi.
Xotira tartibi
Row-major massivda a[i][j] bo‘yicha j ni ichki sikl qilish ketma-ket manzillarni o‘qiydi. Agar i ichki bo‘lsa, stride katta bo‘lib cache line’dan samarasiz foydalanishi mumkin. Column-major layoutda qulay tartib aksincha bo‘lishi mumkin.
Dependence sharti
Interchange qonuniyligi loop dependence direction vectorlari bilan tekshiriladi. Almashtirilgan tartibda birinchi nol bo‘lmagan yo‘nalish manfiy bo‘lib qolsa, consumer producerdan oldin bajarilishi mumkin va transformatsiya taqiqlanadi. Perfect nest bo‘lmagan sikllarda statementlar joylashuvi qo‘shimcha shartlar yaratadi.
Bajarilish tartibi
for i for j S(i,j) va for j for i S(i,j) ayni iteration pointlarni qamraydi, ammo tartibi boshqa. Pure, mustaqil S uchun natija teng. Floating-point reduction yoki I/O kabi order-sensitive amallarda matematik nuqtalar bir xil bo‘lsa ham bit-level yoki observable natija o‘zgarishi mumkin.
Compiler tahlili
Amaliy compiler affine subscriptlarni polyhedral yoki klassik dependence tahlili bilan tekshiradi. Runtime alias guard pointerlar mustaqil bo‘lgan holatda optimized variantni yoqishi mumkin. Tiling ko‘pincha interchange va strip-mining kombinatsiyasidan hosil qilinadi.
Baholash
Tekshiruv rectangular va triangular iteration domain, non-unit step, boundary indeks va dependence distance misollarini qamraydi. Cache miss, TLB miss va vectorization report profitabilityni baholaydi. Correctness sinovida faqat final array emas, ruxsat etilmagan side effect tartibi ham nazorat qilinadi.
Loop Interchange bo‘yicha tahlil natijasi faqat yakuniy xulosa bilan emas, uni hosil qilgan IR versiyasi, target xususiyatlari va qo‘llangan taxminlar bilan birga saqlanadi. Compiler passlari ketma-ket o‘zgarganda oldingi natija avtomatik ravishda haqiqiy deb olinmaydi: tegishli dependencylar invalidatsiya qilinib, zarur qism qayta hisoblanadi. Debug rejimida asosiy invariant buzilgan nuqta va undan oldingi transformatsiya qayd etiladi; release rejimida esa tekshiruvlarning arzon qismi qoldiriladi. Shu yondashuv nazariy jihatdan qonuniy qoida implementatsiya xatosi yoki noto‘g‘ri cost model sabab zararli qarorga aylangan holatni ajratishga yordam beradi.
Kengaytirilgan jihatlar
Triangular loopda ichki bound tashqi induction variablega bog‘liq: for i=0..N for j=0..i. Interchanged variant rectangular emas; yangi j tashqi chegarasi va i uchun j..N boundi hosil qilinadi. Iteration domainni algebraik qayta yozmasdan faqat headerlarni almashtirish xato. Polyhedral representation nuqtalar to‘plami va schedule’ni alohida tasvirlab, bunday transformatsiyani sistematik qiladi. Hardware prefetcher ham stridega sezgir; contiguous ichki loop nafaqat cache missni, balki vector load imkonini yaxshilaydi. Shunga qaramay, outer-loop parallelism kamayib qolsa umumiy tezlik pasayishi mumkin.
Interchange profitabilitysi faqat eng ichki accessga qarab belgilanmaydi. Bir nechta array qarama-qarshi layoutda bo‘lsa, bittasi contiguous bo‘lib boshqasi yomonlashadi. Cost model access chastotasi va element hajmini vaznlashi kerak. Profilga asoslangan qaror target CPU modeli bilan bog‘lanadi va boshqa mashinada qayta baholanishi mumkin.
Optimization report eski va yangi loop order, asosiy array stride hamda legality direction vectorini beradi. Natija source darajasidagi performance tahlilini tushunarli qiladi.
Bog‘liq tushunchalar
loop nesting, data dependence, cache locality, loop tiling, polyhedral model, memory layout