Matematik asoslar va raqamli modellashtirish usullari

KOMPYUTER TADQIQOTLARI VA MODELLASHTIRISH
Algoritmlar va dasturlarni parallelizatsiyalashga kirish
245
Agar shartli filiallar ostida dasturda oz sonli
operatsiyalar mavjud bo'lsa (shakl. 3a), keyin biz bu operatsiyalarni kengaytirish mumkin(fig. 3b) va deterministik
uchun algoritm kamaytirish.
Shakl. 3. Shartli operatorlar
Shartli operatorlar ostida katta deterministik joylar mavjud bo'lsa
dasturlar, biz ushbu sohalarga murojaat qilamiz.
Shunday qilib, biz faqat deterministik grafikalar haqida gapiramiz.
Murakkab grafik algoritmlarini dasturiy ilovalar bilan bir
xil kompyuter tizimida ham hisoblash turli tartibda amalga oshirilishi mumkin. Biz
yozishni kafolatlaymizmi? takrorlash uchun grafik shaklida algoritm
bunday hollarda tatov? Keling
o'tish: saytda harakatlanish, qidiruv
Taklif 1. "Operatsiyani bajarishda yaxlitlash xatolar
faqat kirish argumentlari bilan belgilanadi. Keyin bir xil kirish ma'lumotlari
bilan operatsiyalarda bir xil qisman tartibga mos keladigan algoritmning barcha ilovalari
bir xil natijani, shu jumladan yaxlitlash xatolarining butun majmuasini beradi.
Ushbu bayonotning isboti qiyin emas va men uni o'z-o'zini boshqaruvchingiz uchun qoldiraman-
ish.
Endi grafiklardan foydalanib, biz aniq yozishimiz mumkindeterministik algoritmlar. Lekin
bularning barchasi parallelizatsiya bilan bog'liqmi?
Aytaylik, bizda algoritmning aniq grafigi bor va uning dasturini
amalga oshirish bitta ijrochi (bitta protsessor va bitta yadro) bilan kompyuterda amalga oshiriladi.
Biz ma'lumotlarni aylantirish va ularning i / o bir vaqtning o'zida amalga oshirilishi mumkin emas, deb taxmin qilamiz.
Biz 1dan maksimal qiymatgacha kompyuterda tegishli operatsiyalarni bajarish tartibiga mos keladigan tartibda ustunlarni sanaymiz
. Keyin barcha tugunlar o'zlarining noyob
raqamlarini oladi, ularning qiymatlari 1dan tortib to
n, bu erda n — ustundagi vertices soni. Qachon
bu raqam bilan tugun bo'lsa
men yoyni j raqami bilan tugunga olib boraman, keyin i
< j. Modelda ishlashda
Bunday algoritmni ketma-ket bajarish vaqti bo'ladi Θ
(n). Raqamlash usuli
noyob emas va dastur qaysi dasturlash tiliga yozilganligiga bog'liq,
algoritmning grafigini amalga oshiradi va qaysi hisoblash tizimi amalga oshiriladi (shakl. 4a, 4B).
Shakl. 4. Xuddi shu ustunning vertikallarini raqamlashning turli xil variantlari
O'zboshimchalik bilan yo'naltirilgan asiklik grafikalar uchun quyidagi tasdiqlar to'g'ri-
Daniya.