Xotira ierarxiyasi va kesh - Kompyuter arxitekturasi

9-bo'limda registr xotiradan yuz barobar tez ekanini aytdik. Bu jiddiy muammo: protsessor tez, xotira sekin.

Yechim - ierarxiya: bir necha qatlamli xotira, har biri o'zidan yuqoridagidan kattaroq va sekinroq.

Qatlamlar #

Qatlam	Hajmi	Murojaat vaqti	Nisbat
Registr	~1 KB	~1 takt	1
L1 kesh	32-64 KB	~4 takt	4
L2 kesh	0,5-2 MB	~14 takt	14
L3 kesh	8-64 MB	~50 takt	50
Asosiy xotira	8-64 GB	~200-300 takt	~250
SSD	0,5-4 TB	~100 000 takt	100 000
Qattiq disk	1-20 TB	~10 000 000 takt	10⁷

Bu jadvaldagi raqamlar taxminiy va modelga qarab o'zgaradi, lekin tartib barqaror.

Masshtabni tasavvur qilish

Bir taktni bir soniya deb faraz qilaylik. U holda:

Murojaat	Inson vaqtida
Registr	1 soniya
L1 kesh	4 soniya
L3 kesh	1 daqiqa
Asosiy xotira	4 daqiqa
SSD	1,5 kun
Qattiq disk	4 oy

Protsessor uchun xotiraga borish - bu "to'rt daqiqa kutish". Diskka borish esa "to'rt oy kutish".

Aynan shuning uchun kesh mavjud - va shuning uchun ma'lumotlar bazasi indekslari shunchalik muhim.

Kesh qatori #

Kesh bitta baytni emas, butun qatorni olib keladi. Odatda 64 bayt.

Bu asosiy natijani beradi: agar siz bitta elementni so'rasangiz, uning qo'shnilari ham keshga tushadi.

Kesh qatori 64 bayt, ya'ni 8 ta element birdan olib keladi. Bitta massivni uch xil tartibda 65 536 marta o'qib ko'ramiz:

O'qish tartibi	Keshda topildi	Topilmadi	Foiz
Qator bo'ylab	57 344	8 192	87%
Ustun bo'ylab	0	65 536	0%
Teskari tartibda	57 344	8 192	87%

Qator bo'ylab o'qishda har 8 elementdan 7 tasi keshda topiladi - chunki bitta kesh qatori 8 ta elementni birdan olib keladi.

Uchinchi qatorga e'tibor bering: teskari tartibda o'qish ham 87% beradi. Muhimi yo'nalish emas, qo'shnilik.

87% va 0%. Bir xil sondagi o'qish, bir xil ma'lumot - faqat tartib boshqa.

Teskari tartib ham 87% berganiga e'tibor bering: muhimi tartib oldinga yoki orqaga emas, qo'shni bo'lishi.

Kesh - bu tezlik emas, bu QO'SHNILIKKA qilingan garov

Haqiqiy mashinada o'lchash #

Model yaxshi, lekin uni tekshirish kerak. Quyidagi kod haqiqiy vaqtni o'lchaydi:

Butun ierarxiyani bitta rasmda ko'rsak:

Har pastki qatlam kattaroq, lekin sezilarli darajada sekinroq

Endi eng muhim tajriba. Bir xil sondagi elementni ikki xil tartibda o'qiymiz:

O'qish tartibi	Bajarilgan amallar	Tezlik
Qator bo'ylab (qo'shni elementlar)	bir xil	tez
Ustun bo'ylab (har qadamda sakrash)	bir xil	sezilarli sekin

Ikkala holatda ham bir xil sondagi qo'shish va o'qish bajarildi. Farq faqat murojaat tartibida.

Sabab keyingi bo'limda batafsil ochiladi, lekin qisqasi shunday: qo'shni elementlarni o'qiganda protsessor allaqachon olib kelgan kesh qatoridan foydalanadi. Sakrab o'qiganda esa har safar yangi qator kerak bo'ladi.

Nima uchun aniq raqam emas, "sekinroqmi" deb chop etildi?

Aniq vaqt har mashinada, har ishga tushirishda boshqacha bo'ladi: protsessor modeli, kesh hajmi, fon jarayonlari - hammasi ta'sir qiladi.

Shuning uchun bu darslikda o'lchov natijalari shart sifatida chop etiladi. Shunda kitobdagi natija sizning mashinangizda ham to'g'ri chiqadi.

O'zingiz aniq raqamni ko'rmoqchi bo'lsangiz, print qatorlarini o'zgartiring - lekin taqqoslaganda bir xil sharoitda o'lchaganingizga ishonch hosil qiling.

Uch xil kesh xatosi #

