المؤلف: بليز بارني (Blaise Barney)، مختبر لورانس ليفرمور الوطني، ترجمة زكرياء المهداوي.
ملخص
هذا هو البرنامج التعليمي الأول في ورشة " بدء العمل على حوسبة ليفرمور". وليس الغرض منه سوى تقديم نظرة عامة وسريعة جدا عن الموضوع الواسع والشامل للحوسبة المتوازية( Parallel Computing)، وكمقدمة للدروس اللاحقة. وعلى هذا النحو، فإنه سيغطي أساسيات الحوسبة المتوازية، وهو موجه فقط لمن يود التعرف على هذا الموضوع والذي يخطط لحضور درس واحد أو أكثر من الدروس الأخرى في هذه الورشة. إنه غير موجه لتغطية البرمجة المتوازية بشكل متعمق، لأن هذا يتطلب وقتا أطول بكثير. يبدأ البرنامج التعليمي بمناقشة حول الحوسبة المتوازية - ما هي استخداماتها وكيف، تليها مناقشة حول المفاهيم والمصطلحات المرتبطة بالحوسبة المتوازية. ثم استكشاف مواضيع بنيات الذاكرة المتوازية ونماذج البرمجة. وتتبع هذه المواضيع سلسلة من المناقشات العملية حول عدد من القضايا المعقدة والمتعلقة بتصميم وتنفيذ برامج متوازية. ويختتم البرنامج التعليمي بعدة أمثلة عن كيفية موازاة البرامج التسلسلية البسيطة.
جدول المحتويات
1. ملخص
2. نظرة عامة
1. ما هي الحوسبة المتوازية؟
2. لماذا استخدام الحوسبة المتوازية؟
3. من يستعمل الحوسبة المتوازية؟
3. المفاهيم والمصطلحات
1. بنية الحاسب لـ فون نيومان
2. تصنيف فلين الكلاسيكي
3. بعض المصطلحات المتوازية العامة
4. حدود وتكاليف البرمجة المتوازية
4. بنيات ذاكرة الحاسوب المتوازية
1. الذاكرة المشتركة
2. الذاكرة الموزعة
3. الذاكرة المشتركة-الموزعة الهجينة
5. نماذج البرمجة المتوازية
1. نظرة عامة
2. نموذج الذاكرة المشتركة
3. نموذج الخيوط
4. الذاكرة الموزعة / نموذج تمرير الرسالة
5. نموذج البيانات المتوازي
6. النموذج الهجين
7. SPMD وMBF
6. تصميم البرامج المتوازية
1. الموازاة اليدوية مقابل الموازاة التلقائية
2. فهم المشكلة والبرنامج
3. التجزئة
4. الاتصالات
5. المزامنة
6. تبعيات البيانات
7. موازنة التحميل
8. الحبوبية
9. I / O
10. التصحيح
11. ضبط وتحليل الأداء
7. أمثلة موازية
1. معالجة مصفوفة
2. حساب PI
3. معادلة الحرارة البسيطة
4. معادلة الموجة 1-D
8. المراجع والمزيد من المعلومات
نظرة عامة
ما هي الحوسبة المتوازية (Parallel Computing)؟
• الحوسبة التسلسلية (Serial Computing)
• عادة، تكتب البرمجيات من أجل حوسبة تسلسلية حيث
◦ تقسم المشكلة إلى سلسلة منفصلة من التعليمات
◦ تنفذ التعليمات بالتتابع واحدة تلو الأخرى
◦ تنفذ التعليمات على معالج واحد
◦ يمكن تنفيذ تعليمة واحدة فقط خلال أي لحظة من الزمن
مثلا :
• الحوسبة المتوازية
• يُقصد بالحوسبة المتوازية، في أبسط معانيها، الاستخدام المتزامن لموارد حساب متعددة لحل مشكلة حسابية
◦ تقسم المشكلة إلى أجزاء منفصلة يمكن حلها في وقت واحد
◦ تقسم أيضا كل جزء إلى سلسلة من التعليمات
◦ تنفذ تعليمات كل جزء في وقت واحد على معالجات مختلفة
◦ تستخدم آلية شاملة للرقابة / التنسيق
مثلا :
• يجب أن تكون المشكلة الحسابية قادرة على:
◦ قابلة للتقسيم إلى قطع عمل منفصلة والتي يمكن حلها أو تنفيذها في وقت واحد؛
◦ أن يتم تنفيذ تعليمات البرنامج المتعددة في أي لحظة من الزمن؛
◦ أن تحل في أقل وقت مع موارد حساب متعددة بالمقارنة مع مورد حساب واحد.
• موارد الحساب عادة ما تكون:
◦ جهاز حاسوب واحد مع معالجات/أنوية متعددة
◦ عدد هائل من مثل هذه الحواسيب متصلة بشبكة
• الحواسيب المتوازية (Parallel Computers)
• تعتبر في يومنا هذا جميع أجهزة الحاسوب المستقلة تقريبا متوازية من منظور الأجهزة
◦ وحدات متعددة الوظائف (المخبأة أو ذاكرة التخزين المؤقت L1 – L1 cache، المخبأة أو ذاكرة التخزين المؤقت L2 – L2 cache ، فرع - branch، الجلب المسبق - prefetch، فك شفرة - decode، الفاصلة العائمة - floating-point، معالجة الرسومات (GPU)، عدد صحيح - integer، وما إلى ذلك)
◦ وحدات/أنوية التنفيذ المتعددة
◦ خيوط (threads) الأجهزة المتعددة
IBM BG/Q Compute Chip with 18 cores (PU) and 16 L2 Cache units (L2)
• تربط الشبكات بين العديد من الحواسب المستقلة (عقود - nodes) لإنشاء عناقيد حواسيب متوازية كبيرة
• على سبيل المثال، يظهر الرسم التخطيطي أسفله مجموعة حواسيب متوازية LLNL نموذجية
◦ كل عقدة حساب هو حاسوب متواز متعدد المعالجات في حد ذاته
◦ تربط عقود حساب متعددة فيما بينها بواسطة شبكة ذات عرض حزمة لانهائي (Infiniband)
◦ تستخدم العقود ذات الغرض الخاص، وكذلك متعددة المعالجات لأغراض أخرى
• أغلبية أجهزة الحواسيب المتوازية الكبيرة العالمية (الحواسيب الفائقة - supercomputers) هي مجموعات من الأجهزة التي تنتجها حفنة من (معظم) البائعين المعروفين.
المصدر: Top500.org
لماذا استخدام الحوسبة المتوازية؟
• العالم الحقيقي متواز على نطاق واسع:
• في العالم الطبيعي، العديد من الأحداث المعقدة والمترابطة تحدث في نفس الوقت، ولكن ضمن تسلسل زمني.
• بالمقارنة مع الحوسبة التسلسلية، تعتبر الحوسبة المتوازية أكثر ملاءمة للنمذجة، ولمحاكاة وفهم، ظواهر العالم الحقيقي المعقدة.
• تخيل، على سبيل المثال، نمذجة هذه الظواهر بشكل متسلسل:
• الأسباب الرئيسية:
• توفير الوقت و/أو المال:
◦ نظريا، يؤدي إلقاء المزيد من الموارد في مهمة ما إلى تقصير الوقت اللازم لإنجازها، مع توفير محتمل للتكاليف.
◦ يمكن تركيب الحواسيب المتوازية من مكونات السلع الأساسية الرخيصة.
• حل مشاكل معقدة إضافية/كبيرة:
◦ تعد الكثير من المشاكل جد كبيرة و/أو معقدة حيث أنه من غير العملي أو من المستحيل حلها على جهاز كمبيوتر واحد، وخاصة إذا ما نظرنا إلى ذاكرة الكمبيوتر المحدودة.
◦ مثال: "مشاكل التحدي الكبرى" (en.wikipedia.org/wiki/Grand_Challenge) التي تتطلب بيتافلوبس (PetaFLOPS) و بيتابيتس (PetaBytes) من موارد الحوسبة.
◦ مثال: تعالج محركات بحث الويب / قواعد بيانات الملايين من المعاملات في كل ثانية.
• توفير التزامن (CONCURRENCY):
◦ يمكن لمورد حساب واحد القيام بأمر واحد فقط في نفس الوقت. بينما يمكن للعديد من موارد الحساب أن تفعل أشياء كثيرة في آن واحد.
◦ مثال: توفر الشبكات التعاونية مكانا عالميا حيث يمكن للناس من جميع أنحاء العالم أن يجتمعوا ويضطلعوا بعمل "فعليا".
• الاستفادة من الموارد غير المحلية:
◦ استخدام موارد حساب على شبكة منطقة واسعة، أو حتى الإنترنت عندما تكون موارد الحوسبة المحلية نادرة أو غير كافية.
◦ مثال: تمتلك SETI@home (setiathome.berkeley.edu) أكثر من 1.6 مليون مستخدم في كل بلد تقريبا في العالم. (يونيو 2017).
◦ مثال: تمتلك Folding@home (folding.stanford.edu) أكثر من 1.8 مليون مساهم عالميا (يونيو 2017)
• استخدام أفضل للأجهزة المتوازية الكامنة (UNDERLYING PARALLEL HARDWARE):
◦ تعتبر أجهزة الحاسوب الحديثة، وحتى أجهزة الحاسوب المحمول، متوازية في بنيتها مع معالجات/أنوية متعددة.
◦ يوجه البرنامج المتوازي خصيصا للأجهزة المتوازية ذات الأنوية المتعددة، الخيوط، الخ.
◦ في معظم الحالات، تعمل البرامج التسلسلية المشتغلة على أجهزة الحاسوب الحديثة على "تبديد" قدرة الحوسبة المحتملة.
Intel Xeon processor with 6 cores and 6 L3 cache units
• المستقبل
• خلال العشرين سنة الماضية، تظهر بوضوح الاتجاهات التي تشير إليها الشبكات الأسرع من أي وقت مضى، والأنظمة الموزعة، وبنيات الحواسيب متعددة المعالجات (حتى على مستوى سطح المكتب) أن التوازي هو مستقبل الحوسبة.
• في نفس هذه الفترة الزمنية، كانت هناك زيادة تفوق 500,000 مرة في أداء الحاسوب الفائق، مع عدم وجود نهاية في الأفق حاليا.
• السباق هو بالفعل على الحوسبة بسرعة إكساسكيل (Exascale)!
◦ إكسافلوب (Exaflop) = 1018 حساب في الثانية
المصدر: Top500.org
من يستعمل الحوسبة المتوازية؟
• العلوم والهندسة
• تاريخيا، اعتبرت الحوسبة المتوازية كونها "مكرّسة للحوسبة الفائقة"، وقد استخدمت لنمذجة مشاكل صعبة في العديد من مجالات العلوم والهندسة:
• الهندسة الميكانيكية - من الأطراف الاصطناعية إلى المركبات الفضائية
• الهندسة الكهربائية، تصميم الدوائر، الإلكترونيات الدقيقة
• علم الحاسوب، الرياضيات
• الدفاع، الأسلحة
• الغلاف الجوي، الأرض، البيئة
• الفيزياء - التطبيقية، النووية، الجسيمات، المادة المكثفة، الضغط المرتفع، الانصهار، الضوئيات
• العلوم البيولوجية، التكنولوجيا الحيوية، علم الوراثة
• الكيمياء، العلوم الجزيئية
• الجيولوجيا، علم الزلازل
• الأغراض الصناعية والتجارية
• اليوم، توفر التطبيقات التجارية قوة دافعة متساوية أو كبيرة جدا في سبيل تطوير أجهزة الحاسوب فائقة السرعة. وتتطلب هذه التطبيقات معالجة كميات كبيرة من البيانات بطرق متطورة. مثلا:
• النمذجة المالية والاقتصادية
• إدارة الشركات الوطنية والمتعددة الجنسيات
• الرسومات المتقدمة والواقع الافتراضي، خاصة في صناعة الترفيه
• الفيديو الشبكي وتقنيات الوسائط المتعددة
• بيئات العمل التعاونية
• "البيانات الضخمة (Big Data)"، وقواعد البيانات، واستخراج البيانات
• التنقيب عن النفط
• محركات البحث على شبكة الإنترنت، خدمات الأعمال التجارية على شبكة الإنترنت
• التصوير الطبي والتشخيص
• التصميم الصيدلاني
• التطبيقات العالمية
• يجري حاليا استخدام الحوسبة المتوازية على نطاق واسع في جميع أنحاء العالم، وذلك في طائفة واسعة من التطبيقات.
المصدر: Top500.org
المفاهيم والمصطلحات
تصميم فون نيومان (von Neumann Architecture)
• سمي باسم عالم الرياضيات الهنغاري العبقري جون فون نيومان أول من ألف المتطلبات العامة لجهاز الحاسوب الإلكتروني في أوراقه عام 1945.
• ويعرف أيضا باسم "حاسوب البرامج المخزَّنة (stored-program computer)" – يحتفظ بكل من تعليمات البرنامج والبيانات في الذاكرة الإلكترونية. و يختلف عن أجهزة الحاسوب السابقة التي تمت برمجتها من خلال "الأسلاك الصلبة - hard wiring".
•
جون فون نيومان1940
(المصدر: أرشيف لانل)
• منذ ذلك الحين، اتبعت جميع الحواسيب تقريبا هذا التصميم الأساسي:
• تتألف من أربعة مكونات رئيسية هي:
◦ الذاكرة
◦ وحدة التحكم
◦ وحدة المنطق الحسابية
◦ الإدخال / الإخراج
• القراءة / الكتابة، تستخدم ذاكرة الوصول العشوائي لتخزين كل من تعليمات البرنامج والبيانات
• تعليمات البرنامج هي بيانات مبرمجة تخبر الحاسوب بالقيام بشيء ما
• البيانات هي ببساطة معلومات ستستخدم من قبل البرنامج
• تقوم وحدة التحكم بجلب التعليمات/البيانات من الذاكرة، و تفك شفرة التعليمات ثم تقوم بتنسيق العمليات لإنجاز المهمة المبرمجة تتابعيا.
• تقوم وحدة الحساب بعمليات حسابية أساسية
• الإدخال/الإخراج (Input/Output) هو واجهة المشغل البشري
• المزيد من المعلومات عن إنجازاته الرائعة الأخرى: http://en.wikipedia.org/wiki/John_von_Neuman
• ماذا في ذلك؟ من يهتم؟
◦ حسنا، ما تزال أجهزة الحاسوب المتوازية تتبع هذا التصميم الأساسي، فقط ضاعفت الوحدات. بينما ظلت البنية الأساسية هي نفسها.
التصنيف الكلاسيكي لـ فلين (Flynn)
• هناك طرق مختلفة لتصنيف أجهزة الحاسوب المتوازية. الأمثلة متاحة هنا.
• واحدة من التصنيفات المستخدمة على نطاق واسع، منذ عام 1966، تسمى تصنيف فلين.
• يميز تصنيف فلين بنيات الحاسوب متعددة المعالجات وفقا للكيفية التي يمكن أن تصنف وفقها على طول البعدين المستقلين لتدفق التعليمات (Instruction Stream) ولتدفق البيانات (Data Stream). لكل بعد من هذه الأبعاد حالة واحدة فقط من الحالتين الممكنتين: واحدة (Single) أو متعددة (Multiple).
• تحدد المصفوفة أدناه التصنيفات الأربع الممكنة وفقا لفلين:
• تعليمات وحيدة، بيانات وحيدة (SISD):
• جهاز حاسوب تسلسلي (غير متوازي)
• تعليمات وحيدة: ينفذ تدفق تعليمات واحد فقط من قبل وحدة المعالجة المركزية (CPU) على مدار كل دورة معالجة واحدة
• بيانات وحيدة: تستخدم تدفق بيانات وحيدة فقط كمدخلات على مدار كل دورة معالجة واحدة
• تنفيذ حتمي
• هذا هو أقدم نوع من الحواسيب
• أمثلة: أجهزة الحاسوب الكبيرة من الجيل الأقدم، أجهزة الحاسوب الصغيرة، محطات العمل وأجهزة الحاسوب الشخصية أحادية المعالج/النواة.
 |
 |
