</> Softromeda Edu

16-bo‘lim

Konveyer va shox bashorati

Konveyer g'oyasi va tezlanish chegarasi, to'siqlar, shox bashorati hisoblagichi va spekulyativ bajarish.

🕑 7 daqiqa o‘qish 📄 1 054 so‘z 👁 0 marta ko‘rilgan
Ushbu bo‘lim mundarijasi
  1. Konveyer g'oyasi
  2. To'siqlar
  3. Shox bashorati
  4. Spekulyativ bajarish
  5. Xulosa

10-bo'limdagi mashinamiz har komandani to'liq bajarib, keyin keyingisiga o'tardi. Bu isrofgarchilik: komanda dekodlanayotganda olish qurilmasi bekor turadi.

Yechim zavod konveyeridan olingan.

Konveyer g'oyasi #

Konveyer - bosqichlarni ustma-ust qo'yish Konveyersiz: har komanda oldingisini kutadi k1 OL DE BA XO YO k2 OL DE BA XO YO k3 OL DE BA XO YO k4 OL DE BA XO YO 20 takt Konveyer bilan: bosqichlar ustma-ust ishlaydi k1 OL DE BA XO YO k2 OL DE BA XO YO k3 OL DE BA XO YO k4 OL DE BA XO YO 8 takt 2,5 barobar tezlanish - qo'shimcha element qo'shmasdan Har komanda baribir 5 taktda bajariladi - u tezlashmadi Lekin endi har taktda BITTA komanda tugaydi, oldin har 5 taktda bitta edi
OL - olish, DE - dekodlash, BA - bajarish, XO - xotira, YO - yozish

Raqamlarda:

Taktlar
Konveyersiz, 4 ta komanda20
Konveyer bilan, 4 ta komanda8
Tezlanish2,5 barobar

Komandalar ko'paygan sari tezlanish bosqichlar soniga yaqinlashadi - bizning misolimizda 5 barobargacha.

Kechikish va o'tkazuvchanlik

Diqqat qiling: bitta komandaning o'z vaqti qisqarmadi - u baribir 5 bosqichdan o'tadi.

O'zgargan narsa - tugallanish tezligi: endi har taktda bitta komanda tugaydi.

Bu tarmoqlar darsligidagi kechikish va o'tkazuvchanlik farqining aynan o'zi: yo'lning uzunligi o'zgarmadi, lekin yo'ldan bir vaqtda ko'proq narsa o'tadi.

Xuddi shu sabab bilan zavod konveyeri ham ishlaydi: bitta mashinani yig'ish vaqti qisqarmaydi, lekin soatiga ko'proq mashina chiqadi.

Oxirgi ikki qator eng muhim xulosa. Konveyer kechikishni (latency) kamaytirmaydi - u o'tkazuvchanlikni (throughput) oshiradi.

Bu tarmoqlar darsligining 16-bo'limidagi farqning aynan o'zi, faqat protsessor ichida.

Kir yuvish o'xshatishi

Uchta kir to'plamingiz bor. Har biri uchun: yuvish (30 daq), quritish (30 daq), taxlash (30 daq).

UsulVaqt
Ketma-ket3 × 90 = 270 daqiqa
Konveyer90 + 2 × 30 = 150 daqiqa

Konveyerda birinchi to'plam quritilayotganda ikkinchisini yuvishni boshlaysiz.

Diqqat: bitta to'plam baribir 90 daqiqada tayyor bo'ladi. Tezlashgan narsa - umumiy oqim.

To'siqlar #

Konveyer har doim ham silliq ishlamaydi. Uchta muammo bor:

To'siq turiSababMisol
Ma'lumotKeyingi komanda oldingisining natijasini kutadia = b + c keyin d = a + 1
BoshqaruvSakrash bo'ladimi - hali noma'lumif va halqalar
ResursIkki bosqich bitta qurilmani talab qiladiXotiraga bir vaqtda murojaat

Birinchisi ko'pincha oldinga uzatish (forwarding) bilan hal qilinadi: natija registrga yozilishini kutmasdan, to'g'ridan-to'g'ri keyingi bosqichga beriladi.

Ikkinchisi esa ancha qiyin - va eng qiziq yechimga ega.

Shox bashorati #

Muammo: if komandasi BAJAR bosqichida hal bo'ladi, lekin keyingi komandani OL bosqichida olish kerak. Ya'ni qaror qabul qilinmasdan oldin.

Yechim: taxmin qilish. Protsessor shox qayoqqa ketishini bashorat qiladi va ishlashda davom etadi.

1000 ta shartli o'tishni beshta turli holatda sinaymiz:

Shart turiTo'g'riXatoAniqlikJarima (takt)
Har doim rost999199%15
Har doim yolg'on10000100%0
Navbatma-navbat010000%15 000
Saralangan ma'lumot997399%45
Aralash ma'lumot42757342%8 595

Uchinchi qatorga qarang: shart navbatma-navbat o'zgarsa, bashoratchi hech qachon to'g'ri topa olmaydi va 15 000 takt bekor ketadi.

Eng qizig'i - to'rtinchi va beshinchi qatorlar. Ular bir xil dastur, faqat ma'lumot boshqacha:

Ma'lumotAniqlikJarima
Saralangan99%45 takt
Aralash42%8 595 takt

Ya'ni ma'lumotni oldindan saralash dasturni tezlashtirishi mumkin - garchi bajariladigan amallar soni aynan bir xil bo'lsa ham.

