Лекция 2 Моделирование и анализ параллельных вычислений

£
V
-V ^x
VA.
da
G

XX XX
5 6 7 8
^X , ^X ₂ ^X , ^X 4
xxxxx xxx,
9 10 11 12 13 14 15 16

Guruch. 2.4. O'zgartirilgan kaskad yig'ish sxemasi
birinchi bosqichni bajarish uchun tizimga kirish talab qilinadi p\={n/ logindan foydalanganda parallel operatsiyalar ) protsessorlar. Ikkinchi bosqichni bajarish uchun sizga kerak
logi(n/log ₂ n)2 n
pi=(n/log ₂ n)/2 uchun parallel amallar protsessorlar. Natijada, yig'ishning ushbu usuli quyidagi ko'rsatkichlar bilan tavsiflanadi ­:

T _p =2log ₂ n, p=(n/log ₂ n).
Olingan hisob-kitoblarni hisobga olgan holda ­, o'zgartirilgan kaskad sxemasining tezlashuvi va samaradorligi ko'rsatkichlari quyidagi munosabatlar bilan belgilanadi:
Sp=T\/T _p ={n-\)/2log ₂ n,
Ep=T\/pTp=(n-l)/{2{n/log ₂ n)log ₂ n) ={n-\)/2n.
Ushbu hisob-kitoblarni an'anaviy kaskad sxemasi ko'rsatkichlari bilan taqqoslab ­shuni ta'kidlash mumkinki, taklif qilingan parallel algoritm uchun tezlik 2 baravar kamaydi, ammo yangi yig'ish usulining samaradorligi uchun asimptotik nolga teng bo'lmagan bahoni olish mumkin. quyida
E _p \u003d (n - 1) / 2uW), 25, limEp -\u003e 0,5 da
Shuni ham ta'kidlash mumkinki, ko'rsatkichlarning ushbu qiymatlariga ­5-teoremada belgilangan protsessorlar soni bilan erishiladi. Bundan tashqari, shuni ta'kidlash kerakki, an'anaviy kaskad sxemasidan farqli o'laroq, o'zgartirilgan kaskad algoritmi iqtisodiy jihatdan maqbuldir ­. chunki bu holatda hisob-kitoblarning narxi
C _p \u003d p T _p ={n/log ₂ ri){2log ₂ ri)
algoritmning bajarilish vaqtiga proportsionaldir .­

4. 
   Barcha qisman summalarni hisoblash
   

Keling ­, qiymatlar ketma-ketligining barcha qisman summalarini hisoblashning asl muammosiga qaytaylik va hisob-kitoblarni ketma-ket va parallel tashkil etishning mumkin bo'lgan usullarini tahlil qilaylik. Skayar kompyuterda barcha qisman yig'indilarni hisoblashni bir xil miqdordagi operatsiyalar (!) bilan odatiy ketma-ket yig'ish algoritmi yordamida olish mumkin .­
T\=p.
Parallel bajarishda kaskad sxemasidan aniq foydalanish ­istalgan natijalarga olib kelmaydi; Samarali parallellashtirishga erishish muammolarni hal qilish uchun yangi parallel yo'naltirilgan algoritmlarni ishlab chiqish uchun yangi yondashuvlarni (hatto ketma-ket dasturlashda tengi yo'q) talab qiladi. Shunday qilib, barcha qisman yig'indilarni topishning ko'rib chiqilayotgan muammosi uchun log 2 n natijalarini beruvchi algoritm. parallel operatsiyalar (umumiy summani hisoblashda bo'lgani kabi) quyidagicha bo'lishi mumkin (2.5-rasmga qarang, shuningdek [22]):

• 
  hisob-kitoblar boshlanishidan oldin S ning nusxasi yaratiladi yig'ilgan ­qiymatlar vektorlari (<5=x);
  
• 
  keyin yig'indining har bir iteratsiyasida /, \4Klog2fi, yordamchi vektor Q hosil bo'ladi S vektorini siljitish orqali 2 ^m pozitsiyalar bilan (chapdagi siljish paytida chiqarilgan pozitsiyalar nol qiymatlarga o'rnatiladi); algoritmning takrorlanishi S vektorlarni yig'ishning parallel operatsiyasi bilan tugaydi va Q.
  

Guruch. 2.5. Barcha qisman summalarni hisoblash uchun parallel algoritm sxemasi (qiymatlari *S/_/ i dan o'rtacha qiymatlar yig'indisi jga _ raqamli ketma-ketlik elementlari)
Hammasi bo'lib, parallel algoritm log 2 n da ishlaydi parallel qo'shish operatsiyalari. Algoritmning har bir iteratsiyasida ­n ta skalyar qo‘shish amallari parallel ravishda bajariladi va shu bilan skalyar amallarning umumiy soni ­qiymat bilan aniqlanadi.