Parallel hisoblash

S_kechikish salohiyat tezlikni oshirmoq yilda kechikish butun vazifani bajarish;

s vazifaning parallel qismining bajarilishining kechikishidagi tezlashtirish;

p bu butun topshiriqni bajarish vaqtining vazifaning parallel qismiga nisbatan foizidir parallellashtirishdan oldin.

Beri S_kechikish < 1/(1 - p), bu shuni ko'rsatadiki, dasturning parallashtirilishi mumkin bo'lmagan kichik bir qismi parallellashtirishda mavjud bo'lgan umumiy tezlikni cheklaydi. Katta matematik yoki muhandislik muammosini echadigan dastur odatda bir nechta parallel va bir nechta parallel bo'lmagan (ketma-ket) qismlardan iborat bo'ladi. Agar dasturning parallel bo'lmagan qismi ish vaqtining 10 foizini tashkil etsa (p = 0.9), qancha protsessor qo'shilishidan qat'i nazar, biz 10 martadan ko'p bo'lmagan tezlikni olamiz. Bu ko'proq parallel ijro birliklarini qo'shish foydaliligiga yuqori chegarani qo'yadi. "Agar ketma-ket cheklovlar tufayli vazifani taqsimlab bo'lmaydigan bo'lsa, ko'proq kuch sarflash jadvalga ta'sir qilmaydi. Bolani tug'ilishi, qancha ayol tayinlanganiga qaramay, to'qqiz oy davom etadi."^[16]

Ning grafik tasviri Gustafson qonuni

Amdahl qonuni faqat muammo kattaligi aniqlangan hollarda qo'llaniladi. Amalda, ko'proq hisoblash resurslari mavjud bo'lganda, ular katta muammolarga (katta ma'lumotlar to'plamlariga) o'rganishga moyil bo'ladilar va parallel ravishda sarflanadigan vaqt odatda seriyali ishlarga qaraganda ancha tez o'sadi.^[17] Ushbu holatda, Gustafson qonuni parallel ishlashni kamroq pessimistik va aniqroq baholaydi:^[18]

Amdahl qonuni ham, Gustafson qonuni ham dasturning ketma-ket qismining ishlash vaqti protsessorlar soniga bog'liq emas deb hisoblaydi. Amdahl qonuni barcha muammoni aniq o'lchamda bo'lishini nazarda tutadi, shuning uchun parallel ravishda bajariladigan ishlarning umumiy miqdori ham protsessorlar sonidan mustaqil, Gustafson qonunida esa bajariladigan ishlarning umumiy miqdori parallel ravishda amalga oshiriladi protsessorlar soniga qarab chiziqli ravishda o'zgaradi.

Bog'liqliklar

