3 Amaliy mashg’ulot: Mavzu

Algoritmni parallel bajarish sxemasining tavsifi 
Tanlangan hisoblash sxemasi doirasida o‘rtasida yo‘l bo‘lmagan algoritm 
operatsiyalari parallel ravishda bajarilishi mumkin (masalan, 3.1-rasmdagi hisoblash 
sxemasi uchun barcha ko‘paytirish amallari parallel ravishda bajarilishi mumkin, 
keyin esa birinchi ikkita ayirish amali). Algoritmning parallel bajarilishini 
tavsiflashning mumkin bo'lgan usuli quyidagicha bo'lishi mumkin. 
Algoritmni bajarish uchun ishlatiladigan protsessorlar soni p bo'lsin. Keyin, hisob-
kitoblarni parallel bajarish uchun to'plamni (jadvalni) o'rnatish kerak, unda har bir 
operatsiya uchun i 
∈
V operatsiyani bajarish uchun foydalaniladigan Pi 
protsessorining raqami va ti operatsiyasining boshlanish vaqti ko'rsatilgan. 
Jadvalni amalga oshirish uchun Hp to'plamini belgilashda 
quyidagi talablarga rioya qilish kerak: 
1.
, ya'ni. bir xil protsessor bir vaqtning o'zida turli 
operatsiyalarga tayinlanmasligi kerak; 
2.
, ya'ni. operatsiyaning belgilangan vaqtiga qadar barcha 
kerakli ma'lumotlar allaqachon hisoblangan bo'lishi kerak. 
Parallel algoritmning bajarilish vaqtini aniqlash G algoritmining hisoblash 
sxemasining modelini Hp grafigi bilan birgalikda p protsessorlari yordamida 
bajariladigan parallel algoritm Ap (G, Hp) modeli sifatida ko'rish mumkin. Parallel 
algoritmni bajarish vaqti jadvalda ishlatiladigan maksimal vaqt qiymati bilan 
belgilanadi. 
Tanlangan 
hisoblash 
sxemasi 
uchun 
algoritmning minimal bajarilishini ta'minlaydigan jadvaldan foydalanish maqsadga 
muvofiqdir. 
Bajarish vaqtini qisqartirish eng yaxshi 
hisoblash sxemasini tanlash orqali ta'minlanishi mumkin. Tp (G, Hp), Tp (G) va Tp 
baholari algoritmni parallel bajarish vaqtining ko'rsatkichlari sifatida ishlatilishi 
mumkin. Bundan tashqari, maksimal mumkin bo'lgan parallellikni tahlil qilish 

---

