برمجه تفرعيه

Parallel programming -

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

خلدون خُرزُم

الإمكانات المحتملة لزيادة المقدَّرات الحسابية	نظم التشغيل التفرعية
أنواع الأنظمة المتعددة المعالجات	موازنة الأعباء وتحمل الخلل
البرمجيات الداعمة للأنظمة المتعددة المعالجات	تطبيقات وآفاق

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

الإمكانات المحتملة لزيادة المقدَّرات الحسابية

إن ما يهم بالدرجة الأولى عند تطوير خوارزمية معينة لتنفيذها على نظام متعدد المعالجات؛ هو مدى تسريع الحساب الذي يمكن أن يقدّمه هذا النظام مقارنةً بتنفيذ الخوارزمية على نظام وحيد المعالج. ويمكن حساب معامل التسريع S(p) وفق العلاقة (1)(حيث p عدد المعالجات):

إن معامل التسريع الأعظمي النظري وفق العلاقة (1) هو p بفرض أن زمن تنفيذ الخوارزمية قابل للتقسيم والتوزيع على نحو متساوٍ بين المعالجات، وأن تفريع الخوارزمية لا يتطلب أعباء زمنيةً إضافية. ولا يمكن الوصول عملياً إلى هذا الحدّ النظري للتسريع؛ إذ تُسهم عوامل متعددة في إضافة زمن في النسخة التفرعية للخوارزمية غير موجود في نسختها التسلسلية يَحدُّ من مقدار التسريع، من تلك العوامل:

1- الفترات الزمنية التي لا يمكن لكل المعالجات أن تنفّذ فيها جزءاً من البرنامج، وبهذه الحالة تكون هذه المعالجات بوضعية خمول idle وتوقّف عن العمل.

2- توفّر حسابات إضافية في النسخة التفرعية للبرنامج غير ظاهرة في نسختها التسلسلية، مثل إعادة حساب بعض المعاملات محلياً.

3- الزمن اللازم لتبادل المعطيات بين المعالجات.

إضافةً إلى ذلك فمن المنطقي ألاَّ تقبل بعض مراحل الحسابات التجزئة إلى مهام تفرعية، إذ ينبغي تنفيذها تتابعياً.

فإذا كان المطلوب هو تفريع خوارزمية ما على p معالجاً، وكان الجزء من الحسابات الَّذي لا يمكن تجزئته إلى مهام تفرعية هو f، وبإهمال أي زمن إضافي ناتج من تفريع البرنامج؛ فإن معامل تسريع البرنامج يُعطى بالعلاقة (2) التي تُعرف بقانون «أمدال» Amdahl’s law:

ومنه فإن معامل التسريع الأعظمي هو:

أي إذا وَجَبَ على 5 % من الحسابات أن تُجرى تتابعياً في برنامج ما؛ فإن مقدار التسريع الأعظمي هو 20 مرة مهما كَثُر عدد المعالجات.

أنواع الأنظمة المتعددة المعالجات

يمكن أن تصنّف الأنظمة المتعددة المعالجات من وجهة نظر توزيع الذاكرة في نوعين: نظام متعدد المعالجات ذي ذاكرة مشتركة shared memory؛ وهي الأكثر استخداماً في الأنظمة الحديثة، ونظام متعدد المعالجات ذي ذاكرة موزّعةdistributed memory . كما برز منحى إضافي يستخدم حشداً من الحواسيب الشخصية أو محطات العمل لتشكيل منصَّة عمل تسمى العنقود cluster.

البرمجيات الداعمة للأنظمة المتعددة المعالجات

جرى تصميم لغات البرمجة التفرعية والبيئات الموافقة تبعاً للنموذج العتادي للنظام التفرعي؛ وتحديداً وفق هيكلية الذاكرة: ذاكرة موزّعة، أو ذاكرة مشتركة، أو نظام عنقودي.

1- الأنظمة المتعددة المعالجات ذات الذاكرة المشتركة

تدعم بيئة تعدد المعالجات المفتوحة Open Multi-Processing (OpenMP) البرمجة بلغة C أو ++C للأنظمة التفرعية ذات الذاكرة المشتركة بهيكليات ونظم تشغيل مختلفة. تقدّم هذه البيئة للمبرمجين واجهات عمل لتطوير التطبيقات التفرعية؛ إن كانت على الحواسيب الشخصية المتضمِّنة معالجات متعددة النوى أو الحواسيب المخصَّصة العالية الأداء.

