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

Protsessorlar o’rtasida qismiy masalalarni taqsimlash. Protsessorlar

o’rtasida qismiy masalalarni taqsimlash parallel usulni ishlab chiqishning so’nggi bosqichidir. Shuni ta’kidlash kerakki, protsessorlar uchun yuklami muvozanatlash nazorati faqat taqsimlangan xotiraga ega hisoblash tizimlarida, ko ’p protsessorlar uchun (umumiy xotiraga ega tizimlar), yuklanishni balanslash odatda operatsion tizim tomonidan avtomatik ravishda amalga oshiriladi. Bundan tashqari, protsessorlar o’rtasida qismiy masalalarni taqsimlashning ushbu bosqichi, agar qismiy masalalarlar soni mavjud protsessorlar soniga to’g’ri kelsa, ortiqcha bo’ladi va hisoblash tizimining ma’lumot uzatish tarmog’ining topologiyasi to’liq grafdir (ya’ni, barcha protsessorlar bir-biri bilan to’g’ridan-to’g’ri aloqa liniyalari orqali bog’langan).

Ushbu bosqich muvaffaqiyatining asosiy ko’rsatkichi protsessorlardan foydalanish samaradorligi bo’lib, protsessorlar asl muammoni hal qilish bilan bog’liq bo’lgan hisoblashlarda foydalanilgan vaqtning nisbati sifatida aniqlanadi. Ushbu yo’nalishda yaxshi natijalarga erishish usullari bir xil bo’lib qolmoqda: avvalgidek, protsessorlar o’rtasida hisoblash yukining teng taqsimlanishini ta’minlash va ular o’rtasida yetkaziladigan xabarlarning sonini kamaytirish kerak. Dizaynning oldingi bosqichlarida bo’lgani kabi protsessorlar o’rtasida pastki chiziqlarni taqsimlash muammosining eng maqbul yechimi "qismiy masalalar - xabarlar" grafining ma’lumot ulanishini tahlil qilishga asoslangan. Shunday qilib, xususan, ma’lumotlarni to’g’ridan-to’g’ri uzatish liniyalari mavjud bo’lgan protsessorlarga axborot shovqinlari bilan qismiy masalalarlarni joylashtirish tavsiya etiladi.

Ta’kidlash joizki, protsessorlar o’rtasidagi ma’lumot almashinuvini minimallashtirish talabi yagona yuklash shartiga zid kelishi mumkin. Biz barcha qismiy masalalarni bitta protsessorga joylashtiramiz va protsessor almashinuvini butunlay yo’q qilamiz, ammo bu holatda aksariyat protsessorlarga yuk minimal bo’lishi aniq.

Maksimal qiymatni topish bo’yicha o’quv vazifasi uchun qismiy masalalarlarni protsessorlar o’rtasida taqsimlash hech qanday qiyinchiliklarga olib kelmaydi - faqat ma’lumot uzatish kanallari mavjud bo’lgan protsessorlarda axborot aloqalari mavjud bo’lgan pastki qismlarni joylashtirishni ta’minlash kifoya. Ta’lim vazifasining axborot aloqalari tarkibi chiziqli grafik shakliga ega bo’lganligi sababli, ushbu talabni deyarli har qanday kompyuter tizimining tarmoq topologiyasi uchun qondirish mumkin.

Agar hisoblash sxemasi muammoni hal qilish jarayonida o’zgarishi mumkin bo’lsa, hisoblash yukini muvozanatlash masalalarini hal qilish ancha murakkablashadi. Buning sababi, masalan, qisman differentsial tenglamalarni yechishda bir xil bo’lmagan panjara, matritsalarning siyrakligi va boshqalar bo’lishi mumkin. Bundan tashqari, loyihalash bosqichlarida ishlatiladigan qismiy masalalar yechimining hisoblash murakkabligini taxminiy hisoblash mumkin, va nihoyat hisob-kitoblar jarayonida qismiy masalalar soni o’zgarishi mumkin. Bunday holatlarda parallel dasturni bajarish paytida to’g’ridan-to’g’ri protsessorlar o’rtasida asosiy qismiy masalalarni qayta taqsimlash kerak bo’lishi mumkin (yoki, odatda, hisoblash yukini dinamik muvozanatni amalga oshirish kerak). Bu savollar parallel hisoblash sohasidagi eng qiyin (va eng qiziqarli) savollar qatoriga kiradi.

Misol tariqasida, odatda menejer-ishchi sxemasi deb ataladigan hisoblash ish yukini taqsimlashni dinamik boshqarishning keng tarqalgan usulining qisqacha tavsifini keltiramiz. Ushbu yondashuvdan foydalanganda, qismiy masalalar paydo bo’lishi va hisoblash jarayonida tugashi mumkinligi taxmin qilinmoqda, qismiy masalalar orasidagi axborot o’zaro ta’sirlari umuman yo’q yoki minimaldir. Ko’rib chiqilgan sxema bo’yicha tizimdagi yuklanish taqsimotini boshqarish uchun alohida protsessor-menejer ajratilgan bo’lib, u barcha mavjud qismiy masalalar haqida ma’lumotga ega. Tizimdagi qolgan protsessorlar hisoblash yukini olish uchun protsessor menejeriga murojaat qiladigan ijrochilar. Hisoblash jarayonida hosil bo’lgan yangi qismiy masalalar menejer protsessoriga qaytariladi va ularni bajaruvchi protsessorlarning keyingi qo’ng’iroqlari paytida hal qilish mumkin. Hisoblashlarning tugallanishi, bajaruvchi protsessorlar ularga berilgan barcha qismiy masalalarning yechimini tugatgan paytga to’g’ri keladi va protsessor menejerida bajariladigan hisoblash ishlari yo’q.

qismiy masalalarni ajratish bosqichini tekshirish uchun [1] da taklif qilingan ro’yxat quyidagicha:

• 
  protsessorga bir nechta vazifalarni taqsimlash qo’shimcha hisoblash xarajatlarining oshishiga olib keladimi?
  
• 
  hisob-kitoblarni dinamik ravishda muvozanatlash zarurmi?
  
• 
  “menejer-ijrochi” sxemasidan foydalanganda protsessor-menejerda “qiyinchilik” bormi?
  

Adabiyotlar

1. 
   Foster I. Designing and Building Parallel Programs: Concepts and Tools for Software Engineering. Reading, MA: Addison-Wesley, 1995.
   
2. 
   Fox G.C. et al. Solving Problems on Concurrent Processors. — Prentice Hall, Englewood Cliffs, NJ, 1988.