مفاهيم اساسية لبناء خوارزمية متوازية بكلفة امثلية

** مفاهيم اساسية لبناء خوارزمية متوازية بكلفة امثلية **

ليكن زمن تنفيذ الخوارزمية التسلسلية لاتجاز مهمة بحجم n  هو  o(n)  و زمن تتفيذ الإصدار المتوازي لهذه الخوارزمية هو o(log n)  حيث: عدد المعالجات المستعملة، كل منها يمسك عنصر بيانات واحد.

ولذلك فان الكلفة هي:

Cost=no(log n ) = o(nlog n) هذه الكلفة ليست أمثلية.

وللحصول على خوارزمية بكلفة أمثلية  نحتاج أحد أمرين : إما تخفيض زمن التتفيذ (1)0 أو انقاص عدد المعالجات إلى n/logn ولذلك فإن ناتج الضرب ل n  n/log مع o(log n ) يعطيo(n)

ليكن كل معالج يأخذ n   log عنصر بيانات. فإذا كانت العملية التسلسلية خطية في عدد عناصر البيانات عندها كل من لـ  n/log n معالج سينجز عملية تسلسلية على التوازي على كل من عناصر بياناتها

ال   log n في زمن o(log  n )  إضافة الى  أن المعالجات ال  n/log n ستتجز الخوارزمية السابقة (غير الأفضلية) على النتائج n/log n من الخطوة التسلسلية في:

     &

**خواص الخوارزميات المتوازية**

&   خواص الخوارزميات المتوازية:

هناك خصائص هامة نرغب في الحصول عليها في الخوارزمية المتوازية.

1-عدد المعالجات : الخاصية الأولى هي عدد المعالجات المستخدمة في الخوارزمية. بفرض n هو حجم المسألة التي نريد حلها فإن:

ا- p(n) يجب أن تكون أصغر من n : إنه من غير الواقعي أن نفترض أن المعالجات أكثر من مفردات المعلومات خاصة من أجل قيم كبيرة جدا لـ n.

ولنلك من المهم أن تكون (P)n تعبر عن دالة أسية أو لوغاريتمية في n وهذا يعني: O<X<I   p(n)=n^x  .