7 amaliy ish Mavzu: Kaskadli yig'indilik sxemalari va qisman yig'indini hisoblash Ishning maqsadi

7 - amaliy ish
Mavzu: Kaskadli yig'indilik sxemalari va qisman yig'indini hisoblash
Ishning maqsadi: Mavzu bo'yicha kerakli bilimlarni o'rganish va o'zlashtirish
Parallel hisoblash usullarini qurish va tahlil qilish usullari bilan dastlabki tanishish uchun raqamli qiymatlar ketma-ketligining qisman yig'indilarini topishning nisbatan oddiy masalasini ko'rib chiqamiz.
,
yig'iladigan qiymatlar soni qaerda (bu muammo prefiks summasi muammosi sifatida ham tanilgan - 3.3-bo'limga qarang).
Ushbu muammoni hal qilishning mumkin bo'lgan parallel usullarini o'rganishni biz uni shakllantirishning yanada sodda versiyasi bilan boshlaymiz - mavjud qiymatlar to'plamining umumiy yig'indisini hisoblash muammosi bilan (ushbu shaklda yig'ish muammosi umumiy qisqartirish muammosining alohida holatidir - 3.3-bo'limga qarang.)
...
Ketma-ket yig'ish algoritmi
Ushbu muammoni hal qilishning an'anaviy algoritmi raqamli to'plam elementlarini ketma-ket yig'ishdir

Ushbu algoritmning hisoblash sxemasi quyidagicha ifodalanishi mumkin (4.1-rasmga qarang):
,
bu erda yig'ish operatsiyalari ko'pligi (tepaliklar operatsiya kiritilishini bildiradi, har bir tepalik , yig'ilgan summaning qo'shimcha qiymatiga mos keladi ) va

operatsiyalarning axborotga bog'liqligini aniqlaydigan ko'plab yoylar mavjud.

Shakl: 4.1. Summa algoritmining ketma-ket hisoblash sxemasi
Ko'rib turganingizdek, ushbu "standart" yig'ish algoritmi faqat qat'iy ketma-ket bajarilishga imkon beradi va uni parallel qilish mumkin emas .
Kaskad yig'indisi
Yig'ish algoritmining parallelligi faqat qo'shish operatsiyasining assotsiativligidan foydalangan holda hisoblash jarayonini barpo etishning boshqa usuli bilan mumkin bo'ladi. Natijada yig'ilishning yangi versiyasi (adabiyotda kaskadli sxema sifatida tanilgan ) quyidagicha (4.2-rasmga qarang):

• 
  kaskadli sxemaning birinchi takrorlanishida barcha dastlabki ma'lumotlar juftlarga bo'linadi va har bir juftlik uchun qiymatlar yig'indisi hisoblanadi,
  
• 
  u holda barcha olingan juftlar yig'indilari ham juftlarga bo'linadi va juftliklar qiymatlari yig'indisi yana bajariladi va hokazo.
  

Ushbu hisoblash sxemasi grafik sifatida belgilanishi mumkin (ruxsat bering )
,

Shakl: 4.2. Kaskadli yig'ilish algoritmi
grafaning tepalari qaerda ( - kirish operatsiyalari, - birinchi takrorlash operatsiyalari va boshqalar) va grafik yoylari to'plami munosabatlar bilan belgilanadi:
...


Savollar:

1. 
   Tasvirlab bering n natija bilan algoritm yig'ish
   
2. 
   Kaskadli summa sxemasini tavsiflang .
   
3. 
   Parallel algoritmning bajarilish vaqtini tavsiflang.