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

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

	T <1	(n t L —+ 1	t = - + 7L
R	T = 1	1 r	R

Teoremaning isboti ­parallel algoritmning jadvalini tuzishning amaliy usulini beradi. Dastlab, jadval ishlatiladigan protsessorlarning cheklangan sonini hisobga olmasdan tuzilishi mumkin ( parakompyuter uchun jadval). Keyin, teoremani chiqarish sxemasiga ko'ra, ­ma'lum miqdordagi protsessorlar uchun jadval tuzilishi mumkin.

4. 
   Parallel algoritm samaradorligi ko'rsatkichlari
   

Tezlashtirish (tezlashtirish), p protsessorlari uchun parallel algoritm yordamida olingan, hisob-kitoblarni bajarishning ketma-ket varianti bilan solishtirganda ­, qiymat bilan aniqlanadi.
S _p (n)=Ti(n)/T _p (n),
bular. skaler kompyuterda masalalarni yechish vaqtining parallel algoritmni bajarish vaqtiga nisbati sifatida ( n qiymati echilayotgan masalaning hisoblash murakkabligini parametrlash uchun ishlatiladi ­va masalan, kirish soni sifatida tushunish mumkin). muammo ma'lumotlari).
Samaradorlik _ masalani yechishda parallel algoritm bilan protsessorlardan foydalanish ­munosabat bilan aniqlanadi
E _p {n)=Ti{n)/(pT _p (n))=S _P {n)/p
protsessorlar muammoni hal qilishda haqiqatda ishtirok etadigan algoritmni bajarish vaqtining o'rtacha qismini aniqlaydi ).­
Yuqoridagi munosabatlardan shuni ko'rsatish mumkinki, eng yaxshi holatda S _p {n)=p va E _p (n)=\. Parallel hisoblash samaradorligini baholash uchun ushbu ko'rsatkichlarni amaliy qo'llashda ­ikkita muhim jihatni hisobga olish kerak:
• Muayyan sharoitlarda tezlashuv ishlatiladigan protsessorlar sonidan ko'p bo'lishi mumkin S _p (n) > p - bu holda, superchiziqli (superchiziqli) mavjudligi haqida gapiriladi. tezlashuv. Bunday vaziyatlarning paradoksal tabiatiga qaramasdan ­(tezlanish protsessorlar sonidan oshib ketadi), amalda superlinear tezlashuv sodir bo'lishi mumkin. Ushbu hodisaning sabablaridan biri ketma-ket va parallel dasturlarni bajarish shartlarining o'xshash emasligi bo'lishi mumkin. Masalan, ­bitta protsessorda muammoni hal qilishda, qayta ishlanayotgan barcha ma'lumotlarni saqlash uchun RAM etarli emas, keyin esa sekinroq tashqi xotiradan foydalanish kerak bo'ladi ( ­bir nechta protsessorlardan foydalanilganda, RAM etarli bo'lishi mumkin protsessorlar o'rtasida ma'lumotlarni taqsimlash). Superchiziqli tezlashuvning yana bir sababi , masalani yechish murakkabligining ishlov beriladigan ma'lumotlar hajmiga bog'liqligining chiziqli bo'lmagan tabiati bo'lishi mumkin. ­Masalan, ko'pchilikka ma'lum bo'lgan pufakchali tartiblash algoritmi kerakli amallar sonining tartiblangan ma'lumotlar soniga kvadratik bog'liqligi bilan tavsiflanadi. Natijada , tartiblanuvchi massivni protsessorlar o'rtasida taqsimlashda protsessorlar ­sonidan oshib ketadigan tezlikni olish mumkin (bu misol 9-bobda batafsilroq muhokama qilinadi). Superchiziqli tezlanishning manbai, shuningdek , ketma-ket va parallel usullarning hisoblash sxemalari o'rtasidagi farq bo'lishi mumkin ,
• Aniqroq o‘rganilganda shuni ta’kidlash mumkinki, ko‘rsatkichlardan birida parallel hisoblash sifatini oshirishga urinishlar (tezlashtirish yoki samaradorlik) ­boshqa ko‘rsatkich bo‘yicha ­vaziyatning yomonlashishiga olib kelishi mumkin, chunki parallel hisoblash sifati ko‘rsatkichlari. hisoblash ko'pincha qarama-qarshidir. Misol uchun, tezlashuvning o'sishiga odatda protsessorlar sonini ko'paytirish orqali erishish mumkin, bu, qoida tariqasida, samaradorlikning pasayishiga olib keladi . Aksincha, samaradorlikning oshishi ko'p hollarda protsessorlar sonini kamaytirish orqali erishiladi (cheklovchi holatda ideal samaradorlik ­_Ep ( n ) = 1 bitta protsessor yordamida osonlik bilan erishiladi). Natijada, parallel hisoblash usullarini ishlab chiqish ­ko'pincha kerakli tezlashtirish va samaradorlik ko'rsatkichlarini hisobga olgan holda ba'zi bir kompromis variantni tanlashni o'z ichiga oladi.
xarajatlarni (xarajatlarni) baholash foydali bo'lishi mumkin. masalani parallel hal qilish vaqti va foydalanilgan protsessorlar sonining mahsuloti sifatida aniqlanadigan hisoblash­
C _p \u003d pT _p .
Shu munosabat bilan biz optimal xarajatlar (xarajat-optimal) tushunchasini belgilashimiz ­mumkin . qiymati eng yaxshi ketma-ket algoritmni bajarish vaqtiga mutanosib bo'lgan usul sifatida parallel ­algoritm.
Bundan tashqari, kiritilgan tushunchalarni tasvirlash uchun keyingi kichik bo'limda ­biz raqamli qiymatlar ketma-ketligi uchun qisman yig'indilarni hisoblash muammosini hal qilish bo'yicha misolni ko'rib chiqamiz. Bundan tashqari , ushbu ko'rsatkichlar hisoblash matematikasining bir qator tipik muammolarini hal qilishda 6-11 ma'ruzalarda ko'rib chiqilgan barcha parallel algoritmlarning samaradorligini tavsiflash uchun ishlatiladi .­

