G‘afarov, A. F. Galimyanov parallel hisobiyotlar qo'llanma Qozon

Parallel algoritmning bajarilish vaqtining yuqori chegarasi

Ishlatilgan protsessorlarning istalgan soni uchun - s amal qiladi

parallel algoritmning bajarilish vaqti uchun keyingi yuqori chegara

^< ÿ ^{+ 1/}

(3.24)

Haqiqatan ham, ÿ bo'lsin minimal darajaga erishish uchun jadvalga ega bo'ling

^{mumkin bo'lgan bajarilish vaqti ÿ. Har bir iteratsiya uchun 0 <<} ÿ

jadvalni bajarish ÿ
bilan belgilang
tranzaktsiyalar soni

t takrorlash vaqtida bajariladi . Algoritmni bajarish jadvali bilan

Machine Translated by Google
s protsessorlari yordamida quyidagi tarzda qurish mumkin.

Algoritmning bajarilishini quyidagilarga ajratamiz ÿ qadamlar; har bir qadamda t quyidagicha

jadvalning t iteratsiyasida bajarilgan barcha operatsiyalarni bajarish

^ÿ. Bu amallar uchun nt / s dan ortiq bo'lmagan iteratsiyalarda bajarilishi mumkin
s protsessorlaridan foydalanish . Natijada Ts algoritmining bajarilish vaqti quyidagicha baholash mumkin:

ÿ ÿ
= ÿ ] [⁼<1 ÿ ] + 1[ = ⁼ 1

1
+ ^{ÿ ,}
(3,25)

bu yerda ]*[ - yo‘nalish bo‘yicha butun songacha yaxlitlash amalini bildiradi

kattalashtirish.

Yuqoridagi fikr-mulohazalar, mohiyatan, amaliy yo'l beradi parallel algoritmni rejalashtirish. Dastlab shunday bo'lishi mumkin jadval cheklangan sonini hisobga olmasdan tuzilgan protsessorlar ( parakompyuter uchun jadval). Keyin, muvofiq

yuqorida tavsiflangan sxema bo'yicha, ma'lum bir uchun jadval tuzilishi mumkin

protsessorlar soni.

8.