Oddiy hissoblash algaritimlarini tadbiq etgan holda parallel protsesorlarning samaradorligini baholash

I BOB Oddiy hissoblash algaritimlari

Raqamli tahlil (DTA) - raqamli balandlik rejimi (DEM) asosida erning atributlarini hisoblash va xususiyatlarni ajratib olishning raqamli axborotni qayta ishlash texnologiyasi. ¹ DEMs aniq va aniqlik bilan 5-10 yil oldin 1000 m qarorlardan bugungi kunda ko'plab joylarda 1-5 m qarorlarga o'tdi. Yuqori aniqlik va fayl o'lchamlari natijasida past o'lchamlari va kichikroq DEMlar ushun qiyalik, profil egriligi va gidrologik er sathining parametrlari kabi er sathining ko'plab parametrlari yuqori aniqlik va katta hajmga nisbatan qo'llanilganda vaqtni talab qiladigan bo'lib qoladi. ma'lumotlar hajmi. Demak, parallel hisoblashlar geografik informatika fanining asosiy vositasiga aylandi. 
Yuqori samaradorlikdagi geo-hisoblashlar taqsimlangan jarayonlar bo'yicha hisob-kitoblarni bajarish ushun ko'p vaqt talab etadi. Shu bilan birga, tizimning ishonchliligi asosiy kalitga aylanadi, o'n minglab protsessorlarga ega klasterning barqarorligi doimiy ravishda tarmoq, xotira, protsessorlar va operatsion tizimlar kabi katta miqdordagi qo'shimcha qurilmalar va dasturiy ta'minotning ishdan chiqishiga olib keladi. Shuning ushun nosozliklarga bardoshlik ishonchli hisoblashlarning zarur tarkibiy qismiga aylandi.
Katta o'lchovli ilmiy hisoblash ko'proq hisoblash vazifalarini olib keladi, shunda ish vaqti kichik o'lchamdagi dasturlarga qaraganda uzoqroq bo'ladi. Shu bilan birga, ishlamay qolish xavfi yuqori bo'ladi va bu ko'p vaqtni va saqlashni o'z ichiga olgan holda ko'plab resurs chiqindilariga olib kelishi mumkin. Tekshiruv punkti ^4- xato bardoshliligi ushun keng qo'llaniladi. Asosiy g'oya shundan iboratki, jarayonning asosiy pozitsiyasini qayta ishlashda hozirgi holat va ma'lumotlar barqaror saqlash ushun saqlanishi kerak. Ko'p sonli nazorat punktlari vaqti-vaqti bilan parallel tizimda saqlanadi. Jarayon bajarilmasa, ushbu jarayon bilan bog'liq barcha jarayonlar hisoblashni qayta boshlash ushun oxirgi nazorat punktiga qaytarilishi kerak. Nazorat-o'tkazish punktlarining ishlashi ma'lumotlarning katta / katta hajmdagi ulanishiga olib keladi, bu esa ishlashning qiyinlashishiga olib keladi.
Qayta tiklash jarayonini tezlashtirish ushun Yang va boshqalar. Parallel qayta hisoblash asosida "xato-bardoshli parallel algoritm" deb nomlangan yangi darajadagi xatolarga bardoshli sxemasini taqdim etdi. Biroq, usul asosan parallel ravishda qayta hisoblash amalga oshiriladimi yoki yo'qmi ta'sir ko'rsatadigan dasturning ko'rsatma darajasiga qo'llaniladi. Agar dasturning ishlamay qolgan qismi qayta ishlamasa, u holda parallel qayta hisoblash tugallanmaydi; shuning ushun qayta hisoblash ishlashi ta'minlanmaydi. Bundan tashqari, Yang va boshqalar. shuningdek dasturlarni taqsimlash va ish yukini qayta taqsimlashni hal etuvchi takomillashtirilgan yondashuvni taklif qildi. Yuqoridagilardan kelib chiqqan holda, ushbu yondashuvlar ma'lumotni ajratishdan ko'ra dasturni ajratish bilan bog'liq asosiy masalalarni muhokama qildi. Parallel DTA ushun parallel qayta hisoblash usuli birinchi navbatda Miao va boshqalar tomonidan taqdim etilgan. zaxira hisoblash mexanizmining samaradorligini oshirish. Ular xatolarni aniqlashning ortiqcha xarajatlarini kamaytirish ushun ma'lumotlar bloklarini hisoblashda xatolar mavjudligini yoki yo'qligini tekshirish ushun bir nechta mavzular strategiyasini o'z ichiga olgan yaxshilangan xatolarni aniqlash sxemasini taqdim etdilar. qo'shiq va boshqalar. nosozliklarga bardoshli parallel hisoblash algoritmi amalga oshirilib, DTA ushun nazorat qilish texnikasini qo'lladi ortiqcha mexanizmini qabul Bu jihatdan qayta hisoblash usuli shuqur nazariy muhokama etiladi.Parallel qayta hisoblash usuli ushun dastlabki ishlash va tahlil adabiyotlarda muhokama etiladi.Ushbu hujjat turli xil qisqartirish strategiyalari va dizaynlarida tizimning ishlashini tahlil qilishni kengaytiradi va xatolarni aniqlash va xatolar paydo bo'lganda qayta hisoblashni boshlash ushun ko'p tarmoqli mexanizmni qo'llagan holda parallel hisoblash tizimini master / qul rejimida amalga oshiradi. Bizning tizimimiz ma'lumotlarni tarqatishning turli usullari bilan shug'ullanishi va ularning ishlashini bir nechta tajribalar bilan taqqoslashi mumkin.
Qolgan qismlar keyingi qismda keltirilgan tezkor qayta hisoblash jarayoni doirasidan boshlanadi. Keyin master-qul rejimida parallel qayta hisoblash usulini amalga oshirish algoritmlari berilgan va asosiy jarayonga ko'p tarmoqli mexanizm qo'llaniladi. Ishlash tahlili ham ushbu bo'limda ko'rib chiqiladi. Ba'zi eksperimental natijalar "Eksperimentlar va tahlillar" bo'limida tahlil qilinadi, so'ngi bo'limda xulosa va kelgusi ishlar.

