Oddiy hissoblash algaritimlarini tadbiq etgan holda parallel protsesorlarning samaradorligini baholash

II BOB KO'P YO'NALISHLI REJIMDA MA'LUMOTLARNI TARQATISH STRATEGIYASI

2.1 Ma'lumotni tarqatishda va xatolarni aniqlash

Ma'lumotni tarqatishda va xatolarni aniqlashda yuqori samaradorlikni ta'minlash ushun biz umumiy xotira rejimiga asoslangan ko'p tarmoqli texnologiyani qabul qilamiz. Har bir ip ma'lumotlarni tarqatish va xatolarni aniqlash ushun javobgardir. Taqqoslashdan keyin biron bir xato yuzaga kelsa, oqim, shuningdek, qayta hisoblashni amalga oshirish ushun yangi xato sodir bo'lgan mantiqiy ma'lumotlar blokini qayta tarqatish ushun javobgardir.
Asosiy tugundagi asosiy jarayon diskdagi asosiy xotiraga barcha ma'lumotlarni o'qiydi va ajratilgan ma'lumotlar bloklari soniga qarab iplarni hosil qiladi. Har bir ip oldindan bloklangan har bir ma'lumot blokini jarayonga va uning nusxasini ko'chirish jarayonini qul tugunlariga tarqatish ushun javobgardir. Ma'lumotlar blokini taqsimlashni tugatgandan so'ng, har bir oqim har bir ma'lumot blokining hisoblash natijalarini olishni kutadi. Ma'lumotlar bloki natijalari va uning nusxasi olingandan so'ng, oqim natijalar izchil yoki yo'qligini taqqoslaydi. Agar natijalar izchil bo'lsa, bu hisoblash to'g'ri ekanligini ko'rsatadi va ip natijani sigortalash ushun xotiraga yuboradi. Aks holda, agar natija noto'g'ri bo'lsa, tegishli ma'lumotlar bloki K-bloklarga qaytariladi va qayta hisoblash ishlarini parallel ravishda bajarish ushun K yangi jarayonlarga taqsimlanadi. Faqatgina barcha ma'lumotlar bloklarining natijalari olinib, ularning to'g'riligi aniqlanib, natijalar butun to'plamga qo'shilgandan so'ng, ip yopilishi mumkin edi. Va nihoyat, asosiy jarayon butun natijani disk fayliga saqlash ushun javobgardir.
Tarmoqli tugundagi jarayon va boshqa qul tugunidagi nusxalash jarayoni ma'lumotlar blokini olish, natijani hisoblash va natijani tegishli oqimga qaytarish ushun javobgardir. Jarayon ma'lumotlar blokini oladi va ma'lumotlar bloki natijalarini hisoblashni boshlaydi. Va nihoyat, ma'lumotlar bloki natijasini oldindan tayinlash bo'yicha ipga yuboradi.
Ma'lumotlar bloki to'g'ridan-to'g'ri dastur tugmachasidagi har bir jarayon tomonidan o'qilganda, hisoblash vaqti va tezlanish nisbati quyidagicha beriladi.
bu erda ε - bu har bir hisoblash jarayonidagi qo'shimcha tugatish initsiatsiyalangan tugun.
Yuqori samarali parallel hisoblash muhiti ushun ε juda kichik qiymat, ya'ni n ² ε ≪ 2 T _o'qish + 3 T _r + (1 + 1 / K ) T _c + T _cp , shuning ushun tezlikni nisbati n yaqinlashadi . Yuqoridagi tahlil ma'lumotlar bloklari o'rtasida vazifalarni bajarish bo'yicha aloqa yo'qligi taxminiga asoslangan.
5-rasmko'p oqimli rejimda hisoblash jarayonlari soni bilan tezlikni nisbati o'zgarishini ko'rsatadi. Tezlikni nisbati hisoblash jarayonlari sonining ko'payishi bilan ortadi, ammo jarayonlar soni belgilangan qiymatga yetganda, tezlikni nisbati pasaygan ko'rinadi. Sababi - bu tizim vaqtini, xususan ko'p sonli jarayonlarda sarflaydigan jarayonlarning ortiqcha xarajati.

