DOPIPE - DOPIPE

DOPIPE parallellik bajarish usuli pastadir darajasidagi parallellik bayonotlarni tsiklda quvurlash orqali. Quvurli parallellik ilmoqlar, funktsiyalar va algoritmik bosqichlar kabi mavhumlikning turli darajalarida mavjud bo'lishi mumkin. Darajasi parallellik dasturchilarning ushbu kontseptsiyadan maksimal darajada foydalanish qobiliyatiga bog'liq. Bu, shuningdek, mustaqil vazifalarni aniqlash va ajratish va ularni parallel ravishda bajarish kabi omillarga bog'liq.[1]

Fon

Ish bilan ta'minlashning asosiy maqsadi pastadir darajasidagi parallellik - dasturning ketma-ket topshiriqlarini izlash va ajratish va ular haqida oldindan hech qanday ma'lumot bermasdan ularni parallel vazifalarga aylantirish algoritm. Ma'lumotlarning takrorlanadigan va bajarilish vaqtini ko'p sarf qiladigan qismlari yaxshi nomzodlardir pastadir darajasidagi parallellik. Ning ba'zi bir keng tarqalgan dasturlari pastadir darajasidagi parallellik matematik tahlilda joylashgan bo'lib, ular ichki ko'chadan takrorlanadigan ko'p o'lchovli matritsalardan foydalaniladi.[2]

Parallelizatsiya texnikasining har xil turlari mavjud bo'lib, ular ma'lumotlarni saqlashning yuqori harajati, parallellik darajasi va ma'lumotlar bog'liqliklari. Ba'zi ma'lum texnikalar quyidagilardir: DOALL, DOACROSS va DOPIPE.

DOALL: Ushbu usul biz takrorlanishning har qanday takrorlanishini takrorlashlar orasidagi o'zaro ta'sirsiz parallel qilishimiz mumkin bo'lgan joyda qo'llaniladi. Shunday qilib, umumiy ish vaqti N * T dan kamayadi (ketma-ket protsessor uchun, bu erda T har bir takrorlash uchun bajarilish vaqti) faqat T ga teng bo'ladi (chunki barcha N takrorlanishlar parallel ravishda bajariladi).

DOACROSS: Ushbu usul ma'lumotlarga bog'liqlik ehtimoli mavjud bo'lgan har bir joyda qo'llaniladi. Demak, biz vazifalarni shu tarzda parallel qilamizki, barcha ma'lumotlar mustaqil vazifalari parallel ravishda, lekin qaramlari ketma-ket bajariladi. Parallel protsessorlarda bog'liq vazifalarni sinxronlashtirish uchun ishlatiladigan sinxronizatsiya darajasi mavjud.

Tavsif

DOPIPE - bu quvurli har bir takrorlash paytida hosil bo'lgan har bir element keyingi takrorlashda sarflanadigan dasturlarda ishlatiladigan parallellashtirish texnikasi. Quyidagi misol ko'chadan ichidagi vazifalarni buzish va ularni bajarish orqali bajarilishning umumiy vaqtini qisqartirish uchun DOPIPE texnikasini qanday amalga oshirishni ko'rsatadi. quvurli uslubi. Vazifalarni buzish shunday sodir bo'ladiki, hamma bog'liqliklar tsikl ichida bir tomonlama, ya'ni quyidagi takrorlash avvalgi takrorlanishga bog'liq emas.

Misol

Quyidagi dastur a-ni ko'rsatadi psevdokod[2] DOPIPE parallelligi uchun.

Ushbu kodda biz takrorlanadigan tsikl ichida uchta vazifa (F0, F1 va F2) mavjudligini ko'ramiz j uchun 1 dan N. Quyidagi koddagi bog'liqliklar ro'yxati:

F1 [j] → T F1 [j + 1], F1 iborasini takrorlashda nazarda tutadi j + 1 takrorlashda F1 iborasidan keyin bajarilishi kerak j. Bu haqiqiy qaramlik deb ham ataladi.

F1 [j] → T F2 [j], F2 iborasini takrorlashda nazarda tutadi j takrorlashda F1 iborasidan keyin bajarilishi kerak j.

uchun (j = 1; j <= N; j ++) {F0: o [j] = x [j] - a [j]; F1: z [j] = z [j-1] * 5; F2: y [j] = z [j] * w [j];}

