نور عبدو
تحدثنا في المقال السابق ( سلسلة علوم الحاسوب -10- الحوسبة التفرعية (الجزء الأول)) عن مفهوم الحوسبة التفرعية، والغاية منها، وذكرنا المجالات التي يثبت هذا النوع من الحوسبة أهميته في إيجاد حلول لها، كما أشرنا إلى أن الحواسيب المستخدمة للمعالجة طُوِّرت لتأمين البيئة المناسبة للعمل التفرّعي، ولنتفق على تسميتها الحواسيب التفرعيّة.
كيف يمكن تصنيف الحواسيب التفرعية؟
حقيقةً هنالك عدّة تصنيفات، تبعًا لـ:
- طريقة تعاملها مع البيانات والتعليمات.
- طريقة تشاركها للذاكرة الرئيسية.
يوجد نوعان منها حسب طريقة تشاركها للذاكرة الرئيسية:
- حواسيب متعددة المعالجات ذات ذاكرة مشتركة ( Shared memory multiprocessors):
يقصد بالحواسيب متعددة المعالجات، الحواسيب التي تستخدم أكثر من وحدة معالجة مركزية (CPU) واحدة ضمن نظام حاسوبي واحد، ويشار بالذاكرة المشتركة إلى الذاكرة العشوائية التي يمكن لوحدات معالجة عدّة الوصول إليها ضمن نظام حاسوبي متعدد المعالجات.
إذًا توجد مجموعة من المعالجات، يعمل كلٌّ منها على حدى، لكن تتشارك بالذاكرة، حيث يمكن لأي معالج أن يصل إلى أي عنوان من عناوين الذاكرة الرئيسية المشتركة، لذا تُعتبر هذه الحواسيب التوسع الطبيعي للحواسيب التقليدية. وبالرغم من ظهور بعض المشاكل فيما يخص العنونة والمقاطع الحرجة، يبقى التعامل مع الذاكرة المشتركة أسهل من التعامل مع الذاكرة الموزّعة.
كيف يمكن برمجة هذا النوع من الحواسيب؟
توجد عدّة طرق منها: لغات البرمجة التفرعية (Parallel programming languages)، والمترجمات التفرعية (Parallelizing compilers)، والمكتبات على مستوى المستثمر (User-level libraries)، والمسالك (Threads).
- حواسيب متعددة المعالجات ذات ذاكرة موزّعة (Distributed memory multiprocessors):
يقصد بالحواسيب المتعددة المعالجات ذات الذاكرة الموزّعة، بتجمّع من الحواسيب يكون لكل منها ذاكرة خاصّة به، ويتم التشارك وتبادل المعلومات فيما بينها باستخدام شبكة، لكن الطريقة المستخدمة عادةً هي تبادل الرسائل، أي: عملية تمرير التعليمة كرسالة من إجراء لآخر سواء على نفس الجهاز أو على عدّة أجهزة.
يمكنك التعرّف على تصنيفات أخرى للحواسيب التفرعية: حمل الملف PDF
كيف يمكن تقييم أداء البرنامج التفرّعي؟
إذا كانت المسألة لدي مؤلفة من عدّة أجزاء تسلسلية، هل من الجيد تحويلها لمسألة تفرعية؟
لتقييم الخوارزميات التسلسلية نعمد إلى حساب التعقيد الزمني والحسابي، أي كم تستهلك الخوارزمية من الوقت، وكم عدد العمليات التي تقوم بها، لكن الخوارزميات التفرعيّة موزّعة على عدّة معالجات، لذا طريقة التقييم مختلفة، تعتمد على ثلاثة عوامل هي معامل الاستجابة (التسريع)، والفاعليّة، والكلفة.
- معامل الاستجابة/التسريع (Speedup Factor: S(p)):
بما أننا نستخدم عدّة معالِجات يجب معرفة مقدار الزيادة في سرعة العمل، أي تحديد مقدار الربح الذي نحصل عليه عند استخدام البرمجة التفرعية مقارنةً بالتسلسلية، عبر حساب النسبة بين زمن التنفيذ على معالج وحيد (ts) إلى زمن تنفيذه على p معالج (tp).
أو يمكن حساب معامل الاستجابة من خلال النسبة:
عدد العمليات الحسابية باستخدام معالج وحيد/ عدد العمليات الحسابية باستخدام p معالج.
والقيمة العظمى لمعامل الاستجابة تتمثل بعدد المعالجات المتوفرة للحل، لكن نادرًا ما نحصل عليها، نظرًا للتأخير الزمني الناتج عن العمليات المسؤولة عن الاتصال، إضافةً إلى أن جزء من العمل يجب تنفيذه بشكل تسلسلي، حيث يتم تعيين المهام للمعالجات التفرعية وتخصيص البيانات لكل منها.
- الفاعليّة (Efficiency: E):
مدى استخدام الآلة التفرعيّة، أي مدى استثمار المعالجات المتوفرة (الـ multiprocessor).
يمكن حساب الفعاليّة من خلال:
زمن التنفيذ باستخدام معالج وحيد/ (زمن التنفيذ التفرعي* عدد المعالجات)
أي: معامل الاستجابة/ عدد المعالجات.
وتكون الفعاليّة عظمى ( 100%) عندما تعمل كافة المعالجات كامل الوقت وتحقق معامل استجابة مساوٍ لعدد المعالجات، ولذات السبب السابق ذكره لا يمكن تحقيق هذه الأمثلية، وإنما تحقيق أفضل استثمار ممكن للآلة التفرعية.
- الكلفة (Cost/ Work):
تعبّر عن كميّة العمل المنجز، أو كلفة البرنامج التفرعي.
يمكن حساب الكلفة من خلال ضرب قيمة زمن التنفيذ بعدد المعالجات المستخدمة.
أي:
كلفة البرنامج التسلسلي= زمن التنفيذ * 1.
كلفة البرنامج التفرعي= زمن التنفيذ * عدد المعالجات.
تكون الكلفة أمثليّة عندما تكون قيمتها باستخدام حاسب وحيد المعالج مساوية لقيمتها باستخدام حاسب متعدد المعالجات، أي كلما اقتربت كلفة التنفيذ التفرّعي من كلفة التنفيذ التسلسلي كان الحل أفضل، لكن لماذا؟
لأنه باستخدام المعالجة التفرعية تُستهلك عدّة معالجات بدلًا من معالج واحد، بالإضافة إلى تأمين الاتصال فيما بينهم.
الاستجابة العظمى وقانون أمدال (Maximum Speedup- Amadahl’s Law):
أشرنا منذ قليل إلى حتميّة وجود جزء تسلسلي ضمن-غالبية- البرامج التي نريد تنفيذها تفرعيًّا، وسنفرض أن الرمز f يرمز إلى نسبة الجزء التسلسلي من برنامجنا (أي ستُنفَّذ على معالج واحد أما البقية ستُوزَّع على بقية المعالجات حيث يمكن تفريعهم)، ويقع ضمن المجال [0,1]، وبالتالي تكون نسبة الجزء التفرعي من البرنامج هي (1-f)، فيكون زمن تنفيذ الجزء التسلسلي (f * ts)، أما زمن تنفيذ الجزء التفرعي أي للجزء المتبقي
((1-f) * ts)
ولمعرفة زمن تنفيذ الجزء التفرعي على أحد المعالجات نطبق قسمة هذا الزمن ككل على عدد المعالجات، كما يلي:
ليكون زمن التنفيذ التفرعي للبرنامج ككل كما يلي:
الآن نحتاج لمعرفة مقدار الزيادة في سرعة المعالجة، وهذا من خلال معامل الاستجابة، الذي قانونه: نسبة زمن التنفيذ التسلسلي إلى زمن التنفيذ التفرعي، فينتج القانون التالي:
الآن، الاستجابة العظمى!
ضمن القانون السابق، بفرض زدنا عدد المعالجات لأقصى حدّ ممكن، سيصل معامل الاستجابة إلى قيمة ثابتة
(عند عدد معين للمعالِجات)، ولن يكون هنالك فائدة من هذه الزيادة بعده.
إذًا وجود جزء تسلسلي في البرنامج يشكّل عائقًا أمام التفريع الكامل والحصول على سرعة عظمى، والإكثار من عدد المعالجات بشكل اعتباطي لن يؤدي لتحسين السرعة دائمًا.
لكن نظريًّا لا توجد مسألة خاوية من الجزء التسلسلي إلّا فيما ندر، مثل: برامج التحويلات الهندسية على الصور.
قابليّة التوسّع وقانون غوستافسون (Scalability- Gustafson Law):
مفهوم قابلية التوسّع عمومًا مرتبط بالبنية الصلبة، لكن بالنسبة للخوارزميات التفرعية يرتبط ارتباطًا وثيقًا بطبيعة المسألة المطلوب معالجتها، حيث يعني القدرة على التعامل مع حجم أكبر من البيانات بعد تطبيق زيادة بسيطة في عدد خطوات الحساب. عند الحل بطريقة تفرعيّة يجب أن تأخذ بعين الاعتبار التعامل مع بيانات بحجم أكبر.
أما بالنسبة لقانون غوستافسون فهو مشابه لقانون أمدال لكنه يعتمد على مفهوم قابلية التوسّع، وينصّ على أن زيادة حجم المسالة تتناسب طردًا مع عدد المعالجات المستخدمة، لكن بشرط بقاء الجزء التسلسلي ثابت عند تلك الزيادة، أي: يجب أن يزداد حجم الجزء التفرعي فقط عند زيادة حجم المسألة.
وبفرض f يرمز إلى نسبة الجزء التسلسلي ( كما فعلنا منذ قليل)، وبالتالي تكون نسبة الجزء التفرعي هي (1-f)، فيكون زمن تنفيذ الجزء التسلسلي(f * ts)، أما زمن تنفيذ الجزء الذي يمكن تفريعه
((1-f) * ts)
فعند تنفيذ هذا الأخير على n جزء (أي كمية الجزء التفرعي التي قمنا بزيادتها) يكون الزمن هو الزمن السابق مضروبًا بـ n أي يصبح القانون
(n * (1-f) * ts)
فيكون زمن تنفيذ الجزء التسلسلي ككل :
ts = (f * ts) + (n * (1-f) * ts).
أما زمن تنفيذ الجزء التفرعي ككل (زمن تنفيذ الجزء التسلسلي مضافًا إليه زمن التنفيذ على أحد المعالجات التفرعيّة) هو
tp = (f * ts) + ((1-f) * ts).
الآن نحسب معامل الاستجابة، لمعرفة مقدار الزيادة في سرعة المعالجة، فينتج القانون التالي:
وهو قانون غوستافسون.
إذًا نستنتج أنّه عند عدم القدرة على تحديد عدد المعالجات نستخدم قانون أمدال الذي يعطي معامل الاستجابة بغض النظر عن حجم المسألة، أما في حال تحديد عدد المعالجات نستخدم قانون غوستافسون.
كيف تُكتَب البرامج التفرعية؟
القاعدة الأساسية هنا: نقوم بكتابة برامج (إجرائيات، خوارزميات…) تفرعيّة لتُنفَّذ على أكثر من معالج، سواءً ضمن آلة واحدة (حاسوب متعدد المعالجات Multiprocessor) أو على أكثر من آلة (تجمّع من الحواسيب Computer Cluster).
لكن كيف يمكن ربط هذه المعالجات/ الآلات معًا؟
يتم ذلك بواسطة شبكة ما، لكن استخدام شبكة يفرض الحاجة إلى طرق وبروتوكولات للتواصل وإدارة العمليات بين هذه الآلات، وقد أشرنا إلى هذا سابقًا بطريقة البرمجة باستخدام تبادل الرسائل (Message passing computing)، أي أن أجزاء البرنامج التفرعي تتبادل الرسائل فيما بينها.
في البدايةً، ظهرت عدّة محاولات لتصميم نظام متعدد المعالجات معتمد على طريقة تبادل الرسائل. أحد الوسائل المتاحة كانت تصميم لغة برمجة تفرعية Parallel programming languages (أي أنشئت لتكتب برامج تفرعية فقط) مثل لغة OCCAM التي كانت تعمل مع معالجات خاصة اسمها Transputers لها أربع قنوات اتصال فيزيائية، تُربط بواسطة هذه القنوات عدّة معالجات من النوع Transputers معًا.
بعدها ظهرت محاولات لتوسيع قواعد التعامل مع لغة برمجة تسلسلية (من مثل: C، أو C++، أو Fortran …)، لتصبح قادرة على تبادل الرسائل.
لكن المحاولة الوحيدة التي لاقت نجاحًا حتى الآن هي إضافة مكتبات تحوي التوابع اللازمة لتبادل الرسائل إلى إحدى اللغات الموجودة حاليًا، ومن هذه المكتبات PVM (Parallel Virtual Machine)، وMPI (Message Passing Interface) التي يمكن استخدامها مع لغات البرمجة C ، و C++، وغيرها.
لكن باستخدام هكذا مكتبة برمجية على مستوى المستثمر، نحتاج إلى وسيلتين أساسيتين، هما:
- طريقة لإنشاء إجراءات منفصلة (Separate Processes) لتُنفَّذ على حواسيب مختلفة.
- طرية لإرسال واستقبال الرسائل.
هناك أمور عدّة يجب أخذها بالحسبان أثناء حل المشاكل، ما مدى قابلية المسألة التي أعمل على حلّها للتفريع؟ ما هو عدد المعالجات المناسب لخوارزمية الحل؟ عند حدوث مشاكل، هل أغيّر عدد المعالجات؟ هل أستبدل العتاد؟ أم هل فقط أعيد النظر في الكود البرمجي المطبّق؟ وغيرها العديد من التساؤلات المنطقية.
ببساطة يمكنك اعتبار البرمجة التفرعية، منهجية تفكير..
بعد كل هذا، هل يمكن اعتبار الحوسبة التفرعية ترف علمي؟ ما رأيك؟
المصادر:
- computing
- Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers (2nd Edition(
- إعداد: نور عبدو.
- تدقيق لغوي: رأفت فياض.
