13-
mavzu: Parallelashtirish algoritmlarining samaradorlik
ko‘rsatkichlari
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
,
где
есть
множество
операций
суммирования
(вершины
обозначают
операции
ввода,
каждая
вершина
,
,
соответствует прибавлению значения к накапливаемой сумме ), а
есть множество дуг, определяющих информационные зависимости операций.
Kassa summasi
4.1-rasm. Yig’indini ketma-ket hisoblash algoritmi
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
