Matematik asoslar va raqamli modellashtirish usullari

KOMPYUTER TADQIQOTLARI VA MODELLASHTIRISH
Algoritmlar va dasturlarni parallelizatsiyalashga kirish
249
Biz vaqtincha dasturlar va kompyuterlardan uzoqlashamiz va umuman ba'zi
faoliyatlar haqida gapiramiz. Shu bilan birga, faoliyat
muayyan maqsadga erishishga qaratilgan bir qator harakatlarning izchil bajarilishini tushunamiz.
Faoliyatning odatiy namunasi sendvich tayyorlash jarayonidir. Sandviç yaratish uchun zarur bo'lgan harakatlar ketma-ketligi (mutlaqo
to'g'ri emas) quyidagicha ta'riflanishi mumkin
.
1. Nonni kesib oling.
2. Sosisni kesib oling.
3. Yog 'bilan bo'yash (agar yog' etarli bo'lsa).
4. Kolibasni nonning bir bo'lagi ustiga qo'ying (yoki ehtimol
, kolbasa uchun non —
Matroskin mushuk Eduard Uspenskiyning mashhur kitobida ikkinchi variant
afzalroq deb hisoblaydi).
Faoliyatni tashkil etuvchi barcha harakatlar, biz hisoblanamizatomik yoki
bo'linmas, ya'ni. harakatni bajarishga kirishgan ijrochi,
harakat tugagunga qadar chalg'itishi va boshqa hech narsa qila olmaydi. Shu bilan birga, ijrochining harakatlari o'rtasida
partiyaga pul topish mumkin. Biz bor deylikbir p va Q faoliyati
ABC va efg atomik harakatlaridan tashkil topgan. Har ikkala faoliyat
ham bir xil ijrochini amalga oshirish uchun topshiriladi. Natijada nima bo'ladi?
Agar p va Q faoliyati qat'iy ravishda ketma-ket amalga oshirilsa, biz
quyidagi agregatlarni olamiz: ABCDEF. Aebcfg, aebfcg: lekin bizning taxminlarda
, ijrochi, atom operatsiya p faoliyatini
amalga oshirish, yanada atom operatsiya q faoliyatini amalga oshirish uchun o'tish mumkin, va hokazo. D. faoliyati
bir faoliyat ichida atom operatsiyalari tartibi saqlanadi esa, ularning turli galma bilan bo'linmas harakatlar
bo'linadi . . . , efgabc. Olingan hodisa ingliz tilida
"interleaving" deb nomlangan. Ikki faoliyatning pseudoparallel ijrosi ularning
bo'linmas operatsiyalarining o'zgarishiga olib kelganligi
sababli, pseudoparallel ijro etilishining natijasi ketma-ket bajarilish natijasidan farq qilishi mumkin.
Misol keltiring. Pust bizga ikkita p va Q faoliyati mavjud
atom operatsiyalari har biri:
P
Q
x
= 2
x
= 3
y
= x
− 1
y
= x + 1
Ularning ketma-ket ishlashi (PQ) bilan biz natijani qo'lga kiritamiz
x
= 3, y = 4. Ammo
faoliyatning atomik harakatlarining turli xil o'zgarishi bilan biz ham foyda olishimiz mumkin
(
x
= 2, y= 1), (x = 2, y = 3) va (x = 3, y = 2).
Biz birxil kirish ma'lumotlar to'plami uchun pseudoparallel ishlash har safar bir xil chiqish ma'lumotlarini beradi, agar faoliyati majmui (masalan, dasturlar) deterministik
, deb aytish
uchun boryapmiz. Aks holda, u deterministik emas. Yuqorida
qayd etilmagan dasturlarning namunasi keltirilgan. Ma'lumki, deterministik
faoliyat to'plami vaqtni ajratish rejimida qo'rqmasdan amalga oshirilishi mumkin.
Nerministik bo'lmagan to'plam uchun bunday ijro etish istalmagan. Natijalarni olishdan oldin
faoliyat majmui deterministik yoki yo'qligini aniqlash mumkinmi? Buning uchun
Bernsteinning etarli shartlari mavjud. Keling, ularni birgalikda o'zgaruvchan dasturlarga nisbatan bayon
qilaylik.
Dasturning kirish va chiqish o'zgaruvchilari to'plamlarini kiriting. Har bir atom
operatsiyalari uchun kirish va chiqish o'zgaruvchilari to'plamlari atomik bo'lgan o'zgaruvchilar to'plamidir