|
 UNIVAC1 |
 IBM 360 |
 CRAY1 |
 CDC 7600 |
 PDP1 |
 Dell Laptop |
• تعليمات وحيدة، بيانات متعددة (SIMD):
• نوع من أجهزة الحاسوب المتوازية
• تعليمات وحيدة: تنفذ جميع وحدات المعالجة نفس التعليمات في أي دورة معالجة معينة
• بيانات متعددة: يمكن لكل وحدة معالجة أن تعمل على عنصر بيانات مختلف
• الأنسب للمشاكل المتخصصة التي تتميز بدرجة عالية من الانتظام، مثل معالجة الرسومات/الصور.
• متزامن (بانتظام) ومنفذ حتمي
• صنفان اثنان: مصفوفات المعالج وخطوط الأنابيب المتجهة
• أمثلة:
◦ مصفوفات المعالج: Thinking Machines CM-2, MasPar MP-1 & MP-2, ILLIAC IV
◦ خطوط الأنابيب المتجهة: IBM 9000, Cray X-MP, Y-MP & C90, Fujitsu VP, NEC SX-2, Hitachi S820, ETA10
• معظم أجهزة الحاسوب الحديثة، وخاصة تلك التي تمتلك وحدات معالج الرسومات (GPUs) تستخدم تعليمات SIMD ووحدات التنفيذ.
 |
 |
|
 ILLIAC IV |
 MasPar |
 |
 Cray X-MP |
 Cray Y-MP |
 Thinking Machines CM-2 |
 Cell Processor (GPU) |
• تعليمات متعددة، بيانات وحيدة (MISD):
• نوع من أجهزة الحاسوب المتوازية
• تعليمات متعددة: تعمل كل وحدة معالجة على البيانات بشكل مستقل عن طريق تدفقات تعليمات منفصلة.
• بيانات وحيدة: يوزع تدفق واحد من البيانات في وحدات معالجة متعددة.
• لا يوجد سوى عدد قليل (إن وجد) من الأمثلة الفعلية لهذه الفئة من أجهزة الحاسوب المتوازية .
• بعض الاستخدامات التي يمكن تصورها:
◦ مرشحات تردد متعددة تعمل على تدفق إشارة واحد
◦ خوارزميات تشفير متعددة تحاول كسر رسالة مشفرة واحدة.
 |
 |
• تعليمات متعددة، بيانات متعددة (MIMD):
• نوع من أجهزة الحاسوب المتوازية
• تعليمات متعددة: قد يقوم كل معالج بتنفيذ تدفق تعليمات مختلف
• بيانات متعددة: قد يعمل كل معالج مع تدفق بيانات مختلف
• يمكن أن يكون التنفيذ متزامنا أو غير متزامن، حتمي أو غير حتمي
• حاليا، هو النوع الأكثر شيوعا من أجهزة الحاسوب المتوازية – توجد معظم الحواسيب الفائقة ضمن هذه الفئة.
• أمثلة: معظم الحواسيب الفائقة الحالية، عناقيد (clusters) و"شبكات" أجهزة حاسوب متوازية مشبكة، أجهزة حاسوب SMP متعددة المعالجات، وأجهزة حاسوب شخصية متعددة الأنوية.
• ملاحظة: تشمل أيضا العديد من بنيات MIMD المكونات الفرعية التنفيذية SIMD
 |
 |
|
 IBM POWER5 |
 HP/Compaq Alphaserver |
 Intel IA32 |
 AMD Opteron |
 Cray XT3 |
 IBM BG/L |
