Matematik asoslar va raqamli modellashtirish usullari

2010 Yil, T. 2, № 3, P. 231-272
252
Va Karpov
O'zgaruvchan "
y " ketma-ket dasturda birinchi bo'lib hisoblash uchun ishlatiladi
operatorda
S
1
, keyin operatorda bekor qilinadi
S
2
. Agar seni olgan ijrochi-
operatorni bajarish
S
1
, qiymati foydalanadi "
y " bu qiymatni bekor qilishdan oldin
ijrochi
S
2
, keyin parallelizatsiya xavfsiz. Keling, shunday
qilaylik. Tegishli operatorlarni amalga oshirishdan oldin, ushbu
o'zgarishning qiymatini mahalliy xotiraga ko'chiramiz ijro etuvchilar va lishpotom ularni bajarishga ruxsat beradioperatsiyalar. Keyin
hisob-kitoblar to'g'ri bo'ladi. Operatorlarga qaramlikning bu shakli antidependence
(antidependence) deb ataladi. Uning yozuvining odatiy shakli quyidagicha ko'rinadi
S
1
δ
−1
S
2
, va grafik vakillik
bu shaklga ega (shakl. 7):
Shakl. 7. Qarama-qarshilik
Va nihoyat, qolganbir ko'rish Bernsteinning ikkinchi shartining qulashi, ya'ni vaziyat,
ikki operator (yoki operator bloklari)uchun
S
1
va
S
2
izchil dastur,
dinamik ravishda bir-birini ta'qib qilib, quyidagilar amalga oshirildi:
* o'tish W(S
1
) va W(
S
2
) bo'sh,
* o'tish W(S
1
) r bilan(
S
2
) bo'sh emas,
• R(S) kesishishi
1
) va W(
S
2
) bo'sh.
Misol ko'rib chiqaylik:
S
1
:
x = 2 * y + z
;
S
2
:
y = a
−
x;
Bu parallelizatsiya nuqtai nazaridan eng qiyin holat. Ope ning natijasi-
ratora
S
1
operatorni bajarish uchun ishlatiladi
S
2
. Agar operatorlar
bir-birini dinamik ravishda ta'qib qilsalar, ularning parallelizatsiyasi mumkin emas. Ushbu turdagi qaramlik
oqim qaramligi yoki haqiqiy qaramlik deb ataladi. Uni yozib olish odat tusiga kiradi
S
1
δ
S
2
va tasvir (shakl. 8).
Shakl. 8. Oqim yoki haqiqiy, qaramlik
To'rtta dasturiy ta'minot qismiga qarab, kiritilgan belgilarni ishlatish
yuqorida keltirilgan operatorlar grafik jihatdan quyidagi tarzda tasvirlanishi mumkin (shakl. 9).
Shakl. 9. Dasturiy qismdagi qaramliklarning grafik ko'rinishi
Albatta, imkoniyatlarni ta'sir qiladigan qaramlik ketma-ket
dasturlarni parallel qilish uchta qaramlik bilan iste'mol qilinmaydi. Dasturda
turli xil kirish moslamalari uchun boshqa operatorlarning dinamik tartibini o'zgartiradigan shartli operatorlar bo'lishi mumkin
. Misol sifatida
S
1
:
x = cos(z);
if (x > 0) {
S
2
:
a = b + c;