Мавзу: Parallel dasturlarni modellashtirish. Parallel algoritmlarni ishlab chiqish bosqichlari. Ishning maqsadi

o'rtasida qismiy inasalalarni taqsimlash

rasm. Parallel algoritmlarni ishlab chiqishning umumiy sxemasi

Umuman olganda, ishlatilgan har bir protsessor uchun hisob-kitoblarning miqdori taxminan bir xil bo’lishi kerakligi aniq - bu protsessorlarning yagona hisoblash yukini (muvozanatini) ta’minlaydi. Bundan tashqari, protsessorlar o’rtasida quyi qismlarni taqsimlash qismiy masalalar orasidagi axborot aloqalari (aloqa shovqinlari) soni minimal bo’ladigan tarzda amalga oshirilishi kerakligi aniq.

Yuqoridagi barcha dizayn bosqichlarini tugatgandan so’ng, ishlab chiqilgan parallel usullarning samaradorligini baholash mumkin: buning uchun odatda ishlab chiqarilgan parallel hisoblashlarning sifat ko’rsatkichlarining qiymatlari (tezlashuv, samaradorlik, o’lchovlilik) aniqlanadi. Tahlil natijalariga ko’ra rivojlanishning individual (cheklangan holatda, barchasini) takrorlash kerak bo ’lishi mumkin - shuni ta’kidlash kerakki, rivojlanishning oldingi bosqichlariga qaytish parallel hisoblash davrlarini loyihalashning har qanday bosqichida yuz berishi mumkin.

Shu sababli, yuqoridagi dizayn sxemasida tez-tez bajariladigan qo’shimcha harakatlar, mavjud bo’lgan protsessorlarni aniqlagandan so’ng, yaratilgan vazifalar to’plamining tarkibini sozlash - pastki qismlarni oz miqdordagi protsessorlar mavjud bo’lganda kattalashtirish (yig’ish) mumkin yoki aksincha, batafsilroq. Umuman olganda, ushbu harakatlar ishlab chiqilgan algoritmni miqyosi sifatida aniqlanishi

mumkin va parallel hisoblash dizaynida alohida bosqich sifatida ajratib ko’rsatilishi mumkin.

Yakuniy ravishda olingan parallel usulni qo’llash uchun, yaratilgan qismiy masalalar to’plamini yechish uchun dasturlarni ishlab chiqish va tanlangan qismiy masalalar taqsimlash sxemasiga muvofiq ishlab chiqilgan dasturlarni protsessorlar orasida joylashtirish kerak. Hisoblashlarni amalga oshirish uchun bajariladigan dasturlar (ijro etilish bosqichidagi dasturlar odatda jarayonlar deb nomlanadi), axborot shovqinlarini amalga oshirish uchun dasturlar ixtiyorida ma’lumotlar almashish vositalariga (xabarlarni uzatish kanallari) ega bo’lishi kerak.

Shuni ta’kidlash kerakki, har bir protsessor odatda bitta qismiy masalani yechish uchun ajratiladi, ammo agar ko’p sonli qismiy masalalar mavjud bo’lsa yoki cheklangan miqdordagi protsessorlardan foydalanilsa, ushbu qoidaga rioya qilinmasligi mumkin va natijada protsessorlarda bir vaqtning o’zida bir nechta dastur (jarayonlar) bajarilishi mumkin. Xususan, parallel dasturni ishlab chiqish va dastlabki tekshirish paytida barcha protseduralarni bajarish uchun bitta protsessordan foydalanish mumkin (bitta protsessorda joylashganida, jarayonlar vaqtni taqsimlash rejimida bajariladi).

Parallel hisoblashlarni loyihalash va amalga oshirishning puxta ishlab chiqilgan sxemasini ko’rib chiqib, shuni ta’kidlash mumkinki, ushbu yondashuv asosan protsessorlar orasidagi aloqa kanallari orqali xabarlarni uzatish orqali zarur bo’lgan o’zaro aloqalar amalga oshirilganda taqsimlangan xotiraga ega hisoblash tizimlariga qaratilgan. Shunga qaramay, ushbu sxema parallel hisoblashlarning samaradorligini yo’qotmasdan va umumiy xotiraga ega tizimlar uchun parallel usullarni ishlab chiqishda qo’llanilishi mumkin - bu holda ma’lumotlarning o’zaro ta’sirini ta’minlash uchun xabarlarni uzatish mexanizmlari umumiy (kirish uchun) operatsiyalar bilan almashtirilishi kerak. birgalikda) o’zgaruvchilar.

Parallel hisoblashlarni loyihalash va amalga oshirishning ko’rib chiqilayotgan sxemasi parallel algoritmlar va dasturlarni tushunish uchun yo’lni taqdim etadi. Dizayn bosqichida parallel usulni "qismiy masalalar - xabarlar" grafi sifatida ko’rsatish mumkin, bu axborotga bog’liqlik grafini kengaytirilgan (yig’ilgan) tasvirlashdan boshqa narsa emas (“operatsiyalar - operandlar” grafi - 3-ma’ruzani ko’ring). Xuddi shunday, parallel dastumi tavsiflash uchun, “jarayonlar - kanallar” grafi ko’rinishidagi modeldan foydalanish mumkin, bunda qismiy masalalar o’rniga jarayonlar kontseptsiyasidan foydalaniladi va axborotga bog’liqliklar xabarlarni uzatish kanallari bilan almashtiriladi. Bundan tashqari, ushbu model hisoblash tizimining protsessorlari o’rtasida jarayonlarning taqsimlanishini ko’rsatishi mumkin, agar qismiy masalalar soni protsessorlar sonidan oshsa - 2-rasm.

