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

K _n ap=nl0g ₂ n
(parallel algoritm ­ketma-ket yig'ish usuliga nisbatan ko'proq (!) operatsiyalarni o'z ichiga oladi). Kerakli protsessorlar soni yig'ilgan qiymatlar soni bilan belgilanadi (p = n).
Olingan munosabatlarni hisobga olgan holda, ­barcha qisman summalarni hisoblash uchun parallel algoritmning tezlashuvi va samaradorligi ko'rsatkichlari quyidagicha baholanadi:
Sp=Ti/ _Tp =n/kirish,
Ep=Ti/pT _p =n/(plog ₂ n ) =n/{nlog ₂ n)=\/ login.
, yig'ilgan qiymatlar sonining ko'payishi bilan ­algoritm samaradorligi ­ham pasayadi va agar bu ko'rsatkichning qiymatini oshirish zarur bo'lsa, algoritmni o'zgartirish foydali bo'lishi mumkin. an'anaviy kaskad sxemasi.

4. 
   Maksimal erishish mumkin bo'lgan qiymatni baholash
   

parallellik
Parallel hisoblash sifatini baholash ­tezlashtirish va samaradorlik ko'rsatkichlarining eng yaxshi ( maksimal erishiladigan) qiymatlarini bilishni nazarda tutadi, ammo ideal qiymatlarni olish S _p = p tezlashtirish uchun va Ep=\ samaradorlik uchun barcha hisoblash vaqtini talab qiladigan vazifalar uchun taqdim etilmasligi mumkin . ­Shunday qilib, oldingi paragrafda ko'rib chiqilgan o'quv misoli uchun raqamli qiymatlar yig'indisini parallel hisoblash uchun minimal erishish mumkin bo'lgan vaqt login hisoblanadi. Ushbu muammoni hal qilishda ma'lum bir yordamni ­ushbu ma'ruza boshida keltirilgan nazariy bayonotlar berishi mumkin . Ularga qo'shimcha ravishda, biz maksimal erishish mumkin bo'lgan parallelizmni baholashda juda foydali bo'lishi mumkin bo'lgan bir qator qonuniyatlarni ko'rib chiqamiz ¹.

1. 
   Amdahl qonuni. Maksimal tezlashuvga erishish, bajarilgan hisob-kitoblarda ­parallel hisoblab bo'lmaydigan ketma-ket hisob-kitoblarning mavjudligi bilan to'sqinlik qilishi mumkin. Keling, / - qo'llaniladigan ma'lumotlarni qayta ishlash algoritmidagi ketma-ket hisob-kitoblarning nisbati , keyin Amdal qonuniga muvofiq (Amdahl) p protsessorlardan foydalanilganda hisoblash jarayonining tezlashishi ­qiymat bilan chegaralanadi
   

o'n bir