تعريف النموذج اللوغاريتمي

يمكن أن نتحقق من قواعد تعريف النموذج اللوغاريتمي ونطبقها على خوارزمية حساب ناتج جداء  مصفوفتين و تحليل الكلفة الناتجة :

الدخل : مصفوفتين   A=(aij) و  B=(bij ) من الحجم n 

الخرج : مصفوفة C=(cij )  من الحجم n حيث C=AB

الخطوات:

1. حساب ال n3 ناتج على التوازي حيث : t_aj = a_ik * b_kj
2. حساب الn2  مجموع على التوازي حيث : Ij=1…..n , c_ji=t_i1j+ t_i2j+……+t_inj

نتعمل المخطط التالي للتوضيح و نرمز فيه ب tk بدلا من tikj  و فيه n=8 و هو في الشكل التالي :

• الكلفة:

الخطوة l تتطلب وحدة زمن واحدة و n3 معالج.

لخطوة 2 تطلب [log n] + 1 خطوة و n3 معالج مطلوب.

عندما يكون العدد p من المعالجات ثابتا يكون التولزي منتهيا.

يمكن تحليل انجاز الخوارزمية عن طريق مقياسين أخرين وهما: زيادة السرعة والفعالية.

زيادة السرعة up  speed ونرمز لها Sp(n) تعرف بأنها النسبة بين كلفة الزمن لأفضل خوارزمية تسلسلية متوفرة وكلفة الزمن لخوارزمية التوازي التي نحللها.

 عندما تكون خوارزمية التوازي تملك على الأغلب p  معالج متوفر فإن: Sp(n)=T1(n)/Tp(n)  حيث n هو حجم المسألة.&