تعتمد OpenMP على تعدد النياسب multithreading، وهو طريقة تفريع parallelizing من خلالها يقوم نيسب thread رئيسي (مجموعة من التعليمات التي تُنفذ تسلسلياً) بالتشعب إلى عدد محدد من النياسب التابعة slaves ليجري تقسيم المهمة فيما بينها، بحيث تُنفذ تفرعياً كل منها على نواة أو معالج. يجري تشكيل النياسب للجزء من البرنامج المعَد للتنفيذ التفرعي قبل التنفيذ. ويعطى كل نيسب رقماً تعريفياً خاصاً به، في حين يأخذ النيسب الرئيسي الرقم التعريفي صفراً. وبعد التنفيذ التفرعي لهذا الجزء من البرنامج، تعود النياسب التابعة لتنضم إلى النيسب الرئيسي الذي يُكمل تنفيذ البرنامج. تتكون الوحدات الأساسية لــ OpenMP من عناصر خلق النياسب، وتوزيع الأعباء، والتزامن بين النياسب، وإدارة معطيات البرنامج ومتحولاته. ولمّا كانت OpenMP خاصة بالأنظمة ذات الذاكرة المشتركة، فإن متحولات البرنامج العامة تكون متاحة لجميع النياسب، إضافة إلى المتحولات الداخلية الخاصة بكل نيسب.

توفر مكتبات مثل Pthreads وShmem العديد من البرامج الفرعية التي تتيح إمكان توليد النياسب وإدارتها، وهذا يؤدي إلى سهولة نسبية بالبرمجة.

2- الأنظمة المتعددة المعالجات ذات الذاكرة الموزّعة

توفِّر الواجهة البينيّة لتمرير الرسائل Message Passing Interface (MPI) مجموعة من البرامج الفرعية ضمن مكتبة معيارية تُتيح كتابة برامج فعالة بلغات برمجة - مثل C, C++, Fortran- لتبادل الرسائل بين عقد النظام التفرعي وتزامن المهام الموزّعة بينها الذي يعتمد على بنية الذاكرة الموزّعة، مثل: الحواسيب التفرعية، والعناقيد، والشبكات غير المتجانسة. واعتماداً على برامج المكتبة تلك بالإمكان بناء برامج للتراسل في تلك الأنظمة التفرعية. لا تُعدّ MPI لغة برمجة، وإنما يجري استدعاء برامجها الفرعية من قبل برامج النظام. جرى تصميم MPI لتوفر طوبولوجيا افتراضية virtual، والتزامن، وآليات التراسل بين مجموعة من الإجرائيات على نحو مستقل عن لغة البرمجة، حيث يجري مقابلة كل إجرائية بعقدة معالجة (حاسب أو مخدم)، وللحصول على أداء مرتفع يجري عادة نسب إجرائية واحدة إلى كل عقدة معالجة. وتدعم جميع منصات عمل أنظمة الحسابات العالية الأداء الواجهة MPI مع قابلية للتوسع scalability.

تحتوي الهيكلية الأساسية لبرنامج يستخدم MPI على رابط communicator، وهو متحول variable يُعرِّف الإجرائيات المسموح بها بالتخاطب فيما بينها، كما تحتوي الهيكلية أيضاً على تهيئة لبيئة MPI قبل أن يجري استدعاء أي تابع من توابعها، وإغلاقها عند الانتهاء من تلك البيئة.

يشمل تراسل المعطيات في MPI نوعين: تراسل نقطة إلى نقطة، وفيه يتشارك معالجان فقط بتبادل المعطيات، والنوع الثاني هو تراسل المعطيات الجمعي، وفيه تتشارك كل المعالجات المعرّفة داخل رابط بتبادل المعطيات.

3- الأنظمة العنقودية

توفر الآلة الافتراضية التفرعية Parallel Virtual Machine (PVM) بيئة للمبرمجين لتطوير تطبيقات على أنظمة متعددة المعالجات - تحديداً الأنظمة العنقودية - والتحكم في المهام الموزّعة على العقد والتزامن بينها. كما تتيح تلك البيئة الأدوات البرمجية اللازمة لتبادل الرسائل بين عقد النظام التفرعي. تُستخدم هذه البيئة على نطاقٍ واسع؛ إذ تضمن التشغيل البيني interoperability بين عقد النظام حتى غير المتجانسة وبوجود نظم تشغيل مختلفة.

نظم التشغيل التفرعية

