Matematik asoslar va raqamli modellashtirish usullari

axborot:
Teorema.
Izchil operatorlari dinamik tartibda har qanday o'zgarish
ma'lumotlarga ko'ra, barcha bog'liqliklarni saqlaydigan dastur dastur algoritmining grafigini o'zgartirmaydi.
Bunday konvertatsiya dasturda xotiraga kirishning barcha operatsiyalari tartibini saqlab qoladi
va xotiradagi yozuvlar bundan mustasno, mavjud bo'lishi mumkin, i / u operatsiyalari.
Mavzu ikkinchi. Nima uchun tsikllarda haqiqiy bog'liqliklar mavjud bo'lsa, biz
dasturni parallelizatsiya qilishning mumkin emasligi haqida emas, balki bunday parallelizmning lisho muammolari haqida gapirmayapmiz
? Qisman javob yuqorida berilgan. Ko'rib chiqilgan uch o'lchamli tsiklda
haqiqiy qaramlik mavjud edi, ammo parallelizatsiya nazariyasiga ko'ra mumkin edi.
Biroq, tsikllarda parallelizatsiya nazariyasi
qabul qilinishi mumkin bo'lmagan yoki katta xarajatlar bilan bog'liq bo'lgan holatlar mavjud, ammo ekvivalent
transformatsiyalar yordamida biz bu parallellikni samarali amalga oshirishimiz mumkin.
P
Rimer
13. Misol 9 dan bir tsiklni ko'rib chiqing.
do i = 1,
u
1
do j = 1,
u
2
S:
a[i, j] = a[i-1, j-1] * 2
enddo
enddo
Uni tahlil qilsak, biz
ichki tsiklni faqat oxirida to'siqni sinxronizatsiya qilish bilan parallellashtirish mumkin degan xulosaga keldik. Shuni esda tutingki
, dasturlardagi tsikl operatorlari mavjud faqat ro'yxatga olish shaklini qisqartirish. Biz tsikllarni kengaytiramiz va
qator elementlari orasidagi bog'liqliklarni tasvirlaymiz
a tekislikda
(i, j) (shakl. 10).
Shakl. 10. Misol uchun qator elementlari orasidagi bog'liqlik 13
2010 Yil, T. 2, № 3, P. 231-272
268
Va Karpov
Ko'rib turganingizdek, array elementlari orasidagi ma'lumotlarga bog'liqliklar
ushbu grafik ko'rinishning diagonallarida joylashgan. Bunday holda, har
bir diagonali bo'lishi mumkin boshqa diagonaldan qat'i nazar, ijrochiga to'ldiriladi. Shunday qilib
, indeks o'zgarmaydigan tsikllarni (algoritm grafigini saqlab qolish) mos ravishda almashtirish orqali biz
ketma-ket kodning bir qismini parallellashtira olamiz va hatto yaxshi miyalar
bilan ijrochilarning to'g'ri yuklanishini ta'minlay olamiz.
Tsiklda haqiqiy bog'liqlik mavjud bo'lganda parallelizatsiya qilishning bu usuli, albatta,
nostandart emas. Biroq, uning mohiyati loop carried dependence
-ni loopdan mustaqil ravishda qaramlikka aylantirishdir.
Shunga o'xshash, ammo standart usullar to'plami mavjud. Oddiylik uchun biz bir
o'lchamli tsikllarda rematrivat bo'lamiz.