Mavzu: Dinamik parallel hisoblashlar uchun parallel jarayonlarni tashkillash Mundarija

2.7. Tezlashtirish omili

Tezlashtirish koeffitsienti muhim ahamiyatga ega va odatda bitta kompyuterda t (1) parallel dasturning bajarilish vaqtining N kompyuterlari yoki protsessorlari bo'lgan samolyotda t (N) bajarilish vaqtiga nisbati sifatida aniqlanadi: C (N) = t (1) / t (N) ). Amdahl qonuniga binoan N tugunli samolyotda masalani parallel shaklda hal qilishning cheklovli tezlanishi: (C) = 1 / (a ​​+ (1-a) / N) nisbati bilan aniqlanadi, bu erda a - ketma-ket bajariladigan operatsiyalarning nisbati. Cheksiz N da cheklovli tezlashuv aniq 1 / a ga teng. Darhaqiqat, tezlashuv samolyotda dasturning parallel bajarilishini boshqarish, ma'lumotlar almashinuvini amalga oshirish uchun sarflangan vaqt tufayli marginaldan kamroqdir. Amalda, tezlanish vazifaning murakkabligiga va miloddan avvalgi kompyuterlarning (protsessorlarning) N soniga qarab qanday harakat qilishini tushunish muhimroq.

C (x1, x2,…, xk, N) masala murakkabligining x1, x2,…, xk parametrlariga va samolyotdagi N tugunlari soniga qarab masala echimining parallel shaklda tezlanishini belgilaydigan funktsiya bo'lsin. Ko'pgina vazifalar uchun faqat C (x1, x2, ..., xk, N) chegara qiymatini aniqlash kifoya, agar biz kompyuterlar yoki samolyot tugunlari soni cheklanmagan deb hisoblasak (bu holda zarur resurslarning etishmasligi sababli parallel dasturni bajarishda hech qanday kechikishlar bo'lmaydi) ) va samolyotda parallel dasturning bajarilishini tashkil etish uchun tizim xarajatlarini hisobga olmaslik (almashinish shovqinlari, boshqarish va hk. [7]). Aynan shu taxminlarga ko'ra tezlashtirish koeffitsienti odatda ko'plab usullar va parallel dasturlar uchun belgilanadi. Masalaning hisoblash murakkabligini tavsiflovchi x1, x2,…, xk parametrlari sifatida ko'p hollarda masalaning o'lchamini belgilaydigan parametrlardan foydalaniladi, bular ham uning echish usulini ifodalovchi dasturning argumentlari hisoblanadi. Dasturga muvofiq [1¸n] segmentini ikkiga bo'lishning parallel usulidan foydalanib, n! Qiymatlarini hisoblashning oddiy masalasi misolini ko'rib chiqing: Fakt (i, j) = 1 agar i = j boshqa Fakt (i, l (i + j) / 2û) ´ ´Fakt (ë (i + j) / 2û + 1, j)), bu erda ëaû a ga eng yaqin butun sondir. Shubhasiz, F (1, n) = n! Agar n qiymatini hisoblash jarayonini amalga oshirishga harakat qilsangiz! ushbu dasturga muvofiq, yuzaga keladigan barcha parallellashuv imkoniyatlaridan foydalangan holda, bu jarayon 3-rasmda ko'rsatilgan sxema bo'yicha amalga oshirilishini ko'rsatish oson. Parametr n (yuqoridagi funktsiya argumenti) masalaning hisoblash murakkabligini tavsiflaydi va C (n) koeffitsienti (cheksiz ko'p samolyot tugunlari uchun) O (n / log2n) kabi harakat qiladi va n ning cheksiz ortishi bilan cheksizlikka intiladi. Shunday qilib, vazifa murakkablashib borishi bilan (ortib boruvchi n), cheklanmagan resurslar mavjud bo'lgan taqdirda ushbu dasturning bajarilish vaqtini cheksiz qisqartirish mumkin. Boshqa muammolarning ko'plab misollari mavjud (matritsani ko'paytirish, chiziqli tenglamalarni echish va hk), ular uchun tezlashuv koeffitsienti murakkabligi oshishi bilan cheksiz ortadi. Ushbu turdagi parallel dasturlar cheksiz parallellikka ega dasturlar deb nomlanadi. Parallelizatsiya chuqurligi va darajasi Uslubning (yoki uni ifodalovchi algoritmning) parallellanish chuqurligini belgilaydigan va parallel dastur komponentlarining hisoblash murakkabligini intuitiv ravishda tavsiflovchi yana bir parametrni kiritamiz, bu uning mustaqil qismlari deb qaraladi va bir vaqtning o'zida bajarilishi mumkin. Ushbu parametr ko'pincha adabiyotda bir vaqtning o'zida don deb nomlanadi. Ta'rif. Parallelizatsiya chuqurligi d deganda biz paralel dasturda samolyotda bajarilishi davomida aniqlangan va rejalashtirilgan mustaqil jarayonlar sifatida qaraladigan komponentlarning o'rtacha hisoblash murakkabligini tushunamiz. D ga teskari qiymat bir vaqtning o'zida bajarilishi mumkin bo'lgan parallel dastur komponentalarining o'rtacha sonini tavsiflovchi parallellik darajasi sifatida aniqlanadi. N o'lchamdagi kvadrat matritsalarni ko'paytirishning oddiy misolini ko'rib chiqing va har xil d va samolyotdagi cheksiz sonli kompyuterlar uchun bu masalaning parallel echimi uchun chegara tezlashuv koeffitsientini aniqlang:

1) d1 - natijada matritsaning hisoblash murakkabligi bir qatorga va paralelleşmesi darajasi - matritsaning barcha qatorlar bir vaqtning o'zida hisob:  ,