1.1 Parallel qayta hisoblash asoslari

DTA sohasida DEM umuman olganda katta hajmdagi ma'lumotlarga ega. DEM ma'lumotlarini qayta ishlash ko'proq vaqt talab etadi va shu bilan kirish / chiqish narxini oshiradi. Jarayon bajarilmasa, qayta boshlash ushun ish kerak va barcha hisob-kitoblar orqaga qaytariladi. Nosozlikni oldini olish ushun tizimning to'g'ri xizmatini ta'minlash ushun ba'zi choralar talab qilinadi. Jarayonlar o'rtasida aloqa va hisoblashning ko'pligiga duch kelganda, ma'lumotlarga ishlov berish samaradorligini oshirishga imkon beradigan, ajratilgan ma'lumotlar bloklarini qayta ishlash ushun ko'p oqimli yoki ko'p jarayonli rejim qabul qilinadi. Ichki bloklarni qayta ishlash kamroq hisoblash resurslari va saqlash joylaridan foydalanishning afzalliklariga ega. Muvaffaqiyatsiz bo'lsa, parallel qayta hisoblash (PR) barcha omon qolgan jarayonlarni orqaga qaytarishni talab qilmaydi. Buning o'rniga muvaffaqiyatsiz jarayon bloklarini parallel ravishda hisoblash ushun omon qolgan jarayonlardan foydalanadi. Agar asosiy tugun ishlamasa, barcha ma'lumotlar bloklari qayta hisoblab chiqiladi. Asosiy tugun ishlamay qolmasligi ushun zaxira mexanizmi qabul qilinishi mumkin. Ma'lumotni tarqatish jarayonida bo'linadigan ma'lumotlar bloki sonini tartibga solish ushun tezkor omil qabul qilinadi. Agar boshqa biron bir tugun bajarilmasa, ma'lumotlar bloki qayta tarqatiladi va qayta hisob-kitob qilinadi.
Asosiy tugunning asosiy jarayonining vazifalari ma'lumotlarni tarqatish, xatolarni aniqlash va natijalarni birlashtirish. PR doirasi. Asosiy tugundagi asosiy jarayon diskdagi ma'lumotlarni o'qiydi va ajratilgan ma'lumotlar bloklari soniga ko'ra ko'plab oqimlarni hosil qiladi. Har bir ip har bir blok blokni protsessorga va uning nusxasini qul tugunlariga tarqatish ushun javobgardir. Keyin har bir ip o'zlarining natijalarini olishni kutishadi. Sub-blok natijalari va uning nusxasi olinganidan so'ng, natijalar izchil yoki yo'qligini taqqoslaydi. Agar natijalar izchil bo'lsa, bu hisoblash to'g'ri ekanligini ko'rsatadi va ip natijalarni sigortalash ushun xotiraga yuboradi. Termoyadroviy protsedura natijalarni har bir panjara katakchasining holatiga muvofiq saqlash va ortiqcha qismlarning mustahkamligini oldini olishdir. Agar natijalar mos kelmasa, tegishli hisoblash mantiqiy bloki qayta hisoblash jarayonini amalga oshirish ushun yangi jarayonga qayta taqsimlanadi. Faqatgina barcha mantiqiy sub-bloklarning natijalari aniqlangan va aniqlangan natijalar aniqlangan va natijalar butun to'plamga qo'shilgandan keyingina ip yopilishi mumkin. Va nihoyat, asosiy jarayon butun natijalarni disk fayliga saqlaydi va yozadi.

