Operatsiyalar-operandalar

6-Topshiriq
Mavzu: “Operatsiyalar-operandalar” xisoblashlar modeli

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.
Algoritmni parallel bajarish sxemasining tavsifi
Tanlangan hisoblash sxemasi doirasida o‘rtasida yo‘l bo‘lmagan algoritm operatsiyalari parallel ravishda bajarilishi mumkin (masalan, 3.1-rasmdagi hisoblash sxemasi uchun barcha ko‘paytirish amallari parallel ravishda bajarilishi mumkin, keyin esa birinchi ikkita ayirish amali). Algoritmning parallel bajarilishini tavsiflashning mumkin bo'lgan usuli quyidagicha bo'lishi mumkin.
Algoritmni bajarish uchun ishlatiladigan protsessorlar soni p bo'lsin. Keyin, hisob-kitoblarni parallel bajarish uchun to'plamni (jadvalni) o'rnatish kerak, unda har bir operatsiya uchun i ∈ V operatsiyani bajarish uchun foydalaniladigan Pi protsessorining raqami va ti operatsiyasining boshlanish vaqti ko'rsatilgan. Jadvalni amalga oshirish uchun Hp to'plamini belgilashda quyidagi talablarga rioya qilish kerak:
1. , ya'ni. bir xil protsessor bir vaqtning o'zida turli operatsiyalarga tayinlanmasligi kerak;
2. , ya'ni. operatsiyaning belgilangan vaqtiga qadar barcha kerakli ma'lumotlar allaqachon hisoblangan bo'lishi kerak.
Parallel algoritmning bajarilish vaqtini aniqlash
G algoritmining hisoblash sxemasining modelini Hp grafigi bilan birgalikda p protsessorlari yordamida bajariladigan parallel algoritm Ap (G, Hp) modeli sifatida ko'rish mumkin. Parallel algoritmni bajarish vaqti jadvalda ishlatiladigan maksimal vaqt qiymati bilan belgilanadi
.
Tanlangan hisoblash sxemasi uchun algoritmning minimal bajarilishini ta'minlaydigan jadvaldan foydalanish maqsadga muvofiqdir.
.
Bajarish vaqtini qisqartirish eng yaxshi hisoblash sxemasini tanlash orqali ta'minlanishi mumkin. Tp (G, Hp), Tp (G) va Tp baholari algoritmni parallel bajarish vaqtining ko'rsatkichlari sifatida ishlatilishi mumkin. Bundan tashqari, maksimal mumkin bo'lgan parallellikni tahlil qilish uchun algoritmning eng tez bajarilishini baholashni aniqlash mumkin.

Tp (G, Hp), Tp (G) va Tp baholari algoritmni parallel bajarish vaqtining ko'rsatkichlari sifatida ishlatilishi mumkin. Bundan tashqari, maksimal mumkin bo'lgan parallellikni tahlil qilish uchun algoritmning eng tez bajarilishini baholashni aniqlash mumkin.

T∞ smetasini cheksiz miqdordagi protsessorlardan foydalanganda parallel algoritmni bajarishning minimal mumkin bo'lgan vaqti deb hisoblash mumkin (nazariy tahlilda cheksiz miqdordagi protsessorli hisoblash tizimi tushunchasi, odatda parakompyuter deb ataladi, keng qo'llaniladi. parallel hisoblash). T1 bahosi bitta protsessordan foydalanganda algoritmning bajarilish vaqtini aniqlaydi va shu bilan muammoni hal qilish algoritmining ketma-ket versiyasini bajarish vaqtini ifodalaydi.
qayerda | |, eslaylik, G hisoblash sxemasining kirish cho'qqilarisiz uchlari soni. Shuni ta'kidlash kerakki, agar T1 bahosini aniqlashda biz muammoni hal qilish uchun faqat bitta tanlangan algoritmni ko'rib chiqish bilan cheklansak.

u holda bunday baholash yordamida olingan tezlashtirish ko'rsatkichlari tanlangan algoritmning parallellashuv samaradorligini tavsiflaydi. Hisoblash matematikasining o'rganilayotgan muammosini parallel hal qilish samaradorligini baholash uchun T1 qiymatini barcha mumkin bo'lgan ketma-ket algoritmlarni hisobga olgan holda aniqlash kerak.
(samarali parallel algoritm bitta protsessorda bajarilganda eng yaxshi ketma-ketlik usuliga mos kelmasligi mumkin).
Parallel algoritmning bajarilish vaqtini baholash xususiyatlarini tavsiflovchi nazariy bayonotlarni isbotsiz keltiramiz [18].
Teorema 1. Parallel algoritmning minimal mumkin bo'lgan bajarish vaqti algoritmning hisoblash sxemasining maksimal yo'lining uzunligi bilan belgilanadi, ya'ni.

