الحساب المتزامن مقابل غير المتزامن
يظهر الشكل التالي نموذج المتوازي المتزامن المجمع (BSP):
الشكل 8: نموذج المتوازي المتزامن المجمع
بعيداً عن نموذج البرمجة المستخدم، يمكن للمطور تحديد حساب موزع إما متزامن أو غير متزامن. ويشير هذا التمييز إلى وجود أو غياب آلية تنسيق (عالمية) تقوم بمزامنة عمليات المهمة. ويكون أي برنامج موزع متزامناً إذا وفقط إذا كانت مهام المكون تعمل في وضع تزامن. وهذا يعني أنه بالنسبة لبعض الثوابت $(c \geq 1)$، إذا وفقط إذا اتخذت أي مهمة $(c + 1)$ من الخطوات، فإن كل مهمة أخرى يجب أن تتخذ على الأقل $c$ من الخطوات.1 وفي وقت لاحق، إذا اتخذت أي مهمة $(c + 2)$ من الخطوات، فإن كل مهمة أخرى يجب أن تتخذ ما لا يقل عن $(c + 1)$ من الخطوات. ومن الواضح أن هذا القيد يتطلب آلية تنسيق يمكن من خلالها مزامنة أنشطة المهام وإنفاذ توقيتها وفقاً لذلك. وعادةً ما يكون لهذه الآليات تأثير مهم على الأداء. وعادةً، في البرامج المتزامنة، يجب أن تنتظر المهام الموزعة عند نقاط محددة مسبقاً لإكمال حسابات معينة أو لوصول بيانات معينة.3 وأي برنامج ليست متزامناً هو برنامج غير متزامن. ولا تفرض البرامج غير المتزامنة أي متطلب للانتظار عند نقاط محددة سلفاً أو لوصول بيانات معينة. ومن الواضح أن عدم التزامن الحسابي له تأثير أقل على الأداء ولكنه يعني أنه يجب تقييم صحة/صلاحية البرنامج.
على سبيل المثال، تتضمن برامج MapReduce وPregel حساباً متزامناً، بينما تكون تلك الموجودة ضمن GraphLab غير متزامنة. ويستخدم برنامج Pregel نموذج المتوازي المتزامن المجمع (BSP)2، وهو نموذج متزامن يستخدم عادةً للتنفيذ الفعال للبرامج الموزعة. ويجمع نموذج المتوازي المتزامن المجمع بين السمات الثلاث: المكونات، وجهاز توجيه، وأسلوب المزامنة. ويتألف مكون BSP من معالج والبيانات المخزنة في الذاكرة المحلية، ولكن لا يمنع النموذج الترتيبات الأخرى، مثل الاحتفاظ بالبيانات في الذاكرات البعيدة. نموذج BSP محايد فيما يتعلق بعدد المعالجات، سواء كانت اثنين أو مليون. يمكن كتابة برامج BSP لـ $v$ من المعالجات الموزعة الظاهرية للتشغيل على $p$ من المعالجات الموزعة المادية، حيث $(v > p)$.
يعتمد BSP على نموذج البرمجة تمرير الرسائل، لإرسال واستقبال الرسائل من خلال جهاز توجيه الذي، من حيث المبدأ، يمكنه فقط تمرير الرسائل نقطة إلى نقطة بين أزواج من المكونات. (لا يوفر النموذج أي مرافق بث، على الرغم من أنه يمكن للمطورين تنفيذها باستخدام اتصالات متعددة من نقطة إلى نقطة.) لتحقيق المزامنة، يقسم BSP كل حساب إلى سلسلة من الخطوات تسمى الخطوات الفائقة. وفي كل خطوة فائقة، $S$، يتم تعيين مهمة لكل مكون تشمل حساب (محلي). ويمكن للمكونات في $S$ إرسال رسائل إلى $(c + 1)$ من المكونات في الخطوة الفائقة $(S + 1)$ ويسمح لها ضمنياً بتلقي الرسائل من المكونات في الخطوة الفائقة $(S - 1)$. في كل خطوة فائقة، تعمل المهام في وقت واحد ولا تتواصل مع بعضها البعض. وعبر الخطوات الفائقة، تتحرك المهام في وضع تزامن: لا توجد مهمة في $(S + 1)$ يمكن أن تبدأ قبل تثبيت كل مهمة في $S$. ولتلبية هذا الشرط، يطبق BSP آلية مزامنة عالمية على غرار الحواجز، كما هو موضح في الشكل 8. ولأن BSP لا يوفر عمليات الوصول المتزامنة إلى أي موقع ذاكرة واحد، فإنه لا يتطلب أي آلية مزامنة خارج الحواجز.
هناك مصدر قلق أساسي آخر في أي إعداد موزع يكمن في تخصيص البيانات بحيث لا يتعرض الحساب للإبطاء بسبب أزمنة الانتقال غير الموحدة للوصول إلى الذاكرة أو الأحمال غير المتساوية بين المهام الفردية. ويعزز BSP أزمنة الانتقال الموحدة للوصول باستخدام البيانات المحلية: يتم توصيل البيانات عبر الخطوات الفائقة قبل تشغيل عمليات حساب المهام الفعلية، وبالتالي فإن النموذج يفصل الحساب والاتصال. ويعني مثل هذا الفصل أنه لا يوجد تخطيط شبكة معين يكون مفضلاً بعيداً عن المتطلبات لتقديم معدل نقل عالي. فكل من تخطيطات الشريط المستعرض الفراشة، والمكعب متعدد الأبعاد، والبصري مقبولة.
عبر المهام ضمن أي خطوة فائقة، لا يزال من الممكن أن تختلف وحدات تخزين البيانات، ويعتمد تحميل المهام بشكل أساسي على البرنامج الموزع والمسؤوليات التي يفرضها على المهام المكونة له. وبناءً على ذلك، يصبح الوقت اللازم لإنهاء أي خطوة فائقة مقيداً بأبطأ مهمة لها. (لا يمكن تنفيذ خطوة فائقة قبل انتهاء أبطأ مهمة.) يمثل هذا الحد تحديا كبيرا لنموذج BSP لأنه يمكن أن يخلق عدم توازن التحميل، والذي عادة ما يؤدي إلى تدهور الأداء. كما يمكن أن يحدث عدم موازنة التحميل بسبب المجموعات غير المتجانسة، خاصة على السحابة. وجدير بالملاحظة أنه على الرغم من أن BSP يقترح العديد من خيارات التصميم، إلا أنه لا يجعل استخدامها إلزامياً. والواقع أن BSP يترك العديد من خيارات التصميم مفتوحة (على سبيل المثال، يمكن تنفيذ التزامن القائم على الحواجز بدقة عالية أو إيقاف تشغيله بالكامل إذا كان غير الضروري للتطبيق المحدد).
المراجع
- أ. س. تاننباوم وإم. في. ستين (12 أكتوبر 2006). الأنظمة الموزعة: المبادئ والنماذج قاعة برينتيس، النسخة الثانية
- ل. ج. فاليانت (1990). نموذج سد الفجوات للحوسبة الموازية في اتصالات جمعية آلات الحوسبة
- D. P. Bertsekas وJ. N. Tsitsiklis (1 يناير، 1997). Parallel and Distributed Computation: Numerical Methods Athena Scientific، الطبعة الأولى