Matematik asoslar va raqamli modellashtirish usullari

2010 Yil, T. 2, № 3, P. 231-272
250
Va Karpov
operatsiya o'qiydi va yozadi. R(P) dasturining kirish o'zgaruvchilari to'plami ("read" so'zidan R)
barcha ajralmas harakatlar uchun kirish o'zgaruvchilari to'plamlarini birlashtirish. Xuddi
shu tarzda, W(P) (W "write" so'zidan) dasturning chiqish o'zgaruvchilari to'plami
barcha bo'linmas harakatlar uchun chiqish o'zgaruvchilari to'plamlarini birlashtiradi. Masalan, P dasturi uchun
x = u + v
y = x * w
R(P)ni oling
=
{u, v, x, w}, W(P) = {x, y}. Eslatma, o'zgaruvchan x r mavjud (P),
shunday qilib, W (P) da.
Endi Bernstaynning shartlarini bildiramiz.
Agar ikkita faoliyat ma'lumotlari uchun P va Q bo'lsa
* v(P) va W (Q) kesishishi bo'sh
• * R(Q) bilan V(P)
kesishishi bo'sh• * R(P) va W (Q) kesishishi bo'sh,
keyin p va Q ning bajarilishi deterministik.
Agar ushbu shartlar bajarilmasa, p va Q
ning psevdo-parallel bajarilishi deterministik bo'lishi mumkin yoki mavjud bo'lmasligi mumkin. Ikki faoliyatning holati tabiiy ravishda
ularning soniga umumlashtiriladi.
Endi ketma-ket dasturlarning parallelligi uchun tahlilga qaytishimiz mumkin,
bir qator operatorlardan (yoki ularning bloklaridan) iborat.
Bernsteinning shartlari parallel hisoblash tizimidagi bir ketma-ket dastur operatorlari uchun to'g'ri yoki yo'qligini aniqlashimiz kerak bo'lgan birinchi narsa
. P
va Q faoliyati sifatida ikkita ketma-ket dastur operatori faoliyat yuritsin
S
1
va
S
2
.
Agar ular uchun Bernsteinning shartlari bajarilsa, u holda pseudoparallelno (agar bitta
ijrochi bo'lsa) — vaqtni ajratish rejimida — ular deterministik faoliyat to'plamini beradi.
Ko'rinib turibdiki, bir nechta ijrochilar
mavjud bo'lsa, deterministik bo'lishi kerak. Quyidagi misolni ko'rib chiqaylik. Voidoperatorlar
S
1
va
S
2
dinamik ravishda do'st oldida
do'stingizga va ko'rinishga ega:
S
1
:
x = 2 * y + z;
S
2
:
d = a
−
b;
Operatorlarning kirish va chiqish ma'lumotlari
S
1
va
S
2
ular umuman kesishmaydi. Ular mumkin
ijro etingpsevdoparallel
ammo ular deterministik faoliyat to'plamini tashkil qiladi. Lekin
parallellikni amalga oshirish mumkinmi?
lekin bir dastur doirasida? Bir
qarashda-hech narsa to'sqinlik qilmaydi! Biroq, operatorlarni amalga oshirishning qat'iy dinamik tartibi
shunday ko'rinadi:
S
1
:
x = 2 * y + z;
S
3/2
:
a = x;
S
2
:
d = a
−
b;
Va hammasi! Agar bu qism uchun qurilgan bo'lsa katta algoritm grafigi, keyin bilib oling-
bu nima
S
2
hisoblashdan oldin bajarish mumkin emas
S
3/2
va bu, o'z navbatida, ijro etishdan oldin
S
1
.
Hech qanday parallellik yo'q. . .
Bernstein shartlarini shakllantirishda bir vaqtning o'zida amalga oshirilishi mumkinligini tahlil qilish-
operatorlar nia
S
1
va
S
2
parallel kompyuter kompleksida ketma-ket dastur
tushuntirish kerak:
Agar ikkita operator (yoki operator bloklari)
S
1
va
S
2
izchil dastur,