15-bo‘lim
Keshga do'st kod
Matritsa ko'paytirishda murojaat tartibini o'zgartirish, AoS va SoA joylashuvi, bo'laklab ishlash va o'lchash metodikasi.
Ushbu bo‘lim mundarijasi
14-bo'limda kesh qanday ishlashini ko'rdik. Endi undan foydalanishni o'rganamiz.
Muhim nuqta: bu bo'limdagi o'zgarishlar algoritmni o'zgartirmaydi. Amallar soni bir xil qoladi - faqat tartib boshqacha bo'ladi.
Matritsa ko'paytirish #
Klassik misol. C = A × B da B matritsasi ustun
bo'ylab o'qiladi - bu 14-bo'limda ko'rgan eng yomon holat.
128×128 matritsalarni ko'paytirishda xotiraga murojaatlarni sanaymiz:
| Usul | Keshda topildi | Topilmadi | Foiz |
|---|---|---|---|
| Oddiy | 2 069 880 | 2 124 424 | 49% |
B ko'chirilgan | 3 684 480 | 509 824 | 87% |
Ikkala usul ham bir xil sondagi murojaat qildi va bir
xil natijani berdi. Farq faqat B matritsaning o'qilish
tartibida.
Oddiy usulda B ustun bo'ylab o'qiladi - har element
yangi kesh qatorini talab qiladi. Ko'chirilgandan keyin esa
u qator bo'ylab o'qiladi.
Ko'chirishning o'zi ham vaqt oladi, lekin u bir marta bajariladi - keyingi millionlab murojaat esa tez ketadi.
49% dan 87% ga. Kesh xatolari to'rt barobardan ko'proq kamaydi.
E'tibor bering: ko'chirish qo'shimcha ish talab qiladi -
N² ta nusxalash. Lekin ko'paytirishning o'zi N³ amal,
shuning uchun qo'shimcha xarajat tez qoplanadi.
Bu darslikdagi boshqa o'lchovlar haqiqiy vaqtni o'lchaydi. Bu yerda esa model ishlatildi. Sababi ochiq aytilishi kerak.
Sabab shundaki, talqin qilinadigan tillarda har bir amal qo'shimcha xarajat bilan keladi va u kesh xatosidan ancha qimmat. Natijada kesh ta'siri shovqin ostida qolib ketadi.
Sinab ko'rildi: 200x200 matritsada natija ishga tushirishdan ishga tushirishga o'zgarib turdi - ba'zan ko'chirilgan variant tezroq, ba'zan sekinroq chiqdi.
Shuning uchun bu yerda mexanizmni ko'rsatadigan model tanlandi. C yoki Rust da xuddi shu o'zgarish real va barqaror tezlanish beradi - o'sha tillarda ustama xarajat yo'q.
Xulosa metodik: o'lchov nimani o'lchayotganini biling. Noto'g'ri sharoitda olingan raqam yo'q raqamdan yomonroq.
Tuzilmalar massivi va massivlar tuzilmasi #
Ikkinchi klassik naqsh. Bir xil ma'lumotni ikki xil joylashtirish mumkin:
| Usul | Joylashuv |
|---|---|
| AoS (array of structs) | [x,y,z,...][x,y,z,...] |
| SoA (struct of arrays) | [x,x,x,...][y,y,y,...] |
4096 ta zarrachaning faqat x koordinatasini yig'moqchimiz.
Har zarrachada 8 ta maydon bor, bizga esa faqat bittasi kerak.
| Joylashuv | Keshda topildi | Topilmadi | Foiz |
|---|---|---|---|
| Tuzilmalar massivi (AoS) | 0 | 4 096 | 0% |
| Massivlar tuzilmasi (SoA) | 3 584 | 512 | 87% |
Sabab shundaki, AoS da har kesh qatorida bizga kerak bo'lgan 1 ta element va kerak bo'lmagan 7 tasi keladi.
Foydali baytlar ulushini hisoblasak:
| Joylashuv | Olib kelingan | Ishlatilgan | Foydali ulush |
|---|---|---|---|
| AoS | 64 bayt | 8 bayt | 12% |
| SoA | 64 bayt | 64 bayt | 100% |
Ya'ni AoS da xotira kanalining 88 foizi bekorga band bo'ladi.
AoS yomon emas - u boshqa vazifa uchun yaxshi.
| Vazifa | Qaysi biri yaxshi |
|---|---|
| Bitta maydonni hamma obyektda o'qish | SoA |
| Bitta obyektning hamma maydonini o'qish | AoS |
| Obyektlarni ro'yxatga qo'shish/olib tashlash | AoS |
| SIMD bilan ishlash (17-bo'lim) | SoA |
O'yin dvigatellarida ko'pincha ikkalasi aralash ishlatiladi: tez-tez birga o'qiladigan maydonlar birga, qolganlari alohida.
Qoida: ma'lumotni ishlatish tartibiga qarab joylashtiring, kontseptual chiroylilikka qarab emas.
Yana uchta amaliy usul #
1. Bo'laklab ishlash (blocking). Katta massivni keshga sig'adigan bo'laklarga bo'lib ishlash. Matritsa ko'paytirishda bu ko'chirishdan ham yaxshiroq natija beradi.
2. Maydonlarni tartiblash. 7-bo'limda ko'rgandik:
cdi 20 bayt, dic 13 bayt. Kichikroq tuzilma - kesh
qatoriga ko'proq element sig'adi.
3. Ko'rsatkichlardan qochish. Bog'langan ro'yxat, daraxt va ko'rsatkichli tuzilmalar xotira bo'ylab tarqalib ketadi. Massiv esa qo'shni.
Bu bo'limdagi usullar kuchli, lekin ular kodni murakkablashtiradi.
Tartib shunday bo'lishi kerak:
| Qadam | Nima qilinadi |
|---|---|
| 1 | Ishlaydigan, o'qiladigan kod yozing |
| 2 | Sekinlik haqiqatan muammomi - o'lchang |
| 3 | Qaysi joy sekinligini profilchi bilan toping |
| 4 | Faqat o'sha joyni optimallashtiring |
| 5 | Yana o'lchang - yaxshilandimi |
Eng ko'p uchraydigan xato - 3-qadamni tashlab ketish. Dasturchilar qaysi joy sekin ekanini taxmin qilishda juda yomon.
Va ko'pincha javob bu bo'limda emas: sekinlik algoritmda
(O(n²) o'rniga O(n log n)), keraksiz baza so'rovlarida
yoki tarmoq kutishida bo'ladi.
Kesh optimallashtirish - oxirgi chora, birinchi emas.
Ikki oqim turli o'zgaruvchilar bilan ishlayotgan bo'lsa ham, agar ular bitta kesh qatorida yotsa, protsessor ularni doimo bir-biriga moslashtirib turadi.
Natijada kod parallel bo'lsa ham sekinlashadi - ba'zan bir oqimlisidan ham sekin.
Bunga yolg'on almashish (false sharing) deyiladi.
| Belgisi | Yechim |
|---|---|
| Oqim qo'shilsa tezlik pasayadi | Har oqimning ma'lumotini alohida kesh qatoriga qo'ying |
| Hisoblagichlar massivi sekin | Ular orasiga to'ldiruvchi qo'shing |
Buni topish qiyin, chunki kodga qaraganda hech qanday umumiy ma'lumot ko'rinmaydi. U faqat xotira joylashuvida bor.
Ko'p oqimli kod 17-bo'limda ko'riladi.
- Matritsa ko'paytirishda nima uchun
Bustun bo'ylab o'qilishini tushuntiring. - Ko'chirish 49% dan 87% ga ko'tardi - bu nimani anglatadi?
- Ko'chirishning o'zi ham vaqt oladi. U qachon o'zini oqlaydi?
- AoS va SoA farqini o'z so'zlaringiz bilan yozing.
- AoS da foydali ulush nima uchun 12% ekanini hisoblang.
- Har zarrachada 4 ta maydon bo'lsa, ulush qanday o'zgarardi?
- Ikkita maydonni birga o'qiydigan vazifa uchun qaysi usul yaxshi?
- Uchala maydonni ham o'qisak, AoS yutadimi? Nega?
- O'z loyihangizda ustun bo'ylab o'qilayotgan joy bormi - tekshiring.
- Optimallashtirishdan oldin o'lchash nima uchun zarurligini yozing.
Xulosa #
- Keshga do'st kod algoritmni o'zgartirmaydi - faqat murojaat tartibini.
- Matritsa ko'paytirishda
Bni ko'chirish kesh topilishini 49% dan 87% ga oshirdi. - Qo'shimcha
N²nusxalashN³amal fonida arzon tushadi. - AoS bitta obyektning hamma maydoni uchun, SoA hamma obyektning bitta maydoni uchun yaxshi.
- Bizning misolda AoS foydali baytlarning atigi 12% ini ishlatdi.
- Boshqa usullar: bo'laklab ishlash, maydonlarni tartiblash, ko'rsatkichlardan qochish.
- Talqin qilinadigan tillarda kesh ta'sirini vaqt bilan o'lchab bo'lmaydi - ustama xarajat uni bosib ketadi.
- Shuning uchun bu bo'limda model ishlatildi; C va Rust da ta'sir real.
- Optimallashtirishdan oldin o'lchang va profillang - taxmin qilmang.
- Ko'p oqimli kodda yolg'on almashish parallel kodni sekinlashtirishi mumkin.
Keyingi bo'limda protsessorning ichki tezlashtirish mexanizmini ko'ramiz - konveyer.
O‘qish tarixini saqlamoqchimisiz?
Tizimga kirsangiz, tugatgan bo‘limlaringiz saqlanadi va qoldirgan joyingizdan davom etasiz.
Xatolik topdingizmi?
Imlo xatosi, ishlamaydigan kod yoki noto‘g‘ri ma‘lumotni ko‘rsangiz - bizga xabar bering. Har bir xabar administrator tomonidan ko‘rib chiqiladi.