5-rasm. Ko'p yo'nalishli rejimda tezlikni nisbatlarini tahlil qilish.
Yuqoridagi tahlil shuni ko'rsatadiki, belgilangan parallel hisoblash muhiti ushun ma'lumotlar hajmi va algoritmi oldindan aniqlanganda, tezlikni tejashning maqbul nisbati olinishi mumkin bo'lgan zarur bo'lgan hisoblash jarayoni bo'lishi kerak. Shu bilan birga, ko'p sonli hisoblash jarayonlari bir vaqtning o'zida I / O ga ulanadigan bo'lsa, tizimning ish faoliyatini pasaytirib bo'lmaydigan hollarda, I / O muammosi e'tiborga olinishi kerak.

2.2 Tajribalar va tahlillar

Tajribalar kichik miqyosli klaster tizimida o'tkazildi. Har bir tugun Intel XeonE5645, 2,8 Gigagertsli, to'rt yadroli protsessor va 8 Gb xotiraga ega. Tugunlar Gigabit Ethernet ulanishini qabul qiladi. Asosiy / qul parallel parallel hisoblash modeli qabul qilingan. Birlamchi tugun ma'lumotlarni tarqatish va qayta ishlash natijalari ushun javobgardir. Dastur muhiti GDAL 1.6.1, OpenMP 1.5.4, GCC 4.4.7 va MPICH2-ga ega. Sinov ma'lumotlari sifatida ikki xil ma'lumotlar to'plamidan foydalaniladi: kichik ma'lumotlarning hajmi 1,61 Gb, katta ma'lumotlar to'plami esa 6,9 Gb. Ma'lumot turi suzuvchi nuqta va rasm turi TIFF formatidir.
Ushbu hujjatda taklif qilingan PR samaradorligini tekshirish ushun tajriba DTA qiyalik algoritmini qo'llaydi. Gradient (nishab) - bu sirt birligining tik sekinlik darajasi; vertikal balandlikning gorizontal masofaga, qiyalik yuzasiga nisbati qiyalik deyiladi.
Ushbu hujjatda biz master / qul rejimi bilan parallel ravishda qayta hisoblash algoritmini amalga oshirdik, unda bosh tugun ma'lumotlarni tarqatish, taqqoslash natijalari va sinish va diskka saqlash ushun javob beradi, va qul tugun bilan vazifalarni hisoblash ushun javobgardir. ma'lumotlar bloki. Mustaqil ravishda tarqatish usulida amalga oshiriladigan jarayonlar soni bilan umumiy hisoblash vaqtini ko'rsatadi. Biz faqat to'liq hisoblash protsedurasida jarayonning ishdan chiqishini aniqlaymiz va muvaffaqiyatsiz jarayonni qayta hisoblash natijasi to'rtta qayta hisoblash jarayoni bilan yakunlanadi, bunda dastlabki ma'lumotlar blokini to'rtta pastki bloklarga bo'lish kerak.