qaerda tum va tsl - mos ravishda ko'paytirish va qo'shish operatsiyalarining bajarilish vaqti;

2) d2 - natijada olingan matritsaning bitta elementini hisoblashning murakkabligi, va parallellanish darajasi - bu hosil bo'lgan matritsaning barcha elementlarini bir vaqtning o'zida hisoblash:

;

3) d3 - ko'paytirish operatsiyasining murakkabligi, va parallellanish darajasi - natijada olingan matritsaning barcha elementlarini hisoblashda barcha ko'paytirish amallarini bir vaqtda bajarish:

, bu erda r1 bir oz doimiy, r1 £ 1; O (x) - x ga yaqin qiymat;

4) d4 - ko'paytirish amalining o'rtacha murakkabligi va   natijada olingan matritsa elementlarini hisoblashda yig'indining parallel hisoblanishi ; parallelizatsiya darajasi [1¸n] segmentini ikkiga bo'lish yo'li bilan yuqoridagi yig'indining keyingi parallel hisob-kitobi bilan barcha ko'paytirish amallarini bir vaqtda bajarish shartidan kelib chiqib belgilanadi (yuqoridagi faktorialni parallel hisoblash misoliga qarang):

, bu erda r2 £ r1.

To'rt holatda ham tezlanish koeffitsienti n ning ortishi bilan cheksiz o'sib borishini ko'rish oson. Shu bilan birga, ushbu o'sishning hosilasi (tezlashishi) har xil d uchun farq qiladi, masalan, d1, d2, d3 uchun tezlanish koeffitsienti mos ravishda O (n), O (n2) va O (r1 × n3) ga ko'payadi.

Parallellanish darajasi 1 / d qiymatiga qarab kamaymaydigan funktsiya kabi harakat qiladi va har doim uning chegarasi bilan belgilanadigan va har doim parallellik chuqurligi bilan chegaralangan chegara qiymati mavjud. Vazifani parallellashtirish darajasining o'zgarishi, uni bajarish vaqtini minimallashtirish va resurslardan foydalanish nuqtai nazaridan kompyuterda bajarish jarayonini optimallashtirishda juda muhimdir. Bu parallel dasturni ishlab chiqish bosqichida ham, uni samolyotda statik rejalashtirishda ham, bajarilish bosqichida ham, paralellik darajasi dinamik ravishda o'zgarib turganda, tayyor jarayonlarning old qismini oshirish, bu esa samolyotning ish hajmining oshishiga olib keladi. Almashinish shovqinlarining intensivligi Samolyotning parallel ishlash samaradorligi, shuningdek, aloqa dasturining o'tkazuvchanligi va parallel dasturni bajarish paytida uning tarkibiy qismlari o'rtasidagi almashinuv shovqinlarining intensivligiga bog'liq. Shuning uchun, parallellanish darajasi o'zgarganda, dastur samolyotda bajarilganda, o'zaro ta'sir o'tkazish intensivligi qanday o'zgarishini tushunish muhimdir

