أساسيات البرمجة التفرعية (الجزء الثاني)

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

في الخوارزميات التسلسلية كنا نقوم بحساب التعقيد للوقت وعدد العمليات، ونصنّف التعقيدات إلى خطية وأسية وانفجارية... إلخ. حيث كنا نعرف التعليمات التي تأخذ أكبر زمن ونحسب التعقيدَ الزمني لها. ولكن الأمرَ في البرمجةِ التفرعية مختلف، فالخوارزمية موّزعة على عدةِ حواسيب، لذلك هنالك ثلاثةُ عوامل نحدّدُ من خلالها تعقيدَ الخوارزمية وكفاءتها، وهي معاملُ التسريع والفعاليةُ والكلفة.

1. معامل التسريع أو زيادة السرعة (Speedup Factor): هذا المعامل مماثلٌ لمعامل التعقيدِ في حالة البرمجة التسلسلية، ويقوم بتقييم أداءِ الحساب التفرعي، حيث يمثّلُ الربحَ الذي أحصل عليه إذا استخدمتُ الآلة التفرعية مقارنة بالآلة التسلسلية، ونحصل عليه من العلاقة:

معامل التسريع = زمن التنفيذ باستخدام معالج واحد \ زمن التنفيذ التفرعي

المشكلة في هذه العلاقة هي في عملية حسابِ زمنِ التنفيذ باستخدام معالجٍ واحد، حيث إن لم نستطع إيجادَ التقديرِ المناسب للمسألة المطروحة تسلسلياً، عندها نضطرُّ إلى تجريب حل المسألة على معالج وحيد وحساب الزمن.

قد تظهر مشكلةٌ أخرى وهي وجود معالجات ذات سرعات مختلفة، أي منها سنختار لحساب زمن التنفيذ التسلسلي؟ يمكن إيجاد أسوء حالة أو الوسطية أو أفضل حالة لاعتمادها.

كما يمكن التعبير عن معامل التسريع باستخدام عدد خطوات الحل:

معامل التسريع = عدد خطوات الحل باستخدام معالج واحد \ عدد خطوات الحل باستخدام p معالج

القيمة العظمى لمعامل التسريع هو عدد المعالجات المتوفرة للحل، بافتراض أننا نستخدم المعالجات بشكل متماثل، ولكننا لا نصلُ لهذه الحالة لأسبابٍ عديدة منها أن التوزيعَ لا يكون بالتساوي دائماً، ففي بعض الأحيان هناك حواسيبٌ لا تأخذ أيَّ جزءٍ من العمل، وهناك حواسيب تأخذ جزءًا أكبرَ من غيرها. كما لدينا زمنُ التواصل بين الحواسيب، فقد تكون البنية سيئة وبالتالي زمن التواصل كبير... إلخ. ولكن يمكننا القول كلما اقترب معامل التسريع من عدد الحواسيب التفرعية تكون الأمورُ أفضل.

2. الفاعلية (Efficiency): بسبب المشاكل التي ظهرت في حساب معاملِ زيادة السرعة، فإننا نحاول إيجادَ معاملٍ جديد لتقييم أداء الحساب التفرعي، وهذا المعامل ينبع من السؤال التالي: ما مدى استخدام الآلة التفرعية؟

الحالة المثالية هي عندما يكون استخدامُ الآلة التفرعية 100%، ويتحقق ذلك عندما يكون معامل زيادة السرعة أعظمي أي يساوي عدد المعالجات.

الفاعلية = زمن التنفيذ على معالج واحد \ ز من التنفيذ التفرعي × عدد المعالجات

= معامل زيادة السرعة \ عدد المعالجات

ولكن نادراً ما نجد مسألةً تفرعيةً خالصة، فلابدّ من وجود جزءٍ تسلسلي بحت يعمل على معالج واحد فقط بلحظة ما وتتوقف بقيةُ المعالجات خلال هذا الجزء، لهذا فإننا نحاول أن نصل بالفاعلية إلى درجة قريبة من القصوى.

3. الكلفة أو العمل Cost(Work): بشكل عام، نحصل على كلفةِ برنامج من جداء زمن التنفيذ بعدد المعالجات المشاركة وبالتالي:

كلفة البرنامج التفرعي = زمن التنفيذ × عدد المعالجات

كلفة البرنامج التسلسلي = زمن التنفيذ × 1 (عدد المعالجات = 1)

للاستفادة من هذا المعامل في تقييم الأداء ننفذُ البرنامجَ مرتين تسلسلياً وتفرعياً ونقارن بين الكلفتين، وعندها إذا كانت كلفة البرنامج التفرعي تساوي كلفةَ البرنامج التسلسلي، فهذا يعني أن استغلالَ التفريع ممتاز.

الاستجابة العظمى وقانون أمدال (Maximum Speedup - Amdahl’s law):

أغلب المسائل التي نتعامل معها لها جزءٌ تسلسلي وجزء قابل للتفريع. بفرض أن نسبةَ الجزء التسلسلي هي f، بالتالي زمن تنفيذ هذا الجزء f×ts، حيث ts زمن التنفيذ التسلسلي دون أي تفريع، يكون زمن تنفيذ الجزء التفرعي (1-f)×ts ككل، وحتى نعلم زمن تنفيذ الجزء التفرعي على أحد المعالجات، نأخذ زمن التنفيذ على جميع المعالجات ونقسم على عددها، أي زمن التنفيذ التفرعي على معالج واحد هو: ts×f+((1-f)×ts)/p