6-rasm. Ma'lumotni mustaqil tarqatish va bajarilmagan protsess ushun to'rtta qayta hisoblash jarayoni bilan umumiy hisoblash vaqti.
Biz ko'paytirishning ikki tomonlama mexanizmini qabul qildik, bunda asosiy jarayon ma'lumotlar blokini ikki marta tarqatadi: biri jarayonga taqsimlanadi, ikkinchisi esa uni nusxalash jarayoniga. natijalarni ikkita DEM ma'lumotlar to'plamlari bilan ko'rsatadi, biri 1,6 Gb hajmli, boshqasi esa 6,9 Gb. ko'rsatilgandek, umumiy hisoblash vaqti jarayonlar sonining ko'payishi bilan kamayadi (ma'lumotlar bloklari). Jarayonning etishmovchiligi yuzaga kelganligi sababli, qayta hisoblash protsedurasini bajarish ushun atigi to'rtta yangi jarayon boshlanadi; shu sababli, tizimning ortiqcha xarajatlari unchalik katta emas. Faqat asosiy tugundagi asosiy jarayon ma'lumotlarni tarqatish, natijalarni taqqoslash, natijalarni birlashtirish va boshqalar ushun javob beradi va shu qadar bandki, qul tugunlaridan hisoblash jarayonlari aloqani kutishi kerak. Shunday qilib, hisoblashning umumiy vaqti tezda kamaymaydi va hisoblash ushun javobgar bo'lgan jarayonlar soni ma'lum bir qiymatga yetganda, jarayonlar yoki ma'lumotlar bloklari soni bilan birgalikda vaqt asta-sekin o'sib boradi. Masalan, 1-ma'lumotlar to'plamida 32-sonli jarayon eng kichik vaqtni oladigan muhim nuqtadir. Jarayon soni 32 dan oshganda, umumiy vaqt asta-sekin o'sib boradi. 2-ma'lumotlar bazasi ushun kritik nuqta 64 dir.
Yuqoridagi tajriba bosh tugundagi asosiy jarayonga ma'lumotlarni ketma-ket tarqatish va hisoblash jarayoni va ikkita nusxalash jarayonidan ikkita natijaning to'g'riligini olish va taqqoslash imkonini beradi. Afzalligi shundaki, ma'lumotlar diskdan xotiraga tartibda o'qiladi, bu I / O ziddiyatiga olib kelmaydi va noqulay tomoni shundaki, qul tugunidagi hisoblash jarayonlari ma'lumotlar tarqalishini kutadi. Quyidagi tajribalar asosiy jarayonda ma'lumotlar bloklarini parallel ravishda taqsimlashi, natijalarning to'g'riligini taqqoslashi va qayta hisoblash jarayoni boshlangan yoki qilinmaganligini aniqlashi mumkin bo'lgan ko'p tarmoqlarni qo'llaydi. Asosiy jarayondagi iplar soni bilan umumiy hisoblash vaqtini ko'rsatadi. Muvaffaqiyatsiz jarayon ushun qayta hisoblash protsedurasini bajarish ushun to'rtta jarayon boshlanadi. ko'rsatilgandek, ikkita ma'lumotlar to'plami ushun iplar sonining ko'payishi bilan vaqt kamayadi. Sababi shundaki, har bir ma'lumotlar blokini taqsimlash, taqqoslash natijalari va parallel ravishda qayta hisoblash jarayonini boshlash bilan shug'ullanadigan ko'plab mavzular mavjud. Ko'p tarmoqli texnikadan foydalangan holda parallel ravishda taqsimlash ma'lumotni mustaqil tarqatish bilan taqqoslaganda ma'lumotlarni tarqatishda va xatolarni aniqlashda yuqori samaradorlikni ta'minlaydi.

7-rasm. Parallel ravishda tarqatish va muvaffaqiyatsiz jarayon ushun to'rtta qayta hisoblash jarayonlarining umumiy soni.
Shubhasiz, parallel ravishda ma'lumot tarqatishda umumiy hisoblash vaqti mustaqil ma'lumot tarqatish vaqtiga qaraganda ancha past. Bundan tashqari, ma'lumotlarni parallel ravishda tarqatish vaqti mustaqil ma'lumotlar tarqatish bilan taqqoslanadigan iplar soniga qarab tezda kamayadi.Har bir jarayon parallel blokirovka qilingan fayl tizimidan foydalangan holda to'g'ridan-to'g'ri diskdan ma'lumot blokini o'qiyotganda, jarayonlar soni bilan tezkor hisoblash tezligi kamayadi. Ma'lumotni o'qish barcha jarayonlar bilan bir vaqtda amalga oshirilganligi va umumiy vaqt asosan hisoblash vaqti bilan aniqlanganligi sababli, hisoblashning umumiy vaqti tezda pasayishi kerak, bunda ma'lumotlar soni ko'payishi bilan ma'lumotlar bloki kichrayadi har bir jarayon tomonidan to'g'ridan-to'g'ri diskdan ma'lumotlarni o'qish bilan bu vaziyatni ko'rsatadi.

8-rasm. Har bir jarayon bo'yicha diskdan ma'lumotlarni to'g'ridan-to'g'ri o'qish va muvaffaqiyatsiz jarayon ushun to'rtta qayta hisoblash jarayonlarining umumiy soni.