Resurslardan, xususan, samolyot tugunlaridan real foydalanish to'g'risida aniqroq g'oya ularning dasturning parallel bajarilishi T oralig'idagi yuklamasining o'rtacha qiymati bilan berilgan:  bu erda Li (t), i = 1, 2, ..., N - i-tugunning yuki. Odatda samolyotning ish yuki faqat uning protsessorlarining ish yuki bilan baholanadi, bu ko'pincha hisoblash vazifalari uchun asoslanadi. Ammo, vazifa shunday bo'lishi mumkinki, uning dasturida vaqtning asosiy qismi tashqi qurilmalar bilan ishlashga (kirish / chiqish) yoki ma'lumotlarning murakkab massivlarini qayta ishlashga sarflanadi. Ushbu holatlarda asosiy e'tibor xotirani, portlarni, tashqi qurilmalarni va boshqalarni samarali boshqarishni tashkil etishga qaratiladi da, samolyotlarning parallel ishlashini boshqarish muammosini o'rganayotganda, uning samaradorligi dasturni bajarish, disk bilan almashish paytida paydo bo'lgan kirish / chiqish buyruqlarining intensivligiga bog'liq ekanligi ko'rsatildi. xotira, shu jumladan, birinchisi yo'qligi sababli RAM va disk xotirasi o'rtasida sahifalar almashinuvi, shuningdek tugunlar o'rtasida ma'lumotlar almashinuvi tufayli. Agar ko'rsatilgan yo'llarning biron birining tirbandlik darajasi, ya'ni unda ishlaydigan uskunalar λ / m nisbati sifatida aniqlansa, bu erda λ kirish oqimining intensivligi, m uning xizmatining intensivligi va bu nisbat birdan kattaroq bo'lib chiqsa, bu yo'l to'siq bo'lib, keskin kamayib boradi parallel samolyot ishlashining umumiy ko'rsatkichlari. N - samolyot tugunlari sonining ko'payishi bilan ma'lum bir murakkablikdagi vazifa uchun samolyot resurslaridan foydalanish samaradorligi ko'rsatkichining o'zgarishini umumiy xususiyatini kuzatish qiziq.

