تخفيض عدد المعالجات 

 **تخفيض عدد المعالجات **

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

و لنرى كيفية تحقق هذا الهدف , لنفترض أن لدينا خوارزمية متوازية تأخذ كلفة زمنية   O(log  n)و تستعمل  O(n)  معالج و لنفترض أيضاً أن أفضل خوارزمية تسلسلية متوفرة تحل المسألة نفسها لها كلفة خطية.

و هذا يؤدي إلـى أن الخوارزمية المتوازية لها فعالية O(1/log  n) و هي بعيدة عن الكلفة الأمثلية في بعض الأحيان يمكن تحويل خوارزمية متوازية بمثل هذه الفعالية إلى خوارزمية متوازية أخرى بزمن O(log  n ) و عدد المعالجات O(n/log  n ) و منه بفعالية (1)q ، و منه ينتج ما يلي: يجب أن تقسم المسألة من الحجم n كما في طريقة التقسيم و التخصيص إلى n   n/log مسألة جزئية بحجم n  log ، عندئذ تحل كل مسالة جزئية بواسطة معالج مفرد باستعمال أفضل خوارزمية تسلسلية متوفرة (خطياً مع n log).

إذا وصل حل كل من المسائل الجزئية ال n   n/log إلى المسألة الابتدائية من الترتيب n n/log عندئذ نستطيع أن نستعمل الخوارزمية المتوازية بأخذ زمن:

و بشكل عام يجب أن تطبق المعادلة التالية على المسألة pnمن أجل kيقسمn:

العلاقة 5:   

تعني العلاقة (5) أن المسألة Pn  يمكن أن تجزأ إلى k مسألة جزئية Pn/k من نفس النوع ، تولد حلولها مسالة pk يمكن أن تحل بعد ان يتم حل جميع المسائل الجزئية k .

لنفترض أنه لكي نحل pk  يوجد لدينا :

1 - خوارزمية متوازية Ap تمثل ب TAP(n) و HAP(n)

2 - خوارزمية تسلسلية A مع كلفة (مثلاً عدد العمليات ) TA(n)

لنفترض أن TAP(n)HAP(n)=Ta(n)f(n) حيث (n)f دالة متزايدة ب n.

و لذلك فإن فعالية الخوارزمية Ap تعطى بالعلاقة (l/f(n وهذا يعني أن الخوارزمية تقوم باستعمال إضافي (زائد) للمصادر.

ومنه يمكننا أن نستتتج ونفترض دالة (n)   g كما يلي:

من العلاقة 6 نجد انه يمكن حل pk  كما يلي :

1-حل pn/g(n)  بمعالج مفرد باستعمال خوارزمية A

2-حل pg(n)  باستعمال خوارزمية متوازية Ap .

يماثل هذا الإجراء خوارزمية متوازية جديدة A* و H*  تعطى بالعلاقة