بعض المصطلحات العامة المتوازية
• مثل كل شيء آخر، الحوسبة المتوازية لها "لغة اصطلاحية" خاصة بها. وقد تم جرد بعض من المصطلحات الأكثر شيوعا والمرتبطة بالحوسبة المتوازية أسفله.
• ستتم مناقشة معظم هذه المصطلحات بمزيد من التفصيل في وقت لاحق.
الحوسبة الفائقة / الحوسبة عالية الأداء - High Performance Computing (HPC)
تستخدم أسرع وأكبر أجهزة الحاسوب العالمية لحل المشاكل الكبيرة.
العقدة - Node
عبارة عن "حاسوب في صندوق" مستقل من وحدات معالجة مركزية/معالجات/أنوية متعددة، ذاكرة، واجهات الشبكة، وما إلى ذلك. وتشبك العقد معا لتكون حاسوبا فائقا.
وحدة المعالجة المركزية CPU / المقبس / المعالج / النواة - CPU / Socket / Processor / Core
هذا يختلف اعتمادا على من تتحدث إليه. في الماضي، كانت وحدة المعالجة المركزية (CPU) مكون التنفيذ الوحيد للحاسوب. ثم، دمجت وحدات معالجة مركزية متعددة في عقدة. بعد ذلك، قسمت وحدات المعالجة المركزية الفردية إلى عدة "أنوية"، كل منها أصبحت وحدة تنفيذ وحيدة. تسمى وحدات المعالجة المركزية مع الأنوية المتعددة أحيانا "مقابس" – تعتمد على المورد. والنتيجة هي عقدة ذات وحدات معالجة مركزية متعددة، تحتوي كل منها على عدة أنوية. يخلط بين التسميات في بعض الأحيان. أتساءل لماذا؟
المهمة - Task
قسم منفصل منطقيا من العمل الحسابي. والمهمة هي عادة برنامج أو شبه برنامج مجموعة من التعليمات التي تنفذ بواسطة معالج. ويتألف البرنامج المتوازي من مهام متعددة تشتغل على معالجات متعددة.
المواردة - Pipelining
تقسيم مهمة إلى خطوات تؤديها وحدات المعالج المختلفة، مع مدخلات تتدفق من خلالها، يشبه بشكل كبير خط التجميع؛ نوع من الحوسبة المتوازية.
الذاكرة المشتركة - Shared Memory
من وجهة نظر دقيقة للأجهزة، فهي تصف بنية الحاسوب حيث لدى جميع المعالجات وصول مباشر (قائم على الناقل عادة) إلى الذاكرة الملموسة المشتركة. ومن الناحية البرمجية، فإنها تصف نموذجا حيث كل المهام المتوازية لها نفس "صورة" الذاكرة ويمكنها أن تعنون وتلج مباشرة نفس مواقع الذاكرة المنطقية بغض النظر عن مكان وجود الذاكرة الملموسة فعلا.
المعالج المتعدد المتناظر - Symmetric Multi-Processor (SMP)
بنية جهاز الذاكرة المشتركة حيث تشترك المعالجات المتعددة في مساحة عنوان واحد ولديها وصول متساو إلى جميع الموارد.
الذاكرة الموزعة - Distributed Memory
تشير، في الأجهزة، إلى الوصول للذاكرة القائمة على الشبكة للذاكرة الملموسة غير المشتركة. وكنموذج برمجي، يمكن للمهام أن "ترى" منطقيا ذاكرة الجهاز المحلي فقط ويجب استخدام الاتصالات للوصول إلى الذاكرة على الأجهزة الأخرى حيث يتم تنفيذ المهام الأخرى.
الاتصالات - Communications
عادة ما تحتاج المهام المتوازية إلى تبادل البيانات. هناك عدة طرق لتحقيق ذلك، كأن تتم عبر ناقل ذاكرة مشتركة أو عن طريق الشبكة، إلا أنه عادة ما يُشار إلى الحدث الفعلي لتبادل البيانات بالاتصالات بغض النظر عن الطريقة المستخدمة.
التزامن - Synchronization
هو تنسيق المهام المتوازية في الوقت الحقيقي، وغالبا ما يرتبط بالاتصالات. كما أنه في الغالب ما تنفذ عن طريق إنشاء نقطة التزامن ضمن تطبيق حيث لا يجوز لمهمة ما المضي قدما حتى تصل مهمة أو مهام أخرى إلى نفس النقطة أو ما يعادلها منطقيا.
المزامنة عادة ما ينطوي على الانتظار من قبل مهمة واحدة على الأقل، وبالتالي يمكن أن يؤدي إلى زيادة في وقت تنفيذ التطبيق المتوازي.
الحبوبية - Granularity
في الحوسبة المتوازية، يقصد بالحبوبية ذلك المقياس النوعي للحساب بالنسبة للاتصالات.
• خشنة: يتم إجراء كميات كبيرة نسبيا من العمل الحسابي بين أحداث الاتصالات
• دقيقة: يتم إجراء كميات صغيرة نسبيا من العمل الحسابي بين أحداث الاتصالات
التسريع المرصود - Observed Speedup
يعرف التسريع المرصود لشفرة والذي تتم موازاته على النحو التالي:
وقت التنفيذ التسلسلي على مدار الساعة ----------------------------------- وقت التنفيذ المتوازي على مدار الساعة
هو واحد من أبسط وأكثر المؤشرات استخداما وعلى نطاق واسع لأداء برنامج متوازي.
تكلفة التوازي - Parallel Overhead
هو مقدار الوقت اللازم لتنسيق المهام المتوازية، مقابل القيام بعمل مستفاد منه. يمكن أن تشمل تكلفة التوازي عوامل مثل:
• وقت بدء المهمة
• التزامنات
• اتصالات البيانات
• تكلفة البرامج تفرضها اللغات المتوازية والمكتبات وأنظمة التشغيل وما إلى ذلك.
• وقت إنهاء المهمة
التوازي الضخم - Massively Parallel
يشير إلى الأجهزة التي تؤلف نظام مواز معين - تملك العديد من عناصر المعالجة. يظل معنى "العديد" يتزايد، ولكن حاليا، أكبر أجهزة الكمبيوتر المتوازية تتكون من عناصر المعالجة تحسب من مئات الآلاف إلى الملايين.
التوازي المربك - Embarrassingly Parallel
حل العديد من المهام المماثلة، ولكنها مستقلة في آن واحد؛ وليس هناك حاجة إلى التنسيق بين المهام.
قابلية التوسع - Scalability
تشير إلى قابلية نظام متوازي (أجهزة و/أو برمجيات) في إثبات الزيادة التناسبية في التسريع المتوازي مع إضافة المزيد من الموارد. وتشمل العوامل التي تساهم في قابلية التوسع:
• الأجهزة – خاصة حيز نطاقات ذاكرة وحدة المعالجة المركزية وخصائص اتصالات الشبكة
• خوارزمية التطبيق
• تكلفة التوازي ذات الصلة
• مميزات تطبيقك الخاص
حدود وتكاليف البرمجة المتوازية
• قانون أمدال (Amdahl):
• ينص قانون أمدال على أن تسارع البرنامج المحتمل يعرف بأنه أجزاء الشفرة (P) التي يمكن موازاتها:
• إذا لم يكن بالإمكان موازاة الشفرة، فإن P=0 و speedup=1 (لا يوجد تسارع).
• إذا تمت موازاة كل الشفرة، P=1 وسرعة غير منتهية (من الناحية النظرية).
• إذا كان بالإمكان موازاة 50٪ من الشفرة، فإن الحد الأقصى speedup=2، وهذا يعني أنه سيتم تشغيل الشفرة مرتين أسرع.
• بإدخال عدد من المعالجات التي تؤدي الى توازي في العمل، يمكن صياغة العلاقة على النحو التالي:
حيث P = كسر التوازي، N = عدد المعالجات و S = الكسر التسلسلي.
• وسرعان ما يصبح واضحا أن هناك حدودا لقابلية توسع الموازاة. فمثلا:
• الاقتباس "الشهير": يمكنك قضاء العمر مدى الحياة للحصول على 95٪ من الشفرة الخاصة بك لتكون متوازية، ولن تحقق أبدا أفضل من تسريع بـ 20 مرة بغض النظر عن عدد المعالجات التي تستعملها في ذلك!
• مع ذلك، تظهر بعض المشاكل زيادة الأداء بزيادة حجم المشكلة. فمثلا:
• يمكننا زيادة حجم المشكلة عن طريق مضاعفة أبعاد الشبكة وخفض الخطوة الزمنية إلى النصف. وهذا يؤدي إلى أربعة أضعاف عدد نقاط الشبكة ومرتين عدد الخطوات الزمنية. ثم تبدو التوقيتات كالتالي:
• تعد المشاكل التي تزيد من نسبة الوقت المتوازي بحجمها أكثر قابلية للتطوير من المشاكل التي لها نسبة الوقت المتوازي ثابتة.
• تعقيد - Complexity:
• تعتبر التطبيقات المتوازية، عموما، أكثر تعقيدا من نظيراتها من التطبيقات التسلسلية، وربما يكون بمعدل أسي. ليس فقط لان لديك تنفيذ لتدفقات من التعليمات المتعددة في نفس الوقت، ولكن لأنك تمتلك أيضا بيانات متدفقة بينها.
• وتقاس تكاليف التعقيد في وقت البرمجة في كل جانب تقريبا من دورة تطوير البرمجيات:
• التصميم
• الترميز
• التصحيح
• الضبط
• الصيانة
• إن التمسك بممارسات تطوير البرمجيات "الجيدة" أمر ضروري عند العمل بتطبيقات متوازية - خاصة إذا كان شخص ما سيعمل بجانبك على البرنامج.
• قابلية النقل - Portability:
• بفضل التوحيد القياسي في العديد من واجهات برمجة التطبيقات APIs مثل MPI وخيوط POSIX وOpenMP، فإن قضايا قابلية النقل بالبرامج المتوازية ليست خطيرة كما في السنوات الماضية. ومع ذلك...
• تطبق جميع قضايا النقل المعتادة المرتبطة بالبرامج التسلسلية على البرامج المتوازية. على سبيل المثال، إذا كنت تستخدم "تحسينات" المورد إلى Fortran، C أو C++، فستصبح قابلية النقل مشكلة.
• على الرغم من وجود معايير لعدة واجهات برمجة التطبيقات، فإن عمليات التنفيذ تختلف في عدد من التفاصيل، وأحيانا في نقطة تتطلب تعديلات في الشفرة (الترميز) من أجل تحقيق قابلية النقل.
• يمكن أن تساهم أنظمة التشغيل بدور رئيسي في قضايا قابلية نقل الشفرة.
• تعد بنيات الأجهزة قابلة للتغيير بشكل كبير ويمكن أن تؤثر على قابلية النقل.
• متطلبات الموارد - Resource Requirements:
• الغرض الأساسي من البرمجة المتوازية هو تقليل وقت التنفيذ على مدار الساعة، ولكن من أجل تحقيق ذلك، فإن الأمر يتطلب المزيد من وقت وحدة المعالجة المركزية. على سبيل المثال، الشفرة المتوازية التي يتم تشغيلها خلال ساعة واحدة على ثمان معالجات تستخدم في الواقع 8 ساعات من وقت وحدة المعالجة المركزية.
• قد تكون كمية الذاكرة المطلوبة للشفرات المتوازية أكبر من مثيلتها بالنسبة للشفرات التسلسلية، وذلك بسبب الحاجة إلى تكرار البيانات والتكلفة المرتبطة بمكتبات الدعم المتوازي والنظم الفرعية.
• بالنسبة للبرامج القصيرة المتوازية، يمكن أن يكون هناك انخفاض في الأداء مقارنة بالتنفيذ التسلسلي المتشابه. ويمكن أن تكون التكلفة المرتبطة بتهيئة البيئة المتوازية، وإنشاء المهام، والاتصالات وإنهاء المهام، جزءا كبيرا من وقت التنفيذ الإجمالي للمدى القصير.
• قابلية التوسع - Scalability:
• نوعان من قابلية التوسع قائمان على الوقت إلى الحل: التحجيم القوي والتحجيم الضعيف.
• التحجيم القوي - Strong scaling:
• يبقى حجم المشكلة الإجمالي ثابتا كلما تمت إضافة المزيد من المعالجات.
• الهدف هو تشغيل نفس حجم المشكلة بشكل أسرع
• يقصد بالتحجيم الكامل حل المشكلة في زمن 1/p (مقارنة بالتسلسل)
• التحجيم الضعيف - Weak scaling:
• يبقى حجم المشكلة لكل معالج ثابتا كلما تمت إضافة المزيد من المعالجات.
• الهدف هو تشغيل مشكلة أكبر في نفس المدة الزمنية
• يقصد بالتحجيم الكامل أن المشكلة Px تشتغل في نفس الوقت الذي يشتغل فيه معالج واحد
• إن قدرة أداء برنامج متوازي على التوسع هي نتيجة لعدد من العوامل المترابطة. ببساطة، إن إضافة المزيد من المعالجات نادرا ما يكون هو الحل.
• قد تكون للخوارزمية حدود متأصلة لقابلية التوسع. وفي مرحلة ما، يؤدي إضافة المزيد من الموارد إلى تقليل الأداء. وهذا حالة مشتركة في العديد من التطبيقات المتوازية.
• تلعب عوامل الأجهزة دورا هاما في قابلية التوسع. أمثلة:
• سعة نطاق ناقل ذاكرة وحدة المعالجة المركزية على آلة SMP
• سعة نطاق شبكة الاتصالات
• كمية الذاكرة المتاحة في أية آلة معينة أو مجموعة آلات
• سرعة المعالج على مدار الساعة
• يمكن لمكتبات الدعم المتوازي وبرامج النظم الفرعية أن تحد قابلية التوسع المستقلة لتطبيقك.
بنيات ذاكرة الحاسوب المتوازية
الذاكرة المشتركة - Shared Memory
• الخصائص العامة
• تختلف أجهزة الحاسوب المتوازية ذات الذاكرة المشتركة كثيرا، ولكنها تشترك عموما في قابلية جميع المعالجات في الوصول إلى كل الذاكرة كحيز عنوان عام.
• يمكن أن تعمل العديد من المعالجات بشكل مستقل ولكنها تشترك في نفس موارد الذاكرة.
• تكون التغييرات التي ينجزها معالج واحد في موقع الذاكرة مرئية لجميع المعالجات الأخرى.
• تاريخيا، تم تصنيف آلات الذاكرة المشتركة إلى ذاكرة موحدة الوصول (UMA) وذاكرة غير موحدة الوصول (NUMA)، وذلك استنادا إلى أوقات الوصول إلى الذاكرة.
• الذاكرة موحدة الوصول - Uniform Memory Access (UMA)
• تتمثل اليوم بشكل شائع من قبل الآلات المعالج المتعدد المتناظر (SMP)
• معالجات متطابقة
• وصول متساوي وأوقات وصول إلى الذاكرة
• تسمى أحيانا ذاكرة موحدة الوصول متماسكة مخبأة (CC-UMA). ويقصد بمتماسكة مخبأة إنه إذا قام معالج واحد بتحديث موقع في الذاكرة المشتركة، فإن جميع المعالجات الأخرى تعلم التحديث. يتم تحقيق التماسك المخبأ على مستوى العتاد.
• الذاكرة غير موحدة الوصول - Non-Uniform Memory Access (NUMA)
• غالبا ما تُصنع عن طريق ربط مادي (فيزيائي) لاثنين أو أكثر من الآلات المعالج المتعدد المتناظرSMP
• يمكن لآلة المعالج المتعدد المتناظرSMP الوصول مباشرة لذاكرة آلة المعالج المتعدد المتناظر SMP أخرى.
• ليس لكل المعالجات وقت وصول متساو إلى جميع الذاكرات
• يعتبر الوصول إلى الذاكرة عبر الرابط أبطأ
• إذا تم الحفاظ على التماسك المخبأ، حينها يمكن أيضا أن تسمى ذاكرة غير موحدة الوصول متماسكة مخبأة (CC-NUMA)
• الإيجابيات
• يوفر حيز العنوان العام منظور برمجة سهل الاستخدام للذاكرة
• يعد تبادل البيانات بين المهام سريعا وموحدا على حد سواء لقرب الذاكرة من وحدات المعالجة المركزية
• السلبيات
• السلبية الأساسية هي عدم قابلية التوسع بين الذاكرة ووحدات المعالجة المركزية. حيث أنه يمكن بإضافة المزيد من وحدات المعالجة المركزية أن تزيد حركة المرور هندسيا على مسار الذاكرة المشتركة لوحدة المعالجة المركزية، أما بالنسبة للأنظمة المتماسكة المخبأة، فإن حركة المرور المرتبطة بإدارة الذاكرة/المخبأة تزداد هندسيا.
• مسؤولية المبرمج لتنظيم التزامن الذي يضمن الوصول "الصحيح" للذاكرة الإجمالية.
معماريات ذاكرة الحاسوب المتوازية
الذاكرة الموزعة - Distributed Memory
• الخصائص العامة
مثل أنظمة الذاكرة المشتركة، تتنوع أنظمة الذاكرة الموزعة كثيرا ولكنها تتقاسم مميزات مشتركة. وتتطلب أنظمة الذاكرة الموزعة شبكة اتصالات للتوصيل بين الذاكرة والمعالج.
• تمتلك المعالجات ذاكرة محلية خاصة بها. ولا يتم تعيين عناوين الذاكرة في معالج واحد إلى معالج آخر، لذلك ليس هناك مفهوم حيز عنوان عام عبر جميع المعالجات.
• ولأن كل معالج له ذاكرة محلية خاصة به، فإنه يعمل بشكل مستقل. إذ ليست للتغييرات التي يجريها على ذاكرته المحلية أي تأثير على ذاكرة المعالجات الأخرى. وبالتالي، فإن مفهوم التماسك المخبأ لا ينطبق.
• عندما يحتاج المعالج إلى الوصول إلى البيانات في معالج آخر، فإنه عادة ما يكون من مهمة المبرمج لتحديد صريح لكيفية وزمن توصيل البيانات. كما يعد كذلك التزامن بين المهام من مسؤولية المبرمج.
• تختلف "معمارية" الشبكة المستخدمة لنقل البيانات بشكل كبير، على الرغم من أنها يمكن أن تكون بسيطة مثل شبكة الإيثرنت.
• الإيجابيات
• تعد الذاكرة قابلة للتوسع مع عدد المعالجات. حيث كلما زاد عدد المعالجات ازداد حجم الذاكرة بشكل تناسبي.
• يمكن لكل معالج أن يصل بسرعة إلى الذاكرة الخاصة به دون تدخل ودون تكلفة المتكبدة مع محاولة الحفاظ على التماسك المخبأ العام.
• فعالية التكلفة: يمكن استخدام السلع، والمعالجات الجاهزة والتشبيك.
• السلبيات
• المبرمج هو المسؤول عن العديد من التفاصيل المرتبطة باتصال البيانات بين المعالجات.
• قد يكون من الصعب تعيين هياكل البيانات المتوفرة، استنادا على الذاكرة الإجمالية، إلى تنظيم الذاكرة هذا.
• أوقات الذاكرة غير موحدة الوصول – تستغرق البيانات الموجودة على عقدة بعيدة وقتا أطول للوصول مقارنة بالبيانات المحلية للعقدة.
الذاكرة المشتركة-الموزعة الهجينة - Hybrid Distributed-Shared Memory
• الخصائص العامة
• تستخدم اليوم أكبر وأسرع أجهزة الحاسوب في العالم معمارية الذاكرة المشتركة والموزعة على حد سواء.
 |
 |
