Matematik asoslar va raqamli modellashtirish usullari

KOMPYUTER TADQIQOTLARI VA MODELLASHTIRISH
Algoritmlar va dasturlarni parallelizatsiyalashga kirish
257
Ko'rib turganingizdek, operatorlar
S
1
1
va
S
2
2
shu qator elementi foydalaning
a
[1]. Qachon
bu shunday
S
1
1
bu qaramlikning manbai va
S
2
2
- oqim. Shunga ko'ra, k
= 1, λ = 2. Pisto-
yangi qaramliklar
D
= λ
− κ = 1. Operatorlar ketma-ket amalga oshirilganda, a[1] qiymati
birinchi bo'lib o'zgaradi va undan keyin ishlatiladi-bu haqiqiy qaramlikdir. Iteratsiyalarni
parallel ravishda bajarish mumkin emas!
Lekin aylanish jarayonida haqiqiy bog'liqlik mavjud bo'lganda parallelizatsiya har doim ham taqiqlanganmi?
Keling, ko'rib chiqaylik
P
Rimer
3. Bo'sh davr
do i = 1, u
S
1
:
a[i] = d[i] + 5 * i
S
2
:
c[i] = a[i-2] * 2
enddo
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[0] * 2
S
3
1
:
a[3] = d[3] + 5 * 3
S
3
2
:
c[3] = a[1] * 2
. . .
Ko'rib turganingizdek, operatorlar
S
1
1
va
S
3
2
shu qator elementi foydalaning
a
[1]. Qachon
bu shunday
S
1
1
bu qaramlikning manbai va
S
3
2
- oqim. Shunga ko'ra, k
= 1, λ = 3. Pisto-
yangi qaramliklar
D
= κ
− λ = 2. Operatorlar ketma-ket amalga oshirilganda, a[1] qiymati
birinchi bo'lib o'zgaradi va undan keyin ishlatiladi-bu haqiqiy qaramlikdir. Lekin!!!
1-iteratsiya bo'yicha hisoblangan qiymat faqat 3-iteratsiya uchun hisoblash uchun ishlatiladi.
3-iteratsiya bo'yicha hisoblangan qiymat faqat 5-iteratsiya va boshqalarda qo'llaniladi
. 2-x ijrochilariga parallel ravishda yinelemalarni bajarish mumkin
,ulardan biri faqat g'alati yinelemalarni amalga oshiradi, ikkinchisi esa hatto!
Haqida
UMUMIY TASDIQLASH
2. Agar qaramlik masofa
D
> 0, keyin operatorlar o'rtasida
tsiklning tanasi oqim qaramligi mavjud. Qachon
D
> 1 davr bo'lishi mumkinbarallen emas
ko'proq
D ijrochilari.
O'rganilmagan holda, faqat bitta ish bor edi
D
= 0.
P
Rimer
4. Bo'sh davr
do i = 1, u
S
1
:
a[i] = d[i] + 5 * i
S
2
:
c[i] = a[i] * 2
enddo