Kafedrasi kompyuter arxitekturasi moduli bo‘yicha

3 Amaliy mashg’ulot:
Mavzu: “Operatsiyalar-operandalar” xisoblashlar modeli
Ishdan maqsad: "Operand operatsiyalari" grafigi ko'rinishidagi hisoblash modeli o’rganish.
Nazariy qism
Muammolarni hal qilish uchun tanlangan algoritmlardagi mavjud ma'lumotlarga bog'liqlikni tavsiflash uchun "operatsiyalar-operandlar" grafigi ko'rinishidagi modeldan foydalanish mumkin (parallel hisoblashlarni modellashtirish bo'yicha qo'shimcha ma'lumot olish mumkin). Taqdim etilgan materialning murakkabligini kamaytirish uchun modelni qurishda har qanday hisoblash operatsiyalarini bajarish vaqti bir xil va 1 ga teng (ba'zi o'lchov birliklarida); Bundan tashqari, hisoblash qurilmalari o'rtasida ma'lumotlarni uzatish hech qanday vaqt sarflamasdan bir zumda amalga oshiriladi deb taxmin qilinadi (masalan, parallel hisoblash tizimida umumiy umumiy xotira mavjudligida bu haqiqat bo'lishi mumkin). Parallel algoritmlarning aloqa murakkabligini tahlil qilish qo'llanmaning 3-bo'limida amalga oshiriladi. Hisoblash masalasini yechish uchun tekshirilayotgan algoritmda bajariladigan amallar to‘plamini va operatsiyalar o‘rtasida mavjud bo‘lgan axborot bog‘liqliklarini G = (V, R) asiklik yo‘naltirilgan grafik ko‘rinishida ifodalaymiz,

Guruch. 3.1. "Operand operatsiyalari" hisoblash modeliga misol
Bu yerda V = {1, ..., | V |} - algoritm amallarini ifodalovchi grafikning uchlari to'plami, R - grafik yoylari to'plami (bu holda yoy r = (i, j) ) agar j amali i) amal natijasini ishlatsagina grafikga tegishlidir. Misol uchun, rasmda. 3.1 ikki burchakning koordinatalari bilan belgilangan to'rtburchaklar maydonini hisoblash algoritmining grafigini ko'rsatadi. Berilgan misoldan ko'rinib turibdiki, masalani yechish uchun tanlangan algoritmni bajarish uchun turli xil hisoblash sxemalaridan foydalanish va shunga mos ravishda turli xil hisoblash modellarini qurish mumkin.
Quyida ko'rsatilgandek, turli xil hisoblash sxemalari parallellashtirish uchun turli xil imkoniyatlarga ega va shuning uchun hisoblash modelini qurishda parallel bajarish uchun algoritmning eng mos hisoblash sxemasini tanlash vazifasi qo'yilishi mumkin. Algoritmning ko'rib chiqilayotgan hisoblash modelida kirish yoylari bo'lmagan cho'qqilar kiritish amallarini belgilash uchun, chiqish yo'li bo'lmagan cho'qqilar esa chiqish amallari uchun ishlatilishi mumkin. Grafikning kirish cho'qqilari bo'lmagan cho'qqilari to'plami bilan va grafikning diametrini (maksimal yo'lning uzunligini) d (G) bilan belgilaymiz.