Tushunish ma'lumotlar bog'liqliklari amalga oshirishda muhim ahamiyatga ega parallel algoritmlar. Hech bir dastur qaram hisob-kitoblarning eng uzun zanjiridan tezroq ishlay olmaydi ( tanqidiy yo'l), chunki zanjirdagi oldingi hisob-kitoblarga bog'liq hisob-kitoblar tartibda bajarilishi kerak. Biroq, aksariyat algoritmlar faqat qaram hisob-kitoblarning uzoq zanjiridan iborat emas; parallel ravishda mustaqil hisob-kitoblarni amalga oshirish uchun odatda imkoniyatlar mavjud.

Ruxsat bering P_men va P_j ikkita dastur segmenti bo'ling. Bernshteynning shartlari^[19] ikkalasi mustaqil bo'lgan va parallel ravishda bajarilishi mumkin bo'lgan vaqtni tasvirlang. Uchun P_men, ruxsat bering Men_men barcha kiritilgan o'zgaruvchilar bo'lishi va O_men chiqish o'zgaruvchilari va shunga o'xshash P_j. P_men va P_j agar ular qoniqtirsalar mustaqil

Birinchi shartning buzilishi oqimga bog'liqlikni keltirib chiqaradi, ikkinchi segment tomonidan qo'llaniladigan natijani beradigan birinchi segmentga mos keladi. Ikkinchi shart, ikkinchi segment birinchi segmentga kerak bo'lgan o'zgaruvchini hosil qilganda, qaramlikka qarshilikni anglatadi. Uchinchi va yakuniy shart chiqishga bog'liqlikni anglatadi: ikkita segment bir joyga yozganda, natija mantiqan oxirgi bajarilgan segmentdan kelib chiqadi.^[20]

Bir necha turdagi bog'liqliklarni ko'rsatadigan quyidagi funktsiyalarni ko'rib chiqing:

1: funktsiya Dep (a, b) 2: c: = a * b3: d: = 3 * c4: yakuniy funktsiya

Ushbu misolda 3 buyrug'i 2 buyrug'idan oldin (yoki hatto unga parallel ravishda) bajarilishi mumkin emas, chunki 3 buyrug'i 2 buyrug'ining natijasidan foydalanadi. Bu 1 shartni buzadi va shu bilan oqimga bog'liqlikni keltirib chiqaradi.

1: funktsiya NoDep (a, b) 2: c: = a * b3: d: = 3 * b4: e: = a + b5: end funktsiyasi

Ushbu misolda ko'rsatmalar o'rtasida bog'liqliklar mavjud emas, shuning uchun ularning hammasi parallel ravishda bajarilishi mumkin.

Bernshteynning shartlari xotirani turli jarayonlar o'rtasida bo'lishishga imkon bermaydi. Buning uchun kirishlar o'rtasida buyurtmani bajarishning ba'zi vositalari zarur, masalan semaforalar, to'siqlar yoki boshqasi sinxronizatsiya usuli.

Musobaqa shartlari, o'zaro chiqarib tashlash, sinxronizatsiya va parallel sekinlashuv

Parallel dasturdagi kichik topshiriqlar ko'pincha chaqiriladi iplar. Ba'zi parallel kompyuter arxitekturalari deb nomlanuvchi iplarning kichikroq, engil versiyalaridan foydalaniladi tolalar, boshqalar esa ma'lum bo'lgan katta versiyalardan foydalanadilar jarayonlar. Biroq, "iplar" odatda subtasks uchun umumiy atama sifatida qabul qilinadi.^[21] Tez-tez iplar kerak bo'ladi sinxronlashtirildi ga kirish ob'ekt yoki boshqa manba, masalan, qachon ular yangilanishi kerak o'zgaruvchan bu ular o'rtasida taqsimlanadi. Sinxronizatsiya qilinmasdan, ikkita ip orasidagi ko'rsatmalar har qanday tartibda o'zaro bog'lanishi mumkin. Masalan, quyidagi dasturni ko'rib chiqing:

Ip A	B mavzu
1A: V o'zgaruvchini o'qing	1B: V o'zgaruvchini o'qing
2A: V o'zgaruvchiga 1 qo'shing	2B: V o'zgaruvchiga 1 qo'shing
3A: V o'zgaruvchiga qaytadan yozing	3B: V o'zgaruvchiga qaytadan yozing

Agar 1B buyrug'i 1A va 3A oralig'ida bajarilsa yoki 1A buyrug'i 1B va 3B orasida bajarilsa, dastur noto'g'ri ma'lumotlar hosil qiladi. Bu a sifatida tanilgan poyga holati. Dasturchi a dan foydalanishi kerak qulflash ta'minlash uchun o'zaro chiqarib tashlash. Qulf bu dasturlash tili konstruktsiyasidir, bu bitta o'zgaruvchiga o'zgaruvchini boshqarish va shu qator o'zgaruvchisi ochilmaguncha boshqa oqimlarning uni o'qish yoki yozishdan saqlanishiga imkon beradi. Qulfni ushlab turgan ip uni bajarishi mumkin muhim bo'lim (ba'zi bir o'zgaruvchiga eksklyuziv kirishni talab qiladigan dastur bo'limi) va tugagandan so'ng ma'lumotlarni qulfdan chiqarish. Shuning uchun dasturning to'g'ri bajarilishini kafolatlash uchun yuqoridagi dastur qulflardan foydalanish uchun qayta yozilishi mumkin:

Ip A	B mavzu
1A: V o'zgaruvchini qulflash	1B: V o'zgaruvchini qulflash
2A: V o'zgaruvchini o'qing	2B: V o'zgaruvchini o'qing
3A: V o'zgaruvchiga 1 qo'shing	3B: V o'zgaruvchiga 1 qo'shing
4A: V o'zgaruvchiga qaytadan yozing	4B: V o'zgaruvchiga qaytadan yozing
5A: V o'zgaruvchining qulfini oching	5B: V o'zgaruvchining qulfini oching