Tekshirish punkti yordamida an'anaviy qayta hisoblash bilan taqqoslaganda, bizning PR xatolarni bir vaqtning o'zida tiklash ushun yanada nozik granularity pastki bloklarini oladi. Ammo, ehtimol, nazorat nuqtasi usuli xatolarni tiklash ushun nozik taneli bo'lish strategiyasini ham qabul qilishi mumkin. Oddiy parallel qayta hisoblash strategiyasi, oddiy qayta hisoblash strategiyasi va 2-ma'lumotlar to'plamidan foydalangan holda PRni qayta hisoblash strategiyamizni taqqoslaydi. Oddiy qayta hisoblash strategiyasida biz xato yuz beradigan blok to'g'ridan-to'g'ri taqsimlanadigan strategiyani ishlab chiqamiz. ma'lumotlar blokini pastki bloklarga bo'lmasdan yana hisoblash ushun hisoblash jarayoniga. Oddiy parallel ravishda qayta hisoblash strategiyasida xatolar bo'lgan ma'lumotlar bloki bir nechta hisoblash jarayonlariga tarqatish orqali bir vaqtning o'zida hisoblash ushun bir necha kichik bloklarga bo'linadi. Bundan tashqari, PR-ni qayta hisoblash usulimizda ma'lumotlar blokini to'ldirish shart emas; ammo to'liq hisoblash paytida xatoning sababini aniqlash ushun qism natijasi asosiy jarayonga yuboriladi. Ma'lumotlar blokining har bir qismi mantiqiy pastki blok sifatida ko'rib chiqilishi mumkin. Agar mantiqiy pastki blokda xato bo'lsa, ushbu pastki blokda yuzaga kelgan xatoni tuzatish ushun darhol qayta hisoblash jarayoni boshlanadi. PR usulimizda hisoblash, xatolarni aniqlash va qayta hisoblash jarayoni deyarli bir vaqtning o'zida bajariladi; shu sababli, butun vaqt juda qisqartiriladi.

9-rasm. Uchta hisoblash usullarini taqqoslash.
Hisoblash jarayonlarining soni oshib borganda, ma'lumotlar blokining hajmi kichiklashadi va qayta hisoblash ushun ajratilgan sub-ma'lumotlar bloklarining hajmi dastlabki ma'lumotlar bloklaridan biri bilan aniq farq qilmaydi. Shunday qilib, sub-blokni qayta hisoblash vaqti va ma'lumotlar blokining to'g'ridan-to'g'ri hisoblash vaqti teng ravishda yaqinlashadi. Shuning ushun oddiy hisoblashning hisoblash vaqti oddiy parallel hisoblashdan aniqroq bo'lmaydi. PR algoritmi yanada samaraliroq natijalarga erishadi, xususan, jarayonlar soni kichikroq bo'lganda, har bir ma'lumotlar blokining kattaligi katta, shuning ushun pastki blokning kattaligi ham katta va PR usulida bir-biriga mos keladigan strategiya sezilarli darajada kamayadi. ko'rsatilganidek, qayta hisoblash vaqti.

2.3 Algoritmlаr, ulаrning хоssаlаri. Bеrilish usullаri vа strukturаlаri

