Loop Tiling — katta iteratsiya fazosini kichik bloklar yoki tile’larga bo‘lib, har blok ichidagi hisoblarni birga bajarish transformatsiyasi. Blocking deb ham ataladi; asosiy maqsad ma’lumotni cache yoki boshqa tez xotirada qayta ishlatishdir.
Bloklash mexanizmi
Ikki o‘lchamli siklda ii va jj tile boshlanishlarini yuritadi, ichki i hamda j esa blok chegarasigacha boradi. Oxirgi tile to‘liq bo‘lmasligi mumkin, shu sabab min(ii+T, N) kabi boundary qo‘llanadi. Matritsa ko‘paytirishda k o‘lchamini ham tile qilish operand bloklarini cache’da ushlab turadi.
Tile o‘lchami
Tile size juda kichik bo‘lsa loop overhead oshadi, juda katta bo‘lsa working set cachega sig‘maydi. Optimal qiymat cache hajmi, associativity, line size, TLB, SIMD width va thread taqsimotiga bog‘liq. GPUda shared memory va occupancy ham cheklov beradi.
Qonuniylik
Transformatsiya iteration orderni o‘zgartirgani uchun dependence qonuniyligi zarur. Affine loop nestda tiling odatda strip-mining va interchange sifatida qaraladi. Wavefront dependence bo‘lsa rectangular tile’larni oddiy tartibda parallel bajarish mumkin emas; skewing yoki diagonal schedule kerak bo‘lishi mumkin.
Parametr tanlash
Compiler static cost model, profile-guided tuning yoki auto-tuning bilan tile size tanlaydi. Parametrni hard-code qilishdan oldin target va problem size diapazoni belgilanadi. Multilevel cache uchun nested tiling bir necha blok o‘lchamini qo‘llashi mumkin.
Chegara sinovlari
Sinov non-multiple dimension, juda kichik N, zero size va overflow qilishi mumkin bo‘lgan tile arithmeticni qamraydi. Original hamda tiled natija taqqoslanadi; floating-point reduction order o‘zgarsa tolerance va tilning fast-math sharti ochiq belgilanadi. Hardware counter locality foydasini tasdiqlaydi.
Loop Tiling 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
Tiling faqat CPU cache uchun emas. Distributed memoryda tile domainlar node’lar orasida taqsimlanadi va halo exchange dependence chegaralarini uzatadi. GPUda thread block bir tile’ni shared memoryga ko‘chirib, ko‘p marta ishlatadi; bank conflict va coalesced global access hisobga olinadi. Cache-oblivious algoritm fixed tile size o‘rniga recursive bo‘linish bilan hierarchyga moslashadi. Compiler avtomatik tilingda array layoutni bilmasa foydani noto‘g‘ri baholashi mumkin. Matrix dimension va leading stride runtime qiymat bo‘lsa, bir nechta tile variantini yaratib dispatch qilish yoki library kernel tanlash keng tarqalgan.
Tile looplar yaratishda ii + T integer overflow qilmasligi uchun bound safe shaklda hisoblanadi. min expression side effectli N ni takror o‘qimasligi kerak. Parallel tile schedulingda deterministic natija talab qilinsa reduction va write conflict tartibi belgilanadi. Autotuner tanlagan parametr problem class, target va compiler versiyasi bilan birga cache qilinadi.
Bog‘liq tushunchalar
blocking, cache locality, loop interchange, strip mining, polyhedral optimization, matrix multiplication