|
Mavzu: Parallel algoritmlar va ularning ishlab chiqish texnalogiyasi
|
| Sana | 27.06.2023 | | Hajmi | 61.09 Kb. | | #75903 |
Bog'liq paralel algoritmlar va ularning ishlab chiqish texnalogiyasi 01 material 2, Менгниқулова Нафиса, a284ebd1-19b7-4cd2-8b80-5e390d5594d5, JHNbX09iRiksCw6ZefA9wg, axborotning-korinishi-xususiyatlari-va-turlari, 5-lekciya, 1-lekciya (3), E.N.Pertsik. Geourbanistika, Simsiz aloqa tizimlari
Mavzu: Parallel algoritmlar va ularning ishlab chiqish texnalogiyasi
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.
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.
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.
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
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:
Tezlanish koeffitsiyenti
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:
Raqobatli o’qish / raqobatli yozish (CRCW);
Raqobatli o’qish / maxsus yozish (CREW);
Maxsus o’qish / raqobatli yozish (ERCW);
Maxsus o’qish / maxsus yozish (EREW);
Oddiy parallel operatsiyalar
Endi ikkita elementar operatsiyani ko’ramiz:
Kiruvchi ma’lumotlarni protsessorlarga taqsimlash;
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. (pBirinchi 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 pKo’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
Dunyoda axborot - kommunikatsiya texnologiyalarining rivojlanishida
signallarni tiklash, raqamli ishlov berish masalalarini yechishda ko„p yadroli
arxitektura asosida yaratilgan uzluksiz algoritmlardan foydalanish va optimal
yechimlar topish uchun unumdorligi yuqori, samarali uzluksiz algoritmlar ishlab
chiqish muhim ahamiyat kasb etmoqda. Splaynlar bo„lakli funksiyalar sinfi sifatida hisoblashlarning kamligi, raqamli ishlash algoritmlarining moslashuvchanligi,
optimal differensial va ekstremal xossalari, parametrlarni hisoblashning soddaligi,
xatoliklarning yaxlitlashga ta‟sir darajasining pastligi tufayli signallarga raqamli
ishlov berishning uzluksiz algoritmlarini yaratishda matematik vosita hisoblanadi.
Ushbu yo„nalishda dunyoning rivojlangan mamlakatlarida, jumladan AQSH,Rossiya
federatsiyasi, Xitoy, Janubiy Koreya, Germaniya va Yaponiya davlatlarida
signallarga raqamli ishlov berishning uzluksiz texnologiyalari hamda signallarni
tahlil qilish va tiklash masalalarida uzluksiz qayta ishlash va splayn funksiyalar
usullarini takomillashtirish ustida jadal tadqiqot ishlari olib borilmoqda.
Ko„p yadroli arxitektura asosida parallel algoritmlarni va dasturiy vositalarni
ishlab chiqish xususan, kompyuterning tarqatilgan va umumiy xotira turlarida parallel
texnologiyalari yaratish muammolari jahon va O„zbekiston ilmiy adabiyotida
ancha keng yoritilgan.
ADABIYOTLAR TAHLILI VA METODOLOGIYA
Dunyoda uzluksiz algoritmlar rivojining zamonaviy bosqichida murakkab
jarayonlarni tez va sifatli tahlil qilish va ulkan hajmdagi axborotni real vaqtda qayta
ishlash tezligini oshirish usullari va algoritmlarini ishlab chiqish hamda uzluksiz
ishlov berish texnologiyalari asosida zamonaviy protsessorlarning hisoblash
jarayonlarini tezkorligini oshirish masalalari o„rganilmoqda. Hisoblash jarayonidagi
buyruqlarni konveyrli va uzluksiz shakllantirish, katta hajmdagi buyruqlarni amalga
oshirishning yangi texnologiyalarini yaratish asosida tezkorlikning sifatli o„sish
ko„rsatkichiga erishish mumkin. SHu kabi tezkor hisoblash usul va algoritmlarni
takomillashtirish va dasturiy vositalarni ishlab chiqish dolzarb masalalardan biri
hisoblanadi.
Respublikamizda ham signallarga raqamli ishlov berish masalalarini yechishda
uzluksiz algoritmlar yaratish va ishlov berish jarayonlarini ko„p yadroli arxitektura
asosida amalga oshirishga qaratilgan ilmiy tadqiqot ishlari olib borilmoqda.
Mazkur vazifalarni amalga oshirishda, jumladan, signallarga raqamli ishlov
berishda kubik splaynlar asosida ko„p yadroli protsessorlar uchun uzluksiz
algoritmlar yaratish, ma‟lumotlarga tezkor ishlov berish, signallarni raqamli ishlash
algoritmlarining samaradorligini oshirish va signallarning lokal xususiyatlarini
aniqlashga mo„ljallangan usul, algoritm, apparat va dasturiy vositalarni ishlab chiqish
muhim vazifalardan biri hisoblanadi.
O„zbekiston Respublikasi Prezidentining 2017 yil 7 fevraldagi PF-4947-son
«O„zbekiston Respublikasini yanada rivojlantirish bo„yicha Harakatlar strategiyasi ACADEMIC RESEARCH IN EDUCATIONAL SCIENCES VOLUME 2 | ISSUE 3 | 2021
ISSN: 2181-1385
Scientific Journal Impact Factor (SJIF) 2021: 5.723
DOI: 10.24411/2181-1385-2021-00446
Academic Research, Uzbekistan 630 www.ares.uz
to„g„risida» gi va 2018 yil 19 fevraldagi PF-5349-son «Axborot texnologiyalari va
kommunikatsiyalari sohasini yanada takomillashtirish chora-tadbirlari to„g„risida» gi
Farmonlari,2018 yil 7 martdagi Vazirlar Mahkamasining «Aloqa, axborotlashtirish va
telekommunikatsiya xizmatlari sifatini yanada yaxshilashga doir chora-tadbirlar
to„g„risida» gi 185-sonli qarori hamda, mazkur faoliyatga tegishli boshqa me‟yoriy-
huquqiy hujjatlarda belgilangan vazifalarni amalga oshirishga ushbu maqola tadqiqoti
ma‟lum darajada xizmat qiladi. Signallarni raqamli ishlashning parallel usullari va algoritmlari, splayn
koeffitsientlarini nuqtali formulalar yordamida parallel hisoblash algoritmlari, skalyar
va vektorli protsessorlarning ishlash usullari o„rganib chiqilgan. Signallarni raqamli
ishlashning ko„p yadroli arxitekturaga mo„ljallangan parallel algoritmlari yaratilgan.
Parabolik splaynlar bilan yaqinlashish koeffitsientlarini hisoblash metodlarini tahlil
qilish shuni ko„rsatdiki,splayn funksiyalarning tajriba natijalari asosida qurish
muammosi – koeffitsientlarni hisoblash masalasiga olib keladi. Splaynni ifodalash
uchun formuladagi koeffitsientlarning qiymatlari na‟munalar funksiyasi va tugunlar
orasidagi masofalar ifodasi bilan berilgan. Deffekti2d bo„lgan splaynlar uchun
algoritm mutlaqo barqaror, lekin1d da silliqlovchi rekurent splaynlar
chegaralangan sohalar uchun barqaror, interpolyasion splaynlar esa barqaror emas.
Kubik splaynlar juda kata matematik afzallikka ega.Ular berilgan nuqtalarni
interpolyatsilovchi va kvadrat bilan integrallanuvchi ikkinchi hosilasi mavjud bo„lgan
barcha funksiyalar ichida minimal yassilik xususiyatiga ega bo„lgan yagona
funksiyadir.
Amaliyotda1d defektli kubik bazisli splaynlar ancha keng tarqalgan.
Bunday splaynlar 1, ii xx oraliqlarning har birida kubik ko„p hadlar bilan mos
keladi. f (x) funksiyasini yaqinlashtirish uchun kubik bazisli splaynlar to„rtta juft
ko„paytmalarning yig„indisi ko„rinishida tasvirlanadi. Bundan f (x) funksiyasini
bazisli splaynlar orqali yaqinlashtirish formulasini quyidagi ko„rinishda yozish
mumkin:
Splaynlarni hisoblash matematikasida keng qo„llanilayotganligi sabablaridan
yana bir ko„rinishi,
ularning qiymatlarini kompyuterlarda hisoblashning qulayligi va ular yordamida
interpolyasiyalash kabi jarayonlarning keng sinfdagi to„rlar uchun yaxshi
yaqinlashishligidadir. Ko„p yadroli protsessorda splayn-funksiyani hisoblashning
parallel usuli quyidagi ketma-ketliklardan iborat.YUqorida keltirilgan (2) formulada
to„rtta juft ko„paytmalarni alohida protsessor yadrolarida parallel hisoblashi uchun
massiv ko„rinishiga keltirib olinadi:
Protsessorning hisoblash jarayonining bir taktidan keyin to„rtta massivni yig„indilari
parallel ravishda hisoblanadi. Ko„p yadroli protsessorda kubik bazisli splaynlar asosida parallel algoritmlarni
amalga oshirish tuzilmasini ishlab chiqish,ko„p yadroli protsessorlarga mo„ljallangan
parallel algoritmlarni Open MP texnologiyasi yordamida tashkil qilish usullari,
splayn usullar yordamida ko„p yadroli protsessorlar uchun seysmik signallarni
raqamli ishlashning parallel algoritmlarini amalga oshiruvchi dasturiy majmua
yaratish masalalari ko„rib chiqilgan. Bazis splaynlarni parallellashtirish jarayonlarini
modellashtirishning dasturiy majmuasini asosiy maqsadi – ko„p yadroli
protsessorlarda splayn usuli yordamida signallarga parallel ishlov berishdir.
Dasturiy majmua bitta dasturiy paket ko„rinishida rasmiylashtirilgan bo„lib,
belgilangan parametrlar bilan o„zaro bog„lanlangan qism-dasturlar (protsedura)dan
tashkil topgan. Dasturiy paketning hamma protseduralari vektorlashtirish usulida
ishlaydi. Bu esa tizimning ishlash samaradorligini oshirishga va natijalarni yanada yaxshi bo„lishiga olib keladi.Dasturiy majmuaning parallellashtirish bo„limi
protsessorning yadrolar sonini kiritgan holda N ta hajmga ega kiruvchi signalga
ketma-ket va parallel ishlov berish uchun sarflangan vaqtni aniqlash hamda bir
o„lchovli signalni approksimatsiyalash natijalarini diagramma ko„rnishida tahlil qilish
imkoniyatlarini beradi. YAratilgan dasturiy majmuaning umumiy tuzulmasi
quyidagicha keltirilgan ya„ni izlanishlarga asosan tuzilma 2- qismdan tashkil topgan.
1- qism ketma-ket hisoblash, 2- qism parallel hisoblash deb nomlangan. 1- qismda
“Bir o„lchovli splayn parametrlarini hisoblash dasturi” va “Xatoliklarni baholash
dasturi” joylashgan. 2- qismda “Ko„p yadroli protsessorlarda parallel algoritmlarni
amalga oshirish dasturi” va “Open MP texnologiyasi asosida parallel algoritmlarni
amalga oshirish dasturi” joylashgan.Bundan ko„rinib turibdi-ki Open MP
texnologiyasi asosida parallel algoritmlarni amalga oshirish dasturini C++ dasturlash
tilida, hisoblash jarayonlarini vektorlashtirishni va signallarini raqamli ishlab chiqish
jarayonini JAVA dasturlash tilida ishlab chiqsa bo„ladi.
Demak parallel oqimlar yordamida hisoblashlarni parallellashtirishning mavjud
kutubxonasi protsedura va funksiyalardan foydalanishga nisbatan taklif etilgan
algoritmlardan foydalanish samaradorlikni oshirish imkoni ni berar ekan. Ushbu
mulohazalarni inobatga olib, parallelsikl jarayonlarini tashkil qilish va to„liq
nazoratga olish uchun JAVA dasturlash tilida faqat splayn-funksiya usullari uchun
maxsus protseduralar yaratildi va tizimli dastur sifatida kutubxonaga joylashtirildi.
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.
Misol parallel algoritm
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
Xulosa
Xulosa qilib shuni ta‟kidlab aytish mumkin, ko„p yadroli protsessorlarda
signallarga raqamli ishlov berishda splayn-funksiyalar usullari shunisi bilan
qulayki,ular har qanday signalni bazisli funksiya koeffitsiyentiga ko„paytirish va
ko„paytmalarni jamlash ko„rinishida tasvirlash imkonini beradi.Bu esa ko„p yadroli
arxitektura yordamida hisoblashlarni samarali algoritmlarini yaratish imkonini beradi.
Open MP dasturiy vositasi yordamida ko„p yadroli protsessor yadrolariga va maxsus
xotira turlariga murojaatlarni to„g„ri yo„lga qo„yish mumkin. JAVA dasturlash tilida
esa parallel hisoblash jarayonlarini tashkil qilish uchun Thread, Runnable va Stream
sinflari mavjud bo„lib, parallel oqimlar bajarilishiga ajratilgan vaqtlarni nazorat qilish
va optimallashtirish imkonini beradi.
Splaynning parametrlarini topishda lokal hisoblash formulalaridan foydalanish
algebraik tenglamalar sistemasini yechishdan xalos qiladi.Lokal formulalar usuli
boshqa usullarga nisbatan hisoblashlar sonini keskin kamaytirish imkonini
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:
Дж. Макконел
Основы современных алгоритмов
М: Москва. 2001
А. Ахо, Дж. Хопкрофт, Дж. Ульман
Построение и анализ вычислительных алгоритмов
М.: Мир, 1979
А. Ахо, Дж. Хопкрофт, Дж. Ульман
Структуры данных и алгоритмы
М.: Вильямс, 2000
М. Гэри, Д. Джонсон
Вычислительные машины и труднорешаемые задачи
М.: Мир, 1982
Емеличев В.А
Лекции по теории графов
М.: Наука, 1990
Т. Кормен, Ч. Лейзер, Р. Ривест
Алгоритмы. Построение и анализ
МЦНМО, Москва, 1999
Кристофидес Н
Теория графов. Алгоритмический подход
М.: Мир, 1978
Л. Ловас, М. Пламмер
Прикладные задачи теории графов
М.: Мир, 1998
Липский В
Комбинаторика для программистов
М.: Мир, 1988
Новиков Ф.А
Дискретная математика для программистов
СПб.: Питер, 2001
Э. Рейнгольд, Ю. Нивергельт, Н. Део
Комбинаторные алгоритмы
М.: Мир, 1980
|
| |