Turi	Sabab	Yechim
Majburiy	Ma'lumot birinchi marta o'qilyapti	Oldindan o'qish
Sig'im	Ishchi to'plam keshdan katta	Bo'laklab ishlash
Konflikt	Ikki manzil bir joyga tushadi	Tartibni o'zgartirish

Uchinchisi eng nozik: bizning modelimizda ustun bo'ylab o'qish 0% berdi. Sabab shundaki, N = 256 va kesh qatorlari soni ham 64 - manzillar doim bir xil joyga tushdi.

Massiv o'lchamini bir oz o'zgartirish (masalan 257 ga) natijani sezilarli yaxshilashi mumkin. Bu haqiqiy optimallashtirish usuli va u massiv to'ldirish (*array padding*) deb ataladi.

Bu bilim qayerda kerak bo'ladi?

Kesh haqida bilim kundalik kodda ham foyda beradi:

Vaziyat	To'g'ri tanlov
Katta massivni aylanish	Xotiradagi tartibda
Tuzilmalar massivi	Maydonlarni 7-bo'limdagidek tartiblang
Ko'p kichik obyekt	Bitta katta massiv afzalroq
Bog'langan ro'yxat va massiv	Massiv ko'pincha tezroq

Oxirgisi ko'pchilikni ajablantiradi: nazariy jihatdan bog'langan ro'yxatga qo'shish O(1), massivga esa O(n).

Lekin amalda massiv ko'pincha yutadi - chunki uning elementlari qo'shni va kesh ular bilan yaxshi ishlaydi. Bog'langan ro'yxat esa xotira bo'ylab tarqalib ketadi.

Algoritmlar darsligidagi Big-O tahlili xotirani bir xil tezlikda deb hisoblaydi. Haqiqatda esa bunday emas - shuning uchun nazariy baho va amaliy o'lchov ba'zan farq qiladi.

Keshni faqat tezlik deb bilmang

Kesh xavfsizlikka ham ta'sir qiladi. Ma'lumot keshda bormi yoki yo'qmi - buni vaqt bo'yicha aniqlash mumkin.

Shu asosda yon kanal hujumlari quriladi: hujumchi o'zining kodini ishlatib, boshqa jarayon qaysi manzillarga murojaat qilganini taxmin qiladi.

2018-yilda e'lon qilingan Spectre va Meltdown zaifliklari aynan shunga asoslangan edi: ular spekulyativ bajarish (16-bo'lim) va kesh vaqtini birga ishlatgan.

Himoya operatsion tizim va kompilyator darajasida qilinadi. Kriptografik kod yozayotgan bo'lsangiz, vaqt bo'yicha barqaror algoritmlar ishlatish kerak - bu "Amaliy kriptografiya" darsligida ko'rilgan.

Amaliy topshiriq

Ierarxiyaning olti qatlamini yoddan tartib bilan yozing.
Registr va asosiy xotira o'rtasidagi tezlik farqi necha barobar?
Bir taktni bir soniya deb olsak, SSD ga murojaat qancha vaqt oladi?
Kesh qatori 64 bayt bo'lsa, 4 baytli sondan nechtasi sig'adi?
Qator bo'ylab o'qishda nima uchun 87% chiqishini hisoblab ko'rsating.
Teskari tartibda o'qish nima uchun ham 87% berishini tushuntiring.
Ustun bo'ylab o'qishda nima uchun 0% chiqadi?
Kesh qatori 128 bayt bo'lsa, foiz qanday o'zgarardi?
Bog'langan ro'yxat massivdan nima uchun sekinroq ekanini ayting.
Kompyuteringiz kesh hajmlarini toping (lscpu yoki tizim ma'lumoti).

Xulosa #

Protsessor tez, xotira sekin - yechim ko'p qatlamli ierarxiya.
Registrdan diskkacha farq o'n million barobargacha yetadi.
Kesh bitta baytni emas, butun qatorni (odatda 64 bayt) olib keladi.
Shuning uchun qo'shni elementlarni o'qish juda arzon.
Modelda qator bo'ylab o'qish 87%, ustun bo'ylab 0% berdi.
Bir xil ish, bir xil ma'lumot - farq faqat murojaat tartibida.
Uch xil kesh xatosi: majburiy, sig'im va konflikt.
Konflikt xatolarini massiv o'lchamini o'zgartirib kamaytirish mumkin.
Amalda massiv bog'langan ro'yxatdan tezroq bo'lishi mumkin - kesh tufayli.
Kesh vaqti yon kanal hujumlariga ham asos bo'ladi (Spectre, Meltdown).

Keyingi bo'limda bu bilimni amalda qo'llaymiz - keshga do'st kod yozishni o'rganamiz.