Parallel Algoritmlar

BUXORO DAVLAT UNIVERSITETI

FIZIKA-MATEMATIKA FAKULTETI

AMALIY MATEMATIKA YO’NALISHI

ALGORITMLAR NAZARIYASI FANIDAN

MAVZU: Parallel Algoritmlar

Bajardi: Qalandarov J.

Rahbar: Mo’minov B.

Buxoro-2010

Mundarija:

Mavzuning dolzarbligi

Bu ishda ikki vazifa – algoritmlarning dastur effektivligiga qanday ta’sir etishi va turli xil algoritmlarning analizini o’rganishdir. Ba’zi bir zamonaviy dasturiy ta’minotlarga e’tibor qilsak, ularning ayrim tuzuvchilari na 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.

Parallelikka kirish

Bu kurs ishida biz parallel dasturlashda ishlatiladigan asosiy tushunchalarni keltiramiz. Avvalo, ishni kompyuterning ma’lumotlarni qayta ishlash tushunchasini keltirishdan boshlaymiz. So’ngra kompyuter sistemalarining arxitekturasiga o’tamiz. Oxirda parallel algoritmlarning analizida ishlatiladigan prinsiplarni tahlil qilamiz.

Komyuter sistemalarining kategoriyalari.

Komyuter sistemalarini to’rtta asosiy kategoriyaga ajratish mumkin. Bu uchun qanday ishlashi haqidagi ko’rsatmani birmuncha almashtiramiz. Markaziy protssessor nuqtai nazaridandastur 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.

1. Bitta qoida / bitta ma’lumotlar oqimi.

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.

1. Bitta qoida / bir nechta ma’lumotlar oqimi.

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.

1. Bir nechta qoida / bitta ma’lumotlar oqimi

Bir vaqtda faqat bir xil ma’lumotlar ustida amal bajarish avval g’alati tuyulishi mumkin, chunki qndaydir bir sonni kvadratga ko’tarish, ikkiga ko’paytirish, o’nga bo’lish kabi dasturlar kamdan-kam uchraydi. Lekin bu holatga boshqa nuqtai-nazardan qarasak, bunday tipdagi mashinalarda sonning tub yoki murakkabligini tekshirishni takomillashtish mumkinligini ko’ramiz. Agar protsessorlar soni N ta bo’lsa, unda biz ixtiyoriy 1 va N2 orasidagi sonlarning tub yoki murakkabligini MISD – mashina orqali bitta operatsiyada tekshirishimiz mumkin. Agar X son murakkab bo’lsa, unda ga to’g’ri kelmaydigan bo’luvchisi bo’lishi kerak. Sonning tubligini tekshirish uchun X<N2 sonni birinchi protsessorga ikkiga bo’lishga, ikkinchisini uchga bo’lishga, uchinchisini to’rtga va hokazo (K-1) protsessorni K ga bo’lishga buyruq beramiz. Bunda K=[]. Agar bu protsessorlarning birontasida bo’lish muvaffaqiyatli amalga oshirilsa, X murakkab son. Shuning uchun biz natijaga bitta operatsiya bilan erishamiz. Bundan ko’rish qiyin emaski, ketma-ket mashinaga bu algoritmni bajarish uchunkamida har birida bitta bo’lish amalga oshiriladigan ta o’tish kerak bo’ladi.

1. Bir nechta qoida / bir nechta ma’lumotlar oqimi

Bu kategoriya kategoriyalar orasida ancha murakkabidir. MIMD –sistemalar holatida biz o’z qoidasini amalga oshira oladigan bir nechta protsessor bilan ish ko’ramiz. Bundan tashqari, bir nechta bir nechta ma’lumotlar oqimi ham mavjud va har qaysi protsessor o’z ma’lumotlar to’plami bilan ishlay oladi.

Bu amaliyotda MIMD – sistema har qaysi protsessorda o’z dasturini yoki o’sha dasturning alohida qismlarini yoki SIMD – konfiguratsiyaday vektorli amallarni bajara olishini anglatadi. Ko’pchilik parallelizmning yangicha yondashuvlarida, masalan komyuter klasterlari yoki multiprotsessorli sistemalarning asosida MIMD – kategoriya yotadi.

Parallel arxitekturalar