Dasturni optimallashtirish, kompilyatorni optimallashtirish, ko'chadan optimallashtirish, ob'ekt kodlarini optimallashtirish va hokazolarda muhokama qilinadigan optimallashtirish bilan adashtirmaslik kerak.
Kompyuter fanida algoritmik samaradorlik bu algoritm foydalanadigan hisoblash manbalari soniga taalluqli algoritmning xossasidir. Resurslardan foydalanishni aniqlash ushun algoritmni tahlil qilish kerak va algoritm samaradorligini turli xil resurslardan foydalanishga qarab o'lchash mumkin. Algoritmik samaradorlikni takrorlanuvchi yoki uzluksiz jarayon ushun muhandislik samaradorligiga o'xshash deb hisoblash mumkin.
Maksimal samaradorlik ushun biz resurslardan foydalanishni minimallashtirishni xohlaymiz. Ammo vaqt va makon murakkabligi kabi turli xil resurslarni to'g'ridan-to'g'ri taqqoslash mumkin emas, shuning ushun ikkala algoritmning qaysi biri samaraliroq hisoblanadi, ko'pincha samaradorlik qaysi o'lchov eng muhim deb hisoblanadi.
Masalan, pufakchalarni saralash va timsort ikkalasi ham elementlarning ro'yxatini eng kichikidan kattasiga qarab saralash algoritmidir. Pufakchali tartib ro'yxatni kvadratlarning soniga mutanosib ravishda tartiblashtiradi ({\ displaystyle \ scriptstyle {{\ mathcal {O}} \ chap (n ^ {2} \ o'ng)}} {\ displaystyle \ skript uslubi {{\ mathcal {O}} \ chap (n ^ {2} \ o'ng)}}, Big O notation-ga qarang), faqat ro'yxatning uzunligiga qarab doimiy ravishda oz miqdordagi qo'shimcha xotira talab etiladi ({\ textstyle \ scriptstyle) {{\ mathcal {O}} \ chap (1 \ o'ng)}} {\ textstyle \ skript uslubi {{\ mathcal {O}} \ chap (1 \ o'ng)}}). Timsort vaqtni linearitmik tartibda (logarifmiga nisbatan mutanosib ravishda) ro'yxat uzunligiga qarab tartiblaydi ({\ textstyle \ scriptstyle {\ mathcal {O \ chap (n \ log n \ right)}}} {\ textstyle \ skriptstayl {) \ mathcal {O \ chap (n \ log n \ right)}}}), lekin bo'sh joy talablari ro'yxat uzunligiga to'g'ri keladi ({\ textstyle \ skript uslubi {\ mathcal {O \ chap (n \ right)} }} {\ textstyle \ skript uslubi {\ mathcal {O \ chap (n \ o'ng)}}}). Agar ushbu dastur ushun katta ro'yxatlarni yuqori tezlikda saralash kerak bo'lsa, timsort - bu eng yaxshi tanlov; ammo, Agar saralashning xotira izini minimallashtirish muhimroq bo'lsa, qabariq turini tanlash afzalroqdir.
Umumiy nuqtai Agar algoritm hisoblash qiymati sifatida ham ma'lum bo'lsa, uning resurs iste'moli ma'lum maqbul darajadan past yoki past bo'lsa samarali hisoblanadi. Qo'pol qilib aytganda, "maqbul" degani: bu mavjud kompyuterda o'rtacha vaqt yoki bo'sh vaqt ichida ishlaydi, odatda kirish hajmining funktsiyasi sifatida. 1950-yillardan beri kompyuterlar mavjud hisoblash quvvati va xotira hajmida keskin o'sishni kuzatdilar, shuning ushun hozirgi maqbul darajalar hatto 10 yil oldin qabul qilinishi mumkin emas edi. Aslida, har ikki yilda kompyuter quvvatining taxminan ikki baravar ko'payishi tufayli, zamonaviy smartfonlarda va o'rnatilgan tizimlarda maqbul bo'lgan vazifalar 10 yil oldin sanoat serverlari ushun qabul qilib bo'lmaydigan darajada samarasiz bo'lgan bo'lishi mumkin. Kompyuter ishlab chiqaruvchilari tez-tez yangi modellarni chiqaradilar, ko'pincha yuqori ko'rsatkichlarga ega. Dasturiy ta'minot narxi ancha yuqori bo'lishi mumkin, shuning ushun ba'zi holatlarda yuqori ko'rsatkichlarga erishishning eng oddiy va arzon usuli shunchaki mavjud kompyuter bilan mos keladigan bo'lsa, tezroq kompyuter sotib olish bo'lishi mumkin. Algoritm tomonidan ishlatiladigan manbalarni o'lchashning ko'p usullari mavjud: eng keng tarqalgan ikkita chora - bu tezlik va xotiradan foydalanish; boshqa chora-tadbirlar uzatish tezligi, diskdan vaqtincha foydalanish, uzoq muddatli diskdan foydalanish, quvvat sarfi, mulkning umumiy qiymati, tashqi stimullarga javob vaqti va boshqalarni o'z ichiga olishi mumkin. Ushbu choralarning aksariyati algoritmga kirish hajmiga bog'liq, ya'ni ishlov beriladigan ma'lumotlar miqdori. Ular, shuningdek, ma'lumotlarning tartibga solish usuliga bog'liq bo'lishi mumkin; masalan, ba'zi saralash algoritmlari allaqachon saralangan yoki teskari tartibda ajratilgan ma'lumotlarda sust ishlaydilar. Amaliyotda aniqlik va / yoki ishonchlilik talablari kabi algoritmning samaradorligiga ta'sir ko'rsatadigan boshqa omillar ham mavjud. Quyida batafsil aytib o'tilganidek, algoritmni amalga oshirish usuli ham haqiqiy samaradorlikka sezilarli ta'sir ko'rsatishi mumkin, ammo uning ko'p jihatlari optimallashtirish bilan bog'liq.