نَحتْ أنظمة التشغيل الحديثة منحيين لتلبية الاهتمامات المتزايدة للتطبيقات التفرعية. المنحى الأول اتخذته نظم التشغيل الحديثة من UNIX وWindows بدءاً من الإصدار NT والتي تهتم بالأنظمة المتعددة المعالجات المتناظرة symmetric multiprocessing، في حين اتخذ المنحى الآخر نوى نظم تشغيل مخصصة custom kernels. تهتم نظم التشغيل التفرعية بصورة أساسية بالجدولة، والتزامن، وتعدد النياسب، وإدارة الذاكرة وتحمل الخلل.

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

موازنة الأعباء وتحمل الخلل

يهدف توزيع الأعباء (الإجرائيات) بصورة متوازنة بين المعالجات إلى الحصول على أعلى أداء ممكن من النظام التفرعي، ويُقسم إلى نوعين: التوزيع السكوني؛ إذ تُوزّع إجرائيات البرنامج قبل البدء بتنفيذها ويُشار إليها على أنها مسألة جدولة ساكنة static scheduling، والتوزيع الديناميكي olynamic حيث تُوزّع الإجرائيات في أثناء تنفيذ البرنامج. يُصنّف التوزيع الديناميكي في: مركزي- وهو المستخدم على نطاق واسع- حيث يجري توزيع الإجرائيات بواسطة برنامج مركزي يُنفَّذ على أحد المعالجات ويقوم بدور السيد master، في حين تقوم الإجرائيات الموزعة على المعالجات بدور التابع slave. أما الصنف الآخر فهو غير المركزي، وبه تعمل مجموعة من المعالجات على المسألة المعنية عن طريق إمرار الإجرائيات بينها. تلجأ الأنظمة العالية الأداء إلى التوزيع الديناميكي المركزي المتعدد الطبقات؛ إذ تأخذ هيكلية المعالجات البنية الشجرية أو العنقودية، وفيها توزِّع كل طبقة الإجرائيات على الطبقة الأدنى وفق علاقة السيد-التابع.

تُتيح البنى التفرعية وتوزيع المهام تحمل الخلل، ففي حال اكتُشِف خلل بأحد المعالجات -عن طريق المراقبة المستمرة لأدائها- يجري إعادة توزيع المهام الموكلة إليه على معالجات أخرى عاملة، ولتجنب انخفاض الأدائية في النظام كله بهذه الحالات تُصمم الأنظمة بحيث تحتوي عادة على معالجات إضافية احتياطية تعمل بحالة تأهب hot-standby تبدأ بتنفيذ المهام الموكلة فور إسنادها إليها، ويسبق ذلك إعادة دمج المعالج وفق هيكلية النظام.

تطبيقات وآفاق

برزت البرمجة والحوسبة التفرعية لتحقيق المسائل التي تحتاج إلى مُقدَّرات حسابية هائلة. وبرزت الحاجة في مختلف مناحي الحياة إلى الإمكانات التي تتيحها الحوسبة التفرعية. وعلى سبيل المثال في مجال الإنترنت (الشابكة) ومع ازدياد الحاجة إلى الخدمات المتنوعة التي تقدّمها- مثل محرّكات البحث والتنقيب في المعطيات والخدمات التجارية المعتمدة على الوب ونحوها- يجري تصميم مخدّمات الوِبْ وتنفيذها اعتماداً على الأنظمة العنقودية؛ بهدف الاستجابة لطلبات المستخدمين خلال زمن معقول.

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

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

ويكمن التحدي في كتابة برامج تفرعية ذات كفاءة ودقة للأنظمة التفرعية التي تحتوي على عشرات آلاف المعالجات وبقدرة حسابية من مرتبة بتا عملية فاصلة عائمة في الثانية Petaflops/second.

ثمة مقولة للباحث «باترسون Patterson» من مخبر البرمجة التفرعية في جامعة «بركليBerkley بكاليفورنيا» المستقبل للبرمجة التفرعية، والبرمجة التتابعية في طور الانقراض».

مراجع للاستزادة: -P. Pacheco, An Introduction to Parallel Programming, Morgan Kaufmann, 2011. - T. Rauber, G. Runger, Parallel Programming for Multicore and Cluster Systems, Springer, 2010. - B. Wilkinson, M. Allen, Parallel Programming - Techniques and applications using networked workstations and parallel computers, Second edition, Prentice Hall, 2005. - H. El-Rewini, M. Abd-El-Barr, Advanced Computer Architecture and Parallel Processing, John Wiley & Sons, New Jersey, 2005.

---

- التصنيف : كهرباء وحاسوب - النوع : كهرباء وحاسوب - المجلد : المجلد الرابع مشاركة :