4. 
   Treningga misol. Raqamli qiymatlar ketma-ketligining qisman yig'indilarini hisoblash
   

yuzaga keladigan bir qator muammolarni ko'rsatish uchun ­raqamli qiymatlar ketma-ketligining qisman yig'indilarini topishning nisbatan oddiy masalasini ­ko'rib chiqaylik.
^s k=^ ^x i> 1 ^k

iJ
bu erda n - yig'ilgan qiymatlar soni (bu muammo prefiks yig'indisi muammosi sifatida ham tanilgan).
, ushbu muammoni hal qilishning mumkin bo'lgan parallel usullarini uni shakllantirishning yanada sodda versiyasi bilan - mavjud qiymatlar to'plamining ­umumiy yig'indisini hisoblash muammosi bilan o'rganishni boshlaylik (ushbu shaklda yig'ish muammosi ­alohida holatdir). umumiy qisqartirish muammosi)
■?=!>< •
i=i

1. 
   Ketma-ket yig'ish algoritmi
   

Ushbu muammoni hal qilishning an'anaviy algoritmi ­chi so'zlar to'plamining elementlarini ketma-ket yig'ishdan iborat.
S=0,
S=S+x _u ...
Ushbu algoritmning hisoblash sxemasi quyidagicha ifodalanishi mumkin (2.2-rasmga qarang):
Gi=(Vi, Ri),
bu yerda V\={vo\,...,vo _n , vn,...,vi„} amallar to‘plami ( voi,...,vo« cho‘qqilari kiritish amallarini bildiradi, har bir uchi vi,-, 1 S summasiga x qiymatini qo'shishga mos keladi ), - a