181 
uchun algoritmning eng tez bajarilishini baholashni aniqlash mumkin. 
Tp (G, Hp), Tp (G) va Tp baholari algoritmni parallel bajarish 
vaqtining ko'rsatkichlari sifatida ishlatilishi mumkin. Bundan tashqari, maksimal 
mumkin bo'lgan parallellikni tahlil qilish uchun algoritmning eng tez bajarilishini 
baholashni aniqlash mumkin. 
T∞ smetasini cheksiz miqdordagi protsessorlardan foydalanganda parallel 
algoritmni bajarishning minimal mumkin bo'lgan vaqti deb hisoblash mumkin 
(nazariy tahlilda cheksiz miqdordagi protsessorli hisoblash tizimi tushunchasi, 
odatda parakompyuter deb ataladi, keng qo'llaniladi. parallel hisoblash). T1 bahosi 
bitta protsessordan foydalanganda algoritmning bajarilish vaqtini aniqlaydi va shu 
bilan muammoni hal qilish algoritmining ketma-ket versiyasini bajarish vaqtini 
ifodalaydi. 
qayerda | |, eslaylik, G hisoblash sxemasining kirish 
cho'qqilarisiz uchlari soni. Shuni ta'kidlash kerakki, agar T1 bahosini aniqlashda biz 
muammoni hal qilish uchun faqat bitta tanlangan algoritmni ko'rib chiqish bilan 
cheklansak. 
u holda bunday baholash yordamida olingan tezlashtirish 
ko'rsatkichlari tanlangan algoritmning parallellashuv samaradorligini tavsiflaydi. 
Hisoblash matematikasining o'rganilayotgan muammosini parallel hal qilish 
samaradorligini baholash uchun T1 qiymatini barcha mumkin bo'lgan ketma-ket 
algoritmlarni hisobga olgan holda aniqlash kerak. 
(samarali parallel 
algoritm bitta protsessorda bajarilganda eng yaxshi ketma-ketlik usuliga mos 
kelmasligi 
mumkin). 
Parallel 
algoritmning 
bajarilish 
vaqtini 
baholash 
xususiyatlarini tavsiflovchi nazariy bayonotlarni isbotsiz keltiramiz [18]. 
Teorema 1. Parallel algoritmning minimal mumkin bo'lgan bajarish vaqti 
algoritmning hisoblash sxemasining maksimal yo'lining uzunligi bilan belgilanadi, 
ya'ni. 
Bu erda n - algoritm sxemasidagi kirish cho'qqilari soni. 
Teorema 3. Amaldagi protsessorlar sonining kamayishi bilan algoritmni 
bajarish vaqti protsessorlar sonining kamayishiga mutanosib ravishda ortadi, ya'ni. 

---

182 
Teorema 4. Ishlatiladigan protsessorlarning istalgan soni 
uchun parallel algoritmning bajarilish vaqti uchun quyidagi yuqori chegara amal 
qiladi. 
Teorema 5. T∞ mumkin bo'lgan minimal vaqt bilan 
taqqoslanadigan algoritmning bajarilish vaqti p
∼
T1 / T∞ tartibli protsessorlar 
soniga erishish mumkin, ya'ni, 
Kamroq 
protsessorlar 
bilan algoritmni bajarish vaqti mavjud protsessorlar soni bilan eng yaxshi hisoblash 
vaqtidan 2 barobardan ortiq bo'lishi mumkin emas, ya'ni. 
Yuqoridagi bayonotlar parallel algoritmlarni shakllantirish qoidalari 
bo'yicha quyidagi tavsiyalarni berishga imkon beradi: 
1. algoritm uchun hisoblash sxemasini tanlashda diametri eng kichik diametrli 
grafikdan foydalanish kerak (1-teoremaga qarang); 
2. parallel bajarish uchun protsessorlarning tegishli soni p 
∼
T1 / T∞ qiymati bilan 
aniqlanadi (5-teoremaga qarang); 
3. Parallel algoritmning bajarilish vaqti yuqoridan 4 va 5 teoremalarda berilgan 
qiymatlar bilan chegaralanadi. Algoritmni parallel bajarish jadvalini shakllantirish 
bo'yicha tavsiyalar ishlab chiqish uchun biz 4-teoremaning isbotini keltiramiz. 
Teoremaning isboti 4. H∞ bajarilishning mumkin bo'lgan minimal vaqti T∞ga 
erishish jadvali bo'lsin. H∞ jadvalining bajarilishi t, 0 ≤ t ≤ T∞ har bir takrorlash 
uchun t takrorlash davomida bajarilgan amallar sonini nt bilan belgilaymiz. 
Algoritmning p protsessorlar yordamida bajarilish jadvalini quyidagicha qurish 
mumkin. Algoritmning bajarilishini T∞ bosqichlarga ajratamiz; Har bir qadamda t, 
H∞ jadvalining t iteratsiyasida bajarilgan barcha operatsiyalarni bajarish kerak. Bu 
operatsiyalar p protsessorlaridan foydalanganda ént / pù iteratsiyasidan ko'p 
bo'lmagan holda bajarilishi mumkin. Natijada Tp algoritmining bajarilish vaqtini 
quyidagicha baholash mumkin: 
Teoremaning 
isboti parallel algoritmni rejalashtirishning amaliy usulini beradi. Dastlab, jadval 
ishlatiladigan protsessorlarning cheklangan sonini hisobga olmasdan tuzilishi 
mumkin (parakompyuter uchun jadval). Keyin, teoremani chiqarish sxemasiga rioya