• يمكن أن يكون مكون الذاكرة المشتركة جهاز ذاكرة مشترك و/أو وحدات معالجة الرسومات (GPU).
• مكون الذاكرة الموزعة عبارة عن تشبيك للعديد من أجهزة وحدات معالجة الرسومات/ذاكرات مشتركة، والتي تعرف فقط عن الذاكرة الخاصة بها – وليس عن ذاكرة على جهاز آخر. لذلك، يتطلب الأمر شبكة اتصالات لنقل البيانات من جهاز إلى آخر.
• ويبدو أن الاتجاهات الحالية تشير إلى أن هذا النوع من بنيات الذاكرة سيستمر في الانتشار وسيزداد في الحوسبة الفائقة في المستقبل المنظور.
• الإيجابيات والسلبيات
• كل شيء مشترك بين بنية كل من الذاكرة المشتركة والذاكرة الموزعة.
• زيادة قابلية التطوير هي ميزة هامة لديها
• زيادة تعقيد المبرمج هي سلبية مهم لديها
نماذج البرمجة المتوازية
نظرة عامة
• هناك العديد من نماذج البرمجة المتوازية المستخدمة اليوم:
◦ الذاكرة المشتركة (بدون خيوط)
◦ الخيوط
◦ الذاكرة الموزعة / تمرير الرسالة
◦ البيانات المتوازية
◦ الهجين
◦ برنامج واحد متعدد البيانات (SMPD)
◦ برامج متعددة ذات بيانات متعددة (MPMD )
• توجد نماذج البرمجة المتوازية كتجريد فوق معمارية الأجهزة والذاكرات.
• على الرغم من أنه قد لا يبدو واضحا، إلا أن هذه النماذج ليست محددة لنوع خاص من الأجهزة أو معماريات الذاكرة. في الواقع، أي من هذه النماذج يمكن (نظريا) أن تنفذ على الأجهزة الأساسية. وسنناقش أدناه مثالان من الماضي.
نموذج ذاكرة مشتركة على جهاز ذاكرة موزعة:
مقاربة Kendall Square Research (KSR) ALLCACHE، وزعت ذاكرة جهاز فيزيائيا عبر أجهزة مشبكة، ولكنها تبدو للمستخدم كحيز عنوان عام لذاكرة مشتركة واحدة. وبشكل عام، يشار إلى هذه المقاربة باسم "الذاكرة المشتركة الافتراضية".
 |
 |
نموذج ذاكرة موزعة على جهاز ذاكرة مشتركة:
واجهة تمرير الرسالة Message Passing Interface (MPI) على SGI Origin 2000. تستخدم SGI Origin 2000 النوع CC-NUMA من بنية الذاكرة المشتركة، حيث تملك كل مهمة لديها إمكانية الوصول المباشر إلى حيز العنوان العام عبر جميع الأجهزة. ومع ذلك، فإن قابلية إرسال واستقبال الرسائل باستخدام MPI، كما هو الحال عادة على شبكة من أجهزة الذاكرة الموزعة، تكون منفذة ومستخدمة بشكل مشترك.
 |
 |