أضفنا هذا الحد ts×f لأنّ الحاسوب الأول الذي حصل على الجزء التسلسلي يعمل تفرعياً مع البقية، وبالتالي يجب إضافته للعلاقة.

وبالتالي حتى نقومَ بحساب الزيادة في سرعة المعالجة، يجب أن نقوم بحساب معامل التسريع حسب القانون: زمن التنفيذ التسلسلي على زمن التنفيذ التفرعي، فنحصل على القانون التالي:

تسمّى العلاقة الأخيرة بقانون أمدال، وكما نلاحظ أنّها تحتوي على P أي عدد المعالجات، وهذا يعني أن عددَ المعالجات أمر مهم ويؤثر على الحل.

حتى نثبت أن الإكثار من عدد المعالجات بشكل كبير لا يؤدي إلى تحسنِ معامل التسريع بشكل دائم، سنجعل عدد المعالجات p يتناهى إلى اللانهاية وبالتالي سيتناهى معامل التسريع إلى1/f ولن يتجاوزها مهما زدنا عدد المعالجات:

يوضّح الشكل التالي العلاقة بين عدد المعالجات و زيادة سرعة المعالجة:

نظرياً لا توجد مسألةٌ لا تحوي جزءًا تسلسليًّا، وبالتالي مهما كان الحلُ جيدًا فهو محدود بمنصف الربع الأول ولن يتجاوزه، أي يكون الحل جيدًا ولكنه غير أمثل، ولا يمكن الوصول للحل الأمثل إلا إذا كانت نسبة الجزء التسلسلي معدومة، وهذا الشيء غير موجود عملياً إلا بخوارزميات البحث كالبائع الجوال.

قابلية التوسع وقانون غوستافون (Scalability- Gustafson law):

كثير من الأحيان نكتب خوارزميةً فعّالة لرتبة معينة، ولكن عند تكبير هذه الرتبة نجدها أصبحت غيرَ فعّالة، أو أصبح زمنها كبيرًا جدًا مقارنة بزمنها السابق عندما كانت تحل المشكلة برتبة أقل.

مثلاً في جمع المصفوفات عند تحويل الرتبة من n إلى 2n، ستكونُ الزيادة بمقدار مرتين وهي معقولة، بينما بالضرب ستكونُ الزيادة أكبر بمقدار أربع مرات، أما بمسألة البائع الجوال ستكون الزيادة انفجارية، إذاً تتفاوتُ الزيادة حسب المسألة وأحياناً تكون غير معقولة. عند الحل بطريقة تفرعية يجب أخذُ التوسّع بعين الاعتبار، أي يجب أن نأخذَ بعين الاعتبار التعاملَ مع معطياتٍ بحجم أكبر.

قانون غوستافون: يشبه قانون أمدال لكنّه يعتمدُ على مفهوم التوسّع، وينصّ على أن زيادةَ حجم المسألة يتناسب طرداً مع عدد المعالجات، لكن بشرط بقاء الجزء التسلسلي ثابت عند تلك الزيادة. يوضّح الرسم التالي قانون غوستافون، وسنشرح من أين أتى هذا القانون:

إذا نظرنا إلى الجزء الأفقي من الرسم لحساب زمن الجزء التسلسلي، سنقوم بتجزئة الزمن لإدخال عددِ الحواسيب بالقانون، كما يلي:

القسم الأول هو الجزء التسلسلي من المسألة وزمنه يساوي f×ts، والقسم الثاني هو الجزء الذي يمكن تفريعه وزمنه على حاسب واحد هو (1-f×ts)، والزمن على n معالج هو الزمن السابق بعد ضربه بـn، فيصبح القانون كما يلي:

ts = f×ts+ (1-f) ts×n

وبالنظر للجزء العامودي من الشكل، نستطيع حسابَ الزمن التفرعي، وهو عبارة عن زمن الجزءِ التسلسلي من المسألة وزمن التنفيذ على أحد المعالجات التفرعية (أحدها وليس جميعها لأنّنا هنا قمنا بالتفريع، والحواسب تعمل معاً)، فيكون القانون :

tp = f×ts+ (1-f) ts

ويكون معامل التسريع:

هناك تناسب طردي بين معامل التسريع وعدد الحواسب n كما ذكرنا ولكن بشرط ثباتِ الجزء التسلسلي. لاحظوا أن قيمة f هي نفسها في حدّي القانون .

هناك مشكلة في البرمجة التفرعية هي أنّنا لا نستطيعُ تحسينَ حلٍّ وتعديل حلول لم نراها أثناء كتابتها، لذلك الاتجاه الآن نحو الأدوات التي تسهّل تلك الأمور ويكون تحويل النص البرمجي ليناسب الحلَّ التفرعي أسهل بكثير من قبل.

سؤال سيُطرح علينا دائمًا: ما هو عدد المعالجات المناسب لحل المشكلة؟ لدينا مُخدم بطيء ونريد تسريعَه فما العمل؟ هل نزيد عدد المعالجات؟ هل نستبدل العتاد؟ هل نغيّر المُخدم بأكمله؟

يجب أن نعطي حلولًا منطقية وتابعة لبراهين عمليّة، قد تكون الآلة ممتازة كعتاد ولكن البرمجية المطبّقة سيئة ولا تستخدم الموارد الموجودة.

---------------------------

المصدر:

Parallel Programming-Techniques and applications using networked workstations and parallel computers-Barry WILKINSON & Michael ALLEN

------------------------