Yuqorida qayd qilganimizdek, qo‘yilgan biror masalani EHMda yechish ushun, avval uning matematik modelini, keyin algoritmini va programmasini tuzish kerak bo‘ladi. Algoritm so‘zi va tushunchasi IX asrda yashab ijod etgan buyur alloma Muhammad al-Xorazmiy nomi bilan uzviy bog‘liq. Algoritm so‘zi Al-Xorazmiy nomini Yevropa olimlari tomonidan buzib talaffuz qilinishidan yuzaga kelgan. Al-Xorazmiy birinchi bo‘lib o‘nlik sanoq sistemasining tamoyillarini va undagi to‘rtta amallarni bajarish qoidalarini asoslab bergan.
Algoritmning asosiy xossalari.Algoritmning 5-ta asosiy xossasi bor:
Diskretlilik (Cheklilik). Bu xossaning mazmuni algoritmlarni doimo chekli qadamlardan iborat qilib bo‘laklash imkoniyati mavjudligida. Ya’ni uni chekli sondagi oddiy ko‘rsatmalar ketma-ketligi shaklida ifodalash mumkin. Agar kuzatilayotgan jarayonni chekli qadamlardan iborat qilib qo‘llay olmasak, uni algoritm deb bo‘lmaydi. Tushunarlilik. Biz kundalik hayotimizda berilgan algoritmlar bilan ishlayotgan elektron soatlar, mashinalar, dastgohlar, kompyuterlar, turli avtomatik va mexanik qurilmalarni kuzatamiz. Ijrochiga tavsiya etilayotgan ko‘rsatmalar, uning ushun tushinarli mazmunda bo‘lishi shart, aks holda ijrochi oddiygina amalni ham bajara olmaydi. Undan tashqari, ijrochi har qanday amalni bajara olmasligi ham mumkin. Har bir ijrochining bajarishi mumkin bo‘lgan ko‘rsatmalar yoki buyruqlar majmuasi mavjud, u ijrochining ko‘rsatmalar tizimi (sistemasi) deyiladi. Demak, ijrochi ushun berilayotgan har bir ko‘rsatma ijrochining ko‘rsatmalar tizimiga mansub bo‘lishi lozim.
Ko‘rsatmalarni ijrochining ko‘rsatmalar tizimiga tegishli bo‘ladigan qilib ifodalay bilishimiz muhim ahamiyatga ega. Masalan, quyi sinfning a’lochi o‘quvchisi "son kvadratga oshirilsin" degan ko‘rsatmani tushinmasligi natijasida bajara olmaydi, lekin "son o‘zini o‘ziga ko‘paytirilsin" shaklidagi ko‘rsatmani bemalol bajaradi, shunki u ko‘rsatma mazmunidan ko‘paytirish amalini bajarish kerakligini anglaydi. Aniqlik. Ijrochiga berilayotgan ko‘rsatmalar aniq mazmunda bo‘lishi zarur. Shunki ko‘rsatmadagi noaniqliklar mo‘ljaldagi maqsadga erishishga olib kelmaydi. Odam ushun tushinarli bo‘lgan "3-4 marta silkitilsin", "5-10 daqiqa qizdirilsin", "1-2 qoshiq solinsin", "tenglamalardan biri yechilsin" kabi noaniq ko‘rsatmalar robot yoki kompyuterni qiyin ahvolga solib qo‘yadi. Bundan tashqari, ko‘rsatmalarning qaysi ketma-ketlikda bajarilishi ham muhim ahamiyatga ega. Demak, ko‘rsatmalar aniq berilishi va faqat algoritmda ko‘rsatilgan tartibda bajarilishi shart ekan. Ommaviylik. Har bir algoritm mazmuniga ko‘ra bir turdagi masalalarning barchasi ushun ham o‘rinli bo‘lishi kerak. ya’ni masaladagi boshlang‘ich ma’lumotlar qanday bo‘lishidan qat’iy nazar algorim shu xildagi har qanday masalani yechishga yaroqli bo‘lishi kerak. Masalan, ikki oddiy kasrning umumiy mahrajini topish algoritmi, kasrlarni turlicha o‘zgartirib bersangiz ham ularning umumiy mahrajlarini aniqlab beraveradi. Yoki uchburchakning yuzini topish algoritmi, uchburchakning qanday bo‘lishidan qat’iy nazar, uning yuzini hisoblab beraveradi.
Natijaviylik. Har bir algoritm chekli sondagi qadamlardan so‘ng albatta natija berishi shart. Bajariladigan amallar ko‘p bo‘lsa ham baribir natijaga olib kelishi kerak. Chekli qadamdan so‘ng qo‘yilgan masala yechimga ega emasligini aniqlash ham natija hisoblanadi. Agar ko‘rilayotgan jarayon cheksiz davom etib natija bermasa, uni algoritm deb atay olmaymiz. Algoritmning tasvirlash usullari .Yuqorida ko‘rilgan misollarda odatda biz masalani yechish algoritmini so‘zlar va matematik formulalar orqali ifodaladik. Lekin algoritm boshqa ko‘rinishlarda ham berilishi mumkin. Biz endi algoritmlarning eng ko‘p uchraydigan turlari bilan tanishamiz.
1.Algoritmning so‘zlar orqali ifodalanishi. Bu usulda ijrochi ushun beriladigan har bir ko‘rsatma jumlalar, so‘zlar orqali buyruq shaklida beriladi.
2. Algoritmning formulalar bilan berilish usulidan matematika, fizika, kimyo kabi aniq fanlardagi formulalarni o‘rganishda foydalaniladi. Bu usulni ba’zan analitik ifodalash deyiladi.
3. Algoritmlarning grafik shaklida tasvirlanishida algoritmlar maxsus geometrik figuralar yordamida tasvirlanadi va bu grafik ko‘rinishi blok-sxema deyiladi.
4. Algoritmning jadval ko‘rinishda berilishi. Algoritmning bu tarzda tasvirlanishdan ham ko‘p foydalanamiz. Masalan, maktabda qo‘llanib kelinayotgan to‘rt xonali matematik jadvallar yoki turli xil lotereyalar jadvallari. Funksiyalarning grafiklarini chizishda ham algoritmlarning qiymatlari jadvali ko‘rinishlaridan foydalanamiz. Bu kabi jadvallardan foydalanish algoritmlari sodda bo‘lgan tufayli ularni o‘zlashtirib olish oson. Yuqorida ko‘rilgan algoritmlarning tasvirlash usullarining asosiy maqsadi, qo‘yilgan masalani yechish ushun zarur bo‘lgan amallar ketma-ketligining eng qulay holatinni aniqlash va shu bilan odam tomonidan programma yozishni yanada osonlashtirishdan iborat. Aslida programma ham algoritmning boshqa bir ko‘rinishi bo‘lib, u insonning kompyuter bilan muloqotini qulayroq amalga oshirish ushun mo‘ljallangan.
Blok-sxemalarni tuzishda foydalaniladigan asosiy sodda geometrik figuralar quyidagilardan iborat:
Blok-sxemalar bilan ishlashni yaxshilab o‘zlashtirib olish zarur, shunki bu usul algoritmlarni ifodalashning qulay vositalaridan biri bo‘lib programma tuzishni osonlashtiradi, programmalash qobiliyatini mustahkamlaydi. Algoritmik tillarda blok - sxemaning asosiy strukturalariga maxsus operatorlar mos keladi Shuni aytish kerakni, blok-sxemalardagi yozuvlar odatdagi yozuvlardan katta farq qilmaydi.Misol sifatida ax²+bx+c=0 kvadrat tenglamani yechish algoritmining blok-sxemasi quyida keltirilgan.

