Matematik asoslar va raqamli modellashtirish usullari

KOMPYUTER TADQIQOTLARI VA MODELLASHTIRISH
Algoritmlar va dasturlarni parallelizatsiyalashga kirish
247
Agar sizda cheksiz imkoniyatlarga ega parallel hisoblash tizimi
mavjud bo'lsa, unda siz uni tashkil qilishingiz mumkin kanonik
parallel shaklga muvofiq algoritmni amalga oshirish. PRAM modelini ishlatganda, hisoblash vaqti Θ
(s), bu erda s — ovoz-
bin kanonik parallel shakli, sizga kerak bo'ladi
N ijrochilari, bu erda n
parallel qatlamlarning maksimal kengligi va siz
erishishingiz mumkin bo'lgan maksimal tezlashtirish bo'ladi
Θ
(n)
Θ
(n)
= Θ(
n
s
) bir marta.
Shuni ta'kidlash
kerakki, count tomonidan berilgan algoritmni amalga oshiradigan har qanday hisoblash tizimi grafigning qattiq parallel shakliga mos kelishi mumkin, aksincha,
har qanday qattiq parallel shakli uchun hisoblash tizimini qurish mumkin
, bu algoritmni vertikalar indeksiga to'liq mos keladi. Ushbu bayonotning asoslari
[Voevodin, Voevodin, 2002]da keltirilgan.

Ketma-ket dastur operatorlarining qatlam-parallel shakllari va qaramligining kamchiliklari
Va, aslida, nima uchun keyingi bo'limlarga muhtojmiz? Biz allaqachon bilib oldik va qaror qildik!
Dasturni amalga oshiruvchi algoritmning kanonik parallel shakli
bizga parallel hisoblash tizimida qanday maksimal tezlashtirishni olish mumkinligini aniqlash imkonini beradi
va shuning uchun qaror qabul qilish: oldindan ma'lum
bo'lgan tezlashtirish bilan eski dasturni parallelizatsiya qilish yoki yangi algoritmni tanlash kerak. Lekin! Har doim "lekin"bor. Bizning holatda
ikkita bor.
Birinchidan, kanonik parallel shakl
PRAM modelidagi mashinalarda cheksiz miqdorda resurslar mavjud bo'lganda faqat nazariy tezlashuvni baholashni ta'minlaydi.
PRAM modeliga bo'ysunadigan parallel kompyuterlar aslida mavjud emas, ayniqsa,
cheksiz resurslar mavjud emas. Modelni haqiqatga yaqinlashtirish uchun
siz hisob-kitoblarning tugunlarini qo'yishingiz kerak operatsiyalar vaqti (ehtimol, turli xil
gigantlar uchun farq qiladiva boshqalarda - ma'lumotlarni uzatish vaqti( agar bitta ijrochi ichida
— agar turli ijrochilar orasida boshqalar bo'lsa),
ijrochilarning cheklangan soni. Va endi bunday parametrlangan ustunda (yoki aksincha,grafikalar oilasida
, ijrochilar uchun operatsiyalarni taqsimlash muammosini hal qilishda)
eng yaxshi variantni qidirib, tezlashtirishni baholang. Bu muammo, afsuski, NP-to'liq.
PRAM mashinalarida resurslarni ko'rib chiqmasdan
parallelizm tushunchasi cheksiz parallelizm tushunchasi deb ataladi. Bir vaqtning o'zida, yarim parallel shakllar nazariyasi paydo
bo'lishi dasturlash dunyosida eforiyani keltirib chiqardi: aytaylik, hamma narsa aniq,
parallel, agar iloji bo'lsa, biz barcha qopqoqlarni hisoblaymiz va tashlaymiz! Bu erda emas edi! Shunga
qaramay, cheksiz parallelizm tushunchasi kam emas. Bu
parallel arxitekturada amalga oshirilganda algoritmdan nimani kutish mumkinligini tushunishga imkon beradi.
Ikkinchidan, algoritmni amalga oshiradigan dastur grafigini qurish har doim katta
mehnat zichligiga ega. Ning oddiy dasturiy ta'minot bo'lagini olib chiqaylik (FIG. 5) va biz uning uchun
algoritm grafigini quramiz, bu tsiklni oddiygina dastur yozuvini qisqartirish shakli deb hisoblaymiz. E'tibor bering,
agar qiymat bo'lsa
i keyin dasturda foydalanilmaydi, keyin ustundagi pastki chiziq bo'lishi mumkin
pastga tushing.
Ko'rib turganingizdek, eng oddiy tsikl uchun 4 sonidagi yinelemeler soni
juda katta. Va agar iteratsiya soni 2 000 000 bo'lsa? Va tsikllar soni
yuzga yaqin (haqiqiy vazifa uchun juda ko'p emas)? Ular suzib ketishdi. . . Tegishli grafik
katta kontsert zalini egallaydi, keyin siz bu zalda parallel
parallel shaklni qurishingiz va eng yuqori tezlashuvni aniqlashingiz mumkin.