Bitta ip V o'zgaruvchini muvaffaqiyatli bloklaydi, ikkinchisi esa shunday bo'ladi qulflangan- V qayta ochilguncha davom etish mumkin emas. Bu dasturning to'g'ri bajarilishini kafolatlaydi. Qatorlar manbalarga kirishni ketma-ketlashtirish kerak bo'lganda dasturning to'g'ri bajarilishini ta'minlash uchun qulflar kerak bo'lishi mumkin, ammo ulardan foydalanish dasturni juda sekinlashtirishi va ta'sir qilishi mumkin ishonchlilik.^[22]

Yordamida bir nechta o'zgaruvchini blokirovka qilish atom bo'lmagan qulflar dasturning imkoniyatlarini taqdim etadi boshi berk. An atom qulfi bir vaqtning o'zida bir nechta o'zgaruvchini qulflaydi. Agar ularning hammasini qulflay olmasa, ularning hech birini qulflamaydi. Agar har ikkala ip bir xil ikkita o'zgaruvchini atom bo'lmagan qulflar yordamida qulflashi kerak bo'lsa, ehtimol bitta ip ulardan birini, ikkinchisi esa ikkinchi o'zgaruvchini blokirovka qilishi mumkin. Bunday holatda, har ikkala ip ham tugallanmaydi va natijada blokirovkaga olib keladi.^[23]

Ko'pgina parallel dasturlar ularning pastki topshiriqlarini bajarishni talab qiladi sinxronlikda harakat qilish. Buning uchun a dan foydalanish kerak to'siq. To'siqlar odatda qulf yoki a yordamida amalga oshiriladi semafora.^[24] Deb nomlanuvchi algoritmlarning bir klassi qulfsiz va kutishsiz algoritmlar, qulflar va to'siqlardan foydalanishni butunlay oldini oladi. Biroq, ushbu yondashuvni amalga oshirish umuman qiyin va to'g'ri ishlab chiqilgan ma'lumotlar tuzilmalarini talab qiladi.^[25]

Hamma parallellik ham tezlikni keltirib chiqarmaydi. Umuman olganda, vazifa tobora ko'proq yo'nalishlarga bo'linib ketganligi sababli, ushbu mavzular o'zlarining vaqtining tobora ko'payib boradigan qismini bir-biri bilan muloqot qilish yoki resurslardan foydalanish uchun bir-birlarini kutish bilan o'tkazadilar.^[26][27] Resurs qarama-qarshiligi yoki aloqa xarajatlari boshqa hisob-kitoblarga sarflanadigan vaqtni ustun qilgandan so'ng, yana parallellashtirish (ya'ni ish hajmini ko'proq iplarga bo'lish) tugatish uchun zarur bo'lgan vaqtni qisqartirish o'rniga kuchayadi. Sifatida tanilgan ushbu muammo parallel sekinlashuv,^[28] ba'zi hollarda dasturiy ta'minotni tahlil qilish va qayta ishlash orqali yaxshilanishi mumkin.^[29]

Nozik taneli, qo'pol donali va uyatli parallellik

Ilovalar ko'pincha ularning pastki topshiriqlari bir-birlari bilan sinxronlashi yoki aloqa qilishi zarurligiga qarab tasniflanadi. Ilova nozik paralellikni namoyish etadi, agar uning pastki vazifalari soniyada ko'p marta aloqa qilishlari kerak bo'lsa; u soniyada bir necha marta aloqa qilmasa, qo'pol tanazzulni namoyish etadi va namoyish etadi uyatli parallellik agar ular kamdan-kam hollarda yoki hech qachon muloqot qilishlari shart bo'lmasa. Sharmandali ravishda parallel dasturlarni parallellashtirish eng oson deb hisoblanadi.

Muvofiqlik modellari

Asosiy maqola: Muvofiqlik modeli

Parallel dasturlash tillari va parallel kompyuterlarda a bo'lishi kerak izchillik modeli (xotira modeli sifatida ham tanilgan). Muvofiqlik modeli operatsiyalarni bajarish qoidalarini belgilaydi kompyuter xotirasi yuzaga keladi va natijalar qanday hosil bo'ladi.

