Lim,fan va innovatsiyalar vazirligi muhammad al-xorazimiy nomidagi toshkent axborot texnologiyalari universiteti

OLIY TA’LIM,FAN VA INNOVATSIYALAR VAZIRLIGI


MUHAMMAD AL-XORAZIMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

“Kompyuter arxitekturasi” fanidan

Mustaqil ish

Mavzu: Operatsiyalar-operandlar” grafli hisoblash modeli

Bajardi: 042-20 guruh talabasi

_________________________
Tekshirdi: _________________

Toshkent 2023

Reja:

1. 
   Hisoblash modeli “Operatsiyalar-operandlar” grafigi sifatida
   
2. 
   Parallel algoritmni bajarish sxemasi
   
3. 
   Parallel algoritmni bajarish vaqtini baholash
   

Kirish

Parallellik samaradorligini tahlil qilish murakkab tadqiqot va muhandislik muammolarini hal qilish uchun parallel algoritmlarni ishlab chiqishda hal qiluvchi nuqtadir. Parallellik samaradorligini tahlil qilish, qoida tariqasida, hisoblash jarayonining tezlashishini baholash (muammoni hal qilish uchun zarur bo'lgan vaqtni qisqartirish). Tezlikni baholashni shakllantirish tanlangan hisoblash algoritmi uchun amalga oshirilishi mumkin (muayyan algoritmni parallellashtirish samaradorligini baholash). Yana bir muhim yondashuv ma'lum bir turdagi muammoni hal qilish uchun maksimal tezlikni baholashni qurish bo'lishi mumkin (muammoni hal qilish uchun eng yaxshi parallel yondashuvning samaradorligini baholash).

Ushbu mustaqil ishda biz hisoblash modelini "operatsiyalar-operandlar" grafigi sifatida tasvirlab beramiz, undan masalani yechishning tanlangan algoritmlarida mavjud ma'lumotlarga bog'liqliklarni tavsiflash uchun foydalanish mumkin. Shuningdek, biz mavjud hisoblash modellarini tahlil qilish natijasida olinishi mumkin bo'lgan maksimal parallellik samaradorligini baholaymiz. Bu yerda bayon qilingan nazariyaning amaliy qo‘llanilishi o‘quv materiallarining uchinchi qismida keltirilgan.

1. 
   Hisoblash modeli “Operatsiyalar-operandlar” grafigi sifatida
   

Model "operatsiyalar-operandlar" grafigi muammolarni hal qilishning tanlangan algoritmlarida ma'lumotlarga bog'liqliklarni tavsiflash uchun ishlatilishi mumkin (masalan, Bertsekas va Tsitsiklis (1989) ga qarang). Muammoni soddalashtirish uchun biz modelni qurishda har qanday hisoblash operatsiyalarini bajarish davrlari bir xil bo'ladi va 1 ga teng bo'ladi (ba'zi o'lchov birliklarida). Bundan tashqari, hisoblash protsessorlari o'rtasida ma'lumotlarni uzatish hech qanday vaqt sarflamasdan bir zumda amalga oshiriladi deb taxmin qilamiz (masalan, parallel hisoblash tizimida umumiy umumiy xotira mavjud bo'lsa, bu to'g'ri bo'lishi mumkin). Parallel algoritm aloqa murakkabligini tahlil qilish keyingi bobda amalga oshiriladi.

O'rganilayotgan hisoblash muammosini hal qilish algoritmida bajariladigan operatsiyalar to'plamini va operatsiyalar orasida mavjud bo'lgan axborotga bog'liqliklarni asiklik yo'naltirilgan grafik sifatida tasvirlaymiz.
G = (V , R) ,

1-rasm. "Amallar-operandlar" grafigi ko'rinishidagi hisoblash modeli namunasi
Bu yerda V = {1,..., V } - bajarilayotgan algoritm amallarini ifodalovchi grafik uchlari to‘plami va R.grafik yoylar to‘plamidir (bu holda r = (i, j) j operatsiyasi natijadan foydalansagina grafikga tegishli bo‘ladi.i) operatsiyasini bajarish orqali olingan. Buni ko'rsatish uchun 1-rasmda to'rtburchakning ikki qarama-qarshi burchagining koordinatalari bilan belgilangan maydonini hisoblash uchun ishlatiladigan algoritm grafigi ko'rsatilgan. Berilgan misoldan ko'rinib turibdiki, tanlangan muammoni hal qilish algoritmini amalga oshirish uchun turli xil hisoblash sxemalaridan foydalanish va mos keladigan turli xil hisoblash modellarini qurish mumkin. Keyinchalik ko'rsatilishicha, turli xil hisoblash sxemalari parallellashtirishning turli imkoniyatlariga ega. Shunday qilib, hisoblash modelini qurishda hisoblash sxemasi algoritmini parallel bajarish uchun eng mosini tanlash vazifasi qo'yilishi mumkin.
Ko'rib chiqilayotgan algoritmning hisoblash modelida kiruvchi yoylarsiz cho'qqilar kiritish operatsiyalarini belgilash uchun ishlatilishi mumkin va chiqish yoylari bo'lmagan cho'qqi chiqish uchun ishlatilishi mumkin.operatsiyalar. Kiritish cho’qqilari bo’lmagan grafik cho’qqilar to’plamini deb, grafikning diametrini (maksimal yo’l uzunligini) d (G) deb belgilaymiz.

2. 
   Parallel algoritmni bajarish sxemasi
   

Tanlangan hisoblash sxemasida ular orasida yo‘llari bo‘lmagan algoritm operatsiyalari parallel ravishda bajarilishi mumkin (masalan, 1-rasmda ko‘rsatilgan hisoblash sxemasi uchun, avvalo, barcha ko‘paytirish amallari parallel ravishda bajarilishi mumkin, keyin esa birinchisi). ikkita ayirish amali parallel ravishda amalga oshirilishi mumkin). Algoritmning parallel bajarilishini tavsiflashning mumkin bo'lgan usuli quyida keltirilgan (masalan, Bertsekas va Tsitsiklis (1989) ga qarang).Algoritmni bajarish uchun protsessorlar soni p bo'lsin. Keyin hisob-kitoblarni parallel ravishda bajarish to'plamni (jadvalni) belgilash uchun zarur.

