Parallel hisoblash

Asimptotik tahlil algoritmni nazariy tahlil qilishda uning murakkabligini hisoblash uchun amalga oshiriladi. Asimptotik tahlilda algoritmning murakkablik funksiyasini hisoblash uchun kiritishning katta uzunligidan foydalaniladi. Asimptotik belgilar yuqori va past tezlik chegaralaridan foydalangan holda algoritmning eng tez va eng sekin bajarilish vaqtini tasvirlashning eng oson usuli hisoblanadi[16, 27].
Parallellashtirish samaradorligining asosiy o‘lchovi tezlikni oshirishdir, parallellashtirish samaradorligi (S_N), bitta protsessordagi hisoblash ish yukini(W) bajarish vaqtining N protsessordagi vaqtga nisbati sifatida aniqlanadi, ya’ni
(3.1)
Bunda, - bitta protsessorda ish yukini bajarish vaqti va -N protsessorda ish yukini bajarish vaqti.
vaqti quyidagi uch ta had yig‘indisi orqali hisoblanadi,

bunda ish yukining ketma-ket qismini bajarish uchun ketgan vaqt , parallel qismni bajarish uchun ketgan vaqt va jarayonni parallellashtirish uchun ketgan qo‘shimcha vaqt , bunda umumiy holatda barcha qo‘shimcha vaqtlar sarfini hisobga oladi. Qo‘shimcha vaqtlar sarfini keltirib chiqaruvchi omillar odatda apparat, tarmoq, operatsion tizim yoki algoritmni parallel protsessorda amalga oshirish uchun ketib qolishi mumkin. Biz buni protsessorlar soni N va ish yuki W ga nisbatan funksiya sifatida qarasak quyidagi holat kelib chiqadi,
.
Nazariy tezlashtirish, , nol parallelizatsiya qo‘shimcha xarajatlarini nazarda tutadigan tezlikdir,
.
Haqiqiy tezlik (3.1) formuladan quyidagicha ko‘rinish oladi:
.
Bundan ko‘rinadiki, nazariy tezlashtirish samaradorlik jihatidan erishish mumkin bo‘lgan eng yaxshi holatdir. Haqiqiy tezlashtirishning nazariy tezlikka nisbati parallellashtirish samaradorligi koeffitsiyentiga teng,
.
Ushbu koeffitsiyent parallel protsessorning berilgan parallel algoritmni bajarish samaradorligini bildiruvchi o‘lchovdir. Bundan, parallellashtirish samaradorligi koeffitsiyenti qo‘shimcha vaqt sarfi tufayli ishlashning har qanday jarayonlarida ham birdan kam bo‘lishini bilish mumkin.
Endi ketma-ket jarayonni hisoblash holatini quyidagi formula asosida qarasak,

bu yerda
-W_S ketma-ket ish yuki;
-W_P -parallel ish yuki;
-W -umumiy hisoblash ish yuki (W=W_S +W_p).
Ta’rifi bo‘yicha hisoblash, protsessorlar soni N ta bo‘lgan holatida ham o‘rinli hisoblanadi. Biz W ni ish yukining ixtiyoriy birliklarida aniqlaymiz va protsessor tezligini v (sekundiga ish yuki birligi) deb faraz qilamiz, bu nazariy tezlikni quyidagi ifodaga olib keladi:

yoki

Yuqorida keltirilgan hisoblash samaradorligini baholash formulasining natijasi “foizlarda” yoki “baravar” nisbatlarda qiymatlanadi.
Algoritmlarni baholashda parallel protsessorlar tizimida texnik jihatdan mumkin bo‘lgan hisoblash kechikishlari quyidagi jarayonlarga bog‘liq bo‘ladi:

1. 
   Xotiradan o‘qish – N ta protsessor tomonidan umumiy xotiradan ma’lumotlarni o‘qish;
   
2. 
   Xotiraga yozish – N ta protsessor tomonidan umumiy xotiraga ma’lumotlarni yozish;
   
3. 
   Aloqa - tizimda N ta protsessor mavjud bo‘lganda, bir juft protsessor o‘rtasidagi aloqa kechikishi;
   
4. 
   Ma’lumotlarni qayta ishlash – N ta parallel protsessorlar yordamida ma’lumotlarni qayta ishlashni kechikishi.