Birinchi qat'iylik modellaridan biri edi Lesli Lamport"s ketma-ketlik model. Ketma-ketlik izchilligi - bu parallel dasturning xususiyati, uning parallel bajarilishi ketma-ket dastur bilan bir xil natijalarni beradi. Xususan, agar dastur har qanday bajarilish natijalari bir xil ketma-ketlikda bajarilgan bo'lsa, va har bir alohida protsessorning operatsiyalari ushbu ketma-ketlikda o'z dasturi tomonidan belgilangan tartibda paydo bo'ladigan bo'lsa, ketma-ket izchil bo'ladi. ".^[30]

Dastur tranzaktsion xotirasi izchillik modelining keng tarqalgan turi. Dastur tranzaktsion xotirasi qarz oladi ma'lumotlar bazasi nazariyasi tushunchasi atom operatsiyalari va ularni xotiraga kirish uchun qo'llaydi.

Matematik jihatdan ushbu modellar bir necha usulda namoyish etilishi mumkin. 1962 yilda kiritilgan, Petri to'rlari izchillik modellari qoidalarini kodlashtirishga dastlabki urinishlar edi. Dataflow nazariyasi keyinchalik bularga asoslangan va Dataflow arxitekturalari ma'lumotlar oqimi nazariyasini jismoniy amalga oshirish uchun yaratilgan. 1970-yillarning oxiridan boshlab, jarayon toshlari kabi Aloqa tizimlarining hisob-kitobi va Ketma-ket jarayonlar haqida ma'lumot berish o'zaro ta'sir qiluvchi tarkibiy qismlardan tashkil topgan tizimlar to'g'risida algebraik fikr yuritishga ruxsat berish uchun ishlab chiqilgan. Jarayonni hisoblash oilasiga so'nggi qo'shimchalar, masalan b-hisob, dinamik topologiyalar haqida fikr yuritish qobiliyatini qo'shdi. Lamport kabi mantiq TLA +va shunga o'xshash matematik modellar izlar va Aktyor voqealari diagrammasi, bir vaqtning o'zida tizimlarning xatti-harakatlarini tavsiflash uchun ishlab chiqilgan.

Shuningdek qarang: Ruxsat etilgan ketma-ketlik

Flinn taksonomiyasi

Maykl J. Flinn parallel (va ketma-ket) kompyuterlar va dasturlar uchun eng qadimgi tasniflash tizimlaridan birini yaratdi Flinn taksonomiyasi. Flinn dasturlarni va kompyuterlarni bitta to'plam yoki bir nechta ko'rsatmalar to'plamidan foydalanganligi va ushbu ko'rsatmalar bitta to'plam yoki bir nechta ma'lumotlar to'plamidan foydalanganligi yoki qilmaganligi bo'yicha tasnifladi.

Flinn taksonomiyasi

Yagona ma'lumotlar oqimi

SISD Miss

Bir nechta ma'lumot oqimlari

SIMD MIMD SPMD MPMD

Bitta ko'rsatma - bitta ma'lumot (SISD) tasnifi butunlay ketma-ket dasturga teng. Bitta ko'rsatma - ko'p ma'lumotlar (SIMD) tasnifi katta hajmdagi ma'lumotlar to'plamida bir xil operatsiyani takroriy bajarishga o'xshaydi. Bu odatda amalga oshiriladi signallarni qayta ishlash ilovalar. Ko'p ko'rsatma-bitta ma'lumot (MISD) kamdan kam ishlatiladigan tasnifdir. Bunga qarshi kurashish uchun kompyuter arxitekturalari ishlab chiqilgan (masalan sistolik massivlar), ushbu sinfga mos keladigan bir nechta dastur amalga oshirildi. Ko'p buyruq-ko'p ma'lumotli (MIMD) dasturlar hozirgacha parallel dasturlarning eng keng tarqalgan turi hisoblanadi.

Ga binoan Devid A. Patterson va Jon L. Xennessi, "Ba'zi bir mashinalar, albatta, ushbu toifadagi duragaylardir, ammo bu klassik model sodda, tushunarli va yaxshi taxminiylikni bergani uchun saqlanib qoldi. Bu, ehtimol, tushunarliligi tufayli ham - eng keng tarqalgan sxemadir. . "^[31]

Parallellik turlari