3 Amaliy mashg’ulot: Mavzu: “Operatsiyalar-operandalar” xisoblashlar modeli Ishdan maqsad

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:

• , ya'ni. bir xil protsessor bir vaqtning o'zida turli operatsiyalarga tayinlanmasligi kerak;
• , 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:

• algoritm uchun hisoblash sxemasini tanlashda diametri eng kichik diametrli

grafikdan foydalanish kerak (1-teoremaga qarang);

• parallel bajarish uchun protsessorlarning tegishli soni p ∼ T1 / T∞ qiymati bilan aniqlanadi (5-teoremaga qarang);
• 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