Parallel kompyuterlar tizimlari arxitekturasida ikkita jihat asosiy rol o’ynaydi:

• Protesssorlar va ularning xotiralari o’zaro qanday bog’langanligi;
• Protsessorlarning qanday o’zaro ta’sir qilishi.

Parallel algoritmlarni muhokama qilganda biz ana shu jihatlar haqida gapiramiz. Negaki u yoki bu yechimlar turli masalalar uchun turli samaradorlikka ega bo’lishi mumkin.

Kuchli va kuchsiz bog’langan mashinalar.

Kuchsiz bog’langan mashinalarda har protsessor o’z xususiy xotirasiga ega. Lekin protsessorlar o’rtasidagi aloqa tarmoq kabellari orqali amalga oshiriladi. Bu kompyuterlar klasterlarining bu kompyuterlar klasterlarining arxitekturasi shunday: klasterning har bir kompyuteri alohida kompyuter tizimi va mustaqil iashlay oladi. Parallellik bosh boshqaruvchi kompyuter orqali masalani kompyuterlarga taqsimlash hisobiga amalga oshiriladi. Tor aloqali mashinalarda barecha protsessorlar umumiy markaziy xotiradan foydalanadi. Protsessorlar o’rtasida o’zaro ta’sir shunday amalga oshiriladiki, bunda ulardan biri axborotni umumiy xotiraga yozadi, boshqalari esa shu yerdan o’qib oladi.

Protsessorlarning o’zaro ta’siri.

Kuchsiz aloqali mashinalar o’rtasida protsessorlarning o’zaro ta’siri kabellar yoki similar orqali amalga oshirilishini aytib o’tgan edik. Bunday aloqalarning tashkil qilish mumkin bo’lgan hollarini qaraymiz. Spekrning bir uchida to’liq aloqali tarmoq joylashgan. Bunda har bir protsessor boshqalari bilan ulangan. Boshqa bir uchida esa chiziqli tarmoq mavjud. Bunda protsessorlar zanjirsimon bog’langan va har bir protsessor ikkita uchidagidan tashqari ikkita qo’shnisi bilan bog’langan (uchidagi kompyuterlar bitta qo’shni bilan bog’langan). To’liq aloqali tarmoqda (1-rasm) axborot protsessordan protsessorga juda tez uzatiladi, lekin buni tashkil qilish uchun juda uzun kabel talab qilinadi. Chiziqli tarmoqda esa axborot sekinroq uzatiladi. Sababi, axborot oraliq tugunlardan o’tadi va zanjiring biron joyidan uzilishi ma’lumtlar oqimini uzib qo’yadi. Chiziqli tarmoqqa alternative sifatida turg’unlikni oshiruvchi halqali strukturani tashkil qilish mumkin. U ham chiziqli tarmoq kabi qurilgan. Faqat zanjirning birinchi va so’nggi zvenosi o’zaro ulangan bunday tarmoqda axborot tez tarqaladi. Negaki, axborot protsessorning yarmidan kamidan o’tadi.

1-rasm. To’liq aloqali tarmoq

2- rasm. Chiziqli tarmoq

3- rasm. Halqali tarmoq

4-rasm. Chambarali tarmoq

Masalan, 2- rasmdagi chiziqli tarmoqda birinchi tugundan beshinchi tugunga borish uchun uchta oraliq tugundan o’tishi kerak. 3-rasmdagi halqali tarmoqda esa bitta tugundan o’tishi yetarli 4-rasmdagi tarmoqda protsessorlar ikki o’lchovli chambaraning uchlarida joylashgan. Kabellar qo’shnilarni gorizontal bo’yicha yoki vertical bo’yicha ulagan. Bunday tarmoq halqalidan samarali va turg’un, lekin kabel ko’proq sarf bo’ladi.

Parallel arxitekturada protsessorlarni ulashning bundan boshqa imkoniyatlari ham mavjud. Bularga daraxtsimon tarmoqlar (protsessorlar bironta daraxtni hosil qiladi) va ikki o’lchovli chambarani umumlashtiradigan giperkublarni misol qilish mumkin.

Parallel algoritmlar analizining prinsiplari

Parallel algoritmlar bilan ishlashda bizni ikki tushuncha qiziqtiradi:

