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

i?l = {(Vo/,Vi/),(Vii,Vi/+i), 1
operatsiyalarning ma'lumotlarga bog'liqligini belgilaydigan bir qator yoylar mavjud ­.
I

+
N
XI g X ₂ C LGts
X ₄ (
P
Guruch. 2.2. Yig'ish algoritmining ketma-ket hisoblash sxemasi
Ko'rib turganingizdek, bu "standart" yig'ish algoritmi faqat qat'iy ketma-ket bajarishga imkon beradi va uni ­parallel qilib bo'lmaydi.

2. 
   Kaskad yig'ish sxemasi
   

Yig'ish algoritmining parallelligi faqat qo'shish operatsiyasining assotsiativligidan foydalanishga asoslangan hisoblash jarayonini qurishning boshqa usuli bilan mumkin bo'ladi. Olingan ­yig'indining yangi versiyasi (adabiyotda kaskad sxemasi sifatida tanilgan) quyidagicha (2.3-rasmga qarang):

• 
  kaskad sxemasining birinchi iteratsiyasida barcha dastlabki ma'lumotlar ­juftlarga bo'linadi va ularning qiymatlari yig'indisi har bir juftlik uchun hisoblanadi;
  
• 
  bundan tashqari, barcha olingan summalar ham juftlarga bo'linadi va juftlik qiymatlarining yig'indisi yana amalga oshiriladi va hokazo.
  

Ushbu hisoblash sxemasini grafik sifatida aniqlash mumkin ( n= ^{2k bo'lsin} )

Guruch. 2.3. Yig'ish algoritmining kaskad sxemasi

'i >
2 , I ₂ ),




P
>
Bu yerda ^={(v,i,...,v/i), 01 q} - grafikning uchlari (( voi ,...vo') operatsiyalar kiritilishi, ( ­vi/,...,vi„/ 2 ) birinchi iteratsiyaning yig‘indisi amallari va boshqalar), grafik yoylar to‘plami esa quyidagi munosabatlar bilan aniqlanadi:
Ri ={ ( v,-. 1 , 2J - 1 Vij), (V/-1, 2jVij), KKk,
qiymatga teng ekanligini taxmin qilish oson.­
k= log2n ,
va jami jami operatsiyalar soni
Klast ^{\ u003d} n / 2 + "/4 + ... +1 \ u003d 72 - 1
yig'ish algoritmining ketma-ket versiyasi operatsiyalari soniga to'g'ri keladi . ­Kaskad sxemasining individual iteratsiyasi parallel bajarilishi bilan parallel yig'ish operatsiyalarining umumiy soni teng bo'ladi.