Parallel dasturlash algoritmlari

Parallel algoritmlar va dasturlar

Ba’zi bir zamonaviy dasturiy ta’minotlarga e’tibor qilsak, ularning ayrim tuzuvchilari dasturning ishlash effektivligiga va na xotiraning aql bilan ishlatilishiga e’tibor qilishadi. Ularning fikricha, dastur ko’p joy olsa, foydalanuvchi qo’shimcha xotira sotib olishga majbur bo’ladi yoki yangi tezroq ishlaydigan komyuter sotib oladi. Lekin kompyuterlarning tezligi cheksiz kattalashmaydi. U simli kabelda elektronlarning harakat tezligi bilan, optik kabellarda yorug’likning tarqalish tezligi bilan va hisoblashda qatnashadigan kompyuterlar orasidagi aloqa kanallarining komutativlik tezligi bilan chegaralanadi. Boshqa cheklovlar kompyuter imkoniyatlari bilan bog’liq emas, balki qo’yilgan masalaning murakkablik darajasiga bog’liq. Shunday masalalar mavjudki, ularni yechish uchun eng tez ishlaydigan algoritmlar qo’llanilganda ham odam umri yetmaydi. Bu masalalar orasida yaqinroq javob olish uchun algoritmlar kerak bo’ladigan, juda zarurlari ham mavjud.

Komyuter sistemalarini to’rtta asosiy kategoriyaga ajratish mumkin. Bu uchun qanday ishlashi haqidagi ko’rsatmani birmuncha almashtiramiz. Markaziy protssessor nuqtai nazaridan dastur rasshifrovka qilish va bajarish kerak bo’lgan qoidalar oqimidir. Ma’lumotlarni ham oqim ko’rinishida kiruvchi deb hisoblash mumkin. Biz tahlil qiladigan to’rtta kategoriya ma’lumot va qoidalarning bitta oqimga kirish-kirmasligi bilan aniqlanadi.


Bitta qoida / bitta ma’lumotlar oqimi (SISD).
Bitta qoida / bitta ma’lumotlar oqimi (SISD) modeli o’zida bitta protssesorli klassik modelni ko’rsatadi. Unga eski avlod kompyuterlari bilan bir qatorda ko’pgina zamonaviy kompyuterlar ham misol bo’ladi. Bunday kompyuter protsessori har qanday vaqt momentida faqatgina bitta qoidani bajarishga qodir va faqat bitta ma’lumotlar to’plami bilan ishlay oladi. Bu kabi ketma-ket sistemalarda boshqa kategoriyalardan farqli ravishda hech qanday parallellik yo’q.


Bitta qoida / bir nechta ma’lumotlar oqimi (SIMD).
Bitta qoida / bir nechta ma’lumotlar oqimibo’lgan komyuterlarda (SIMD) bir xil operatsiyani turli xil ma’lumotlar bilan ishlovchi bir nechta protssessorlar mavjud. SIMD - mashinalar ba’zan vektorli protsessorlar deb ham ataladi, chunki ular vektorlar ustida amal bajarish uchun juda qulay. Bunda har qaysi protssesorga bitta vector koordinasi beriladi va amal bajarilgandan so’ng natija vektor kelib chiqadi. Masalan, vektorlarni qo’shish – koordinatalar orqali bajariladigan amal. Vektorlar yig’indisining birinchi koordinatasi – qoshiluvchi vektorlar birinchi koordinatalarining yig’indisi, ikkinchi koordinata – ikkinchi koordinalar yig’indisi va hokazo. Bizning SIMD mashinada har qaysi protssesor kiritiluvchi vektorlarning ikkita koordinatasini haqida qoidasi oladi. Bu yagona qoidani bajargandan so’ng natija to’liq hisoblanadi. E’tibor bersak, N ta elementdan iborat vektorni yechishga SISD mashinaga N ta iteratsion siklni bajarish kerak bo’lsa, protsessorlar soni N tadan kam bo’lmagan SIMD – mashinaga bitta amalning o’zi yetarli.