1. Tezlanish koeffitsiyenti
2. Qiymati

Parallel algoritmlarning tezlanish koeffitsiyenti optimal ketma-ket algoritmning qanchalik tez ishlashini ko’rsatadi. Ma’lumki optimal tartiblash algoritmi O(Nlog N) ta operatsiyani talab qiladi. O(N) murakkablikdagi parallel tartiblash algoritmining tezlanish koeffitsiyenti O(log N) ni tashkil qiladi.

Bizni qiziqtiadigan ikkinchi tushuncha – parallel algoritmning qiymati bo’lib, uni biz ishlatilayotgan protsessorlar sonining algoritm murakkabligiga ko’paytmasi orqali aniqlaymiz. Agar bizning holatda parallel tartiblash algoritmi O(N) ta operatsiya uchun kiruvchi yozuvlar soniga teng protsessorlarni talab qilsa, uning qiymati O(N^) ga teng. Bu parallel tartiblash algoritmi qimmatliroq ekanligini bildiradi, ya’ni bitta protsessordagi ketma-ket tartiblash algoritmining qiymati uning murakkabligi bilan mos keladi va O(Nlog N) ga teng.

Zarur tushunchalardan yana biri vazifaning tarkibiy qismlarga ajralishidir. Agar bizning parallel tartiblash algoritmimiz uchun yagona imkoniyat protsessorlar sonining kiruvchi yozuvlar soniga tengligi shart bo’lsa, unda bunday algoritm kiruvchi yozuvlar sonining yetarlicha katta bo’lishi bilan befoyda bo’lib qoladi. Ketma-ket tartiblash algoritmida hech qanday o’xshash cheklovlar yo’q. Bizni ko’proq protsessorlar soni kiruvchi ma’lumotlar potensial hajmidan yetarlicha kam bo’lgan va bu son kirish uzunligining ortishi bilan kattalashishni talab qilmaydigan parallel tartiblash algoritmlari qiziqtiradi.

PRAM modeli

Parallel sistemalaning muammolaridan biri ma’lumotlarni xotiradan o’qish va xotiraga yozishdir. Masalan, agar ikkita protsessor ma’lumotlarni umumiy xotiraning aynan bitta joyiga yozishga urinsa nima bo’ladi?

Ilgari biz ko’rgan algoritmlarda bu algoritmni amalga oshiradigan mashina ilgaridan berilgan xotira yacheykasi (RAM) ga to’g’ridan-to’g’ri kirish imkoniyatiga ega. Hozir biz qaraydigan algoritmlar bunday mashinalarning parallel varianti (PRAM) ga asoslangan. Bizning PRAM mashinalarning protsessorlari o’zaro chambarchas bog’langan va umumiy xotira blokidan foydalanadi. Har bir protsessorda uncha katta hajmda bo’lmagan ma’lumotlarni saqlash imkoniyatiga ega bo’lgan bir nechta registrlar mavjud, ma’lumotlarning asosiy qismi esa umumiy xotirada saqlanadi.

Protsessorlar orasidagi chambarchas bog’liqlikdan tashqari biz yana ular hammasi xotiradan ma’lumotlarni o’qish, ular ustida operatsiya bajarish va natijani xotiraga yozishdan iborat bo’lgan bir xil siklni amalga oshiradi deb faraz qilamiz. Bu barcha protsessorlar bir vaqtda xotirani o’qishini, bir vaqtda o’qilgan ma’lumotlarni qayta ishlashini, bir vaqtda yozuvni ham bajarishini anglatadi. Xotira yacheykalari ustidagi bahs nafaqat ma’lumotlarni o’qishda, balki natijani yozishda ham kelib chiqadi. Uch qadamli siklning shartlari agar Y protsessor xotira yacheykasidagi ma’lumotlarni o’zgartirgan vaqtda, X protsessor hozirgina o’qilgan ma’lumotlarni qayta ishlashi natijasida biz nima bo’lishi haqida qayg’urmasak ham bo’lishini anglatadi. Bundan tashqari, bitta protsessor xotiradan ma’lumotlarni o’qiyotgan vaqtda, ikkinchisi unga biron ma’lumot yozishga urinishi kabi vaziyatlar ham yuzaga kelmaydi.

