Guruhi talabasining

Ajrat va hukmronlik qil paradigmasi kamchiliklari

bunday paradigma asosida ishlaydigan algoritmlar rekursiyadan foydalanadi 
va bu ularni ishlashini ma’lum miqdorga sekinlashtiradi. Buning ustiga kichik bir 
xato yechimni cheksiz takrorlanishga tushirib qo’yishi mumkin.

asosiy shartni tanlashda yo’l qo’yilgan xato barcha qism masalalarda xatolik 
va ortiqcha xotira ishlatilishiga olib keladi
2. Kesh xotira bilan ishlash
Kesh - bu shaxsiy kompyuter protsessoridan tez-tez so'raladigan 
ma'lumotlarni ma'lum vaqt davomida saqlash uchun foydalanadigan yuqori tezlikda 
ishlaydigan xotira. Bu samaradorlikni sifat jihatidan oshiradi, chunki u protsessorga 
kerakli ma'lumotlarni qidirish va ma'lumotlarni eng tezkor ravishda qanday olish 
kerakligini ko'rsatib beradi. Kesh xotirasi turli xil operatsiyalar tezligiga bevosita 
ta'sir qiladi, chunki u oldindan kerakli ma'lumotlarni saqlaydi. Uning ishlash 
printsipini oddiy misol bilan tavsiflash mumkin. Ularning ishini optimallashtirish 
uchun har qanday kishi ish stolidagi narsalarni ma'lum mantiqiy tartibda tartibga 
solishga harakat qiladi.
Ehtimol, ruchkalar, telefon, kerakli ma'lumotnomalar, joriy hujjatlar va 
boshqalar yaqin joyda joylashgan bo'lishi mumkin, chunki har safar kimdir besh yil 
oldin yillik hisobot ostida kerakli hujjatlarni yashirgan bo'lishi mumkin emas, chunki 
bu vaqt va kuch talab qiladi. Aynan shu printsip asosida kesh-xotira ishlaydi. 
Kompyuter darajasida bu nimani anglatadi? Aslida shunga o'xshash jarayon. Barcha 
ma'lumotlar shaxsiy kompyuterda ma'lum bir ierarxiyada mavjud. Agar ba'zi 
ma'lumot boshqalarga qaraganda tez-tez talab qilinadigan bo'lsa, ular mos ravishda 
yaqinroqdir.
Kesh - bu yuqori tezlikda ishlaydigan xotira, bu sizga protsessorga kerakli 
ma'lumotlarni tezda olish imkonini beradi, buning natijasida shaxsiy kompyuterning 

---

ishlashi sifat jihatidan oshadi. Kesh brauzerlar tomonidan ham qo'llaniladi va oddiy 
tozalash tartibini talab qiladi. Kesh [yoki kesh (ingliz tilidagi kesh, fr. Ref.rf-da 
joylashtirilgan cacher - yashirish; talaffuz qilingan - kesh) - tezkor xotira bilan talab 
qilinishi mumkin bo'lgan ma'lumotni o'z ichiga olgan tezkor kirish bilan, masalan, 
operatsion. Keshdagi ma'lumotlarga kirish tashqi xotiradan ma'lumotni olish yoki 
uni qayta hisoblashdan ko'ra tezroq, bu esa kirishning o'rtacha vaqtini kamaytiradi.
Protsessor ishlash uchun o‘z ma’lumotlarini operativ xotiradan oladi. Bunda 
mikrosxema ichida signallar juda katta chastotada (bir necha yuz MGts) ishlanadi, 
operativ xotiraga murojaatlarning hammasi esa bir necha marta kam chastotada 
sodir bo‘ladi. Chastotaning ichki ko‘paytirish koeffitsienti qanchalik yuqori bo‘lsa, 
protsessor, tashqarida saqlanayotgan ma’lumotlarga qaraganda, o‘zining ichida 
saqlanayotgan ma’lumotlar bilan shunchalik samaraliroq ishlaydi. Odatda 
protsessor o‘zining ichida deyarli hech narsani saqlamaydi. Unda ma’lumotlarga 
ishlov beriladigan yacheykalar (bu «ishchi» yacheykalar registrlar deb ataladi) juda 
kam. Shuning uchun protsessor ishini tezlatish uchun ancha oldin (4-avloddan 
boshlab) keshlash texnologiyasi taklif qilingan.
Kesh – bu bufer vazifasini bajaruvchi xotira yacheykalarining nisbatan 
katta bo‘lmagan to’plami (nabori)dir. Umumiy xotiradan biror narsa o‘qilayotganda 
yoki unga yozilayotganda ma’lumotlarning nusxa (копия)si kesh-xotiraga ham 
kiritiladi. Agar shu ma’lumotlarning o‘zi yana zarur bo‘lib qolsa, ularni uzoqdan 
chaqirib olish zarur bo‘lmaydi – ularni buferdan olish ancha tezroq bo‘ladi. Kesh-
xotiradan foydalanish kompyuter tizimi unumdorligini sezilarli oshirish imkonini 
berdi. 486-protsessorlar uchun keshlash texnologiyasi birinchi marta qo‘llanilganda, 
kesh-xotira onalik platasida protsessorga mumkin qadar yaqinroq joylashar edi; 
bunda sig‘imi katta bo‘lmasa ham, lekin unumdorligi bo‘yicha eng «tez» 
mikrosxemalardan foydalanishar edi.
Bugungi kunda kesh-xotira «piramidali» o‘rnatiladi. Tezligi bo‘yicha eng 
tezkor, lekin hajmi bo‘yicha eng kichik birinchi darajali kesh-xotira protsessor 

---

kristalli 
tarkibiga 
kiradi. 
Ularni 
protsessor 
registrlari 
tayyorlanadigan 
texnologiya bo‘yicha tayyorlashadi, natijada u juda qimmat, lekin juda tezkor va eng 
asosiysi ishonchli bo‘lib qoldi. Uning o‘lchami atigi bir necha o‘n Kbayt bilan 
o‘lchanadi, lekin u tez ishlov berishda juda katta ahamiyatga ega. Ikkinchi daraja 
kesh-xotirasi protsessorning o‘sha kristallining o‘zida joylashishi mumkin (bu holda 
u protsessori yadrosi chastotasida ishlaydi). Odatda ikkinchi daraja kesh-xotira 
hajmi yuzlab Kbaytda (128/256/512 Kbayt va h.k.) o‘lchanadi.
Eng katta, lekin eng sekin kesh-xotira – bu uchinchi daraja keshidir. U 
protsessorga kirmaydi, chunki onalik platasida o‘rnatiladi va uning chastotasida 
ishlaydi. Uning o‘lchamlari 1-2 Mbaytga yetishi mumkin. Birinchi va ikkinchi 
daraja kesh-xotira o‘lchami protsessor narxiga juda katta ta’sir qiladi. Bir modelli va 
berilgan ishchi chastotali protsessorlar kesh-xotira hajmi bilan farqlanishi mumkin.
Dasturlashda 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 “ajrat 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.