Parallel algoritmlarning ishlab chiqish bosqichlari. 5-Mavzu Parallel algoritmlarning ishlab chiqish bosqichlari

Umumiy xarajatlar = vaqtning murakkabligi × ishlatilgan protsessorlar soni

Amdal qonuni .

Amdal qonuni (1967), parallel yechimning eng yaxshi ketma-ket echimga nisbatan maksimal nazariy samaradorligini tavsiflaydi.

bunda Sn – hisoblashlarni necha marta tezlashtirish mumkinligi (tezlanish), n – prossesor(yadro)lar soni, a – ketma-ket bajariladigan kod ulushi (a≠0).

Amdal qonuni

Amdal qonuni, ko'p omillarni hisobga olmaganiga qaramay, parallel algoritmning maksimal erishiladigan samaradorligiga cheklovlar qo'yadi. Masalan, a=1\3, ya'ni algoritmdagi operatsiyalarning uchdan ikki qismi parallel bajarilishi mumkin, va uchdan biri bajarilmaydi. Unda tezlanish Sn<3ga teng bo’ladi. Shunday qilib, protsessorlar (yadrolar) sonidan qat'i nazar va barcha ma'lumotlarni tayyorlash xarajatlari inobatga olinmagan taqdirda ham, muammoni hal qilishni uch martadan ko'proq tezlashtirish mumkin emas bo’ladi.

Gustafson -Barsis qonuni .

Gustafson-Barsis qonuni (1988) bir vaqtning o'zida bajariladigan hisoblash oqimlari soniga va ketma -ket hisoblar ulushiga qarab, parallel dastur bajarilishining ruxsat etilgan maksimal tezlanishini baholaydi. Gustafson -Barsis formulasi quyidagicha:

Bunda a - dasturdagi ketma -ket hisoblarning ulushi, n - protsessorlar soni.

Gustafson -Barsis qonuni .

Gustafson ko'p protsessorli tizimlar ustida ishlayotganda, foydalanuvchilar muammoni hal qilish taktikasini o'zgartirishga moyilligini payqadi. Endi dasturning umumiy bajarilish vaqtining qisqarishi hal qilinayotgan muammoning hajmidan past bo'ladi. Maqsadning bu o'zgarishi Amdal qonunidan Gustafson qonuniga o'tishga olib keladi. Masalan, 100 ta protsessorda dastur 20 daqiqa ishlaydi. 1000 ta protsessorli tizimga o'tishda siz taxminan ikki daqiqa ishlashga erishishingiz mumkin. Biroq, echimning aniqligini olish uchun, hal qilinayotgan muammoning hajmini oshirish mantiqan to'g'ri keladi, ya'ni. umumiy ish vaqtini saqlab turganda, foydalanuvchilar aniqroq natijaga erishadilar. Muammoni hal qilish hajmining oshishi parallel qism ulushining oshishiga olib keladi, chunki ketma -ket qism (kirish -chiqish, iplarni boshqarish, sinxronizatsiya nuqtalari va boshqalar) o'zgarmaydi.