Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti nukus filiali

13-mavzu: Parallelashtirish algoritmlarining samaradorlik 

ko’rsatkichlari, alohida yig’indini xisoblash usullari, yig’indini kaskad 

chizmasi 

 

REJA: 

13.1. Parallelashtirish algoritmlari 

13.2. Yig’indini ketma-ket va kaskadli xisoblash 

13.3. Samaradorlik ko’rsatgichlari 

 

Bir  qator  ketma-ketlikdagi  raqamli  qiymatlarni  topishning  oddiy  vazifasini 

hisoblashning parallel usullarini yaratish va tahlil qilish usullari ko'rib chiqaylik 

, 

Yig’indini ketma-ket xisoblash usuli. 

Ushbu muammoni hal qilishning an'anaviy algoritmi raqamli to'plam 

elementlarini ketma-ket yig'ishdan iborat 

 

, 

где 

 

есть 

множество 

операций 

суммирования 

(вершины 

 

обозначают 

операции 

ввода, 

каждая 

вершина 

, 

, 

соответствует прибавлению значения    к накапливаемой сумме  ), а 

  

---

есть множество дуг, определяющих информационные зависимости операций. 

 

4.1-rasm. 

Yig’indini  ketma-ket hisoblash algoritmi 

Kassa summasi 

Qo'shish operatsiyasining assotiviyasiga asoslangan holda hisoblash jarayonini 

qurishning boshqa usullari bilan yig'ish algoritmining parallelligi mumkin bo'ladi. 

Olingan natija versiyasi (adabiyotda kaskad sxemasi sifatida tanilgan) quyidagilar 

(4.2-rasm): 

 

kaskad sxemasining birinchi iteratsiyasi bo'yicha barcha dastlabki ma'lumotlar 

juftlarga bo'linadi va har bir juft uchun qiymatlar yig'iladi, 

natijada olingan barcha juftlar juftlarga bo'linadi va juft qiymatlari jamlanmasi 

qayta bajariladi va hokazo. 

Ushbu hisoblash sxemasi grafik sifatida belgilanishi mumkin (let) 

, 

 

4.2-rasm. Yig’indini xisoblashning kaskad alogoritmi sxemasi 

Ketma-ket yig'indini xisoblash algoritmining operatsiyalari soni bilan mos keladi. 

Kaskad davri alohida yinelemelerinin parallel ravishda amalga oshirilishi bilan, 

parallel yig'ish operatsiyalari umumiy soni teng