Reja: Parallelizatsiya samaradorligi

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 yordamida olish mumkin va shunga mos ravishda ulush mukammal parallellashtirilishi 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 T seq bitta protsessorda vazifani bajarish vaqti mavjud, olamiz T par ≥ T 0
.
T seq ga bo'linadi va f = bilan ifodalanadi T 0 / 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.
(1.1) 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).