تصميم الخوارزميات المتوازية و تقانات افضل خوارزمية ممكنة

تعتبر عملية التصميم لخوارزمية معينة انها عملية حركية حيوية و تتميز بعدم وجود قانون او قاعدة ثابتة للحصول على خوارزمية معينة ذات كلفة قليلة .

و يجدر الذكر ان هناك الكثير من القضايا و المسائل الهامة جدا لم يتم ايجاد خوارزمية لحلها بعد بحيث تكون ذات كلفة متوسطة او قليلة .

، ولكن هناك بعض الاستراتيجيات الرئيسية تقود للحصول على خوارزميات ذات كلفة مقبولة.

لن الشكل الطبيعي لتطوير الخوارزميات المتوازية هو بالبدء من الخوارزمية التسلسلية ومن ثم تحديد الخطوات المستقلة وأخيرا لحصول طى الخوارزمية المتوازية.

وهذا التحول من التسلسل لى التوازي ينتج غالبا خوارزميات متوازية ذات كلفة منخفضة.

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

سنرمز فيما يلي إلى كل من الزمن والمكونات المادية وعدد المعالجات وللزمن ولعدد المعالجات بآن معا ب: T و H و P و PT على التولي. &

**التقسيم و التخصيص**

& التقسيم والتخصيص impera et Divide:

ان اعتماد هذه التقنية الاساسي هو تجزيء المسالة الكبرى الى مسائل صغيرة جزئية من نفس النوع ولكن بحجم أصغر ومن ثم إعادة ترتيب وتجميع الحلول.

وهي طريقة فعالة جدا حيث تسمح بتجزئة المسالة الى مسائل جزئية مستقلة تحل على التوازي وتجمع حلولها للحصول على حل المسالة الاصلية.

أما بالنسبة لكلفة الحل المتوازي لمسألة حسابية من الترتيب n وبالتالي من الحجم H(n) والعمق (T)n لدينا:

لتكن r عدد صحيح يقسم n ولتكن (Hi)n/r و (Ti)n/r (حيث: i=1,2,,,,,r ) هي كلف