Bahslarga faqatgina xotiraga kirishga raqobatli yoki maxsus huquq berish orqali ruxsat berish mumkin. Raqobatli kirishda xotiraning aynan bitta yacheykasiga bir vaqtda bir nechta protsessor murojaat qilishi mumkin. Maxsus kirishda esa berilgan xotira yacheykasiga aniq momentda faqat bittagina protsessor murojaat qila oladi, bir vaqtdagi ikkita murojaat qilishga urinish esa xatolik haqidagi xabarning paydo bo’lishiga olib keladi. Raqobatli kirish o’qish vaqtida muammo keltirib chiqarmaydi. Bundan tashqari bizga maxsus o’qish huquqi bilan ishlaydigan algoritmlar ham kerak. Maxsus o’qish huquqiga ega bo’lgan bir nechta protsessor bir vaqtda bitta xotira yacheykasiga murojaat qilsa xatolik paydo bo’ladi.

Bundan tashqari yozuv vaqtida maxsus va raqobatli kirishlarni tanlashda ham muammo mavjud. Maxsus kirishda har qaysi xotira yacheykasiga yozuv huquqi faqat bitta protsessorga beriladi, bir necha protsessorlar yozishga harakat qilsa, xatolik paydo bo’ladi. Lekin ikkita protsessor ikkita xotira yacheykasiga bir vaqtda yoza oladi. Raqobatli kirishda esa, masala birmuncha murakkab, ya’ni kelib chiqadigan konfliktlarga ruxsat bera olish kerak. Darajaga ega modelda har bir protsessorga daraja beriladi va yozuv huquqi kattaroq darajali protsessorga beriladi.

Modelning soddalashtirilgan protsessor darajasi uning nomeriga to’g’ri keladi, ya’ni nomer qancha kichik bo’lsa, daraja shuncha katta bo’ladi. Agar, masalan, bitta xotira yacheykasiga 4- va 7- nomerli protsessorlar yozishga urinsa, huquq 4-nomerli protsessorga beriladi.

Ixtiyoriy kirishli modelda raqobat qiladigan protsessorlardan ixtiyoriy biri olinishi mumkin. Oddiy modelda esa faqatgina yoziluvchi ma’lumotlar ustma-ust tushgandagina bir vaqtda yozishga ruxsat beriladi. Kombinatsiyali modelda yoziluvchi ma’lumotlar ustidasistema bir qancha amallarni bajaradi. Masalan, ularning yig’indisi, ko’paytmasi, eng katta yoki eng kichik elementi yoki mantiqiy operatsiya natijasi (va, yoki) yozilgan bo’lishi mumkin. Turli holatlarda bu imkoniyatlardan har biri foydali bo’lishi mumkin.

Bundan kelib chiqadiki, bizda yozish va o’qish imkoniyatlarining 4 xil kombinatsiyasi mavjud:

1. Raqobatli o’qish / raqobatli yozish (CRCW);
2. Raqobatli o’qish / maxsus yozish (CREW);
3. Maxsus o’qish / raqobatli yozish (ERCW);
4. Maxsus o’qish / maxsus yozish (EREW);

Oddiy parallel operatsiyalar

Endi ikkita elementar operatsiyani ko’ramiz:

1. Kiruvchi ma’lumotlarni protsessorlarga taqsimlash;
2. Ro’yxatning eng katta va eng kichik elementini aniqlash;

Quyida biz i- protsessorni Pi , protsessorlar sonini p, kiruvchi ro’yxatdagi elementlar sonini N, j- xotira yacheykasini Mj bilan belgilaymiz. Bajariladigan parallel operatsiyalar qavsda Parallel Start va Parallel End kabi yoziladi. Agar boshida bitta blok operatsiyasi, undan keyin ikkinchisi parallel bajarilsa, ular alohida qavslar juftiga kiritiladi.

CREW PRAM modelida berilganlarni taqsimlash

Eslaymizki, CREW modelda bitta xotira yacheykasini bir vaqtda bir necha protsessorlar o’qiy oladi. Natijada, berilganlarni barcha protsessorlarga juda tez kiritish mumkin.

P[1] M[1] ga qiymatni kiritadi

Parallel Start

for k=2 to p do