Agar ushbu kod ketma-ket bajarilgan bo'lsa, unda sarf qilingan umumiy vaqt N * (T) ga teng bo'lar ediF0 + TF1 + TF2), bu erda TF0, TF1 va TF2 F0, F1 va F2 funktsiyalarining bajarilish vaqtini navbati bilan belgilang.Endi, agar ko'chadan ichidagi bayonotlarni quyidagi tarzda quvurlash orqali tsiklni parallellashtirsak:

uchun (j = 1; j <= N; j ++) {F0: o [j] = x [j] - a [j]; // DOALL parallelligi} uchun (j = 1; j <= N; j ++) {F1: z [j] = z [j-1] * 5; // DOPIPE parallelligi post (j); // F1 natijasi joylashtirilgan va foydalanish uchun} uchun (j = 1; j <= N; j ++) {wait (j); // F1 tugaguncha kutadi va F2 F2 tomonidan ishlatilishi uchun z [j] qiymatini hosil qiladi: y [j] = z [j] * w [j];}

F0 mustaqil funktsiya bo'lgani uchun, ya'ni hech qanday ko'chadan bog'liqlikka ega emas (bog'liqlik yo'q) j + 1 yoki j-1 takrorlash). Ikkala tsikldagi boshqa bayonotlar bo'yicha ham bog'liqlik yo'q. Shunday qilib, biz ushbu funktsiyani butunlay ajratib olishimiz va uni DOALL yordamida parallel ravishda bajarishimiz mumkin parallellik. Boshqa tomondan, F1 va F2 bayonotlari bog'liqdir (yuqorida bayon qilingan), shuning uchun biz ularni ikki xil ko'chadanlarga ajratamiz va ularni quvurli moda. Biz foydalanamiz post (j) va kuting (j) F1 va F2 tsikllarini sinxronlashtirish uchun.

Ning birinchi takrorlanishidan boshlab j, F1 bayonoti T da bajariladiF1 vaqt. Ayni paytda, F2 bajarilmayapti, chunki u qiymatni kutmoqda z [j] F1 tomonidan ishlab chiqarilishi kerak. F1 takrorlash uchun uning bajarilishini tugatganda j, bu qiymatni ishlatadi post (j). F1-ning bajarilishini kutgandan so'ng kuting (j), F2 qiymati bajarilganligi sababli uning bajarilishini boshlaydi z [j] foydalanish uchun mavjud. Shuningdek, F1 ning bajarilishi F2 tomonidan cheklanmaganligi sababli, F1 bajariladi j + 1 bir vaqtning o'zida. Quyidagi rasmda barcha bayonotlarning bajarilish muddati ko'rsatilgan.

DOPIPE misoli

Rasmdan biz F0 ni bajarish uchun umumiy vaqt T ekanligini ko'rmoqdamizF0, chunki F0 ning barcha takrorlanishi parallel ravishda bajariladi. F1 va F2 uchun umumiy ijro vaqti N * T ga tengF1 + TF2 (ahamiyatsiz sinxronizatsiya vaqtini hisobga olgan holda).

Bu ketma-ket bajarish paytida olingan vaqtdan ancha kam.

Boshqa modellar bilan taqqoslash

DOALL parallellik asosan bo'linish va zabt etish tamoyili asosida ishlaydi. Bu erda barcha vazifalar noyob ma'lumotlar to'plamidan foydalanadigan turli xil takrorlashlarda ishlaydi. Shunday qilib, ushbu dastur bilan bog'liq muammo shundaki, katta miqdordagi ma'lumotlar birgalikda hisoblanganda, katta kesh bo'shliq boshqacha ishlash uchun kerak iplar. Yo'q, chunki bog'liqliklar ichida iplar, iplararo aloqa uchun qo'shimcha xarajatlar yo'q.

DOPIPE-da, iplar o'rtasida sinxronizatsiya ustuni mavjud. Biroq, uning truboprovodli tuzilishi tufayli u kamroq kesh hajmini talab qiladi, chunki ishlab chiqarilgan ma'lumotlar darhol iste'molchi tomonidan iste'mol qilinadi.[2]

Shuningdek qarang

Adabiyotlar

  1. ^ Pankratius, Viktor; Adl-Tabatabai, Ali-Rizo; Tichy, Valter (2011). Ko'p yadroli dasturiy ta'minotni ishlab chiqish asoslari. CRC press.
  2. ^ a b v Solihin, Yan (2016). Parallel ko'p yadroli me'morchilik asoslari. Chapman va Hall / CRC.