Bu erda n - algoritm sxemasidagi kirish cho'qqilari soni.
Teorema 3. Amaldagi protsessorlar sonining kamayishi bilan algoritmni bajarish vaqti protsessorlar sonining kamayishiga mutanosib ravishda ortadi, ya'ni.

Teorema 4. Ishlatiladigan protsessorlarning istalgan soni uchun parallel algoritmning bajarilish vaqti uchun quyidagi yuqori chegara amal qiladi.

Teorema 5. T∞ mumkin bo'lgan minimal vaqt bilan taqqoslanadigan algoritmning bajarilish vaqti p∼ T1 / T∞ tartibli protsessorlar soniga erishish mumkin, ya'ni,

Kamroq protsessorlar bilan algoritmni bajarish vaqti mavjud protsessorlar soni bilan eng yaxshi hisoblash vaqtidan 2 barobardan ortiq bo'lishi mumkin emas, ya'ni.

Yuqoridagi bayonotlar parallel algoritmlarni shakllantirish qoidalari bo'yicha quyidagi tavsiyalarni berishga imkon beradi:
1. algoritm uchun hisoblash sxemasini tanlashda diametri eng kichik diametrli grafikdan foydalanish kerak (1-teoremaga qarang);
2. parallel bajarish uchun protsessorlarning tegishli soni p ∼ T1 / T∞ qiymati bilan aniqlanadi (5-teoremaga qarang);
3. Parallel algoritmning bajarilish vaqti yuqoridan 4 va 5 teoremalarda berilgan qiymatlar bilan chegaralanadi.
Algoritmni parallel bajarish jadvalini shakllantirish bo'yicha tavsiyalar ishlab chiqish uchun biz 4-teoremaning isbotini keltiramiz. Teoremaning isboti 4. H∞ bajarilishning mumkin bo'lgan minimal vaqti T∞ga erishish jadvali bo'lsin. H∞ jadvalining bajarilishi t, 0 ≤ t ≤ T∞ har bir takrorlash uchun t takrorlash davomida bajarilgan amallar sonini nt bilan belgilaymiz. Algoritmning p protsessorlar yordamida bajarilish jadvalini quyidagicha qurish mumkin. Algoritmning bajarilishini T∞ bosqichlarga ajratamiz; Har bir qadamda t, H∞ jadvalining t iteratsiyasida bajarilgan barcha operatsiyalarni bajarish kerak. Bu operatsiyalar p protsessorlaridan foydalanganda ént / pù iteratsiyasidan ko'p bo'lmagan holda bajarilishi mumkin. Natijada Tp algoritmining bajarilish vaqtini quyidagicha baholash mumkin:

Teoremaning isboti parallel algoritmni rejalashtirishning amaliy usulini beradi. Dastlab, jadval ishlatiladigan protsessorlarning cheklangan sonini hisobga olmasdan tuzilishi mumkin (parakompyuter uchun jadval). Keyin, teoremani chiqarish sxemasiga rioya qilgan holda, ma'lum miqdordagi protsessorlar uchun jadval tuzilishi mumkin. Parallel algoritm ishlash ko'rsatkichlari
Hisoblashlarning ketma-ket versiyasiga nisbatan p protsessorlari uchun parallel algoritmdan foydalanganda olingan tezlik aniqlanadi.

skaler kompyuterda masalalarni yechish vaqtining parallel algoritmni bajarish vaqtiga nisbati sifatida (n qiymati echilayotgan masalaning hisoblash murakkabligini parametrlash uchun ishlatiladi va masalan, kirish miqdori sifatida tushunish mumkin). muammo ma'lumotlari). Muammoni hal qilishda parallel algoritm bo'yicha protsessorlardan foydalanish samaradorligi quyidagi nisbat bilan aniqlanadi:

(samaradorlik qiymati algoritmni bajarish vaqtining o'rtacha qismini aniqlaydi, bu vaqt davomida protsessorlar haqiqatda muammoni hal qilish uchun ishlatiladi). Yuqoridagi munosabatlardan kelib chiqadigan bo'lsak, eng yaxshi holatda Sp (n) = p va Ep (n) = 1. 4-bo'limda bu ko'rsatkichlar hisoblash matematikasining tipik masalalarini hal qilish uchun ko'rib chiqilgan bir qator parallel algoritmlar uchun aniqlanadi.