Parallel hisoblash

3.2. Parallel hisoblash jarayonining samaradorligini baholash

Algoritmni tahlil qilish algoritm samarali yoki yo‘qligini aniqlashga yordam beradi. Umuman olganda, algoritm uning bajarilish vaqti (Vaqt murakkabligi) va unga kerak bo‘lgan bo‘sh joy miqdori (Kosmik murakkablik) asosida tahlil qilinadi.

Bizda arzon narxlarda mavjud bo‘lgan murakkab xotira qurilmalari mavjud bo‘lganligi sababli, saqlash joyi endi muammo emas. Demak, kosmik murakkablikka unchalik ahamiyat berilmaydi.
Parallel algoritmlar kompyuterning hisoblash tezligini oshirish uchun mo‘ljallangan. Parallel algoritmni tahlil qilish uchun biz odatda quyidagi parametrlarni ko‘rib chiqamiz -

• 
  Vaqtning murakkabligi (bajarish vaqti),
  
• 
  Amaldagi protsessorlarning umumiy soni,
  
• 
  Umumiy xarajat.
  

Algoritmning bajarilish vaqtini baholash uning samaradorligini tahlil qilishda juda muhimdir. Bajarilish vaqti algoritm tomonidan muammoni hal qilish uchun sarflangan vaqt asosida o‘lchanadi. Umumiy bajarilish vaqti algoritm bajarila boshlagan paytdan to to‘xtab qolgan vaqtgacha hisoblanadi. Agar barcha protsessorlar bir vaqtning o‘zida bajarishni boshlamasa yoki tugatmasa, u holda algoritmning umumiy bajarilish vaqti birinchi protsessor o‘z ishini boshlagan vaqtdan oxirgi protsessor o‘z bajarilishini to‘xtatgan paytgacha bo‘ladi.
Algoritmning vaqt murakkabligini uch toifaga bo‘lish mumkin-

• 
  Eng yomon holatdagi murakkablik - Berilgan kirish uchun algoritm tomonidan talab qilinadigan vaqt maksimal bo‘lganda.
  
• 
  O‘rtacha murakkablik - berilgan kirish uchun algoritm tomonidan talab qilinadigan vaqt miqdori o‘rtacha bo‘lganda.
  
• 
  Eng yaxshi holat murakkabligi - Berilgan kirish uchun algoritm tomonidan talab qilinadigan vaqt minimal bo‘lganda.
  

Algoritmning murakkabligi yoki samaradorligi - bu algoritm tomonidan kerakli natijani olish uchun bajariladigan qadamlar soni.