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

Sp _{_} <
* /+(1 f)!p f
Shunday qilib, masalan, bajarilgan hisob-kitoblarda ketma-ket ko'rsatmalarning atigi 10% bo'lsa, parallelizmdan foydalanish samarasi ­ma'lumotlarni qayta ishlashning 10 barobar tezlashishidan oshmasligi kerak. Kaskad sxemasi uchun qiymatlar yig'indisini hisoblashning ko'rib chiqilayotgan o'quv misolida ketma-ket hisob-kitoblarning nisbati /=^ 2 «/ ni tashkil qiladi va natijada ­mumkin bo'lgan tezlashtirish qiymati S*= bahosi bilan cheklanadi. n/log 2 tt .
Amdal qonuni parallel dasturlash sohasidagi eng jiddiy muammolardan birini tavsiflaydi ­(ketma-ket ko'rsatmalarning ma'lum bir nisbati bo'lmagan algoritmlar amalda mavjud emas). Biroq, ketma-ket harakatlarning nisbati ko'pincha muammolarni parallel ravishda hal qilish imkoniyatini emas ­, balki qo'llaniladigan algoritmlarning ketma-ket xususiyatlarini tavsiflaydi. Shu sababli, parallellashtirish uchun ko'proq mos keladigan usullarni tanlash orqali ketma-ket hisob-kitoblarning nisbati sezilarli darajada kamayishi mumkin.
Shuni ham ta'kidlash kerakki, Amdal qonuni ketma-ket hisob-kitoblarning ulushi / doimiy qiymat ­bo'lib, hal qilinayotgan muammoning hisoblash murakkabligini belgilaydigan ­n parametriga bog'liq emas degan faraz ostida ko'rib chiqiladi. Biroq, ko'p sonli masalalar uchun kasr /=A(a) n ning kamayuvchi funksiyasi bo'lib, bu holda protsessorlarning belgilangan soni uchun tezlikni ­hal qilinayotgan masalaning hisoblash murakkabligini oshirish orqali oshirish mumkin. Bu mulohazani tezlashtirish S _p = S _p (n) degan bayonot sifatida shakllantirish mumkin. n parametrining ortib boruvchi funktsiyasidir ( bu bayonot ko'pincha ­Amdahl effekti deb ataladi). Shunday qilib, masalan, protsessorlarning qat'iy sonidan foydalangan holda qiymatlar yig'indisini hisoblash bo'yicha o'quv misoli uchun yig'ilgan ma'lumotlar to'plamini n / p o'lchamdagi bloklarga bo'lish mumkin, ular uchun qisman summalarni birinchi navbatda parallel ravishda hisoblash mumkin. , va keyin ­bu summalar kaskad sxemasi yordamida qo'shilishi mumkin. Bu holda bajarilgan operatsiyalarning ketma-ket qismining davomiyligi (eng kichik mumkin bo'lgan parallel bajarish vaqti)
Tp=(n/p)+log _2p ,
bu esa ketma-ket hisob-kitoblarning ulushini miqdor sifatida baholashga olib keladi
f^(l/p)+log ₂ p/n.
Olingan ifodadan kelib chiqqan holda, ketma-ket ­hisob-kitoblarning nisbati / ortib borishi bilan kamayadi n va cheklovchi holatda biz maksimal mumkin bo'lgan tezlashuvning ideal bahosini olamiz ­S * = p.

2.