P[k] M[1] dan qiymatni

o’qiydi

end for

Parallel end

Taqsimlash 2 etapda bajariladi. Birinchisida ma’lumotlar xotiraga yoziladi, ikkinchisida barcha protsessorlar uni o’qiydi. Bunday tezlik faqatgina raqobatli o’qish hisobiga bo’lishi mumkin. Endi bu protsedura chekli o’qish modeli uchun qanday ko’rinishda bo’lishini ko’ramiz.

EREW PRAM modelda berilganlarni taqsimlash

Maxsus o’qish modelida PL protsessor tomonidan ma’lumotni faqatgina bitta protsessor o’qiy oladi. Agar biz shunchaki, qolgan protsessorlar bilan ketma-ket o’qish siklini tashkil qilsak, unda parallelizmling barcha ustunliklarini ko’rsatuvchi ketma-ket algoritmga ega bo’lamiz. Mabodo, agar biz ikkinchi protsessorda ma’lumotni boshqa xotira yacheykasiga yozish uchun o’qish / qayta ishlash / yozish siklidan foydalansak, unda keying qadamda ma’lumotni ikkita protsessor o’qiy oladigan bo’ladi. Keyin uni yana ikkita yachekaga yozsak, biz to’rtta protsessordan foydalana olamiz. Natijada bizda quyidagi algoritm kelib chiqadi.

Р[1] М[1] ga qiymat kiritadi

procLoc=1

for j=1 to log p do

Parallel Start

for k=procLoc+1 to 2*procLoc do

P[k] M[k-procloc] ni o’qiydi

P[k] M[k] ga yozadi

end for k

Parallel End

procLoc=procLoc*2

end for j

Avval algoritm ma’lumotni M1 yacheykaga yozadi. Tashqi siklning birinchi qadamida, P2 protsessor bu ma’lumotni o’qiydi va uni M2 ga yozadi, PL o’zgaruvchi bo’lsa, 2 ni qabul qiladi. Ikkinchi o’tishda P3 va P4 protsessorlar M1 va M2 yacheykalar tarkibini o’qiydi, PL o’zgaruvchi esa 4 ni qabul qiladi. Uchinchi o’tishda P5 dan P8 gacha protsessorlar M1 dan M4 gacha yacheykalarning tarkibini o’qiydi va uni M5 dan M8 gacha yacheykalarga yozadi.

Ko’rinib turibdiki, (p 2 ning darajasi bo’lganda) oxirdan bitta oldingi qadamda protsessorlarning yarmi kerakli qiymatni o’qiydi va M1 dan Mp/2 gacha bo’lgan yacheykalarga yozadi, undan keyin esa qolgan protsessorlar uni o’qiy oladi. Bundan kelib chiqadiki, o’qish va yozish qadamlarini bitta siklda bajarish mumkin ekan, parallel blok bitta siklni bajaradi, tashqi sikl esa, log p iteratsiyani ishlab chiqaradi. Shuning uchun bu parallel taqsimlash algoritmi O(log p) ta operatsiyani bajaradi.

Ro’yxatning eng katta elementini qidirish

Bunda va bundan keying ro’yxatlar ustid bajariladigan amallarda biz faraz qilamizki, ro’yxat M1 dan MN gacha bo’lgan xotira yacheykalarida joylashgan. Bundan tashqari yana faraz qilamizki, bizning ixtiyorimizda p=N/2 ta protsessor mavjud. (p<N/2 bo’lgan holatni algoritmni tuzgandan keyin muhokama qilamiz.)

Birinchi o’tishda Pi protsessor M2i va M2i+1 yacheykalarning qiymatlarini taqqoslaydi va Mi yacheykaga ulardan kattasini yozadi. Ikkinchi o’tishda bizga protsessorlarning faqat yarmi kerak va ularning yordamida biz Mi dan MN/2 gacha bo’lgan yacheykalardagi elementlar juftliklarni taqqoslaymiz hamda juftliklarning katta elementini M1 dan MN/4 gacha bo’lgan yacheykalarga yozamiz. Natijada quyidagi algoritmga ega bo’lamiz.

count=N/2

for i=1 to log(count)+1 do

Parallel Start

for j=1 to count do

P[j] M[2j] ni X ga va M[2j+1] ni Y ga o’qiydi

