Nazorat savollari Raqamli ishlov berish nima uchu kerak?
Unumdorligini baholash usullar
22-Ma’ruza. Parallellik darajasini baholash Amdal qonuni Reja: 1.Parallellik darajasini baholash 2. Amdal qonuni
Tayanch iboralar: parallellik,Amdal qonuni.
Parallellik darajasini baholash Parallel hisoblash- kompyuterda hisoblashni tashkil qilish usuli, bunda dasturlar parallel (bir vaqtning o'zida) ishlaydigan o'zaro ta'sir qiluvchi hisoblash jarayonlari majmuasi sifatida ishlab chiqiladi. Ushbu atama dasturlashdagi parallellik masalalari yig'indisini, shuningdek, samarali apparat tatbiqlarini yaratishni o'z ichiga oladi. Parallel hisoblash nazariyasi algoritmlarning amaliy nazariyasining bo'limidir. Parallel hisoblashni amalga oshirishning turli usullari mavjud. Masalan, har bir hisoblash jarayoni operatsion tizim jarayoni sifatida amalga oshirilishi mumkin yoki hisoblash jarayonlari bitta OT jarayoni doirasidagi bajarilish iplari to'plami bo'lishi mumkin. Parallel dasturlar jismoniy ravishda bitta protsessorda ketma-ket bajarilishi mumkin - o'z navbatida har bir hisoblash jarayonini bajarish bosqichlarini o'zgartirish yoki parallel ravishda - har bir hisoblash jarayoniga bir yoki bir nechta protsessorlarni (yaqin joyda joylashgan yoki kompyuter tarmog'ida taqsimlangan) ajratish. Parallel dasturlarni loyihalashdagi asosiy qiyinchilik turli xil hisoblash jarayonlari o'rtasidagi o'zaro ta'sirlarning to'g'ri ketma-ketligini ta'minlash, shuningdek, jarayonlar o'rtasida taqsimlangan resurslarni muvofiqlashtirishdir. Ba'zi parallel dasturlash tizimlarida komponentlar o'rtasida ma'lumotlarni uzatish dasturchidan yashirin (masalan, va'da mexanizmi yordamida), boshqalarida esa aniq ko'rsatilishi kerak. Aniq shovqinlarni ikki turga bo'lish mumkin: Parallel xabar almashishga asoslangan tizimlarni umumiy xotira tizimlariga qaraganda tushunish odatda osonroq va odatda parallel dasturlashning ilg'or usuli sifatida qaraladi. Xabarlarni uzatish tizimlarini o'rganish va tahlil qilish uchun turli xil matematik nazariyalar mavjud, shu jumladan aktyor modeli va har xil turdagi jarayonlar hisobi. Xabarlar umumiy kogerent xotiraga ega yoki ularsiz simmetrik multiprotsessorlarda samarali amalga oshirilishi mumkin. Taqsimlangan xotira parallelligi va xabarni uzatish parallelligi turli xil ishlash xususiyatlariga ega. Odatda (lekin har doim ham emas), jarayon xotirasi va vazifalarni almashtirish uchun qo'shimcha xarajatlar xabarlarni uzatish tizimlari uchun kamroq bo'ladi, ammo xabarlarni uzatish protsedura chaqiruvlariga qaraganda qimmatroq. Bu farqlar ko'pincha ishlashga ta'sir qiluvchi boshqa omillar bilan bir-biriga mos keladi. Qoida tariqasida, parallel dasturning algoritmi parallel va ketma-ket bo'limlar ketma-ketligidir. Dasturning parallel qismi parallel dastur algoritmi tomonidan aniqlangan sxemalar bo'yicha ma'lumotlarni tarqatish va ma'lumotlar almashinuvini o'z ichiga oladi. Dasturning ketma-ket qismi, qoida tariqasida, barcha yoki alohida jarayonlarda ma'lumotlarni arifmetik qayta ishlashni belgilaydi.
Amdal qonuni- kompyuterlar sonining ko'payishi bilan hisoblash tizimining ishlashidagi o'sishning cheklanishini ko'rsatadi. "Agar vazifa bir necha qismlarga bo'lingan bo'lsa, parallel tizimda umumiy bajarish vaqti eng uzun fragmentni bajarish vaqtidan kam bo'lishi mumkin emas." Ushbu qonunga muvofiq, dasturning bajarilishini tezlashtirish tufayli parallellashtirish uning kompyuterlar to'plamidagi ko'rsatmalari uning ketma-ket ko'rsatmalarini bajarish uchun zarur bo'lgan vaqt bilan chegaralanadi. Ba'zi bir hisoblash muammosini hal qilish kerak bo'lsin. Faraz qilaylik, uning algoritmi shundayki, hisob-kitoblarning umumiy hajmidagi ulushini faqat ketma-ket hisob-kitoblar orqali olish mumkin va shunga mos ravishda ulushni mukammal parallellashtirish mumkin (ya'ni hisoblash vaqti jalb qilingan tugunlar soniga teskari proportsional bo'ladi). Keyin protsessorlardan hisoblash tizimida olinishi mumkin bo'lgan tezlashtirish, bir protsessorli yechim bilan solishtirganda, qiymatdan oshmaydi. Protsessorlar ishlashda bir xil bo'lsin. T 0 - parallel algoritmning ketma-ket qismini bajarish vaqti, masalan, dastlabki ma'lumotlarni hosil qilish va masalani yechishda olingan natijani qayta ishlash. T 1 , T 2 , ... T p- har bir protsessor tomonidan bir-biri bilan o'zaro ta'sir qilmasdan bajariladigan ketma-ket ish vaqti. Keyin vazifani bajarish vaqti da p Protsessorlar tengsizlik bilan aniqlanadi:
bu erda i = 1, 2, ... p. Tenglik qachon erishiladi Ti bir-biriga teng... Demak, almashtirish
T seq - T 0, qaerda Tseqbitta protsessorda vazifani bajarish vaqti mavjud, olamiz Tpar≥ T0
T seq ga bo'linadi va f = bilan ifodalanadi T0 / T seq - hisob-kitoblarning umumiy hajmidagi ketma-ket qismning ulushi (kasri), biz quyidagilarni olamiz:
. (1.1)
Tezlashtirish (Tezlikni oshirmoq) Bu ketma-ket rejimda (1 protsessorda) vazifani bajarish vaqtining parallel rejimda (p protsessorda) vazifani bajarish vaqtiga nisbati.
tengsizlikdan foydalanib, olamiz
(1.2)
Demak, f = 0 va T i tengligi uchun S = p ni, f> 0 va p → ∞ uchun esa, ko‘rinib turibdiki,
... Bu funktsiya pda monoton ravishda ortib boradi va shuning uchun cheksizlikda maksimal darajaga etadi. Shuning uchun, protsessorlar soni yo'q sanashning tezlashishi ketma-ket kesimning kasrining o'zaro nisbatidan oshmasligi kerak.
Amdal qonunini hisobga olgan holda, biz ketma-ket hisob-kitoblarning nisbati deb faraz qildik. f doimiy va parametrga bog'liq emas n, hal qilinayotgan muammoning hisoblash murakkabligini aniqlash... Biroq, ko'p sonli masalalar uchun f = f (n) kasr ning kamayuvchi funktsiyasidir n va bu holda protsessorlarning belgilangan soni uchun tezlashtirish har bir protsessor tomonidan bajariladigan ketma-ket ishlarning ulushini kamaytirish orqali oshirilishi mumkin. Boshqacha qilib aytganda, Sp = Sp (n) tezlashuvi n parametrining ortib borayotgan funktsiyasidir (bu bayonot ko'pincha Amdahl effekti deb ataladi).
Parallelizatsiya samaradorligi bu algoritmning vazifani bajarishda ishtirok etgan barcha protsessorlardan 100% foydalanish qobiliyatidir. Samaradorlikni hisoblash formulasi:
(1.2)
Bular. agar tezlik S = p bo'lsa (p protsessorda mumkin bo'lgan maksimal), u holda vazifani parallellashtirish samaradorligi 100% ni tashkil qiladi. Amdahl qonunidan foydalanib, biz samaradorlikning yuqori chegarasini olamiz:
E≤ 100%
(1.3)
Masalan, p = 100 va f = 0,01 uchun E ≤ 52,25% va p = 1000 va f = 0,01 uchun E ≤ 9,1%.