Matematik asoslar va raqamli modellashtirish usullari

2010 Yil, T. 2, № 3, P. 231-272
258
Va Karpov
Biz qaramlik masofasini hisoblaymiz, qaramlik turini va imkoniyatlarini aniqlaymizparal-
lelivaniya aylanishi.
Buni amalga oshirish uchun biz tsiklni yineleme maydoniga joylashtiramiz. Biz kengaytirish uchun etarli
bir nechta birinchi yinelemeler:
S
1
1
:
a[1] = d[1] + 5 * 1
S
1
2
:
c[1] = a[1] * 2
S
2
1
:
a[2] = d[2] + 5 * 2
S
2
2
:
c[2] = a[2] * 2
. . .
Ko'rib turganingizdek, operatorlar
S
1
1
va
S
1
2
shu qator elementi foydalaning
a
[1]. Qachon
bu shunday
S
1
1
bu qaramlikning manbai va
S
1
2
- oqim. Shunga ko'ra, k
= 1, λ = 1. Pisto-
yangi qaramliklar
D
= λ
− κ = −1. Operatorlar ketma-ket amalga oshirilganda, a[1] qiymati
birinchi bo'lib hisoblab chiqiladi va undan keyin foydalaniladi — bu oqim qaramligi. Biroq, barcha qaramlik
bir iteratsiya ichida joylashgan. Shuning uchun, har bir iteratsiya amalga oshirilishi mumkin uning
ijrochisida. Turli ijrochilarning ruxsat etilgan soni tsiklning yuqori chegarasiga to'g'ri keladi
u va mumkin bo'lgan tezlashtirish
≈ u. Agar biz S operatorlarini almashtirsak
1
va
S
2
tsiklning tanasida, qaramlik turi qarama-qarshilik bilan almashtiriladi, tsiklning qaramlik masofasi
bir xil bo'ladi, shuningdek, parallelizatsiya ehtimoli.
Haqida
UMUMIY TASDIQLASH
3. Agar qaramlik masofa
D
= 0, keyin
tsiklning tana operatorlari o'rtasidagi bog'liqlik turi umuman noaniq.
Har bir iteratsiya alohida ijrochi tomonidan amalga oshirilishi uchun tsikl bo'lishi mumkin.
Ish
D
= 0 odatda rus tilida " zavi-
süneklik, tsikldan mustaqil"
(loop independent dependence). Ish
D
0 deyiladi
davr bilan bog'liq giyohvandlik (loop carried dependence).
Shuni ta'kidlash kerakki, har doim ham tsiklning masofasi doimiy emas, ammo
shunga qaramay, bunday hollarda bu tushunchani parallellik davrlarini tahlil qilish uchun ishlatish mumkin
. Misol uchun, tsikl uchun
do i = 1, u
S
1
:
a[i] = d[i] + 5 * i
S
2
:
c[i] = a[2*i] * 2
enddo
f
(i) = i va g (i) = 2
· i.
F(2) = (1), f (4) = g(2), f(6) = g(3) va boshqalarni ko'rish oson.-
lekin buni aniqlash mumkin —
D
= ?. Birinchi tenglik uchun D =
-1, ikkinchisi-D = -2,
uchinchi uchun —
D
=
−3. Biroq, bu qiymatlarning barchasi noldan kam, shuning uchun barcha qaramliklar
qarama-qarshiliklardir va shuning uchun kirishning kerakli takrorlanishi
bilan tsiklni yinelemelerle parallellashtirish mumkin.
Ko'pincha vaziyatlar bor, qaysi bog'liqliklar bir emas elementlar paydo
, lekin bir necha tillo. Keyinchalik parallelizatsiya qilish imkoniyati to'g'risidagi qaror
barcha qaramlik majmuasini tahlil qilish natijalari bilan amalga oshiriladi.