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

Hisob-kitoblarni mustaqil qismlarga ajratish. Hisob-kitoblarni mustaqil qismlarga bo’lish usulini tanlash asl muammoni hal qilish uchun hisoblash sxemasini tahlil qilishga asoslangan. Tanlangan yondoshuv talablarini qondirish, odatda ajratilgan pastki qismlarda teng miqdordagi hisoblashni va ushbu qismiy masalalar orasidagi minimal bog’liqlikni ta’minlashdir (qolgan barcha narsalar teng, tez-tez o’tkaziladiganlarga nisbatan kattaroq hajmdagi xabarlarni yuborish kamdan- kam operatsiyalariga ustunlik berish kerak). Umuman olganda, muammolarni tahlil qilish va tanlash ancha qiyin muammo hisoblanadi - vaziyat ikkita umumiy hisoblash sxemasining mavjudligini hal qilishga yordam beradi (3-rasm).

3. 
   rasm. Matritsa ma’lumotlarini ajratish: a) chizma sxemasi, b) blok sxemasi Muammolaming katta sinfi uchun hisoblashlar katta ma’lumot to’plamini bir turdagi qayta ishlashni amalga oshirishga qisqartiriladi - masalan, bu sinfga matritsali hisoblar, qisman differentsial tenglamalarni yechishning raqamli usullari va boshqalar kiradi. Bu holda parallelizm mavjudligi qo’l keladi. ma’lumotlar va qismiy masalalarni tanlash mavjud ma’lumotlarning bo’linishigacha kamayadi. Shunday qilib, masalan, qismiy masalalarni shakllantirishda maksimal qiymatni topishda ko’rib chiqilayotgan ta’lim muammosi uchun boshlang’ich matritsani alohida satrlarga (yoki satrlarning ketma-ket guruhlariga) - chiziq ma’lumotlarini ajratish sxemasi deb atash mumkin (3-rasmga qarang) - yoki to’rtburchaklar. Elementlar to’plami - bloklarga ajratish asosida ma’lumot almashish sxemasi. Ko’p sonli muammolarni hal qilish uchun hisoblashlarni ma’lumotlarga ajratish bitta, ikki va uch o’lchovli kichik dasturlarning hosil bo’lishiga olib keladi, bunda faqat yaqin qo’shnilar o’rtasida axborot aloqalari mavjud (bunday sxemalar odatda panjara deb ataladi).
   

4-rasm. Ma’lumotlar dekompozitsiyasidan keyin doimiy tayanch qismiy

masalalaming birinchi, ikkinchi, uchunchi strukturalari

Vazifalarning yana bir qismi uchun hisob-kitoblar bir xil ma’lumot to’plamida turli xil operatsiyalarni bajarishni o’z ichiga olishi mumkin - bu holda ular funksional parallelizmning mavjudligi haqida gapirishadi (misollar sifatida, ma’lumotlar bazalariga so’rovlar ketma-ketligini qayta ishlash vazifalarini keltirish mumkin, bir vaqtning o’zida hisoblashlar, turli hisoblash algoritmlari va hk) yordamida. Ko’pincha funksional dekompozitsiyadan quvurli ma’lumotlarni qayta ishlashni tashkil qilish uchun foydalanish mumkin (masalan, har qanday ma’lumotlarni o’zgartirishni amalga oshirayotganda hisob-kitoblar ma’lumotlarni kiritish, qayta ishlash va saqlashning funksional ketma-ketligiga qisqartirilishi mumkin).

Qismiy masalalrni tanlashda muhim savol bu hisob-kitoblarning dekompozitsiyasining zarur darajasini tanlashdir. Maksimal mumkin bo’lgan qismiy masalalarning shakllanishi hal qilinadigan muammoning maksimal darajadagi parallelizmidan foydalanishni ta’minlaydi, ammo parallel hisoblashlarni tahlil qilishni murakkablashtiradi. Hisoblashlarning dekompozitsiyasida faqat yetarlicha “katta” qismiy masalalardan foydalanish parallel hisoblashlarning aniq sxemasiga olib keladi, ammo bu yetarlicha katta miqdordagi protsessorlardan samarali foydalanishni murakkablashtirishi mumkin. Ushbu ikkita yondashuvning mumkin bo’lgan oqilona kombinatsiyasi parchalanishning tarkibiy elementlari sifatida parallel hisoblash usullari ma’lum bo’lgan qismiy masalalarni ishlatishdan iborat bo’lishi mumkin. Masalan, matritsani ko’paytirish muammosini tahlil qilganda, quyi vektorlar sifatida vektorlarning nuqta hosil qilish usullari yoki matritsa-vektor mahsulotining algoritmlaridan foydalanish mumkin. Hisoblashlami

dekompozitsiyalashning bunday oraliq usuli hisoblash sxemalarining soddaligini ham, parallel hisoblashlarning samaradorligini ham ta’minlaydi. Ushbu yondashuv bilan tanlangan kichik dasturlar asosiy deb nomlanadi, agar ular keyingi ajratishga imkon bermasa yoki boshqacha tarzda kompozitsion bo’lsa, elementar (ajralmas) bo’lishi mumkin.

Ko’rib chiqilayotgan o’quv vazifasi uchun dekompozitsiyaning yetarli darajasi, masalan, matritsani alohida satrlar to’plamiga bo’lish va shu asosda alohida satrlarda maksimal qiymatlarni topish uchun quyi qatorlarni olish; bu holda hosil bo’lgan axborot aloqalarining tuzilishi chiziqli grafikka to’g’ri keladi (5-rasmga qarang).

Hisoblashlarni mustaqil qismlarga bo’lish bosqichining to’g’riligini baholash uchun [1] da keltirilgan savollar ro’yxatidan foydalanishingiz mumkin:

• 
  amalga oshirilgan dekompozitsiya hisob-kitoblar hajmi va xotira hajmini oshirmaydimi?
  
• 
  tanlangan dekompozitsiya usuli yordamida barcha mavjud protsessorlarni teng ravishda yuklash mumkinmi?
  
• 
  hisoblash jarayonining ajratilgan qismlari mavjud protsessorlarni samarali yuklash uchun yetarli bo’ladimi (ularning sonini ko’paytirish imkoniyatini hisobga olgan holda)?