Shubhasiz, agar parallellik chuqurligi o'zgarmasa va samolyotda parallel dasturni bajarishni tashkil etishning umumiy sxemasi saqlanib qolsa, bu ko'rsatkich avval N ning oshishi bilan oshishi kerak (aniqrog'i, kamaymasligi kerak). Biroq, har doim ham N ning optimal qiymati bo'ladi, bundan ham ko'proq dasturni bajarish vaqtini qisqartirish mumkin emas. (yanada murakkabroq vazifa talab qilinadi yoki parallel chuqurlik pasayishi talab qilinadi). Xulosa qilish mumkinki, parallel parallel dasturlarni qurishda nafaqat muammolarni hal qilishning parallel usullarini ishlab chiqishga jiddiy e'tibor qaratish, balki ularni tahlil qilib, samolyot ko'lami va uning texnik imkoniyatlariga maksimal darajada erishish uchun moslashtirish kerak. Barcha ixtirolar singari, dasturlash tillari ham amaliy ahamiyatga ega va ularning yaratilishi va rivojlanishi ham amaldagi amaliy amaliyot, ham kompyuter texnologiyalarining jadal rivojlanishi bilan bog'liq. Kompyuter sanoatining uzoq kutilgan minglab va hattoki yuz minglab tarkibiy qismlari bo'lgan kompyuter tizimlarini (klasterlar, tarmoqlar va boshqalarni) keng ishlab chiqarishga o'tishi ishlab chiquvchilarni bunday tizimlardan samarali foydalanish uchun til va boshqarish vositalarini yaratish muammosini zudlik bilan hal qilishga majbur qilmoqda. Maqolada mualliflar tillar va parallel dasturlash muhitlarini yaratishda turli xil va ko'pincha qarama-qarshi yondashuvlarning ob'ektiv to'qnashuvi mavjud bo'lgan mos yozuvlar nuqtalarini aniqlashga harakat qilishdi. Shunisi aniqki, dasturiy ta'minot kompaniyalari tomonidan yaratilgan dasturiy ta'minot parallel dasturlarni ishlab chiqish va ularni turli xil kompyuter tizimlarida bajarish jarayonlarini hali ham samarali amalga oshirmoqda.

Dasturni parallellashtirish variantlari ko'rib chiqiladi, ularni uch yo'nalishda bajarish mumkin: ma'lumotlar bo'yicha, harakatlarga ko'ra va vektor hisob-kitoblaridan foydalangan holda. Ushbu maqolada faqat parallellashtirishning dastlabki ikkita varianti ko'rib chiqilgan. Mavjud hisoblash modellari ko'rib chiqiladi: Petri to'rlari shaklidagi model, mantiqiy model, raqamli avtomat va Markov jarayonlariga asoslangan model. Parallel taqsimlangan hisoblash samaradorligini baholash va takomillashtirishning mavjud usullarini tahlil qilish amalga oshirildi. Parallel hisoblashlarni baholash va samaradorligini oshirish muammosi to'liq hal qilinmagan va parallel algoritmlarni tahlil qilishning aniq universal usuli ishlab chiqilmagan. Hisoblash jarayonining samaradorligi va mumkin bo'lgan tezlashishini baholashning mavjud variantlari, masalan, Amdahl qonuni, tizim me'morchiligining xususiyatlari va algoritmlarning o'ziga xos xususiyatlarini hisobga olmaydigan ideal taxminlar: ular jarayonlar o'rtasida ma'lumotlar almashinuviga sarf qilingan vaqtni hisobga olmaydilar. O'tkazilgan tahlil asosida keyingi tadqiqotlarning vazifalari shakllantirildi. Ikkinchi bobda parallel hisoblash jarayonining modellari sifatida deterministik bo'lmagan raqamli avtomatika (NDA) va Markov jarayonlari modelidan foydalanish taklif etiladi.

Xulosa

Parallel RS-trigger dasturidan misol sifatida biz har qanday parallel dasturlarga xos bo'lgan ba'zi xususiyatlarni ko'rib chiqdik. Mantiqiy (raqamli) sxemalar misolida, parallel dasturlarning ishlashining ba'zi umumiy jihatlarini ko'rib chiqishda davom etamiz. Bu erda raqamli davrlarni modellashtirish mavzusini tanlash bejiz emas. Ular aslida parallel jarayonlarning ishini "tozalangan shaklda" ifodalaydi. U o'zaro kelishuv, irqlar, sinxronizatsiya, blokirovka ajralishini amalga oshiradi. va boshqalar, shaffof, aniq va sodda.
Shu bilan birga, qanday qilib dasturlashni - "bir vaqtda" yoki parallel deb atashingizdan qat'iy nazar, dasturlash uchun koroutinlar, korutinlar, iplar yoki avtomatlardan foydalanasizmi, [parallel] dasturining natijasi barcha amalga oshirishda bir xil bo'lishi kerak. KPSS doirasidagi parallel dasturlarning avtomat modeli ushbu va faqat shu maqsadni ko'zlaydi.
VKP muhitining avtomatlarini talqin qilish yadrosini amalga oshirish to'g'risida qanday taxminlar qilinmasin, bularning barchasi "taxminlar" bo'ladi, chunki avtomatik dasturlarning ishlash natijasi hisoblash modelini amalga oshirish bilan bog'liq bo'lmasligi kerak. Bu bitta yadroda yoki ularning ko'pchiligida, bitta ipli yoki ko'p ipli versiyada va hokazolarda amalga oshiriladigan dasturiy ta'minot (hozirgi kabi) yoki apparat (umid qilamanki, kelajakda) bo'lishi mumkin. va h.k. bularning barchasi parallel avtomatlashtirilgan dasturlarning ishlash natijalariga hech qanday ta'sir ko'rsatmasligi kerak.