if X>Y

P[j] Х ni M[j] ga yozadi

else

P[j] Y ni M[j] ga yozadi

end if

end for j

Parallel End

count=count/2

end for i

Ko’rinib turibdiki, har bir qadamda orasidan kattasi topiladigan qiymatlar soni biz yagona sonni topmagunimizcha 2 martadan kamayadi. Bu bitta protsessorda turnir metodini amalga oshirishga juda o’zshaydi. Agar p<N/2 bo’lsa, oldindan qiymatlar sonini 2*p gacha kamaytirish mumkin, keyin esa algoritm yuqoridagiday bajariladi.

Ko’rinib turibdiki, sikldagi o’tishlar soni log N ga teng, murakkabligi esa O(log N) tartibga ega.eslaymizki, algortmning qiymatini yuqorida muhokama qilgan edik, ya’ni biz qiymatni ishlatilgan protsessorlar sonining sarflangan vaqtga ko’paytmasi kabi aniqlagan edik. Shuning uchun algoritmning qiymati N/2*O(N log N) ga teng. Oddiy ketma-ket algoritm shu ishni O(N) operatsiya bilan bajaradi, shuning uchun u arzon, parallel algoritm esa anchagina tez ishlaydi.

Agar parallel hisoblashlar haqiqatan ham foyda keltiradigan bo’lsa, unda ketma-ketdan qolishmaydigan alternative qarash bo’lishi kerak. Biz avvalgi variantga diqqat bilan qarasak, protsessorlar soni juda katta qiymatni berganini ko’ramiz. Bu sonni kamaytirish mumkinmi? Agar biz butun qiymati O(N) tartibda va parallel algoritmning bajarilish vaqti esa (O log TV) tartibda bo’lishini xohlasak, protsessorlar sonining tartibi ham O(N/log N) tartibda bo’lishi kerak. Bu shuni anglatadiki, birinchi o’tishda har qaysi N/(N/log TV) tartibda bo’lishi kerak. Bu shuni anglatadiki, birinchi o’tishda har qaysi N/(N/log TV)=log N ta qiymatni qayta ishlashi kerak. Natijada quyidagi algoritmga o’tamiz.

Parallel Start

for j = 1 to N/log N do

P[j] M[l+(j-1)*log N] dan M[j * log N] gacha yacheykalarning maksimum qiymatini ketma ket algoritm bilan topadi

P[j] M[j] ga topilgan maksimumni yozadi

end for

Parallel End

count=N/2

for i=1 to log(count)+1 do

Parallel Start

for j=1 to count do

P[j] M[2j] ni X ga va M[2j+1] ni Y ga o’qiydi

if X>Y

P[j] Х ni M[j] ga yozadi

else

P[j] Y ni M[j] ga yozadi

end if

end for j

Parallel End

count=count/2

end for i

Bu variantda dastlabki qayta ishlash bosqichi mavjud bo’lib, har qaysi protsessor log N ta elementdan tashkil topgan ro’yxat ustida ketma-ket algoritm bajaradi. Bu esa O(log TV) operatsiyani talab qiladi. Algoritmning ikkinchi qismida bizning boshlang’ich urinishimiz keltirilgan. Bunda talab qilinadigan protsessorlar soni (TV/log N)/2 gacha kamaygan (lekin baribir bu bosqichda dastlabki qayta ishlash uchun avvalgiday N/log N ta protsessor talab qilinadi).

Shuning uchun algoritmning to’liq qiymati quyidagiga teng:

Qadam	Qiymat	Vaqt
Dastlabki qayta ishlash	(N / log N)*O(log N)=O(N)	O(log N)
Asosiy sikl	[(N / log N)/2]*O(log N)=O(N)	O(log N)
Jami	O(N)	O(log N)

Parallel izlash

Izlashning parallel metodlarini o’rganishni biz eng oddiy, ya’ni protsessorlar soni ro’yxatning elementlari soniga teng bo’lgan ko’rinishidan boshlaymiz. Analiz bizga bu yechim qiymati bo’yicha optimal yechimdan qanchalik yiroqligini ko’rsatadi. Undan keyin undan keyin biz maksimumni hisoblashda qo’llanilganiday, qiymatni protsessorlar sonini kamaytirish hisobiga kamaytirishga harakat qilamiz. Bunda faraz qilamizki, ro’yxatda dublikatlar yo’q.