1-rasm. Kvadrat tenglamani yechish algoritmi
Chiziqli algoritmlar.Har qanday murakkab algoritmni ham uchta asosiy struktura yordamida tasvirlash mumkin. Bular ketma-ketlik, ayri va takrorlash strukturalaridir. Bu strukturalar asosida chiziqli, tarmoqlanuvchi va takrorlanuvchi hisoblash jarayonlarining algoritmlarini tuzish mumkin. Umuman olganda, algoritmlarni shartli ravishda quyidagi turlarga ajratish mumkin:

1. 
   chiziqli algoritmlar;
   
2. 
   tarmoqlanuvchi algoritmlar;
   
3. 
   takrorlanuvchi yoki siklik algoritmlar;
   
4. 
   ichma-ich joylashgan siklik algoritmlar;
   
5. 
   rekurrent algoritmlar;
   
6. 
   takrorlanishlar soni oldindan no’malum algoritmlar;
   
7. 
   ketma-ket yaqinlashuvchi algoritmlar.
   

Faqat ketma-ket bajariladigan amallardan tashkil topgan algoritmlarga-chiziqli algoritmlar deyiladi. Bunday algoritmni ifodalash ushun ketma-ketlik strukturasi ishlatiladi. Strukturada bajariladigan amal mos keluvchi shakl bilan ko‘rsatiladi. Chiziqli algoritmlar blok-sxemasining umumiy strukturasini quyidagi ko‘rinishda ifodalash mumkin:

2-rasm. Chiziqli algoritmlar blok - sxemasining umumiy strukturasi