- qabul qilish (uzatish) amali

- protsessorlar uchun kirish (chiqish) kanali

2. 
   rasm. “jarayonlar - kanallar” grafi shaklidagi parallel dasturiy model . Parallel hisoblashning ikkita modelidan foydalanish parallel usullarni ishlab chiqishda yuzaga keladigan muammolarni yaxshiroq ajratishga imkon beradi. Birinchi model - “qismiy masalalar - xabarlar” grafi, qismiy hisoblashlar orasidagi axborotga bog’liqlikning past darajasini ta’minlab, bir xil hisoblash murakkabligining pastki qismlarini aniqlash masalalariga e’tibor qaratish imkonini beradi. Ikkinchi model, “jarayonlar - kanallar” grafi, protsessorlar o’rtasida quyi qismlarni taqsimlashga qaratilgan bo’lib, bir xil protsessorlarga intensiv o’zaro ta’sirli jarayonlami joylashtirish orqali qismiy masalalar orasidagi axborot o’zaro ta’sirining murakkabligini kamaytirish uchun yana bir imkoniyatni taqdim etadi. Bunga qo’shimcha ravishda, ushbu model ishlab chiqilgan parallel usulning samaradorligini yaxshiroq tahlil qilish imkonini beradi va parallel hisoblashlarni bajarish jarayonini aniqroq tavsiflash imkoniyatini beradi.
   

Keling, “jarayonlar - kanallar” modelida ishlatiladigan tushunchalar uchun qo’shimcha tushuntirish beraylik:

• 
  jarayon deganda protsessorda bajariladigan dastur tushuniladi, u protsessorning mahalliy xotirasining bir qismini o’z ishiga ishlatadi va parallel dasturning boshqa bajariladigan jarayonlari bilan o’zaro aloqani tashkil qilish uchun bir qator ma’lumotlarni qabul qilish / uzatish operatsiyalarini o’z ichiga oladi;
  
• 
  mantiqiy nuqtai nazardan, ma’lumotlar uzatish kanali xabarlar navbatini ko’rib chiqilishi mumkin, bunda bitta yoki bir nechta jarayonlar ma’lumotlarni uzatish uchun yuborilishi mumkin va boshqa jarayon tomonidan yuborilgan xabarlarni olish mumkin.
  

Umuman olganda, kanallar birinchi uzatish / qabul qilish paytida dinamik ravishda paydo bo’lgan deb hisoblash mumkin. Umumiylik darajasi bo’yicha kanal qabul qilish jarayonidan ma’lumotlarni olish uchun bir yoki bir nechta buyruqlarga mos kelishi mumkin; Xuddi shunday, xabarlarni uzatishda kanal bir yoki bir nechta buyruqlar yordamida ma’lumotni bir yoki bir nechta jarayondan uzatish uchun ishlatilishi mumkin. Parallel usullarni modellashtirish va tahlil qilishning murakkabligini kamaytirish uchun biz kanal sig’imi cheksiz deb taxmin qilamiz va natijada ma’lumotlarni uzatish operatsiyalari deyarli kanallarga xabarlarni nusxalash orqali kechiktirmasdan amalga oshiriladi. Boshqa tomondan, xabarlarni qabul qilish operatsiyalari, agar kanal tomonidan so’ralgan ma’lumotlar hali jarayonlar - xabar manbalari tomonidan yuborilmagan bo’lsa, xabarlarning qabul qilinishi kechikish (blokirovka) ga olib kelishi mumkin.

Ko’rib chiqilayotgan “jarayonlar - kanallar” modelining muhim afzalligi shundan iboratki, u mahalliy (alohida protsessorda bajarilgan) hisoblashlarni va bir vaqtning o’zida ishlaydigan jarayonlarning axborot o’zaro ta’sirini tashkil qilish uchun harakatlami aniq ajratib turadi. Ushbu yondashuv parallel usullaming samaradorligini tahlil qilishning murakkabligini sezilarli darajada kamaytiradi va parallel dasturlarni ishlab chiqish muammolarini sezilarli darajada osonlashtiradi.

2. Parallel algoritmlarning ishlab chiqish bosqichlari

Parallel algoritmlarni ishlab chiqish uchun yuqoridagi metodologiyani batafsil ko’rib chiqing. Ushbu uslub ko’p jihatdan [1] da ishlab chiqilgan yondashuvga tayanadi va yuqorida ta’kidlab o’tilganidek, quyi qismlarni aniqlash, axborotga bog’liqlikni aniqlash, hisoblash tizimining protsessorlari o’rtasida qismiy masalalarni tarqatish va tarqatish bosqichlarini o’z ichiga oladi (1-rasmga qarang).

Berilgan tavsiyalarni namoyish qilish uchun biz A matritsasi elementlari orasida maksimal qiymatni topishning ta’lim muammosidan foydalanamiz (bunday muammo, masalan, Gauss usulining yetakchi elementini aniqlash uchun chiziqli tenglamalar tizimlarini raqamli yechishda paydo bo’ladi):

Ushbu vazifa to’liq tasvirlangan va ma’ruzaning qolgan qismidagi ishlab chiqish bosqichlarini ko’rib chiqqandan so’ng, parallel algoritmlarni ishlab chiqishda ushbu texnikadan foydalanishning to’liq misoli keltirilgan. Bunga qo’shimcha ravishda, ushbu ishlab chiqish sxemasi quyida ko’rib chiqilgan parallel hisoblashlarning barcha usullari taqdimotida qo’llaniladi.