Halqa sharti deyarli har doim bir xil bo'ladi ("yana aylanamizmi?" - deyarli har doim "ha"), shuning uchun bashorat u yerda juda yaxshi ishlaydi.

Uchinchi qator ajablanarli: navbatma-navbat o'zgaruvchi shart 0% aniqlik berdi.

Sabab: ikki bitli hisoblagich har doim "oldingi safar qanday bo'lgan bo'lsa, shunday bo'ladi" deb taxmin qiladi. Aniq navbatma-navbat ketma-ketlikda u har safar adashadi.

Haqiqiy protsessorlarda bu holat uchun murakkabroq bashoratchilar bor - ular naqshni eslab qoladi. Lekin tamoyil bir xil: takrorlanuvchi xulq yaxshi bashorat qilinadi.

Saralangan massiv nima uchun tezroq ishlanadi?

Bu Stack Overflow dagi eng mashhur savollardan biri.

Bir xil ma'lumotni saralangan va saralanmagan holda qayta ishlash tezligi bir necha barobar farq qilishi mumkin. Algoritm bir xil bo'lsa ham.

Yuqoridagi jadval buni tushuntiradi:

Ma'lumotShart xulqiBashorat
SaralanganAvval doim yolg'on, keyin doim rost99%
TasodifiyOldindan aytib bo'lmaydi~50%

Saralangan ma'lumotda shart faqat bir marta o'zgaradi. Tasodifiyda esa har safar.

Amaliy xulosa: ma'lumotni saralash ba'zan qidiruv uchun emas, bashorat uchun ham foyda beradi.

Spekulyativ bajarish #

Protsessor bashoratga ishonib, natijani bilmasdan ishlashda davom etadi. Bashorat noto'g'ri chiqsa - bajarilgan ish bekor qilinadi va konveyer tozalanadi.

Shuning uchun har xato ~15-20 takt turadi. Yuqoridagi jadvalda "jarima" ustuni aynan shuni ko'rsatadi.

Bashorat xato chiqqanda to'g'ri bashorat shox k+1 k+2 k+3 konveyer to'lib ishlaydi xato bashorat shox bekor bekor bekor qaytadan boshlash ~15-20 takt yo'qoladi Nima uchun konveyer uzunligi cheklangan Uzun konveyer ko'proq tezlik beradi, lekin har xato ham qimmatroq turadi
Pentium 4 da konveyer 31 bosqich edi - va bu xatoni juda qimmat qilib qo'ydi
Spekulyativ bajarish - Spectre ning asosi

Bekor qilingan ish izsiz yo'qolmaydi: u keshni o'zgartirib ulguradi.

2018-yilda ochilgan Spectre zaifligi aynan shunga asoslangan:

QadamNima bo'ladi
1Hujumchi bashoratchini "o'rgatadi"
2Protsessor tekshiruvni chetlab o'tib, ma'lumotni o'qiydi
3Bashorat xato ekani aniqlanadi, natija bekor qilinadi
4Lekin kesh o'zgargan bo'lib qoladi
5Hujumchi kesh vaqtini o'lchab, qiymatni tiklaydi

Eng nozik tomoni: protsessor to'g'ri ishlagan - u arxitektura va'dasini buzmagan. Ma'lumot yon kanal orqali sizib chiqdi.

Bu butun sanoat uchun jiddiy dars bo'ldi: tezlik uchun qilingan optimallashtirish xavfsizlikni buzishi mumkin.

Himoya qisman apparatda, qisman operatsion tizim va kompilyatorda qilindi - va ba'zi hollarda tezlik pasayishiga olib keldi.

Amaliy topshiriq
  1. Konveyerning besh bosqichini yoddan yozing.
  2. 10 ta komanda uchun konveyersiz necha takt kerak bo'lardi?
  3. Konveyer bilan esa? Tezlanishni hisoblang.
  4. Komandalar juda ko'p bo'lsa, tezlanish chegarasi qancha?
  5. Nima uchun bitta komandaning o'z vaqti qisqarmasligini tushuntiring.
  6. Kechikish va o'tkazuvchanlik farqini uch qatorda yozing.
  7. Navbatma-navbat o'zgaruvchi shartda nima uchun 0% chiqadi?
  8. Jarima 30 takt bo'lsa, aralash ma'lumot qancha yo'qotardi?
  9. Saralangan ma'lumot nima uchun tezroq ishlashini ayting.
  10. Uzun konveyerning afzalligi va kamchiligini jadval qiling.

Xulosa #

  • Konveyer bosqichlarni ustma-ust bajaradi - qurilmalar bekor turmaydi.
  • U kechikishni kamaytirmaydi, o'tkazuvchanlikni oshiradi.
  • Nazariy tezlanish chegarasi - bosqichlar soni.
  • Uchta to'siq turi: ma'lumot, boshqaruv va resurs.
  • Ma'lumot to'sig'i ko'pincha oldinga uzatish bilan hal qilinadi.
  • Boshqaruv to'sig'i uchun shox bashorati ishlatiladi.
  • Ikki bitli hisoblagich takrorlanuvchi xulqni yaxshi bashorat qiladi.
  • Aniq navbatma-navbat o'zgaruvchi shart uchun u 0% aniqlik beradi.
  • Saralangan ma'lumot tezroq ishlanishining sababi aynan shu.
  • Spekulyativ bajarish Spectre zaifligining asosi bo'ldi.

Keyingi bo'limda parallellikning boshqa turlarini ko'ramiz: SIMD va ko'p yadro.

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.