أنواع التوازي
- 11 دقائق
نظرة أخرى على تطوير البرامج الموزعة تشمل تحديد نوع التوازي، توازي البيانات أم توازي الرسم البياني. يؤكد تصميم توازي البيانات على الطبيعة الموزعة للبيانات وينشرها عبر أجهزة متعددة. وفي الوقت نفسه، يمكن أن يبقى الحساب نفسه بين جميع العقد ويتم تطبيقه على بيانات مختلفة. كبديل، يمكن للمهام على أجهزة مختلفة إجراء مهام حسابية مختلفة. وعندما تكون المهام متطابقة، نصنف البرنامج الموزع على أنه أحادي البرنامج متعدد البيانات (SPMD)؛ وإلا، فإننا نصنفه على أنه متعدد البرامج متعدد البيانات (MPMD).
الفكرة الأساسية خلف توازي البيانات بسيطة: من خلال توزيع ملف كبير عبر أجهزة متعددة، يصبح من الممكن الوصول إلى أجزاء مختلفة من الملف ومعالجتها بالتوازي. وكما تمت مناقشته في وحدة نمطية سابقة، إحدى التقنيات الشائعة لتوزيع البيانات هي تجزئة الملف، حيث يتم تقسيم ملف واحد وتوزيعه عبر عدة خوادم. وشكل آخر من توازي البيانات هو توزيع ملفات كاملة (دون تقسيم) عبر الأجهزة، خاصة إذا كانت الملفات صغيرة والبيانات الواردة بها تعرض هياكل غير منتظمة جداً. نلاحظ أنه يمكن توزيع البيانات بين المهام الموزعة إما بشكل صريح، باستخدام تمرير الرسائل، أو ضمنياً، باستخدام الذاكرة المشتركة، على فرض أن النظام الموزع الأساسي يدعم الذاكرة المشتركة.
الشكل 9: برنامج موزع SPMD يستخدم نموذج البرمجة الذاكرة المشتركة
يتم تحقيق توازي البيانات عندما تشغل كل عقدة مهمة واحدة أو عدة مهام على أجزاء مختلفة من البيانات الموزعة. وكمثال محدد، افترض أن الصفيف A مشترك بين ثلاثة أجهزة في نظام موزع ذي ذاكرة مشتركة. لنفترض أيضاً وجود برنامج موزع يضيف ببساطة جميع عناصر الصفيف A. من الممكن أن تأمر الأجهزة 1 و2 و3 لتشغيل المهمة الإضافية، كل منها على ثلث الصفيف A، أو 50 عنصراً، كما هو موضح في الشكل 9. ويمكن تخصيص البيانات عبر المهام باستخدام نموذج البرمجة الذاكرة المشتركة، والذي يتطلب آلية مزامنة. من الواضح أن مثل هذا البرنامج هو SPMD. في المقابل، يمكن أيضاً توزيع الصفيف A بالتساوي (باستخدام تمرير الرسائل) بواسطة مهمة (رئيسية) بين ثلاثة أجهزة، بما في ذلك جهاز الرئيس، كما هو موضح في الشكل 10. سيقوم كل جهاز بتشغيل المهمة الإضافة بشكل مستقل؛ ومع ذلك، يجب تجميع نتائج التجميع في نهاية المطاف في المهمة الرئيسية من أجل تقديم إجمالي كبير. في مثل هذا السيناريو، كل مهمة مشابهة بمعنى أنه يتم تنفيذ نفس عملية الإضافة، ولكن على جزء مختلف من الصفيف A. ومع ذلك، تقوم المهمة الرئيسية أيضاً بتوزيع البيانات على جميع المهام وتجميع نتائج الجمع، مما يجعلها مختلفة قليلاً عن المهمتين الأخريين. من الواضح أن هذا يجعل البرنامج MPMD. وكما ستتم مناقشتها في وحدة لاحقة حول MapReduce، يستخدم MapReduce توازي البيانات مع برامج MPMD.
الشكل 10: برنامج موزع MPMD يستخدم نموذج البرمجة تمرير الرسائل
توازي الرسم البياني، من الناحية الأخرى، يركز على توزيع الحساب بدلاً من البيانات. ومعظم البرامج الموزعة توجد في الواقع في مكان ما على سلسلة متصلة بين الشكلين. ويستخدم توازي الرسم البياني على نطاق واسع في العديد من المجالات مثل التعلم الآلي، واستخراج البيانات، والفيزياء، وتصميم الدوائر الإلكترونية. ويمكن تصوير العديد من المشاكل في هذه المجالات في شكل رسوم بيانية تمثل فيها الرؤوس الحسابات وتمثل الحواف تبعيات البيانات أو اتصالاتها. وتذكر أن الرسم البياني $G$ هو زوج، $(V، E)$، حيث $V$ هو مجموعة محدودة من الرؤوس و$E$ هو مجموعة محدودة من العلاقات الزوجية، $E \subset (V \times V)$، تسمى الحواف. ويمكن أن ترتبط القيم بالرؤوس والحواف للإشارة إلى مقدار العمل في كل رأس وبيانات الاتصال على كل حافة.
فكر في مشكلة كلاسيكية من تصميم الدائرة: الهدف المشترك للحفاظ على دبابيس معينة من عدة مكونات متساوية كهربائياً عن طريق ربطها سلكياً معاً. إذا افترضنا وجود $n$ من الدبابيس، فإن وجود الترتيب $(n - 1)$ من الأسلاك، يربط كل منها اثنين من الدبابيس، يمكن استخدامه. ومن بين جميع هذه الترتيبات، فإن الترتيب الذي يطلب العدد الأدنى من الأسلاك هو عادة الأكثر تفضيلاً. ومن الواضح أنه يمكن تصوير مشكلة الربط السلكي هذه في شكل مشكلة رسم بياني. وعلى وجه الخصوص، يمكن تمثيل كل دبوس على شكل رأس، وتمثيل كل ترابط بين زوج من الدبابيس، $(u، v)$، على شكل حافة. ويمكن تعيين قيمة، $w(u، v)$، بين $u$ و$v$ لتمثيل التكلفة (كمية الأسلاك المطلوبة) لربط $u$ و$v$. وتصبح المشكلة كيفية العثور على مجموعة فرعية دورية، $S$، من الحواف، $E$، التي تربط جميع الرؤوس، $V$، وأي وزن إجمالي،
$$ w (S) = \Sigma_{(u, v)\in S} w(u, v) $$
هو الحد الأدنى.
نظراً لأن المجموعة الفرعية $S$ دوري ومتصل تماماً، فيجب أن يؤدي إلى شجرة تعرف باسم شجرة التمديد الدنيا. وبالتالي، فإن حل مشكلة الأسلاك تتحول إلى حل مشكلة شجرة التمديد الدنيا، وهي مشكلة كلاسيكية قابلة للحل بواسطة خوارزميات مثل الخاصة بـ Kruskal وPrim.
الشكل 11: رسم بياني مقسم باستخدام قياس قطع الحافة
بمجرد أن يتم وضع نموذج لأي برنامج على شكل رسم بياني، يمكن توزيع البرنامج على أجهزة في نظام موزع باستخدام تقنية تقسيم الرسم البياني، والتي تنطوي على تقسيم العمل (الرؤوس) على العقد الموزعة للحساب الموزع الكفء. وكما هو الحال مع توازي البيانات، فإن الفكرة الأساسية بسيطة: من خلال توزيع رسم بياني كبير عبر أجهزة متعددة، يصبح من الممكن معالجة أجزاء مختلفة من الرسم البياني بالتوازي، مما يؤدي إلى تصميم متوازي للرسم البياني. والهدف القياسي لتقسيم الرسم البياني هو توزيع العمل بشكل موحد على p من المعالجات عن طريق تقسيم الرؤوس إلى p من الأقسام ذات القيم المتساوية بينما ينعكس تقليل الاتصال بين العقد بواسطة الحواف. ويشار عادة إلى مثل هذا الهدف على أنه قياس قطع الحافة القياسي. وفي حين أن مشكلة تقسيم الرسم البياني هي من مسائل NP الصعبة، يمكن للأساليب البحثية تحقيق حلول تقرب من المثالية. كمثال محدد، يوضح الشكل 11 ثلاثة أقسام، $P_{1}$، و$P_{2}$، و$P_{3}$، حيث يتم تقسيم الرؤوس $ \lbrace v_{1}، \cdots، v_{8} \rbrace $ عليها باستخدام قياس قطع الحافة. كل حافة لها قيمة اثنين، تتوافق مع وحدة واحدة من البيانات المتصلة في كل اتجاه. وبالتالي، فإن القيمة الإجمالية لقطع الحافة المعروضة هي 10. وسينتج عن حالات القطع الأخرى المزيد من نسبة استخدام شبكة الاتصالات. وبوضوح، بالنسبة للتطبيقات كثيفة الاتصالات، فإن تقسيم الرسم البياني أمر بالغ الأهمية ويمكن أن يلعب دوراً كبيراً في تشكيل أداء التطبيق الكلي. ويستخدم كل من Pregel وGraphLab تقسيم الرسم البياني، وسنناقش كل منهما بصورة إضافية في الوحدات اللاحقة.
المراجع
- تي. إتش. كورمن، سي إي ليسرسون، آر. إل. ريفيست، وسي شتاين (31 يوليو 2009). مقدمة إلى الخوارزميات إصدارات MIT الصحفية، الطبعة الثالثة
- ب. هندريكسون وتي. جي. كولدا (2000). نماذج تقسيم Graph للحوسبة المتوازية الحوسبة المتوازية
- إم. آر. غاري، دي. إس. جونسون، وإل. ستوكماير (1976). بعض المسائل كثيرة الحدود غير القطعية الكاملة للرسم البياني علوم الكمبيوتر النظرية
- ب. هندريكسون وآر ليلاند (1995). دليل مستخدم Chaco الإصدار 2.0 من التقرير التقني SAND95-2344، مختبرات سانديا الوطنية
- ز. كاريبيس وف. كومار (1998). مخطط سريع ورفيع الجودة متعدد المستويات لتقسيم الرسومات البيانية غير المنتظمة مجلة SIAM للحوسبة العلمية
اختبر معلوماتك
الملاحظات
هل كانت هذه الصفحة مفيدة؟
لا
هل تحتاج إلى مساعدة مع هذا الموضوع؟
هل تريد محاولة استخدام Ask Learn لتوضيح هذا الموضوع أو إرشادك خلاله؟