• أي نموذج يجب استخدامه؟ هذا غالبا ما يكون توليفة بين ما هو متاح و ما هو اختيار شخصي. لا يوجد نموذج "أفضل"، على الرغم من أن هناك بالتأكيد تطبيقات أفضل لبعض النماذج من غيرها.
• تصف الأقسام التالية كل من النماذج المذكورة أعلاه، وتناقش أيضا بعض عمليات التنفيذ الفعلية.
نموذج الذاكرة المشتركة (بدون خيوط)
• تشارك العمليات/المهام حيز عنوان مشترك، في نموذج البرمجة هذا، والذي تقوم بقراءته وكتابته بشكل غير متزامن.
• تستخدم آليات مختلفة مثل الأقفالlocks /منظم المرورsemaphores للتحكم في الوصول إلى الذاكرة المشتركة، وحل التنازعات ولمنع حالة التعارضات والتوقفات التامة.
• قد يكون هذا أبسط نموذج برمجة متوازية.
• ميزة هذا النموذج من وجهة نظر المبرمج هي أن مفهوم "ملكية" البيانات غير موجودة، لذلك ليس هناك حاجة لتحديد اتصالات البيانات بين المهام بوضوح. وتمتلك جميع العمليات رؤية ووصول متساو إلى الذاكرة المشتركة. ويمكن في كثير من الأحيان تبسيط تطوير البرامج.
• من العوائق الهامة من حيث الأداء أن فهم وإدارة موقع البيانات يصبح أكثر صعوبة:
◦ الحفاظ على البيانات المحلية في العملية التي تعمل على ذلك تحافظ على الوصول إلى الذاكرة، وتحديثات المخبأة وحركة مرور الناقل التي تحدث عندما تستخدم العديد من العمليات نفس البيانات.
◦ لسوء الحظ، يعد ضبط موقع البيانات صعب الفهم وقد يكون خارج نطاق التحكم لدى المستخدم العادي.
• آليات تنفيذ هذا النموذج
• على أجهزة الذاكرة المشتركة القائمة بذاتها، وأنظمة التشغيل الأصلية، توفر مترجمات اللغة و/أو العتاد الدعم اللازم لبرمجة الذاكرة المشتركة. فعلى سبيل المثال، يوفر معيار POSIX واجهة برمجة تطبيق (API) لاستخدام الذاكرة المشتركة، بينما يوفر UNIX قطع الذاكرة المشتركة (shmget، shmat، shmctl، الخ).
• على أجهزة الذاكرة الموزعة، توزع الذاكرة فيزيائيا عبر شبكة من الأجهزة، ولكن تصبح عامة عبر الأجهزة والبرمجيات المتخصصة. مجموعة متنوعة من آليات التنفيذ لـ SHMEM متاحة راجع: http://en.wikipedia.org/wiki/SHMEM.
نموذج الخطوط - Threads Model
• هذا النموذج البرمجي هو نوع من برمجة الذاكرة المشتركة.
• في نموذج الخيوط للبرمجة المتوازية، يمكن لعملية واحدة " ثقيلة الوزن" أن تكون لديها عمليات متعددة "خفيفة الوزن"، ومسارات تنفيذ متزامنة.
• على سبيل المثال:
◦ تتم جدولة البرنامج الرئيسي a.out ليشتغل من قبل نظام التشغيل الأصلي. ويقوم a.out بتحميل واكتساب كل موارد النظام والمستخدمين اللازمة لتشغيله. هذه هي عملية "الوزن الثقيل".
◦ يؤدي a.out بعض الأعمال التسلسلية، ثم يقوم بإنشاء عدد من المهام (الخيوط) التي يمكن جدولتها وتشغيلها من قبل نظام التشغيل بشكل متزامن.
◦ يحتوي كل خيط على بيانات محلية، ولكنه أيضا، يشارك الموارد الكاملة لـ a.out. وهذا يوفر التكلفة المرتبطة بتكرار موارد برنامج لكل خيط ("خفيفة الوزن"). ويستفيد كل خيط أيضا من عرض ذاكرة إجمالية لأنه يشارك مساحة الذاكرة لـ a.out.
◦ يمكن وصف عمل الخيوط بشكل أفضل كنهج فرعي ضمن البرنامج الرئيسي. حيث يمكن لأي خيط تنفيذ أي نهج فرعي في نفس الوقت كما بالنسبة للخيوط الأخرى.
◦ تتواصل الخيوط مع بعضها البعض من خلال الذاكرة الإجمالية (تحديث مواقع العناوين). ويتطلب هذا إنشاء تزامن للتأكد من أنه لا يتم تحديث نفس العنوان العام لأكثر من خيط واحد في أي وقت.
◦ يمكن للخيوط أن تأتي وتذهب، ولكن يظل a.out حاضرا لتوفير الموارد المشتركة اللازمة إلى غاية اكتمال التطبيق.
• تطبيقات - Implementations
• من منظور البرمجة، تشتمل عمليات التنفيذ للخيوط عادة على:
◦ مكتبة من النهج الفرعية التي يتم استدعاءها من داخل شفرة المصدر المتوازي
◦ مجموعة من توجيهات المترجم البرمجي المضمنة ضمن شفرة المصدر التسلسلي أو ضمن شفرة المصدر المتوازي
وفي كلتا الحالتين، يكون المبرمج هو المسؤول عن تحديد التوازي (على الرغم من أنه يمكن لمترجمات اللغة أن تقدم المساعدة أحيانا).
• لا تعد عمليات تنفيذ الخيوط جديدة في الحوسبة. فتاريخيا، قام موردو الأجهزة بتوفير آليات تنفيذ ذات إصدارات ملكية خاصة بهم من الخيوط. وتختلف هذه آليات التنفيذ اختلافا جوهريا عن بعضها البعض، مما يجعل الأمر صعبا على المبرمجين لتطوير تطبيقات متسلسلة محمولة.
• أدت جهود توحيد المقاييس المنفصلة إلى إخراج آليتي تنفيذ للخيوط مختلفتين جدا: خيوط POSIX و OpenMP.
• خيوط POSIX
◦ يحددها المقياس IEEE POSIX 1003.1c (1995). لغة C فقط.
◦ جزء من أنظمة التشغيل يونكس/لينكس (Unix/Linux)
◦ بني من منظور مكتبة
◦ يشار إليها عادة باسم Pthreads.
◦ جد متوازية؛ تتطلب اهتمام كبير من مبرمج بالتفاصيل.
• OpenMP
◦ مقياس صناعي، تم تحديده بشكل مشترك وأيدته مجموعة من الموردين الكبار لأجهزة وبرمجيات الحاسوب، والمنظمات والأفراد.
◦ بني من منظور توجيه المترجم (Compiler)
◦ محمول / متعدد المنصات، بما في ذلك منصتي يونكس وويندوز
◦ متوفر في تطبيقات C / C ++ و Fortran
◦ يمكن أن يكون جد سهل وبسيط الاستخدام - يوفر "التوازي التدريجي". ويمكن أن يبدأ برمز تسلسلي.
• آليات تنفيذ أخرى للخيوط، ولكن لم تتم مناقشتها هنا:
◦ خيوط ميكروسوفت
◦ خيوط جافا، خيوط بيثون
◦ خيوط CUDA لوحدات معالجة الرسومات (GPUs)
• المزيد من المعلومات
• دورة خيوط POSIX: computing.llnl.gov/tutorials/pthreads
• دورة OpenMP: computing.llnl.gov/tutorials/openMP
الذاكرة الموزعة / نموذج تمرير رسالة - Distributed Memory / Message Passing Model
• يوضح هذا النموذج الخصائص التالية:
◦ مجموعة من المهام التي تستخدم الذاكرة المحلية الخاصة بها أثناء الحساب. يمكن أن تتواجد مهام متعددة على نفس الجهاز الفيزيائي و/أو عبر عدد اعتباطي من الأجهزة.
◦ بيانات تبادل المهام من خلال الاتصالات بإرسال واستقبال الرسائل.
◦ عادة ما يتطلب نقل البيانات إجراء عمليات تعاونية من قبل كل عملية. على سبيل المثال، يجب أن تكون لعملية الإرسال عملية استقبال مطابقة.
• آليات التنفيذ
• من منظور البرمجة، عادة ما تتضمن آليات تنفيذ تمرير الرسائل مكتبة النُّهج الفرعية. ويتم تضمين الاستدعاءات إلى هذه النُّهج الفرعية في شفرة المصدر. ويكون المبرمج مسؤولا عن تحديد كل التوازي.
• من الناحية التاريخية، كانت هناك مجموعة متنوعة من مكتبات تمرير الرسائل منذ الثمانينيات. وتختلف عمليات التنفيذ هذه اختلافا كبيرا عن بعضها البعض مما يجعل من الصعب على المبرمجين تطوير التطبيقات المحمولة.
• في عام 1992، تم تشكيل منتدى MPI بهدف أساسي هو إنشاء واجهة قياسية لعمليات تنفيذ تمرير الرسائل.
• تم إصدار الجزء 1 من واجهة تمرير الرسائل (MPI) عامَ 1994. بينما تم إصدار الجزء 2 (MPI-2) عامَ 1996 وMPI-3 عامَ 2012. جميع مواصفات MPI متوفرة على شبكة الإنترنت: //www.mpi- forum.org/docs/.
• يعد MPI "بحكم الأمر الواقع" مقياسا صناعيا لتمرير الرسائل، وحلَّ تقريبا محل جميع عمليات التنفيذ المستخدمة الأخرى والخاصة بتمرير الرسائل في أعمال الإنتاج. وتوجد آليات التنفيذ في جميع منصات الحوسبة المتوازية الشهيرة تقريبا. لا تشمل جميع آليات التنفيذ كل شيء في MPI-1 أو MPI-2 أو MPI-3.
• المزيد من المعلومات:
دورة MPI: computing.llnl.gov/tutorials/mpi
نموذج البيانات المتوازية - Data Parallel Model
• قد يشار إليه أيضا كنموذج حيز العنوان العام المجزأ ( Partitioned Global Address Space PGAS).
• يوضح النموذج المتوازي للبيانات الخصائص التالية:
◦ يتعامل مع حيز العنوان بشكل عام
◦ تركز معظم الأعمال المتوازية على أداء العمليات لمجموعة بيانات. وعادة ما تنظم مجموعة البيانات في بنية مشتركة، مثل مصفوفة أو مكعب.
◦ تعمل مجموعة من المهام بشكل جماعي على بنية البيانات نفسها، ومع ذلك، تعمل كل مهمة على جزء مختلف عن نفس بنية البيانات.
◦ تقوم المهام بتنفيذ نفس العملية في جزئها الخاص بالعمل، على سبيل المثال، "إضافة 4 إلى كل عنصر من مصفوفة".
• على معماريات الذاكرة المشتركة، قد تكون لجميع المهام إمكانية الوصول إلى بنية البيانات من خلال الذاكرة الإجمالية.
• على معماريات الذاكرة الموزعة، يمكن تقسيم بنية البيانات الإجمالية بشكل منطقي و/أو فيزيائي من خلال المهام.
• آليات التنفيذ:
• حاليا، هناك العديد من آليات التنفيذية الشهيرة نسبيا، وأحيانا تطورية، مبنية على أساس البيانات المتوازية/نموذج PGAS.
• كوراي فورتران (Coarray Fortran): مجموعة صغيرة من ملحقات فورتران 95 للبرمجة المتوازية SPMD. تعتمد على المترجم. للمزيد من المعلومات: https://en.wikipedia.org/wiki/Coarray_Fortran
• C المتوازي الموحد (UPC Unified Parallel C): امتداد للغة البرمجة C للبرمجة المتوازية SPMD. تعتمد على المترجم. للمزيد من المعلومات: http://upc.lbl.gov/
• المصفوفات العامة Global Arrays: توفر بيئة برمجة نمط الذاكرة المشتركة في سياق بنيات بيانات المصفوفة الموزعة. مكتبة ذات ملكية عامة مع ارتباطات C و Fortran77. مزيد من المعلومات: https://en.wikipedia.org/wiki/Global_Arrays
• X10: لغة برمجة متوازية على أساس PGAS يتم تطويرها من قبل شركة IBM في مركز أبحاث توماس ج. واتسون. للمزيد من المعلومات: http://x10-lang.org/
• Chapel: مشروع لغة برمجة متوازية مفتوح المصدر يقوده كراي (Cray). للمزيد من المعلومات: http://chapel.cray.com/
النموذج الهجين - Hybrid Model
• يجمع النموذج الهجين بين أكثر من نموذج من نماذج البرمجة الموصوفة سابقا.
• حاليا، يوجد مثال شائع لنموذج هجين هو مزيج من نموذج تمرير الرسائل (MPI) مع نموذج الخيوط (OpenMP).
◦ تقوم الخيوط بالعمليات الحسابية المكثفة باستخدام البيانات المحلية للعقدة
◦ تحدث اتصالات بين العمليات على مختلف العقد عبر الشبكة باستخدام MPI
• أثبت هذا النموذج الهجين بأنه يعمل بشكل رائع في البيئات الشهيرة للأجهزة العنقودية متعددة/عديدة الأنوية.
• مثال آخر مماثل وشعبي على نحو متزايد لنموذج هجين هو استخدام MPI مع برمجة CPU-GPU (وحدة المعالجة المركزية - وحدة معالجة الرسومات).
◦ تشغل مهام MPI على وحدات المعالجة المركزية باستخدام الذاكرة المحلية والتواصل مع بعضها البعض عبر الشبكة.
◦ نوى مركزة حسابيا محملة على وحدات معالجة الرسومات على العقدة.
◦ تبادل البيانات بين الذاكرة عقدة المحلية و ووحدات المعالجات الرسومية باستخدام CUDA (أو ما يعادله).
• نماذج هجينة أخرى شائعة:
◦ MPI مع خيوط POSIX (Pthreads)
◦ MPI مع مسرعات غير وحدات معالجة الرسومات (non-GPU)
◦ ...
SPMD وMPMD
• برنامج واحد متعدد البيانات - Single Program Multiple Data (SPMD):
• يعتبر SPMD حاليا نموذج برمجة "عالية المستوى" التي يمكن بناؤها اعتمادا على أي مزيج من نماذج البرمجة المتوازية المذكورة سابقا.
• برنامج واحد: تنفذ جميع المهام نسختها من نفس البرنامج في وقت واحد. هذا البرنامج يمكن أن يكون خيوطا، تمريرا للرسائل، بيانات متوازية أو هجينة.
• بيانات متعددة: قد تستخدم جميع المهام بيانات مختلفة
• عادة ما يكون لبرامج SPMD المنطق الضروري المبرمج فيها للسماح لمهام مختلفة بالتفرع أو بتنفيذ مشروط فقط لتلك الأجزاء من البرنامج التي تم تصميمها لتنفيذها. أي أن المهام لا تحتاج بالضرورة إلى تنفيذ البرنامج بأكمله – بل ربما لجزء منه فقط.
• ربما يكون نموذج SPMD، باستخدام تمرير الرسائل أو البرمجة الهجينة، نموذج البرمجة المتوازية الأكثر استخداما لعناقيد متعددة العقد.
• متعددة بيانات متعددة البرامج - Multiple Program Multiple Data (MPMD):
• مثل SPMD، يعتبر MPMD حاليا نموذج برمجة "عالية المستوى" والتي يمكن بناؤها على أساس أي مزيج من نماذج البرمجة الموازية المذكورة سابقا.
• برامج متعدد: قد تنفذ المهام برامج مختلفة في وقت واحد. ويمكن أن تكون البرامج عبارة عن خيوط، تمرير رسائل، بيانات متوازنة أو هجينة.
• بيانات متعددة: قد تستخدم جميع المهام بيانات مختلفة
• لا تعد تطبيقات MPMD شائعة مثلما هو الأمر بالنسبة لتطبيقات SPMD، ولكنها قد تكون أكثر ملاءمة لأنواع معينة من المشاكل، لا سيما تلك التي تكون أفضل لتفكك وظيفي منه لتفكك مجالي (الذي ستتم مناقشته لاحقا في فصل التجزئة).
تصميم البرامج المتوازية
الموازاة اليدوية مقابل الموازاة التلقائية - Automatic vs. Manual Parallelization
• كان تصميم وتطوير البرامج المتوازية عملية يدوية للغاية. حيث يكون المبرمج هو المسؤول عادة عن تحديد وحاليا عن تنفيذ التوازي.
• في كثير من الأحيان، يستغرق تطوير الشفرات المتوازية يدويا وقتا طويلا، ويكون معقدا، وعرضة للخطأ وعملية تكرارية.
• منذ عدة سنوات، أصبحت أدوات مختلفة متاحة لمساعدة المبرمج على تحويل البرامج التسلسلية إلى برامج متوازية. والنوع الأكثر شيوعا من الأدوات المستخدمة لموازاة برنامج تسلسلي تلقائيا هو مترجم الموازاة أو ما قبل المعالج.
• يعمل مترجم الموازاة عموما بطريقتين مختلفتين:
تلقائية تامة - Fully Automatic
• يحلل المترجم شفرة المصدر ويحدد فرص التوازي.
• يشمل التحليل تحديد مثبطات التوازي وربما ترجيح التكلفة على ما إذا كان التوازي سيحسن الأداء فعلا أم لا.
• تعتبر حلقات التكرار (do، for) الهدف الأكثر شيوعا للتوازي التلقائي.
مبرمج موجه - Programmer Directed
• باستخدام "توجيهات المترجم" أو ربما أعلام المترجم، يقول المبرمج للمترجم بشكل واضح كيفية موازاة الشفرة البرمجية.
• قد تكون قادرة على استخدامها جنبا إلى جنب مع بضع درجات من التوازي التلقائي أيضا.
• يتم إنشاء مترجم الأكثر شيوعا للموازاة المولدة باستخدام الذاكرة المشتركة على العقدة والخيوط (مثل OpenMP).
• إذا كنت تبدأ مع شفرة تسلسلية جاهزة ومقيد بوقت أو ميزانية، فإن التوازي التلقائي قد يكون هو الأفضل. ومع ذلك، هناك العديد من التحذيرات الهامة التي تنطبق على التوازي التلقائي:
◦ قد تنتج نتائج خاطئة
◦ قد يقل الأداء فعلا
◦ أقل مرونة من التوازي اليدوي
◦ تقتصر على مجموعة فرعية (معظمها حلقات التكرار) من الشفرة
◦ قد لا تكون الشفرة متوازية في الواقع إذا كان تحليل المترجم يشير إلى أن هناك مثبطات أو أن الشفرة معقدة جدا
• ينطبق الجزء المتبقي من هذا الفصل على الطريقة اليدوية لتطوير الشفرات المتوازية.
فهم المشكلة والبرنامج
• مما لا شك فيه، أن الخطوة الأولى في تطوير البرمجيات المتوازية هي أولا فهم المشكلة التي ترغب في حلها بالتوازي. إذا بدأت مع برنامج تسلسلي، فإن هذا يتطلب فهم الشفرات البرمجية الجاهزة أيضا.
• قبل قضاء بعض الوقت في محاولة لتطوير حل متواز للمشكلة، حدد ما إذا كانت المشكلة هي التي يمكن أن تكون متوازية بالفعل أم لا.
◦ مثال على سهولة موازاة مشكلة:
احسب الطاقة المحتملة لكل من واحدة من عدة آلاف من التشكلات المستقلة لجزيئة. عندما تنتهي من ذلك، ابحث عن الحد الأدنى لطاقة التشكل.
هذه المشكلة لديها القابلية على أن تحل على التوازي. حيث يمكن تحديد كل واحدة من التشكلات الجزيئية بشكل مستقل. ويعد أيضا حساب الحد الأدنى من طاقة التشكل مشكلة متوازية.
• مثال على مشكلة مع القليل من التوازي أو بدونه:
حساب سلسلة فيبوناتشي (Fibonacci) (0،1،1،2،3،5،8،13،21، ...) باستخدام الصيغة:
F(n) = F(n-1) + F(n-2)
يستخدم حساب القيمة F(n) قيمتي F(n-1) وF(n-2) التي يجب حسابهما أولا.
• تحديد نقاط الحوسبة المكثفة في البرنامج hotspots :
◦ اعرف أين يتم معظم العمل الحقيقي. غالبا ما تحقق معظم البرامج العلمية والتقنية معظم عملها في أماكن قليلة.
◦ يمكن أن تساعدك المحللات وأدوات تحليل الأداء هنا
◦ ركز على موازاة نقاط الحوسبة المكثفة وتجاهل تلك الأقسام من البرنامج ذات الاستخدام القليل لوحدة المعالجة المركزية.
• تحديد نقاط الاختناق (bottlenecks) في البرنامج:
◦ هل هناك مناطق بطيئة بشكل غير متناسب، أو تتسبب في وقف العمل أو إرجاءه؟ على سبيل المثال، ادخال/اخراج (I/O) هو عادة شيء يبطئ البرنامج.
◦ قد يكون من الممكن إعادة هيكلة البرنامج أو استخدام خوارزمية مختلفة لتقليل أو القضاء على المناطق البطيئة غير الضرورية
• تحديد مثبطات التوازي. أحد الفئات الشائعة للمثبط هو الاعتماد على البيانات، كما يتضح من تسلسل فيبوناتشي أعلاه.
• تحقق من الخوارزميات الأخرى إن أمكن. قد يكون هذا هو الاعتبار الأكثر أهمية عند تصميم تطبيق متواز.
• استفد من إيجابيات برنامج المتوازي للطرف الثالث الأمثل ومكتبات الرياضيات المثالية المتاحة من كبار الموردين (IBM's ESSL، Intel's MKL، AMD's AMCL وما إلى ذلك).
التجزئة - Partitioning
• واحدة من الخطوات الأولى في تصميم برنامج متواز هو تقسيم المشكلة إلى "قطع" منفصلة من الأعمال التي يمكن توزيعها على مهام متعددة. ويعرف هذا باسم التحلل أو التجزئة.
• هناك طريقتان أساسيتان لتجزئة العمل الحسابي بين المهام المتوازية: التحلل المجالي والوظيفي.
• التحلل المجالي - Domain Decomposition:
• في هذا النوع من التجزئة، يتم تحليل البيانات المرتبطة بالمشكلة. ثم تعمل كل مهمة متوازية على جزء من البيانات.
• هناك طرق مختلفة لتقسيم البيانات:
• التحلل الوظيفي - Functional Decomposition:
• في هذا النهج، ينصب التركيز على الحساب الذي يتعين القيام به وليس على البيانات التي تتم معالجتها بواسطة الحساب. وتتحلل المشكلة وفقا للعمل الذي يجب القيام به. كل مهمة تنفذ إذن جزءا من العمل الإجمالي.
• يفسح التحلل الوظيفي المجال للمشاكل التي يمكن تقسيمها إلى مهام مختلفة. فمثلا:
نمذجة النظم الإيكولوجية - Ecosystem Modeling
يحسب كل برنامج عدد السكان من مجموعة معينة، حيث يعتمد نمو كل مجموعة على نمو جارتها. ومع مرور الوقت، تحسب كل عملية حالتها الحالية، ثم تتبادل المعلومات مع الكثافات السكانية المجاورة. تتقدم جميع المهام بعدها لحساب الحالة في الخطوة الزمنية التالية.
معالجة الإشارات - Signal Processing
يتم تمرير مجموعة بيانات إشارة الصوت من خلال أربعة مرشحات حسابية مختلفة. كل مرشح عبارة عن عملية منفصلة. يجب أن يمر الجزء الأول من البيانات من خلال المرشح الأول قبل التقدم إلى الثاني. وعندما يحدث ذلك، يمر الجزء الثاني من البيانات من خلال المرشح الأول. وبحلول الوقت الذي يكون فيه الجزء الرابع من البيانات في المرشح الأول، فإن جميع المهام الأربع تكون مشغولة.
نمذجة المناخ - Climate Modeling
يمكن اعتبار كل مكون نموذج كمهمة منفصلة. وتمثل الأسهم تبادل البيانات بين المكونات أثناء الحساب: يولد نموذج الغلاف الجوي بيانات سرعة الرياح التي يستخدمها نموذج المحيطات، ونموذج المحيطات يولد بيانات درجة حرارة سطح البحر التي يستخدمها نموذج الغلاف الجوي، وهلم جرا.
• يعد الجمع بين هذين النوعين من تحلل المشكلة أمرا شائعا وطبيعيا.
الاتصالات - Communications
• من يحتاج الاتصالات؟
تتوقف الحاجة إلى الاتصالات بين المهام على مشكلتك:
تحتاج إلى الاتصالات:
• معظم التطبيقات المتوازية ليست بسيطة جدا، وتتطلب مهام لتبادل البيانات مع بعضها البعض.
• على سبيل المثال، تتطلب مشكلة انتشار الحرارة 2-D مهمة لمعرفة درجات الحرارة التي تحسبها المهام التي لها بيانات مجاورة. للتغييرات على البيانات المجاورة تأثير مباشر على بيانات تلك المهمة.
أنت لا تحتاج إلى الاتصالات:
• بعض أنواع المشاكل يمكن أن تتحلل وتنفذ بالتوازي دون أي حاجة تقريبا إلى المهام لتبادل البيانات. وغالبا ما توصف هذه الأنواع من المشاكل بالمتوازية المحرجة – وتكون هناك حاجة إلى اتصالات قليلة أو معدومة.
• على سبيل المثال، تخيل عملية معالجة الصور حيث يحتاج كل بكسل في صورة بالأبيض والأسود إلى عكس لونه. يمكن بسهولة توزيع بيانات الصورة إلى مهام متعددة تتصرف بعد ذلك بشكل مستقل عن بعضها البعض للقيام بجزءها من العمل.
• العوامل التي يجب مراعاتها:
هناك عدد من العوامل الهامة التي يجب مراعاتها عند تصميم الاتصالات بين المهام الخاصة ببرنامجك:
• كلفة الاتصالات - Communication overhead
◦ ينطوي التواصل بين المهام على كلفة بشكل دائم تقريبا.
◦ تستخدم بدلا من ذلك دورات الجهاز والموارد التي يمكن استخدامها للحساب لتجميع البيانات ونقلها.
◦ تتطلب الاتصالات في كثير من الأحيان نوعا من المزامنة بين المهام، الأمر الذي يمكن أن يؤدي إلى قضاء المهام الوقت في "الانتظار" بدلا من القيام بالعمل.
◦ يمكن أن تؤدي حركة مرور الاتصالات المتنافسة إلى تشبع حيز النطاق الترددي للشبكة، مما يزيد من تفاقم مشاكل الأداء.
• زمن الوصول مقابل حيز النطاق الترددي - Latency vs. Bandwidth
◦ زمن الوصول هو الوقت المستغرق لإرسال رسالة ذات الحجم الأدنى (0 بايت) من نقطة A إلى نقطة B. ويتم التعبير عنها بشكل عام بالميكروثانية.
◦ حيز النطاق الترددي هو مقدار البيانات التي يمكن توصيلها خلال وحدة زمنية. يعبر عنه عادة باسم ميغابايت/ثانية أو جيغابايت/ثانية.
◦ يمكن أن يسبب إرسال العديد من الرسائل الصغيرة جعل كلفة الاتصالات هي المسيطرة. في كثير من الأحيان يكون أكثر كفاءة تحزيم الرسائل الصغيرة في رسالة أكبر، وبالتالي زيادة عرض النطاق الفعال للاتصالات.
• رؤية الاتصالات - Visibility of communications
◦ مع نموذج تمرير الرسائل، تكون الاتصالات صريحة وعموما واضحة تماما وتحت تحكم المبرمج.
◦ مع النموذج المتوازي للبيانات، غالبا ما تحدث الاتصالات بشفافية للمبرمج، وخاصة على بنيات الذاكرة الموزعة. قد لا يكون المبرمج قادرا حتى على معرفة كيفية إنجاز الاتصالات بين المهام بالضبط.
• الاتصالات المتزامنة مقابل الاتصالات غير المتزامنة - Synchronous vs. asynchronous communications
◦ تتطلب الاتصالات المتزامنة نوعا من "المصافحة" بين المهام التي تشارك البيانات. يمكن أن يكون هذا منظما بشكل واضح في الشفرة من قبل المبرمج، أو أنه قد يحدث في مستوى أقل غير معروف بالنسبة للمبرمج.
◦ غالبا ما يشار إلى الاتصالات المتزامنة على أنها حاجبة للاتصالات لأن العمل الآخر يجب أن ينتظر حتى اكتمال الاتصالات.
◦ تسمح الاتصالات غير المتزامنة للمهام بنقل البيانات بشكل مستقل عن بعضها البعض. على سبيل المثال، يمكن للمهمة 1 إعداد وإرسال رسالة إلى المهمة 2، ثم تبدأ فورا بالقيام بأعمال أخرى. عندما تستقبل المهمة 2 البيانات التي لا تهم.
◦ غالبا ما يشار إلى الاتصالات غير المتزامنة على أنها اتصالات غير حاجبة لأنه يمكن القيام بالعمل الآخر في حين أن الاتصالات تجري.
◦ يعتبر الحساب البيني مع الاتصالات أكثر فائدة لاستخدام الاتصالات غير المتزامنة.
• نطاق الاتصالات - Scope of communications
◦ يعتبر معرفة أي المهام التي يجب تتواصل مع بعضها البعض أمرا بالغ الأهمية خلال مرحلة تصميم الشفرة المتوازية. ويمكن تنفيذ كلا النطاقين الموصوفين أدناه بشكل متزامن أو غير متزامن.
◦ نقطة إلى نقطة (Point-to-point) - ينطوي على مهمتين بمهمة واحدة تعمل كمرسل/منتج للبيانات، والآخر يعمل كمستقبل/مستهلك.
◦ الجماعي (Collective) - ينطوي على تبادل البيانات بين أكثر من مهمتين، والتي غالبا ما يتم تحديدها على أنها أعضاء في مجموعة مشتركة، أو جماعي. بعض الاختلافات الشائعة (هناك المزيد):
• كفاءة الاتصالات - Efficiency of communications
◦ في كثير من الأحيان، يملك المبرمج خيارات يمكن أن تؤثر على أداء الاتصالات. سيتم هنا ذكر عدد قليل منها فقط.
◦ ما هي عملية تنفيذ التي ينبغي استخدامها لنموذج معين؟ باستخدام نموذج تمرير الرسائل كمثال على ذلك، قد تكون عملية تنفيذ MPI أسرع على منصة أجهزة معينة أخرى.
◦ ما هو نوع عمليات الاتصال التي ينبغي استخدامها؟ كما تم ذكره سابقا، يمكن لعمليات الاتصالات غير المتزامنة أن تحسن الأداء العام للبرنامج.
◦ نسيج الشبكة - قد توفر بعض المنصات أكثر من شبكة واحدة للاتصالات. فأي واحدة هي الأفضل؟
• التكلفة والتعقيد - Overhead and Complexity
• وأخيرا، ندرك أن هذه ليست سوى قائمة جزئية من الأشياء التي يجب أخذها في عين الاعتبار !!!
المزامنة - Synchronization
• إدارة تسلسل العمل والمهام التي تؤديه هو اعتبار حساس في التصميم لمعظم البرامج المتوازية.
• يمكن أن يكون عاملا هاما في أداء البرنامج (أو عدم وجوده)
• غالبا ما يتطلب "تسلسل" أجزاء من البرنامج.
• أنواع المزامنة:
• الحاجز - Barrier
◦ عادة ما يعني أن جميع المهام معنية
◦ تؤدي كل مهمة عملها حتى تصل إلى الحاجز. ثم تتوقف، أو "يتم منعها".
◦ عندما تصل المهمة الأخيرة إلى الحاجز، تتم مزامنة جميع المهام.
◦ ما يحدث من هنا يختلف. في كثير من الأحيان، يجب أن يتم الجزء التسلسلي من العمل. وفي حالات أخرى، يتم تحرير المهام تلقائيا لمواصلة عملها.
• قفل / سيمافور (ملوحة) - Lock / semaphore
◦ يمكن أن ينطوي على أي عدد من المهام
◦ يستخدم عادة لتسلسل (حماية) الوصول إلى البيانات الإجمالية أو جزء من الشفرة. وقد تستخدم مهمة واحدة فقط في كل مرة القفل / السيمافور / العلم (الخاص بها).
◦ المهمة الأولى للحصول على قفل "يحدد" ذلك. يمكن بعدها لهذه المهمة الوصول إلى البيانات المحمية أو الشفرة بأمان (بشكل متسلسل).
◦ يمكن لمهام أخرى محاولة الحصول على القفل ولكن يجب الانتظار حتى المهمة التي تملك القفل الذي يحررها.
◦ يمكن أن يكون محظورا أو غير محظور
• عمليات الاتصالات المتزامنة - Synchronous communication operations
◦ لا تشمل سوى تلك المهام التي تنفذ عملية الاتصال
◦ عندما تؤدي إحدى المهام عملية الاتصال، يستلزم الأمر وجود شكل من التنسيق مع المهمة (المهام) الأخرى المشاركة في الاتصالات. على سبيل المثال، قبل أن تقوم مهمة بتنفيذ عملية إرسال، يجب أن تتلقى أولا إقرارا من مهمة الاستلام بالموافقة على إرسالها.
◦ تمت مناقشتها سابقا في قسم الاتصالات.
تبعيات البيانات - Data Dependencies
• تعريف:
• توجد تبعية بين تعليمات البرنامج عندما يؤثر ترتيب تنفيذ التعليمة على نتائج البرنامج.
• تنتج تبعية البيانات عن الاستخدامات المتعددة لنفس الموقع (المواقع) في التخزين بواسطة مهام مختلفة.
• تعتبر التبعيات مهمة للبرامج المتوازية لأنها واحدة من المثبطات الأولية للتوازي.
• أمثلة:
• تبعية البيانات في حلقات التكرار - Loop carried data dependence
DO J = MYSTART,MYEND
A(J) = A(J-1) * 2.0
END DO
يجب حساب قيمة A (J-1) قبل قيمة A (J)، وبالتالي فإن A (J) تعرض تبعية البيانات على A (J-1). نقول أن التوازي مثبَّط.
إذا كانت المهمة 2 تحتوي على A(J) والمهمة 1 لها A (J-1)، فإن حساب القيمة الصحيحة لـ A (J) يستلزم ما يلي:
• بنية الذاكرة الموزعة - يجب أن تحصل المهمة 2 على قيمة A (J-1) من المهمة 1 بعد انتهاء المهمة 1 من حسابها
• بنية الذاكرة المشتركة – يجب على المهمة 2 أن تقرأ A (J-1) بعد تحديثها من طرف المهمة 1
task 1 task 2
------ ------
X = 2 X = 4
. .
. .
Y = X**2 Y = X**3
كما هو الحال في المثال السابق، يتم تثبيط التوازي. وتعتمد قيمة Y على:
• بنية الذاكرة الموزعة - إذا أو عندما تتصل قيمة X بين المهام.
• بنية الذاكرة المشتركة - المهمة التي يخزن الماضي قيمة X.
• على الرغم من أن جميع تبعيات البيانات مهمة لتحديد متى يتم تصميم البرامج المتوازية، إلا أن التبعيات في حلقات التكرار ذات أهمية خاصة لأن الحلقات هي ربما الهدف الأكثر شيوعا في جهود الموازاة.
• كيفية التعامل مع تبعيات البيانات:
• بنيات الذاكرة الموزعة - توصيل البيانات المطلوبة في نقاط التزامن.
• بنيات الذاكرة المشتركة – مزامنة عمليات القراءة/الكتابة بين المهام.
موازنة التحميل - Load Balancing
• تشير موازنة التحميل إلى ممارسة توزيع كميات متساوية تقريبا من العمل بين المهام بحيث تبقى جميع المهام مشغولة في كل وقت. ويمكن اعتباره تقليلا من وقت خمول المهمة.
• تعتبر موازنة التحميل مهمة للبرامج المتوازية لأسباب تتعلق بالأداء.على سبيل المثال، إذا كانت جميع المهام تخضع لنقطة تزامن الحاجز، فإن أبطأ مهمة تحدد الأداء العام.
 |
 |
• كيفية تحقيق موازنة التحميل:
• جزئ العمل الذي تتلقاه كل مهمة بالتساوي
◦ بالنسبة لمصفوفة العمليات حيث تؤدي كل مهمة عمل مماثل، قم بتوزيع مجموعة من البيانات بين المهام بالتساوي.
◦ بالنسبة لتكرار الحلقة حيث يتم إنجاز العمل في كل تكرار مماثل، قم بتوزيع التكرارات عبر المهام بالتساوي.
◦ إذا تم استخدام مزيج غير متجانس من الأجهزة ذات خصائص أداء مختلفة، تأكد من استخدام بعض من أنواع أدوات تحليل الأداء للكشف عن أي اختلالات في التحميل. واضبط العمل وفقا لذلك.
• استخدم إسناد العمل الديناميكي
◦ تؤدي بعض فئات المشاكل إلى اختلالات في التحميل حتى لو كانت البيانات موزعة بالتساوي بين المهام:
محاكاة N -body – قد تهاجر الجسيمات عبر نطاقات المهام التي تتطلب المزيد من العمل لبعض المهام.
أساليب الشبكة التكيفية – قد تحتاج بعض المهام إلى تهذيب شبكتها حينما لا يقوم البعض الآخر بذلك.
المصفوفات غير الكثيفة - بعض المهام لديها بيانات فعلية للعمل عليها حينما يكون البعض الآخر في الغالب "مجرد أصفار".
◦ عندما يكون مقدار العمل الذي ستؤديه كل مهمة متغيرا عن قصد أو غير قادر على التنبؤ به، فقد يكون من المفيد استخدام نهج تجمع المهام المجدول (scheduler-task pool). عندما تُنهي كل مهمة عملها، فإنها تتلقى قطعة جديدة من قائمة انتظار العمل.
◦ في نهاية المطاف، قد يصبح من الضروري تصميم خوارزمية تكشف وتتعامل مع اختلالات التحميل لأنها تحدث ديناميكيا داخل الشفرة.
الحبوبية - Granularity
• معدل الاتصالات /الحوسبة - Computation / Communication Ratio :
• في الحوسبة المتوازية، تعتبر الحبوبية مقياسا نوعيا لمعدل الحساب في الاتصالات.
• عادة ما يتم فصل فترات الحساب عن فترات الاتصالات بواسطة أحداث التزامن.
• توازي الحَب-الدقيق - Fine-grain Parallelism :
• يتم إنجاز كميات صغيرة نسبيا من العمل الحسابي بين أحداث الاتصالات
• حوسبة منخفضة إلى مقدار الاتصالات
• يسهل موازنة التحميل
• يدل على كلفة الاتصالات وفرص قليلة لتحسين الأداء
• إذا كانت الحبوبية دقيقة جدا فمن الممكن أن الكلفة المطلوبة للاتصالات والتزامن بين المهام سيستغرق وقتا أطول من الحساب.
• توازي الحَب- الخشن - Coarse-grain Parallelism :
• يتم إنجاز كميات كبيرة نسبيا من العمل الحسابي بين أحداث الاتصالات/المزامنة
• حساب مرتفع إلى مقدار نسبة الاتصالات
• يدل على المزيد من الفرص لزيادة الأداء
• تحميل الموازنة بكفاءة يكون أصعب
ما هو الأفضل؟
• تعتمد الحبوبية الأكثر كفاءة على الخوارزمية وبيئة الأجهزة التي تعمل فيها.
• في معظم الحالات تكون التكلفة المرتبطة بالاتصالات والتزامن عالية بالنسبة لسرعة التنفيذ، ولذلك فمن المفيد أن تكون لها حبوبية خشنة.
• يمكن أن يساعد توازي الحب-الدقيق على خفض الفوقانيات بسبب تحمبل الموازنة.
I / O (إدخال/إخراج)
الأخبار السيئة:
• تعتبر عمليات الإدخال/الإخراج (I/O) عموما مثبطات للتوازي.
• تتطلب عمليات الإدخال/الإخراج أوامر بحجم أكبر من عمليات الذاكرة.
• قد تكون أنظمة الإدخال/الإخراج المتوازية غير ناضجة أو غير متاحة لجميع الأنظمة الأساسية.
• في بيئة حيث تدرك كافة المهام نفس مساحة الملف، يمكن أن تؤدي عمليات الكتابة إلى الكتابة فوق الملف.
• يمكن أن تتأثر عمليات القراءة بقدرة خادم الملفات على التعامل مع طلبات القراءة المتعددة في نفس الوقت.
• الإدخال/الإخراج الذي يجب إجراؤه عبر الشبكة (NFS، غير محلية) يمكن أن يتسبب في اختناقات شديدة وقد يسبب حتى في تعطيب خوادم الملفات.
الأخبار الجيدة:
• أنظمة الملفات المتوازية متاحة. فمثلا:
◦ GPFS: النظام العام للملفات المتوازية (IBM). يسمى حاليا مقياس طيف IBM.
◦ Lustre: لعناقيد لينكس ( Intel)
◦ HDFS نظام الملفات الموزعة Hadoop (Apache)
◦ PanFS: نظام الملفات ActiveScale Panasas لعناقيد لينكس (Panasas ، Inc.)
◦ وللمزيد – انظر http://en.wikipedia.org/wiki/List_of_file_systems#Distributed_parallel_file_systems
• قد أصبح تخصص برمجة الإدخال/الإخراج المتوازية لـ MPI متاحة منذ عام 1996 كجزء من MPI-2. وأصبحت عمليات تنفيذ الحرة والخاصة بالموردين متاحة بشكل شائع.
• بعض الإرشادات:
◦ القاعدة رقم 1: قلل الإدخال/الإخراج الإجمالي قدر الإمكان
◦ إذا كان لديك الوصول إلى نظام ملفات متوازية، استخدمه.
◦ كتابة أجزاء كبيرة من البيانات بدلا من قطع صغيرة وعادة ما تكون أكثر كفاءة بكثير.
◦ ملفات أقل وأكبر أداء أفضل من العديد من الملفات الصغيرة.
◦ احجز الإدخال/الإخراج في أجزاء تسلسلية محددة من الوظيفة، ثم استخدم الاتصالات المتوازية لتوزيع البيانات على المهام المتوازية.على سبيل المثال، يمكن للمهمة 1 قراءة ملف إدخال ثم بعدها توصل البيانات المطلوبة إلى مهام أخرى.وبالمثل، يمكن للمهمة 1 إجراء عملية الكتابة بعد تلقي البيانات المطلوبة من جميع المهام الأخرى.
◦ عمليات الإدخال/الإخراج الإجمالية عبر المهام - بدلا من تنفيذ العديد من مهام الإدخال/الإخراج، تؤدي مجموعة فرعية من المهام.
التصحيح - Debugging
• يكون من الصعب تصحيح الشفرات المتوازية بشكل لا يصدق، لا سيما الشفرات ذات المستوى الصاعد.
• الخبر السار هو أن هناك بعض المصححات الممتازة المتاحة للمساعدة:
• pthreads و OpenMPمخيطة
• MPI
• GPU / مسرع
• Hybrid
• يمتلك مستخدمو حوسبة ليفرمور الوصول إلى العديد من أدوات التصحيح المتوازية المثبتة على عناقيد LC:
• TotalView من RogueWave للبرمجيات
• DDT من Allinea
• Inspector من Intel
• أداة تحليل التتبع المكدس (STAT)- مطورة محليا
• كل هذه الأدوات لديها منحنى تعلم مرتبط بها - أكثر من غيرها.
• للحصول على تفاصيل ومعلومات للبدء، راجع:
◦ صفحات ويب LC في https://hpc.llnl.gov/software/development-environment-software
◦ برنامج TotalView التعليمي: https://computing.llnl.gov/tutorials/totalview/
ضبط وتحليل الأداء - Performance Analysis and Tuning
• كما هو الحال مع التصحيح، يمكن للتحليل و ضبط أداء البرنامج المتوازي أن يكون أكثر صعوبة بكثير من البرامج التسلسلية.
• لحسن الحظ، هناك عدد من الأدوات الممتازة لتحليل أداء البرنامج المتوازي وضبطه.
• لدى مستخدمو حوسبة ليفرمور امكانية الوصول إلى العديد من هذه الأدوات، ومعظمها متاح في جميع عناقيد الإنتاج.
• بعض نقاط البدء للأدوات المثبتة على أنظمة LC:
◦ صفحات ويب LC في https://hpc.llnl.gov/software/development-environment-software
◦ TAU : http://www.cs.uoregon.edu/research/tau/docs.php
◦ HPCToolkit :http://hpctoolkit.org/documentation.html
◦ Open|Speedshop : http://www.openspeedshop.org/
◦ Vampir / Vampirtrace : http://vampir.eu/
◦ Valgrind :http://valgrind.org/
◦ PAPI :http://icl.cs.utk.edu/papi/
◦ Mpitrace : https://computing.llnl.gov/tutorials/bgq/index.html#mpitrace
◦ mpiP :http://mpip.sourceforge.net/
◦ MemP : http://memp.sourceforge.net/
أمثلة متوازية
معالجة المصفوفة - Array Processing
• يوضح المثال التالي الحسابات على عناصر مصفوفة ثنائية الأبعاد. يتم تقييم الدالة في كل عنصر من المصفوفة.
• الحساب على كل عنصر من المصفوفة مستقل عن العناصر الأخرى للمصفوفة.
• المشكلة مكثفة حسابيا.
• يحسب البرنامج التسلسلي عنصرا واحدا في وقت واحد ضمن ترتيب تسلسلي.
• يمكن أن تكون الشفرة التسلسلية على الشكل التالي:
• أسئلة يجب طرحها
• هل هذه المشكلة قادرة على أن تكون متوازية؟
• كيف يمكن تقسيم المشكلة؟
• هل تحتاج إلى اتصالات؟
• هل هناك أي تبعيات للبيانات؟
• هل هناك حاجة إلى التزامن؟
• هل تكون موازنة التحميل مصدر قلق؟
معالجة المصفوفة - Array Processing
الحل المتوازي 1
• حساب العناصر المستقلة عن بعضها البعض - يؤدي إلى حل متوازي محرج.
• يتم توزيع عناصر المصفوفات بالتساوي بحيث تمتلك كل عملية جزء من المصفوفة (مصفوفة فرعية).
◦ يتم اختيار مخطط التوزيع للوصول إلى الذاكرة بكفاءة.على سبيل المثال خطوة واسعة لوحدة (خطوة واسعة لـ 1) عبر المصفوفات الفرعية. تزيد خطوة وحدة من استخدام المخبأة/الذاكرة.
◦ بما أنه من المرغوب فيه الحصول على خطوة وحدة من خلال مصفوفة فرعية، فإن اختيار مخطط التوزيع يعتمد على لغة البرمجة. للمزيد من الخيارات، راجع بلوك - الرسم البياني للتوزيعات الدوريةبلوك - مخطط توزيعات دورية.
• يضمن الحساب المستقل من عناصر المصفوفة عدم الحاجة للاتصال أو التزامن بين المهام.
• بما أن كمية العمل موزعة بالتساوي عبر العمليات، فلا ينبغي أن تكون هناك مخاوف تتعلق بموازنة التحميل.
• بعد توزيع المصفوفة ، تنفذ كل مهمة جزء من حلقة تكرار المقابلة للبيانات التي تمتلكها.
على سبيل المثال، تظهر توزيعات فورتران (عمود - رئيسي) وC (صف - رئيسي):
do j = mystart, myend
do i = 1, n
a(i,j) = fcn(i,j)
end do
end do
for i (i = mystart; i <myend; i++) {
for j (j = 0; j < n; j++) {
a(i,j) = fcn(i,j);
}
}
• لاحظ أن متغيرات الحلقة الخارجية فقط تختلف عن الحل التسلسلي.
• أحد الحلول المحتملة:
• عملية تنفيذ كنموذج بيانات متعددة برنامج واحد (SPMD) - كل مهمة تنفذ نفس البرنامج.
• تهيئ العملية الرئيسية المصفوفة، وترسل المعلومات إلى العمليات العاملة وتتلقى النتائج.
• تتلقى العملية العاملة معلومات، وتنفذ حصتها من الحساب وترسل النتائج إلى الرئيسة.
• باستخدام مخطط تخزين فورتران، يكون أداء توزيع المصفوفة أكثر ذكاء.
• حل الشفرة المستعارة: المميزة باللون الأحمرتتغير للتوازي.
find out if I am MASTER or WORKER
if I am MASTER
initialize the array
send each WORKER info on part of array it owns
send each WORKER its portion of initial array
receive from each WORKER results
else if I am WORKER
receive from MASTER info on part of array I own
receive from MASTER my portion of initial array
# حساب نصيبي من المصفوفة
do j = my first column,my last column
do i = 1,n
a(i,j) = fcn(i,j)
end do
end do
send MASTER results
endif
• أمثلة البرامج:
• برنامج MPI في C: https://computing.llnl.gov/tutorials/mpi/samples/C/mpi_array.c
• برنامج MPI في فورتران: https://computing.llnl.gov/tutorials/mpi/samples/Fortran/mpi_array.f
معالجة المصفوفة
الحل المتوازي 2: تجمع المهام (Pool of Tasks)
• أظهر حل المصفوفة السابق موازنة تحميل ثابتة:
◦ كل مهمة لديها كمية ثابتة من العمل للقيام بها
◦ قد يكون وقت الخمول كبيرا للمعالجات الأسرع أو الأكثر خفة في التحميل – تحدد المهام الأبطأ الأداء العام.
• لا تعد موازنة التحميل الثابتة عادة مصدر قلق كبير إذا كانت جميع المهام تؤدي نفس كمية العمل على أجهزة مماثلة.
• إذا كانت لديك مشكلة في موازنة التحميل (بعض المهام تعمل بشكل أسرع من غيرها)، يمكنك الاستفادة من استخدام نخطط "تجمع المهام".
• مخطط تجمع المهام - Pool of Tasks Scheme :
• يتم استخدام عمليتان
عملية رئيسية:
◦ تحتضن تجمع المهام للعمليات العاملة للقيام بها
◦ يرسل العامل المهمة عند طلبها
◦ تجمع النتائج من العمليات العاملة
عملية عاملة: تفعل ما يلي مرارا وتكرارا
◦ تحصل على مهمة من العملية الرئيسية
◦ تنفذ الحساب
◦ ترسل النتائج إلى العملية الرئيسية
• لا تعرف العمليات العاملة قبليا وقت تشغيل أي جزء من المصفوفة التي سوف يتعاملن معها أو كمية المهام التي سوف يقمن بأدائها.
• تحدث موازنة التحميل الديناميكي في وقت التشغيل: تحصل المهام الأسرع على المزيد من العمل للقيام به.
• حل الشفرة المستعارة: الشفرة باللون الأحمر تتغير للتوازي.
find out if I am MASTER or WORKER
if I am MASTER
do until no more jobs
if request send to WORKER next job
else receive results from WORKER
end do
else if I am WORKER
do until no more jobs
request job from MASTER
receive from MASTER next job
calculate array element: a(i,j) = fcn(i,j)
send results to MASTER
end do
endif
• مناقشة:
• في مثال تجمع المهام أعلاه، تحسب كل مهمة عنصر مصفوفة فردية كمهمة. وتكون الحوسبة إلى مقدار الاتصالات ذات حبوبية دقيقة.
• تحمل حلول الحبوبية الدقيقة المزيد من الاتصالات العامة من أجل تقليل وقت خمول مهمة.
• قد يكون الحل الأمثل هو توزيع المزيد من العمل لكل وظيفة. والكمية "الصحيحة" من العمل هي المشكلة المعتمدة.
حساب PI
• يمكن حساب قيمة PI بطرق مختلفة. إذا اعتبرنا طريقة مونتي كارلو (Monte Carlo) لتقريب : PI
◦ إدراج دائرة بنصف قطر r في مربع بطول 2r
◦ مساحة الدائرة هي Πr 2 ومساحة المربع 4r 2
◦ نسبة مساحة الدائرة من مساحة المربع هي:
Πr 2 / 4r 2 = Π / 4
◦ إذا كنت تولد عشوائيا N نقطة داخل المربع ، تقريبا
N * Π / 4من تلك النقاط ( M ) يجب أن تقع داخل الدائرة.
◦ Π تقارب التالي:
N * Π / 4 = M
Π / 4 = M / N
Π = 4 * M / N
◦ لاحظ أن زيادة عدد النقاط يولد و يحسن التقريب.
• الشفرة المستعارة التسلسلية لهذا الإجراء:
npoints = 10000
circle_count = 0
do j = 1,npoints
generate 2 random numbers between 0 and 1
xcoordinate = random1
ycoordinate = random2
if (xcoordinate, ycoordinate) inside circle
then circle_count = circle_count + 1
end do
PI = 4.0*circle_count/npoints
• المشكلة مكثفة حسابيا - معظم الوقت ينفق في حلقة
• أسئلة يجب طرحها:
◦ هل هذه المشكلة قادرة على أن تكون متوازية؟
◦ كيف يمكن تقسيم المشكلة؟
◦ هل تحتاج الى الاتصالات؟
◦ هل هناك أي تبعيات للبيانات؟
◦ هل هناك حاجة إلى التزامن؟
◦ هل تكون موازنة التحميل مصدر قلق؟
حساب PI
الحل المتوازي
• مشكلة أخرى يسهل موازنتها:
◦ جميع حسابات النقطة مستقلة؛ لا توجد تبعيات للبيانات
◦ يمكن تقسيم العمل بالتساوي؛ لا مخاوف من تحميل التوازن
◦ لا حاجة للاتصال أو التزامن بين المهام
• الاستراتيجية الموازية:
◦ تقسيم الحلقة إلى أجزاء متساوية يمكن تنفيذها من قبل مجموعة من المهام
◦ تؤدي كل مهمة عملها بشكل مستقل
◦ يتم استخدام نموذج SPMD
◦ تتصرف مهمة واحدة كمهمة رئيسية لجمع النتائج وحساب قيمة PI
• حل الشفرة المستعارة: المميزة باللون الأحمر تتغير للتوازي.
npoints = 10000
circle_count = 0
p = number of tasks
num = npoints/p
find out if I am MASTER or WORKER
do j = 1,num
generate 2 random numbers between 0 and 1
xcoordinate = random1
ycoordinate = random2
if (xcoordinate, ycoordinate) inside circle
then circle_count = circle_count + 1
end do
if I am MASTER
receive from WORKERS their circle_counts
compute PI (use MASTER and WORKER calculations)
else if I am WORKER
send to MASTER circle_count
endif
• أمثلة البرامج:
• برنامج MPI في : C https://computing.llnl.gov/tutorials/mpi/samples/C/mpi_pi_reduce.c
• برنامج MPI في : Fortran https://computing.llnl.gov/tutorials/mpi/samples/Fortran/mpi_pi_reduce.f
المعادلة الحرارية البسيطة - Simple Heat Equation
• معظم المشاكل في الحوسبة المتوازية تتطلب التواصل بين المهام. وهناك عدد من المشاكل المشتركة تتطلب التواصل مع المهام المجاورة.
• تصف معادلة الحرارة 2-D تغير درجة الحرارة مع مرور الوقت، نظرا لتوزيع درجة الحرارة الأولية وظروف الحدود.
• يتم استخدام مخطط الفرق المحدود لحل معادلة الحرارة عدديا على منطقة مربعة.
◦ تمثل عناصر المصفوفة ثنائية الأبعاد درجة الحرارة عند النقاط على المربع.
◦ درجة الحرارة الأولية هي صفر على الحدود ومرتفعة في الوسط.
◦ تجرى درجة الحرارة الحدودية عند الصفر.
◦ يتم استخدام خوارزمية الوقت يخطو.
• لحساب العنصر يتم الاعتماد على قيم العنصر المجاورة:
• يحتوي البرنامج التسلسلي على شفرة مثل:
do iy = 2, ny - 1
do ix = 2, nx - 1
u2(ix, iy) = u1(ix, iy) +
cx * (u1(ix+1,iy) + u1(ix-1,iy) - 2.*u1(ix,iy)) +
cy * (u1(ix,iy+1) + u1(ix,iy-1) - 2.*u1(ix,iy))
end do
end do
• أسئلة يجب طرحها:
◦ هل هذه المشكلة قادرة على أن تكون متوازية؟
◦ كيف يمكن تقسيم المشكلة؟
◦ هل تحتاج الى الاتصالات؟
◦ هل هناك أي تبعيات للبيانات؟
◦ هل هناك حاجة إلى التزامن؟
◦ هل تكون موازنة التحميل مصدر قلق؟
المعادلة الحرارية البسيطة
الحل المتوازي
• هذه المشكلة أكثر صعوبة، حيث أن هناك تبعيات للبيانات، والتي تتطلب الاتصالات والتزامن.
• يتم تقسيم مصفوفة كاملة وتوزيعها على شكل مصفوفات فرعية لجميع المهام. كل مهمة تمتلك جزء متساو من مجموع المصفوفة.
• لأن كمية العمل متساوية، لا ينبغي أن يكون تحميلموازنة مصدر قلق
• تحديد تبعيات البيانات:
◦ العناصر الداخلية التي تنتمي إلى مهمة مستقلة عن المهام الأخرى
◦ تعتمد العناصر الحدودية على بيانات المهمة المجاورة، مما يستلزم التواصل.
• التنفيذ كنموذج: SPMD
◦ ترسل العملية الرئيسية المعلومات الأولية للعمليات العاملة، ثم تنتظر لجمع النتائج من جميع العاملات
◦ تحسب العمليات العاملة الحل ضمن عدد محدد من الخطوات الزمنية، وتتواصل عند الضرورة مع العمليات المجاورة
◦ حل الشفرة المستعارة: المميزة باللون الأحمر تتغير للتوازي.
find out if I am MASTER or WORKER
if I am MASTER
initialize array
send each WORKER starting info and subarray
receive results from each WORKER
else if I am WORKER
receive from MASTER starting info and subarray
# Perform time steps
do t = 1, nsteps
update time
send neighbors my border info
receive from neighbors their border info
update my portion of solution array
end do
send MASTER results
endif
• أمثلة البرامج:
• برنامج MPI في : C https://computing.llnl.gov/tutorials/mpi/samples/C/mpi_heat2D.c
• برنامج MPI في : Fortran https://computing.llnl.gov/tutorials/mpi/samples/Fortran/mpi_heat2D.f
معادلة الموجة 1-D – 1-D Wave Equation
• في هذا المثال، يتم حساب الاتساع على طول سلسلة موحدة، وتهتز بعد انقضاء فترة محددة من الزمن.
• ويشمل الحساب ما يلي:
◦ الاتساع على المحور y
◦ i كمؤشر موضع على طول المحور x
◦ نقاط العقدة المفروضة على طول السلسلة
◦ تحديث السعة في خطوات زمنية منفصلة.
• والمعادلة التي يتعين حلها هي معادلة الموجة أحادية البعد:
A(i,t+1) = (2.0 * A(i,t)) - A(i,t-1) + (c * (A(i-1,t) - (2.0 * A(i,t)) + A(i+1,t)))
حيث c ثابت
• لاحظ أن السعة ستعتمد على الجداول الزمنية السابقة (t, t-1) والنقاط المجاورة (i-1, i+1)
• أسئلة يجب طرحها:
◦ هل هذه المشكلة قادرة على أن تكون متوازية؟
◦ كيف يمكن تقسيم المشكلة؟
◦ هل تحتاج للاتصالات؟
◦ هل هناك أي تبعيات للبيانات؟
◦ هل هناك حاجة إلى التزامن؟
◦ هل تكون موازنة التحميل مصدر قلق؟
معادلة الموجة 1-D - 1-D Wave Equation
الحل المتوازي
• هذا مثال آخر عن مشكلة تتعلق بتبعيات البيانات. وسيتضمن الحل المتوازي كلا من الاتصالات والتزامن.
• يتم تقسيم مصفوفة السعة بأكملها وتوزيعها على أنها مصفوفات فرعية لجميع المهام. كل مهمة تمتلك جزءا متساويا من إجمالي المصفوفة.
• موازنة التحميل: تتطلب جميع النقاط عملا متساويا، لذلك يجب تقسيم النقاط بالتساوي
• من شأن تفكيك الكتلة أن يقسم العمل إلى عدد من المهام كقطع، مما يسمح لكل مهمة بتملك نقاط بيانات متجاورة في الغالب.
• تحتاج الاتصالات فقط ان تحدث على حدود البيانات. وكلما زاد حجم الكتلة كلما قل الاتصال على حدود البيانات.
• التنفيذ كنموذج :SPMD
◦ ترسل العملية الرئيسية المعلومات الأولية إلى العمليات العاملة، ثم تنتظر جمع النتائج من جميع العمليات العاملة
◦ تقوم العمليات العاملة بحساب الحل ضمن عدد محدد من الخطوات الزمنية، والتواصل عند الضرورة مع العمليات المجاورة
• حل الشفرة المستعارة: يدل اللون الأحمر على التغيرات للتوازي.
find out number of tasks and task identities
#Identify left and right neighbors
left_neighbor = mytaskid - 1
right_neighbor = mytaskid +1
if mytaskid = first then left_neigbor = last
if mytaskid = last then right_neighbor = first
find out if I am MASTER or WORKER
if I am MASTER
initialize array
send each WORKER starting info and subarray
else if I am WORKER`
receive starting info and subarray from MASTER
endif
#Perform time steps
#In this example the master participates in calculations
do t = 1, nsteps
send left endpoint to left neighbor
receive left endpoint from right neighbor
send right endpoint to right neighbor
receive right endpoint from left neighbor
#Update points along line
do i = 1, npoints
newval(i) = (2.0 * values(i)) - oldval(i)
+ (sqtau * (values(i-1) - (2.0 * values(i)) + values(i+1)))
end do
end do
#Collect results and write to file
if I am MASTER
receive results from each WORKER
write results to file
else if I am WORKER
send results to MASTER
endif
• أمثلة البرامج:
• برنامج MPI في C: https://computing.llnl.gov/tutorials/mpi/samples/C/mpi_wave.c
• برنامج MPI في Fortran: https://computing.llnl.gov/tutorials/mpi/samples/Fortran/mpi_wave.f
هذا يكون البرنامج التعليمي قد اكتمل.
يرجى إكمال نموذج التقييم عبر الإنترنت
المراجع والمزيد من المعلومات
• الكاتب :بليز بارني (Blaise Barney)، حوسبة ليفرمور.
• سيؤدي بك البحث عن "البرمجة المتوازية" أو "الحوسبة المتوازية" على WWW إلى مجموعة واسعة من المعلومات.
• اقتراحات للقراءة:
◦ "تصميم وبناء برامج متوازية." إيان فوستر(Ian Foster) .
◦ " مدخل إلى الحوسبة المتوازية ." أنانث غراما (Ananth Grama)، أنشول غوبتا (Anshul Gupta)، جورج كاريبيس (George Karypis)، فيبين كومار (Vipin Kumar) .
◦ "نظرة عامة على الحواسيب الفائقة الأخيرة ." آج فان دير ستين (A.J. van der Steen)، جاك دونجارا (Jack Dongarra) .
• تم إنشاء الصور/الرسومات من قبل المؤلف، أو من قبل الموظفين الآخرين لـ LLNL ، أو تم الحصول عليها من غير حقوق طبع ونشر، أو من مصادر حكومية أو عامة (مثل http://commons.wikimedia.org/)، أو تم استخدامها بإذن من المؤلفين من عروض أخرى وصفحات ويب.
• التاريخ: تم تطوير هذه المواد من المصادر التالية، التي لم تعد محفوظة أو متاحة.
◦ برامج تعليمية موجودة في "ورشة البرمجة المتوازية SP" لمركزMaui High Performance Computing.
◦ برامج تعليمية موجودة في صفحة الويب "التعليم والتدريب" لمركز كورنيل ثوري (Cornell Theory).