1.2 Parallel qayta hisoblash protsedurasining asoslari.

Tarmoqli tugunni hisoblash jarayoni va boshqa bir qul tugunidagi nusxalash jarayoni ma'lumot blokini olish, natijani hisoblash va natijani tegishli oqimga yuborish ushun javobgardir. Hisoblash jarayoni ma'lumotlar blokini oladi va ma'lumotlar bloki natijasini hisoblaydi. Keyin, ular bir xil mantiqiy ma'lumotlar sub-blokining tegishli natijalarini oldindan belgilangan vaqtga ko'ra asosiy tugundagi ipga yuboradilar.Ma'lumotni tarqatish va xatolarni aniqlash samaradorligini oshirish ushun asosiy jarayonda ko'p tarmoqli texnologiya qo'llaniladi. Har bir ip ma'lumotlarni tarqatish va xatolarni aniqlash ushun javobgardir. Hisoblash natijalarini asosiy jarayon bo'yicha taqqoslashdan keyin xato yuzaga kelsa, oqim, shuningdek, hisoblash xatosi yuzaga kelganda, ma'lumotlar blokini qayta taqsimlash ushun javob beradi va qayta hisoblash jarayonini amalga oshirish ushun yangi jarayonni boshlaydi.Parallel qayta hisoblash ortiqcha ishlov berish mexanizmiga asoslangan. PR-ning asosiy printsipi shundan iboratki, ma'lumotlar bloki bilan jarayon va ma'lumotlar blokining nusxasi bilan jarayon birinchi navbatda ikkita turli xil tugunlarda bir vaqtning o'zida bajariladi. Ushbu ikkita jarayon hisoblash vazifalarini tugatgandan so'ng, ularning natijalari asosiy tugunga yuboriladigan asosiy jarayonga yuboriladi va ushbu ikki natija izchil yoki yo'qligi taqqoslanadi. Hech qanday xato bo'lmasa, asosiy jarayon natijani tashqi faylga saqlaydi. Ikkala natija bir-biriga mos kelmasa, ba'zi xatolar yuzaga kelganda, asosiy jarayon ma'lumotlar blokini kichik sub-bloklar guruhiga, masalan, to'rtta pastki bloklarga ajratadi. Keyin ushbu pastki bloklar parallel ravishda qayta hisoblash ushun omon qolgan hisoblash jarayonlariga taqsimlanadi. 
O'zaro munosabatlarni soddalashtirish ushun ma'lumotlar bloklari o'rtasida bog'liqlik mavjud emas. N hisoblash jarayonlarining to'plami P = {P ₁ , P ₂ ,…, P _n } deb belgilangan; P _i hozirgi jarayonni bildiradi. Ma'lumotlar bloklari to'plami B = {B ₁ , B ₂ ,…, B _n } bilan belgilanadi; B _i ishlov beriladigan qismli blokni bildiradi. Ma'lumotlar natijalari to'plami R = {R ₁ , R ₂ ,…, R _n } bilan belgilanadi; R _i hisoblash natijalarini ifodalaydi. PRning butun jarayoni besh bosqichdan iborat:
Qiyoslash: ish faoliyatini o'lchash Dasturiy ta'minotning yangi versiyalari yoki raqobatbardosh tizimlar bilan taqqoslash ushun ba'zida algoritmlarning nisbiy ishlashini aniqlashga yordam beradigan ko'rsatkichlardan foydalaniladi. Agar yangi tartiblash algoritmi ishlab chiqarilsa, masalan, har qanday funktsional yaxshilanishni hisobga olgan holda, hech bo'lmaganda ma'lum ma'lumotlarga qaraganda unumdorligini ta'minlash ushun uni avvalgilar bilan taqqoslash mumkin. Iste'molchilar tomonidan muqobil etkazib beruvchilarning turli xil mahsulotlarini taqqoslashda, qaysi mahsulot funktsional va ishlash jihatidan ularning o'ziga xos talablariga eng mos kelishini aniqlash ushun mijozlar foydalanishi mumkin. Masalan, asosiy tizim dunyosida Syncsort kabi mustaqil dasturiy ta'minot kompaniyalarining ma'lum mulkiy saralash mahsulotlari tezligi ushun IBM kabi yirik etkazib beruvchilarning mahsulotlari bilan raqobatlashadi. Ba'zi bir mezonlar turli kompilyatsiya qilingan va talqin qilingan tillarning nisbiy tezligini taqqoslaydigan tahlil qilish ushun imkoniyat yaratadi, masalan va Computer Language Benchmarks Game bir necha dasturlash tillarida tipik dasturlash muammolarining bajarilishini taqqoslaydi.
Ortiqcha hisoblash. Oddiy parallel hisoblashda, ma'lumotlar bloki bilan hisoblash jarayonida hisoblash xatosi bor yoki yo'qligini aniqlash ushun, bo'shashganlikni hisoblash strategiyasi odatda qabul qilinadi. Ikki xil qo'shimcha strategiya mavjud: juftlik va ikki baravar ko'paytirish. Ikkilik qisqarish strategiyasi mos ravishda hisoblash ushun ma'lumot blokining ikki nusxasini va uch baravar ko'paytirish strategiyasi mos ravishda hisoblash ushun ma'lumot blokining uch nusxasini qabul qiladi. Uch baravar ko'paytirish ovoz berish orqali to'g'ri natijani aniqlashi mumkin, ammo ko'proq jarayon talab etiladi. Ikkilikni qisqartirishda ikkita protsedura, P va P block, ma'lumotlar bloki B va uning nusxasi B conc bir vaqtning o'zida bajariladi, natijada ularning natijalari, R va R the, to'g'riligini asoslash ushun bir-birini taqqoslash ushun ishlatiladi.