har bir operatsiya uchun qaerda i ϵV protsessor Pi soni operatsiya va operatsiyani bajarish uchun ishlatiladi boshlanish vaqti ti beriladi. Jadvalni amalga oshirish uchun quyidagi talablarga javob berish kerak. to'plamini belgilash:

1. 
   ya'ni bir xil protsessor turli operatsiyalarga tayinlanmasligi kerak bir vaqtning o'zida,
   
2. 
   ya'ni barcha kerakli ma'lumotlar operatsiyadan oldin hisoblangan bo'lishi kerak ijrosi boshlanadi.
   

3. 
   Parallel algoritmni bajarish vaqtini baholash
   

jadvali bilan birgalikda G algoritmining hisoblash sxemasi sifatida qaralishi mumkin yordamida bajarilgan parallel algoritm Ap (G, ) modeli.p protsessorlari. Parallel vaqt algoritmning bajarilishi jadvalda ishlatiladigan maksimal vaqt qiymati bilan belgilanadi

Tanlangan hisoblash sxemasi uchun algoritmni bajarishning minimal vaqtini ta'minlaydigan jadvaldan foydalanish maqsadga muvofiqdir.

Bajarish vaqtini qisqartirish eng yaxshi hisoblash sxemasini o'rnatish orqali ta'minlanishi mumkin

Tahminlar Tp (G, H p ),Tp (G) va Tp algoritmni parallel bajarishda vaqt mezoni sifatida foydalanish mumkin.Maksimal mumkin bo'lgan parallellikni tahlil qilishdan tashqari, algoritmning eng tez bajarilishini baholashni ham belgilash mumkin.

taxmin qilingan bo'lsa, parallel algoritm bajarilishining minimal mumkin bo'lgan vaqti sifatida ko'rib chiqilishi mumkin.Cheksiz miqdordagi protsessorlardan foydalaniladi (parallel hisoblashlarni nazariy tahlil qilishda odatda parakompyuter deb ataladigan cheksiz sonli protsessorli kompyuter tizimi tushunchasi keng qo'llaniladi).
Tahmini T1 algoritmi, agar bitta protsessor ishlatilsa, algoritmning bajarilish vaqtini belgilaydi va shuning uchun bajarilishini ifodalaydi.Muammoni hal qilish algoritmining ketma-ket versiyasi vaqti. Bunday smeta tuzish parallel algoritmlarni tahlil qilishda muhim vazifadir, chunki parallellikdan foydalanish ta'sirini baholash kerak (muammoni hal qilishda tezlikni oshirish). Bundan ko'rinib turibdiki

Bu erda , allaqachon aniqlanganidek, G hisoblash sxemasining uchlari soni bo'lmagan holda kirish uchlari. Shuni ta'kidlash kerakki, agar T1 bahosini aniqlashda biz faqat bitta tanlangan muammoni hal qilish algoritmini ko'rib chiqish bilan cheklansak va qiymatdan foydalansak.