Matematik asoslar va raqamli modellashtirish usullari

to'g'ridan-to'g'ri dinamik ravishda bir-birini ta'qib qilib, bajarildi
KOMPYUTER TADQIQOTLARI VA MODELLASHTIRISH
Algoritmlar va dasturlarni parallelizatsiyalashga kirish
251
* v(S1) va W(S2) kesishishi bo'sh
• * R(S1) bilan V(S2)
kesishishi bo'sh• * R(S1) va W(S2) kesishishi bo'sh,
keyin operatorlar
S
1
va
S
2
turli ijrochilar tomonidan bir vaqtning o'zida bajarilishi mumkin
parallel hisoblash tizimi.
Afsuski, Bernsteinning shartlari etarli, ammo zarur emas va
faqat bir-birini ta'qib qilayotgan operatorlar faqat kirish ma'lumotlarini kesib o'tishlari mumkinligini
ko'rsatadi. Shunday qilib, haqiqiy ketma-ket dasturlarda deyarli yo'q.
Keling, ikkita operator uchun nima sodir bo'lishini ko'rib chiqaylik
S
1
va
S
2
, dinamik ravishda bir-birini ta'qib qilib, Bernsteinning shartlari buziladi
(to'g'ridan-to'g'ri ta'qib qilish bu erda rol o'ynaydi). Bu erda biz [Jordan,
Alaghband, 2003] materialini taqdim etamiz.
Birinchi shartni buzishdan boshlaylik. Shunday qilib, ikkita operator (yoki bloklar) uchun bo'sh joy
operatorlar)
S
1
va
S
2
izchil dasturi, dinamik bir-birini ta'qib,
amalga oshirildi:
* o'tish W(S
1
) va W(
S
2
) bo'sh emas,
* o'tish W(S
1
) r bilan(
S
2
) bo'sh,
• R(S) kesishishi
1
) va W(
S
2
) bo'sh.
Misol ko'rib chiqaylik:
S
1
:
x = 2 * y + z;
S
2
:
x = a
−
b;
Ko'p hollarda, ketma-ket dasturi (va men, biz
amalga dasturi tushunchalar emas, balki boshlang'ich matnlar ustida ish olib bormoqda, deb eslatib o'tamiz), bu voqea
xotira tejash bilan ham bog'liq, turli ma'lumotlar bir xil maydon beriladi qachonpamyati, yoki
beparvolik bilan (yomon so'z aytish emas) dasturchilar. O'zgaruvchining oddiy nomini o'zgartirish "
x»
operatorda
S
2
rivojlanayotgan savollarni yo'q qiladi. Shunga qaramay, dastlabki shaklda operatorlar
bir-biriga bog'liq bo'lib, ushbu turdagi qaramlik biz chiqish ma'lumotlariga (
chiqish qaramligi) qaramlik deb ataymiz. Odatda bunday qaramlik quyidagi kabi yoziladi
S
1
δ
o
S
2
va grafik jihatdan
quyidagicha tasvirlangan (FIG. 6).
Shakl. 6. Chiqish ma'lumotlariga bog'liq
Odatda, chiqish ma'lumotlariga qaramlik parallelizatsiyaga to'sqinlik qilmaydi.
O'zgaruvchilarni qayta nomlang va har ikkala operator ham to'g'ridan-to'g'ri birma
-bir bajarilsa,sog'liq uchun parallel!
Bernsteinning uchinchi sharti yo'q. Ikkita operator (yoki operator bloklari) uchun-
dom)
S
1
va
S
2
izchil dasturi, izchil bir-birini ta'qib, amalga
quyidagilar:
* o'tish W(S
1
) va W(
S
2
) bo'sh,
* o'tish W(S
1
) r bilan(
S
2
) bo'sh,
• R(S) kesishishi
1
) va W(
S
2
) bo'sh emas.
Misol ko'rib chiqaylik:
S
1
:
x = 2 * y + z;
S
2
:
y = a
−
b;