Kafedrasi kompyuter arxitekturasi moduli bo‘yicha

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.