Informatika sohasida parallel algoritm, an’anaviy ketma-ket algoritmlarga qarama-qarshi qo‘yiladigan, — algoritm, uning alohida qismlarini turli hisoblash qurilmalarida bajarish, keyin olingan natijalarni birlashtirish orqali to‘g‘ri yakuniy natijaga erishish mumkin.
Ayrim algoritmlarni mustaqil bajariladigan qismlarga ajratish ancha oson. Masalan, 1 dan 100000 gacha bo‘lgan barcha sonlarni tekshirib, ularning qaysilari tub son ekanini aniqlash vazifasini har bir mavjud protsessorga sonlarning muayyan qismini taqsimlash, so‘ng topilgan tub sonlar to‘plamlarini birlashtirish orqali bajarish mumkin (bunday usul, masalan, GIMPS loyihasida ham qo‘llanadi).
Boshqa tomondan, pi () sonining qiymatini hisoblashga mo‘ljallangan ko‘plab ma’lum algoritmlarni parallel bajariladigan qismlarga ajratib bo‘lmaydi, chunki ularda algoritmning oldingi iteratsiyasi natijasi talab qilinadi. Iterativ sonli usullar, masalan, Nyuton usuli yoki uch jism masalasi, ham faqat ketma-ket bajariladigan algoritmlar hisoblanadi. Ayrim rekursiv algoritmlarni parallellashtirish ham ancha qiyin. Masalan, chuqurlik bo‘yicha qidirish usulini graflarda parallellashtirish qiyin.
Parallel algoritmlar ko‘p protsessorli tizimlar uzluksiz takomillashayotgani va zamonaviy protsessorlardagi yadrolar soni ortayotgani sababli juda muhimdir. Odatda (bir xil unumdorlik ta’minlangan taqdirda), ko‘plab sekin protsessorlardan ko‘ra bitta tezkor protsessorli kompyuterni yaratish osonroq. Biroq protsessorlarning unumdorligi, asosan, texnologik jarayonning takomillashishi (ishlab chiqarish texnologiyasida o‘lcham me’yorlarining kichrayishi) hisobiga ortadi. Bunga esa fizik cheklovlar — mikrosxema elementlarining o‘lchami va issiqlik ajralishiga qo‘yilgan chegaralar to‘sqinlik qiladi. Mazkur cheklovlarni ko‘p protsessorli ishlov berishga o‘tish orqali yengib o‘tish mumkin; bunday yondashuv hatto kichik hisoblash tizimlarida ham samarali bo‘ladi.
Ketma-ket algoritmlarning murakkabligi ularni bajarish uchun zarur xotira hajmi va vaqt (protsessor taktlari soni) bilan ifodalanadi. Parallel algoritmlarda esa yana bir resursni — turli protsessorlar o‘rtasidagi aloqa tizimini ham hisobga olish kerak. Protsessorlar o‘rtasida ma’lumot almashishning ikki usuli mavjud: umumiy xotiradan foydalanish va xabar uzatish tizimi.
Umumiy xotirali tizimlar qo‘shimcha bloklash mexanizmlarini joriy etishni talab qiladi. Ular qayta ishlanayotgan ma’lumotlarga tatbiq etiladi va qo‘shimcha protsessorlardan foydalanishda muayyan cheklovlar keltirib chiqaradi.
Xabar uzatish tizimlari kanallar va xabar bloklari tushunchalaridan foydalanadi. Bu tizim shinasi orqali uzatiladigan trafikni ko‘paytiradi va xabarlar navbatini tashkil qilish uchun qo‘shimcha xotira talab etadi. Zamonaviy protsessorlarni loyihalashda xabar almashishning vazifa bajarilish vaqtiga ta’sirini kamaytirish uchun maxsus kommutatorlar — krossbarlar (crossbar) ko‘zda tutilishi mumkin.
Parallel algoritmlardan foydalanish bilan bog‘liq yana bir muammo — yuklamani muvozanatlash. Masalan, 1 dan 100000 gacha bo‘lgan oraliqdagi tub sonlarni qidirishni mavjud protsessorlar o‘rtasida oson taqsimlash mumkin. Ammo ayrim protsessorlarga ko‘proq ish tushishi, boshqalari esa vazifasini ertaroq tugatib, bekor turib qolishi mumkin. Hisoblash elementlarining unumdorligi va ulardan foydalanish imkoniyati sezilarli darajada farq qiladigan geterogen hisoblash muhitlarida (masalan, grid-tizimlarda) yuklamani muvozanatlash muammosi yanada kuchayadi.
Parallel algoritmlarning taqsimlangan algoritmlar deb ataluvchi turi klasterlarda hamda taqsimlangan hisoblash tizimlarida ishlashning o‘ziga xos jihatlarini hisobga olgan holda, aynan shu muhitlarda foydalanish uchun ishlab chiqiladi.
Adabiyotlar
- RS/6000 SP: MPI dasturlash bo‘yicha amaliy qo‘llanma (ingliz tilida). — IBM RedBook, 1999. — 238 bet — [Arxivga olingan sana: 19 yanvar 2008 yil.]
- Olenyev N. N. MPI tizimida parallel dasturlash asoslari. — M.: Rossiya Fanlar akademiyasining Hisoblash markazi, 2005. — 80 bet — ISBN 5201098320.
- Lukyanenko D. V. MPI yordamida parallel dasturlash amaliyoti. — M.: LENAND, 2024. — 339 bet — ISBN 9785002370344.
- Valkovskiy V. A., Malishkin V. E. Zamonaviy dasturlash va superkompyuterlar elementlari. — Novosibirsk: Nauka, 1990. — 144 bet — ISBN 5-02-029652-X.
Havolalar
veb-arxivlar