Matematik asoslar va raqamli modellashtirish usullari

KOMPYUTER TADQIQOTLARI VA MODELLASHTIRISH
Algoritmlar va dasturlarni parallelizatsiyalashga kirish
241
Ijrochilar soni bo'yicha o'lchovliligi bo'yicha parallel algoritmlarni taqqoslash
ushbu kurs doirasida ko'rib chiqilmaydigan alohida masala.
Biz uchun eng muhimi, turli
parallel algoritmlarning ish vaqtini taqqoslash emas, balki parallel algoritmning mavjud
ketma-ket algoritmlardan qanchalik yaxshi ekanligini aniqlash.
Keling, matematik modellashtirish muammosini hal qiladigan parallel algoritmni
va bir xil vazifa uchun eng yaxshi ketma-ket algoritmni olaylik.
Parallel algoritm ketma-ket nisbatan nisbati bilan belgilanadi tezlashtirish beradi, deb aytish uchun boryapmiz
:
Tezlashtirish = (eng yomon dastlabki ma'lumotlar uchun eng yaxshi ketma-ket algoritmning ishlash vaqti
) / (bir xil dastlabki ma'lumotlar uchun parallel algoritmning ishlash vaqti
).
Agar mavjud bo'lsa, aniq
N ijrochilari tezlashtirish n dan oshmasligi kerak ,
aks holda parallel qismlarni bir ijrochiga ketma-ket bajarish orqali biz
ketma-ket algoritmni yanada yaxshiroq qabul qilamiz.
Tezlashuvning nazariy ta'rifi amalda kamdan-kam hollarda qo'llaniladi.
Eng yaxshi ketma-ket algoritmni topishga harakat qiling (optimal emas, balki eng yaxshi)!
Shuning uchun, tezlashuvning amaliy ta'rifi
, ketma-ket algoritmning ishlash vaqtini va uning parallel versiyasini taqqoslashda keng qo'llaniladi.
Amaliy tezlashtirish = (
eng yomon dastlabki ma'lumotlar uchun ketma-ket algoritmning ishlash vaqti) / (ushbu algoritmning parallel versiyasining
dastlabki ma'lumotlar bilan ishlash vaqti).
Tezlashtirish tushunchasiga qo'shimcha ravishda parallel qiymat tushunchasi joriy etiladi
algoritm.
Qiymati = (parallel algoritm ish vaqti)
× (ijrochilar soni).
Bo'sh izchil algoritmning ish vaqti
T
s
(n) = Θ (F (n)) va qiymati paral-
chap algoritm ham bor Θ
(f (n)), keyin parallel algoritm optimal deb ataladi
qiymati.
Tanlash vazifasi uchun parallel algoritmni yaratish va uning qiymatini baholash mustaqil ravishda
yoki [Aki, 1989] da bo'lishi mumkin.