Agar protsessorlar soni ro’yxatning elementlari soniga teng bo’lsa (p=N), unda har qaysi protsessor qidirilayotgan qiymatni ro’yxatdagi o’ziga tegishli element bilan taqqoslaydi. Agar o’xshashlik sodir bo’lsa, o’xshashlikni topgan protsessor, yacheyka nomerini xotiraning ba’zi maxsus joylariga yozishi mumkin. Keyingi algoritmda faraz qilamizki, ro’yxat M1 dan MN gacha yacheykalarda joylashgan, qidirilayotgan qiymat esa MN+1 –yacheykada, u aniqlangan yacheyka nomeri esa, MN+2 ga yozilgan bo’lishi kerak.

Parallel Sort

for j=1 to N do

P[j] M[j] ni Х ga va M[N+1] ni target ga o’qiydi

if X=target then

j ni M[N+2] ga yozadi

end if

end for

Parallel End

Biz faraz qilamizki, barcha bo’sh xotira yacheykalariga boshlang’ich nolga teng qiymat kiritilgan, shuning uchun algoritm ishining yakunida agar qidirilayotgan qiymat ro’yxatda topilmasa, MN+2 –yacheyka nolga teng bo’ladi. Lekin agar qiymat ro’yxatda topilsa, uni aniqlagan yagona protsessor u joylashgan yacheyka nomerini MN+2 ga yozadi.

N ta MN+2 ning har birida bu algoritm o’qish / qayta ishlash / yozishning bitta siklini bajaradi, shuning uchun umumiy ishlash vaqti O(1), qiymati esa O(N) ga teng. Eslaymizki, optimal ketma-ket izlash algoritmining qiymati O(log N) ga teng edi.

Quyida keltirilgan alternativ parallel algoritm qiymatni va ishlatiladigan protsessorlar soniga bog’liq ravishda ish vaqtini o’zgartirish imkonini beradi.

Protsessorlar soni p<=N bo’lganda

Parallel Start

for j=1 to p do

P [j] М[(j-l)*(N/p)+l] dan M[j*(N/p)] gacha bo’lgan yacheykalardaketma-ket ikkilangan izlashni bajaradi va X tarkib topgan yacheyka nomerini M[N+2] ga yozadi

end for

Parallel End

Agar protsessor bitta bo’lsa, u izlashni M1 dan MN gacha bo’lgan yacheykalarda, aniqrog’i butun ro’yxatda olib boradi. Shuning uchun bitta protsessorda bu algoritm ketma-ket ikkilangan izlashga kelib qoladi. Demak uning qiymati O(log N) ga teng, bajarilish vaqti ham O(log N) ga teng.

N ta protsessor ishlatilganda esa, biz qiymati O(N) va bajarilish vaqti O(1) bo’lgan birinchi parallel variantga qaytamiz. Oraliq variantlarda esa biz har biri N/p ta elementdan tarkib topgan p ta ro’yxat bilan ish ko’ramiz. Bu variantning bajarilish vaqti O(log (N/p)), qiymati esa O(p log (N/p)) ga teng. Lekin p – log TV bo’lgan holatni alohida qarash lozim, bunda log (N/log TV) = log N log (log N). Bu holatda qiymat O((log N)*(log N)) = O(log2 N) bo’lganda, bajarilish vaqti O(log N).

Parallel algoritmning bajarilish vaqti tartibi ketma-ket ikkilamchi izlash tartibiga to’g’ri keladi, lekin baholashdagi konstanta kamroq bo’ladi, shu sababdan parallel algoritm tezroq bajariladi. O(log2 N) qiymat optimal ketma-ket izlashning O(log N) qiymatini oshirib yuboradi, lekin bu parallel algoritm ma’nosini yo’qotadigan darajaga bormaydi.

Xulosa

Odamlar allaqachon ko’p hollarda 2 ta odam ishni alohida bajarganga nisbatan birgalikda tezroq bajarishlarini tushunganlar. Amaliyotda ham parallellik anchagina keng qo’llaniladi. Katta hajmdagi ma’lumotni bir necha ishchiga bo’lib berganda tezroq tartiblash mumkin. Yoki chelak to’la suvni qo’lma-qo’l uzatganda bir joydan ikkinchisiga yugurgandan ko’ra tezroq yuborish mumkin.

