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

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

تعتبر الحاجة إلى تسريع عمليات الحساب حاجة دائمة ومتزايدة، وهي تتجاوز في حجمها ما هو متاح حالياً، ويظهر ذلك جلياً في مجالات مثل:

· النمذجة الرياضية (Numerical modeling).

· المحاكاة (Simulation).

· التنبؤ (Forecasting).

يجب التفكير في إنجاز الحسابات بأسرع زمن ممكن، أو خلال فترة زمنية مقبولة.

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

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

مسائل التحديات الكبرى (Grand Challenge Problems):

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

· نمذجة بنى DNA الضخمة.

· التنبؤ الجوي الشامل (Weather Forecasting).

· نمذجة حركة الأجرام السماوية (Modeling Motion of Astronomical Bodies).

التنبؤ الجوي (Weather Forecasting):

تُعدُّ مسألة التنبؤ الجويّ من أعقد المسائل، وذلك لضخامة المعطيات التي تجب معالجتُها.

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

فإذا أردنا تمثيلَ الغلاف الجوي حتّى ارتفاع 10 أميال، نجعلُ ضلعَ كلِّ مكعب 1 ميل، وبإجراء حساب بسيط يتعلق بمحيط الكرة الأرضيةِ والارتفاعِ الذي لدينا، نجد أن عددَ الخلايا 5×108 خلية. ولمعرفة عددِ العمليات الواجب إجراؤها لمعرفة الحالة الجوية في لحظة معينة، ما علينا سوى معرفة عدد العمليات على خلية واحدة، وعندئذ يكون:

عدد العمليات الكلي = عدد العمليات على خلية واحدة × عدد الخلايا

فإذا فرضنا من أجل كل مرحلة أننا بحاجة إلى 200 عملية فاصلة عائمة (floating point operations) من أجل كل خلية، بالتالي عدد العمليات الكلي من أجل مرحلة واحدة = 5×108×200=1011 عملية فاصلة عائمة.

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

عدد الأيام × عدد المراحل في اليوم × عدد العمليات في المرحلة = 7 × 24 × 60 × 1011=1015 عملية فاصلة عائمة.

وإذا استخدمنا حاسوب قادر على تنفيذ Mflops 100 (مليون عملية فاصلة عائمة في الثانية) عندها يكون:

الزمن اللازم = عدد العمليات الكلي / سرعة الحاسب =1015/108=107 ثانية، وهذا الزمن يساوي تقريباً 100 يوم!

التنبؤ بحالة الجو للأسبوع القادم يحتاج 100 يوم!

لو أردنا حلَّ المسألة خلال فترة زمنية قصيرة نسبياً (عشر دقائق) فنحن بحاجة إلى معالج خيالي، لنحسب سرعته:

عدد العمليات/ الزمن = 1015/600= 1.7 Tflops (أي حوالي 1.7 × 1012 عملية فاصلة عائمة في الثانية) وهذا الحاسوب للأسف غير متوفر!

إن مسألة التنبؤ الجوي مسألة معقدة جداً، ومن الصعب جداً حلها باستخدام البرمجة التسلسلية.

الغاية من الحساب التفرّعيّ:

تقوم البرمجة التفرعية على استخدام أكثر من حاسوب، أو استخدام حاسوب بعدة معالجات لإيجاد حلول لمشاكلَ ذاتِ عددٍ ضخم من العمليات الحاسوبية وذلك لتحقيق ما يلي:

· السرعة: وذلك بتنفيذ عمليات الحساب المطلوبة ضمن زمن أقصر، وهذا هو أحد الطموحات الكبيرة. ولكن السؤال الذي يطرح نفسه هنا: هل يعني استخدامنا N معالج أننا سنزيد السرعة بمقدار N مرة و بالتالي تخفيض زمن التنفيذ بمقدار N مرة؟

هذه الفكرة خاطئة تماماً، حيث نحتاج إلى زمنٍ للتواصل بين المعالجات وجمع النتائج المرحلية وتركيبها و... إلخ.

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

· القدرة على حل مسائل لا يمكن حلها باستخدام حاسوب واحد، أو يكون حلها معقد جداً أو مكلف جداً.

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

أنواع الحواسيب التفرعية:

يوجد نوعان للحواسب التفرعية حسب طريقة تشاركها للذاكرة الرئيسية:

1. حواسيب متعددة المعالجات ذات ذاكرة مشتركة (Shared memory multiprocessors).

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

يتوفر لكل المعالجات فضاءُ ذاكرةٍ وحيد، ويمكن لأي معالج أن يصلَ إلى أي عنوان من عناوين الذاكرة المشتركة. ويمكنُ استخدامُ ذاكرةٍ مخبئية (Cache Memory) لتسريع الوصول إلى الذاكرة المشتركة.

هناك بنيتان محتملتان:

· مسرى رئيسي يربط المعالجات والذواكر:

· جميع المعالجات ترتبط مع الذاكرة:

في هذا النوع، يكتب المبرمجُ بالطريقة التسلسلية العادية، ويتولى نظامُ التشغيل مهمةَ توزيع المهام على كلِّ حواسيب الشبكة. ولبرمجة هذا النوع من الحواسيب، توجد عدةُ طرق، منها خيوطُ التنفيذ أو المسارب (Threads)، والمكتبات على مستوى المستثمر (user-level libraries)، ولغات البرمجة التفرعية (Parallel programming (languages، والمترجمات التفرعية (Parallelizing compilers).

2. حواسيب متعددة المعالجات ذات ذاكرة موزعة (Distributed memory multiprocessors).

كل حاسب له ذاكرته الخاصّة، ولكن يتم التشارك وتبادل المعلومات بينهم عبر الشبكة. وتكون الطريقة المستخدمة للتواصل عادةً هي تبادل الرسائل.

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

لم يتنهِ حديثنا عن البرمجة التفرعية هنا، هناك المزيد في المقال القادم!

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