2. Kesh xotira bilan ishlash

cache-oblivious algoritmlar protsessorning keshini (inglizcha kesh) kesh hajmiga (yoki kesh satrlarining uzunligiga) bog’lamasdan ishlatadigan tarzda yaratilgan algoritmlardir. Optimal cache-oblivious algoritm o'zgaruvchan omillarni hisobga olmagan holda asimptotik ma'noda keshni optimal ravishda ishlatadigan cache-oblivious algoritmdir. Bunday algoritmlar turli xil xotira darajalaridagi kesh hajmidan qat'iy nazar har xil mashinalarda samarali va modifikatsiyasiz ishlaydi.

Oddiy cache-oblivious algoritmlar: matritsani ko'paytirish, tashqi tartiblash, matritsani transpozitsiyasi va boshqa ba'zi vazifalar. Odatda, cache-oblivious algoritmlar “bo’lib tashla va hukmronlik qil” usulidan foydalanadi, bunda vazifa kichik vazifalar va quyi qismlarga bo'linadi. Ajratish jarayonida biz kichik vazifalarga ega bo’lamiz. Bir muncha vaqt o'tganda, ushbu kichik vazifalar kesh hajmiga moslasha boshlaydi, biz ularning qachon moslashishini bilmaymiz, lekin eng kichik asos o'lchamlarga bo'lishda davom etamiz. Keyin kichik vazifa uchun samarali algoritmni qo'llaymiz. Shundan so’ng natijalarni asosiy vazifaning mohiyatiga qarab birlashtiramiz. Masalan, matritsani ko’paytirishning cache-oblivious algoritmi har bir matritsani to'rtta kichik matritsaga rekursiv ravishda bo'lish orqali hosil bo’ladi. Matritsa to’liq holda keshga joylashganda kichik masalalarga mo’ljallangan optimallashtirilgan algoritmdan foydalanamiz, keyinchalik funktsiyalar natijasini matritsaga qo'shamiz.