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

K _par ■ _
Har qanday hisoblash ­operatsiyalarining bajarilish vaqti bir xil va birlik deb faraz qilinganligi sababli, u holda T\ - K _oxirgi , T _p = K _par , shuning uchun jamlash algoritmining kaskad sxemasining tezlashuvi va samaradorligi ko'rsatkichlari ­quyidagicha baholanishi mumkin:
Sp—Ti/Tp —(n— 1)/ log 2 ,
E _p =T\/p T _p ={n-\ )/(plog ₂ n) =(tz- 1 )/{{n/2)log ₂ n ) ,
Bu erda p - n / 2 - kaskad sxemasini bajarish uchun zarur ­bo'lgan protsessorlar soni.
Olingan xususiyatlarni tahlil qilib ­, kaskad sxemasining parallel bajarish vaqti 2-teoremadagi parakompyuter uchun bahoga to'g'ri kelishini ta'kidlashimiz mumkin. Biroq, ­yig'ilgan qiymatlar sonining ko'payishi bilan protsessorlardan foydalanish samaradorligi pasayadi.
UTE _p ->0 da

3. 
   O'zgartirilgan kaskad sxemasi
   

Asimptotik nolga teng bo'lmagan samaradorlikni, masalan, o'zgartirilgan kaskad ­sxemasidan foydalanish orqali olish mumkin (qarang [22]). Hisoblashlarni qurishni soddalashtirish uchun n=2 ^k , k= 2 ^{s ni qabul qilishimiz mumkin} . Keyin, kaskad sxemasining yangi versiyasida barcha ­hisob-kitoblar yig'ishning ikkita ketma-ket bajarilgan bosqichida amalga oshiriladi ­(2.4-rasmga qarang):

• 
  hisob-kitoblarning birinchi bosqichida barcha yig'ilgan qiymatlar ­(n/log ₂ n) ga bo'linadi. guruhlar, har birida login mavjud elementlar ­; keyin har bir guruh uchun qiymatlar yig'indisi ketma-ket yig'ish algoritmi yordamida hisoblanadi; har bir guruhdagi hisob-kitoblar bir-biridan ­mustaqil ravishda amalga oshirilishi mumkin (ya'ni, parallel ravishda - bu hech bo'lmaganda (n/ login) talab qiladi) protsessorlar);
  
• 
  qabul qilish uchun ikkinchi bosqichda (n/ login) individual guruhlarning summalari, odatiy kaskad sxemasi qo'llaniladi.
  

i
haqida
O
V