Parallel dasturlashda ham xuddi shunga o’xshash holatlar qo’llaniladi. Shunday ko’p funksiyali sistemalar mavjudki, ularda har qaysi protsessor bir xil operatsiyani turli xil berilganlar bilan bajaradi. Konveyer sistemalarida har qaysi protsessor vazifaning faqatgina bir qadaminigina bajaradi va navbatdagi qadamni qo’yish uchun natijani keyingi protsessorga yuboradi. Shunday qilib, ma’lumotlar oqimi bilan ishlovchi sistemalar ma’lum bir vazifani bajarishga mo’ljallangan protsessorlar ketma-ketligidan iborat.

Foydalanilgan adabiyotlar:

1. Дж. Макконел

Основы современных алгоритмов

М: Москва. 2001

1. А. Ахо, Дж. Хопкрофт, Дж. Ульман
   Построение и анализ вычислительных алгоритмов
   М.: Мир, 1979
2. А. Ахо, Дж. Хопкрофт, Дж. Ульман
   Структуры данных и алгоритмы
   М.: Вильямс, 2000
3. М. Гэри, Д. Джонсон
   Вычислительные машины и труднорешаемые задачи
   М.: Мир, 1982
4. Емеличев В.А
   Лекции по теории графов
   М.: Наука, 1990
5. Т. Кормен, Ч. Лейзер, Р. Ривест
   Алгоритмы. Построение и анализ
   МЦНМО, Москва, 1999
6. Кристофидес Н
   Теория графов. Алгоритмический подход
   М.: Мир, 1978
7. Л. Ловас, М. Пламмер
   Прикладные задачи теории графов
   М.: Мир, 1998
8. Липский В
   Комбинаторика для программистов
   М.: Мир, 1988
9. Новиков Ф.А
   Дискретная математика для программистов
   СПб.: Питер, 2001
10. Э. Рейнгольд, Ю. Нивергельт, Н. Део
    Комбинаторные алгоритмы
    М.: Мир, 1980

boshlash

N

P[1] M[1] ga qiymatni kiritadi

k=2…p

P[k] M[1] dan qiymatni o’qiydi

Parallel Start

Parallel end

Tamom

P[k] M[k-procloc] ni o’qiydi

P[k] M[k] ga yozadi

Parallel end

procLoc=procLoc*2

Tamom

boshlash

N

P[1] M[1] ga qiymatni kiritadi

procLoc=1

j=1…log p

arallel Start

k= procLoc+1 … 2* procLoc

ha yo’q

boshlash

N

count=N/2

i=1 … log(count)+1

Parallel Start

j=1 … count

P[j] M[2j] ni X ga va M[2j+1] ni Y ga o’qiydi

X >Y

P[j] Х ni M[j] ga yozadi

P[j] Y ni M[j] ga yozadi

Parallel end

procLoc=procLoc*2

Tamom

boshlash

N

Parallel Start

j = 1 … N/log N

P[j] M[l+(j-1)*log N] dan M[j * log N] gacha yacheykalarning maksimum qiymatini ketma-ket algoritm bilan topadi

Parallel end

P[j] M[j] ga topilgan maksimumni yozadi

P[j] Х ni M[j] ga yozadi

X >Y

count=N/2

i=1 … log(count)+1

Parallel Start

j=1 … count

P[j] Y ni M[j] ga yozadi

Parallel end

count=count/2

Tamom

Ha

Yo’q

boshlash

N

Parallel Start

j=1 … N

P[j] M[j] ni Х ga va M[N+1] ni target ga o’qiydi

X=target

j ni M[N+2] ga yozadi

Parallel end

Tamom

boshlash

P

Parallel Start

j=1 to p

P [j] М[(j-l)*(N/p)+l] dan M[j*(N/p)] gacha bo’lgan yacheykalardaketma-ket ikkilangan izlashni bajaradi va X tarkib topgan yacheyka nomerini M[N+2] ga yozadi

Parallel end

Tamom

Parallel Algoritmlar