Matematik asoslar va raqamli modellashtirish usullari

2010 Yil, T. 2, № 3, P. 231-272
246
Va Karpov
Y
Qattiqlashuv
1. Pustzadan yo'naltirilgan asiklik xachir
miqdori bilan qoplon
yuqori
n. Keyin grafaning barcha tepalari indeks bilan belgilanishi mumkin
1, 2, . . . , s, s
≤ n, shuning uchun
indeks bilan yuqoridan
i j indeksi bilan tepaga, keyin i
< j.
Dalil. Grafada o'zboshimchalik bilan sonli vertexlarni oling (albatta,
nol emas), unda hech qanday kamon yo'q. Biz ularni 1 indeks bilan belgilaymiz. Belgilangan tepaliklarni
grafadan olib tashlaymiz va ularning barchasi yoylari bilan birga. Qolgan ustunda
kirish qovurg'alari bo'lmagan bir nechta vertikalarni tanlang va ularni 2 indeks bilan belgilang.
Jarayonni davom ettirsak, biz ustundagi barcha ustunlarni qayta o'lchaymiz. Har bir qadamda biz kamida
bitta vertexni belgilaganimiz uchun maksimal yuqori ko'rsatkich
s oshib keta olmaydi cho'qqilar soni
ustunda
n.
Bunday belgilar bilan yo'naltirilgan asiklik grafigi odatda grafikning
parallel shakli deb ataladi. Yuqoridagilardan kelib chiqadiki, grafada qattiq parallel shakl
bitta bo'lishi mumkin (shakl. 4a, 4B). "Qattiq" so'zining nomi talab bilan bog'liq
i
< j uchun
indeks bilan tugun
i, undan yoy indeks j bilan tugunga chiqadi. Biroq
, "parallel" so'zining mavjudligi qo'shimcha muhokamani talab qiladi. Agar grafikning qattiq parallel shaklida ikkita
a va B tugunlari bir xil indeksga ega bo'lsa, demak, ustunda
a tugunidan b tuguniga olib boradigan yo'l yo'q va aksincha. Natijada, a va B tepaliklariga mos keladigan operatsiyalar
bir-biridan ma'lumotlarni amalga oshirishni talab qilmaydi va bo'lishi mumkin parallel
hisoblash tizimida bir vaqtning o'zida to'ldirilgan. Bu erda-parallelizatsiya!
Xuddi shu indekslarga ega bo'lgan qattiq parallel shakldagi tepaliklar
odatda parallel qatlam deb ataladi. Bir qavatning tugunlariga mos keladigan barcha operatsiyalar
bir vaqtning o'zida kompyuterda bir nechta ijrochilar tomonidan amalga oshirilishi mumkin.
Parallel qatlamdagi vertikalar soni odatda bu qatlamning kengligi va parallel shaklda parallel qatlamlarning soni parallel
shaklning chuqurligi deb ataladi.
Agar qattiq parallel shaklda indeks bilan yuqori bo'lsa
k, keyin hamma uzunligi
ushbu tepaga olib boradigan yo'llar, albatta, oshib ketmaydi
k. Maksimal uzunlikdagi grafaning yuqori
qismini juda muhim deb ataymiz. Grafikning ko'plab qat'iy parallel shakllari orasida
maksimal
qatlam kengligi va minimal chuqurligi bo'lgan yagona parallel shakl mavjud. Ushbu qat'iy parallel shakl uchun
indeks bilan tepaga olib boradigan muhim yo'lning uzunligi
k, har doim k ga teng
− 1. Bunday qattiq parallel shakl
odatda kanonik parallel shakl deb ataladi.
Y
Qattiqlashuv
2. Har qanday yo'naltirilgan asiklik multiforme uchun mavjud
yagona kanonik parallel shakl.
Dalil. Mavjudligini isbotlash uchun
biz kanonik parallel shaklni qurish algoritmini tasvirlaymiz va uning o'ziga xosligini qattiq isbotlash sizni
o'yin-kulgi uchun qoldiradi. Asiklik ustunida biz yoylarni o'z ichiga olmaydigan barcha vertikalarni tanlaymiz va
ularga 1 indeksini beramiz. Ushbu tepaliklarni va ulardan chiqadigan barcha yoylarni grafadan olib tashlang. Qolgan
ustunda, kiruvchi kamonlarga ega bo'lmagan barcha vertikalarni tanlang va ularni 2 indeksini belgilang.
Biz bu jarayonni grafikning barcha tepalari tugagunga qadar davom ettiramiz. Olingan qattiq parallel shaklda
indeks bilan yuqori
k indeksi algoritm k-m qadam tayinlangan edi. Bu k-m degan ma'noni anglatadi
qadam esa, arc bu yuqori uchun etakchi qolgan emas
k
− 1 qadam ular edi! Keyingi-
shunday qilib, bu tepaga olib boradigan ustundagi tanqidiy yo'lning uzunligi
k
− 1.
Ketma-ket kompyuter tizimida algoritmning bajarilishiga mos keladigan qattiq parallel shakl uchun
qatlamlarning kengligi har doim 1ga teng va parallel shaklning chuqurligi
n, bu erda n — ustunlarning soni.