Matematik asoslar va raqamli modellashtirish usullari

2010 Yil, T. 2, № 3, P. 231-272
248
Va Karpov
Shakl. 5. Dastur qismiga mos keladigan algoritmni hisoblash
Haqiqiy dasturni tahlil
qilish ushbu dastur tomonidan amalga oshiriladigan algoritmning kanonik parallel shaklini qurishga oqilona kamaytirilmasligi aniq. Algoritm grafigi
juda past darajadagi tushunchalardan foydalanadi-ma'lumotlar bo'yicha amalga oshiriladigan alohida operatsiyalar yoki
odatdagidek, algoritmni hisoblash operatsiyalari yordamida dekompozitsiya qilish juda
katta granularlikka ega.

Shunday qilib, decomposition darajasini pasaytirish, (masalan, individual operatorlari yoki ularning bloklari) urovengrupp operatsiyalar— bu harakat maqbul miqdorda sarf, parallel uchun tahlil dasturi tahlil qilish uchun, biz

yuqori darajada operatsiyalar darajada tahlil o'tkazish kerak
.
Biz allaqachon oldingi ma'ruzada shunga o'xshash biror narsa
qildik, chunki dasturda kichik shartli filiallar bilan bog'liq grafning noaniqligi yo'q
qilindi, operatsiyalarni kengaytirish orqali (shakl. 3a va 3b).
Bizning dasturimiz operatorlar to'plamidan iborat deb hisoblaymiz
S
1
, S
2
, . . . , S
k
,
dastur matnida muayyan tartibda joylashtirilgan. Misol uchun,
S
1
:
a = 2*b + 15;
S
2
:
b = a + 10*x;
S
3
:
d = b
−
c;
S
4
:
d = a / c;
Dastur matnidagi operatorlarning joylashuvi ularning statik tartibini belgilaydi. Biz har doim
dasturning asl matniga qarab,matndagi ikkita operatordan qaysi biri
yuqorida va qaysi biri past ekanligini aytishimiz mumkin. Biroq operatorlarning statik tartibi har doim ularning
ijro etilishi tartibiga mos kelmaydi. Misol uchun, keyingi dasturiy qism uchun
S
1
:
goto
S
4
;
S
2
:
c = a + 10*b;
S
3
:
goto
S
6
;
S
4
:
d = b
−
c;
S
5
:
goto
S
2
;
S
6
:
b = a / d;
operatorlarning statik tartibi"
S
1
, S
2
, S
3
, S
4
, S
5
, S
6
"va ularning ketma-ketligi tartibi
dasturda bajarish — "
S
1
, S
4
, S
5
, S
2
, S
3
, S
6
». Dasturda operatorlarni bajarish tartibi
(berilgan dastlabki ma'lumotlar bilan) odatda operatorlarning dinamik tartibi deb ataladi. Bizning
asosiy vazifamiz-ketma-ket
dasturda qaysi operatorlarni parallel hisoblash tizimida turli ijrochilar tomonidan amalga oshirilishi mumkinligini
va qanday tezlashtirishni olish mumkinligini aniqlashdir.
Ushbu muammoni hal qilishni boshlashdan oldin, ba'zi ma'lumotlarni eslaylik,
odatda operatsion tizimlar [Karpov, Skates, 2005] kurslarida bayon etilgan.