حوسبة متوازية

الخلفية

عادة ما تكون البرامج الحاسوبية مكتوبة بطريقة تسلسلية. فلحل مشكلة ما، تُبنى وتطبق خوارزمية على شكل تعليمات متسلسلة. وتُنفذ هذه التعليمات على وحدة المعالجة المركزية لجهاز حاسوب واحد. حيث تنفذ تعليمة واحدة فقط في نفس الوقت، وبعدَ الانتهاء منها تُنفذ التعليمة التالية.
أما الحوسبة المتوازية فتستخدم في وَقت واحد عدة عناصر معالجة لحل مشكلة معينة. وتقسَّم المشكلة إلى أجزاء مستقلة بحيث يمكن لكل عنصر من عناصر المعالجة تنفيذ الجزء الخاص به من الخوارزمية في وقت واحد مع العناصر الأخرى. تتنوع العناصر المعالجة وتشمل موارد مختلفة مثل جهاز حاسوب واحد مع معالجات متعددة أو شبكة من عدة حواسيب أو معدات متخصصة أو أي مزيج مما ذكر.
كان رفعُ سرعة تنفيذ العمليات الهم الرئيسي لتحسين أداء الحواسيب منذ منتصف ثمانيات القرن العشرين وحتى عام 2004. حيث أن مدة تنفيذ برنامج تساوي عدد التعليمات مضروبًا في متوسط الوقت اللازم لتنفيذ تعليمة واحد. الحفاظ على كل شيء ثابتًا، وزيادة تردد الساعة الداخلية يخفض من متوسط الوقت المستغرق لتنفيذ تعليمة. وبالتالي يُقلل وقت التنفيذ لجميع البرامج ذات العمليات المحدودة.
يحسب استهلاك الشرائح للطاقة من خلال المعادلة P = C × V² × F،حيث ترمز P إلى الطاقة، وترمز C إلى عدد المكثفات المستعملة أثناء عمل دورة كاملة (تتناسب مع عدد الترانزستورات التي تتغير مدخلاتها)، وترمز V إلى الجهد، أما F فترمز إلى تردد المعالج (دورة في الثانية). وتزيد زيادة التردد من كمية الطاقة المستهلكة. أجبَرَت زيادة استهلاك المعالجات للطاقة في النهاية شركة إنتل في مايو 2004على إلغاء إنتاج معالجاتها تيجاس وجهوك، والتي تعتبر عمومًا نهاية سياسة رفع التردد كنموذج شائع لمعمارية الحواسيب.
على الرغم من قضايا استهلاك الطاقة إضافة للتنبؤات المتكررة عن نهايته، فإن قانون مور ظل صحيحًا. فقد نصَّ قانون مور (الناتج عن ملاحظة تجريبية) على أن كثافة الترانزستورات في المعالجات الدقيقة تتضاعف كل 18 إلى 24 شهرًا. وبنهاية سياسة زيادة التردد، فقد أمكن استخدام هذه الترانزستورات الإضافية (التي لم تعد تستخدم لرفع التردد) لإضافة أجهزة أخرى من أجل إجراء حوسبة متوازية.

توازي الحبيبات الناعمة والحبيبات الخشنة والمربك

غالبا ما تصنف التطبيقات وفقا لمدى حاجة المهام الفرعية للمزامنة أو التواصل مع بعضها البعض. يظهر التطبيق توازي الحبيبات الناعمة (بالإنجليزية: Fine-grained parallelism) إذا كانت المهام الفرعية تتواصل عدة مرات في الثانية الواحدة، أو توازي الحبيبات الخشنة (بالإنجليزية: Coarse-grained parallelism) إذا لم تتواصل عدة مرات في الثانية الواحدة، ويصنف بالتوزاي المربك (بالإنجليزية: Embarrassing parallelism) إذا كانت نادرا ما تضطر للتواصل أو لا يوجد تواصل إطلاقا. تعتبر التطبيقات من صنف التوازي المربك أسهل للموازاة.

نماذج تناسق

يجب أن يكون للغات البرمجة المتوازية ولأجهزة الحاسوب المتوازية نموذج تناسق (المعروف أيضا باسم نموذج الذاكرة). نموذج التناسق (بالإنجليزية: Consistency model) يحدد القواعد لكيفية حدوث العمليات في ذاكرة الحاسوب، وكيفية إنتاج النتائج.
واحد من نماذج التناسق هو نموذج "ليسلي لامبورت" للتناسق المتسلسل. التناسق المتسلسل هو خاصية للبرنامج المتوازي الذي ينتج عن تنفيذه بشكل متواز نفس النتائج إذا نفذ بشكل تسلسلي. بشكل أدق، يكون البرنامج متطابق تسلسليا إذا "... نتائج أي تنفيذ هي نفسها إذا ما نفذت كل العمليات على كل المعالجات بترتيب متسلسل ما، والعمليات في كل معالج تظهر في هذا التسلسل بالترتيب المحدد من قبل البرنامج".
ذاكرة معاملات البرنامج هي نوع شائع من نماذج التناسق. تستعمل ذاكرة معاملات البرنامج مفهوما، استعير من نظريات قواعد البيانات وتطبيقها، هو مفهوم المعاملات الموحدة (بالإنجليزية: Atomic transactions) في عملية الوصول إلى الذاكرة.
رياضيا، يمكن تمثيل هذه النماذج بعدة طرق. شبكة بيتري، الذي تم عرضها في أطروحة الدكتوراه لآدم كارل بيتري سنة 1962، كانت محاولة مبكرة لتدوين قواعد نماذج التناسق. بعدها تم بناء نظرية تدفق البيانات، وتم إنشاء هندسة تدفق البيانات كتطبيق عملي لفكرة نظرية تدفق البيانات. بدأت في أواخر سبعينات القرن العشرين، حيث تم تطوير جبر العمليات مثل حسابات أنظمة الاتصالات وعمليات الاتصال التسلسلية للسماح بالتفكير بشكل جبري حول نظم مكونة من عناصر متفاعلة. إضافات جديدة إلى عائلة جبر العمليات، مثل π-calculus الذي أضاف إمكانية التفكير في طبولوجيا ديناميكية. المنطق مثل Lamport's TLA+ والنماذج الرياضية مثل التعقب ومخططات الأحداث الفاعلة، طورت أيضا لوصف سلوك النظم المتنافسة.

التوازي على مستوى التعليمات

برنامج حاسوبي في جوهره وهو دفق من التعليمات التي ينفذها المعالج. يمكن إعادة ترتيب هذه التعليمات ودمجها في مجموعات يتم تنفيذها بالتوازي دون تغيير نتيجة هذا البرنامج. وهذا ما يسمى بالموازاة على مستوى التعليمات. تطور فكرة الموازاة على مستوى التعليمات هيمنة على هندسة الحاسبات من منتصف ثمانينات وحتى منتصف تسعينات القرن العشرين.
المعالجات الحديثة لديها خطوط أنابيب متعددة المراحل. كل مرحلة في خط الأنابيب توافق عملا مختلفا يقوم به المعالج على التعليمات في هذه المرحلة؛ المعالج الذي يحوي ن مرحلة في خط أنابيب يمكن أن ينجز حتى ن تعليمة مختلفة في مراحل مختلفة. وتعد المعالجات من نوع RISC مثال على المعالجات التي تعمل بنظام خطوط الأنابيب، وفي هذا النوع من المعالجات خمس مراحل: جلب التعليمة، وفك الشفرة، وتنفيذها، والوصول إلى الذاكرة، وكتابة النتائج. المعالج بنتيوم 4 له 35 مراحل في خط الأنابيب.
بالإضافة إلى الموازاة على مستوى التعليمات باستخدام خط الأنابيب، يمكن لبعض المعالجات معالجة أكثر من تعليمة في نفس الوقت. تعرف بالمعالجات سوبرسكيلر. تجمع التعليمات معا إذا لم يكن هناك أي تبعية في البيانات فيما بينها. تعد خوارزمية "سكوربوردنج" وخوارزمية "توماسلو" (التي تشبه سكوربوردنج ولكن تقوم بإعادة تسمية السجلات) من أكثر الأساليب شيوعا لتنفيذ التعليمات بدون ترتيب في تنفيذ الموازاة على مستوى التعليمة.

موازاة البيانات

موازاة البيانات هي عملية الموازاة المتأصلة في جمل التكرار في البرنامج، التي تركز على توزيع هذه البيانات عبر عقد الحوسبة المختلفة بحيث تتم معالجتها بشكل متواز. "غالبا ما تؤدي موازاة التكرار بصورة مماثلة (ليست بالضرورة مطابقة) إلى تسلسل العمليات أو المهام التي تؤدى على عناصر بيانات ذات هياكل كبيرة."  العديد من التطبيقات العلمية والهندسية تستعمل توازي البيانات.
الاعتمادية في حلقات التكرار هي اعتمادية حلقة تكرار على ناتج واحدة أو أكثر من حلقات التكرار السابقة لها. وهذه الاعتمادية في حلقات التكرار تمنع القيام بعمل توزيع لعمليات التكرار. على سبيل المثال، بالنظر إلى الكود التالي الذي يحسب بعض أعداد فيبوناتشي الأولى :
1 : PREV1  = 0
2: PREV2  = 1
4: do:
5: CUR  = PREV1 + PREV2
6 : PREV1  = PREV2
7 : PREV2  = CUR
8: while (CUR < 10)
لا يمكن توزيع هذا التكرار لان CUR يعتمد عليه PREV2 وPREV1، والتي يتم حسابها في كل حلقة تكرار. ولأن التكرار يعتمد في نتيجة على المرحلة السابقة، فلا يمكن أن يتم تنفيذها في نفس الوقت. وبتعاظم حجم مشكلة، يتعاظم مقدار توازي البيانات المتاحة عادة.

الذاكرة والاتصالات

تكون الذاكرة الرئيسية في أجهزة الحواسيب المتوازية إما ذاكرة مشتركة (تشترك جميع عناصر المعالجة في مساحة تخزينية واحدة) أو ذاكرة موزعة (التي يكون فيها لكل عنصر من عناصر التجهيز مساحة تخزينية محلية خاصة به). ومصطلح الذاكرة الموزعة يعني أن الذاكرة موزعة منطقيا، ولكن غالبا ما يعني أيضا أنها موزعة ماديا. الذاكرة المشتركة الموزعة والذاكرة الافتراضية تجمعان بين النهجين، حيث أن كل عنصر معالجة يملك ذاكرة محلية خاصة به وسبيلا للوصول إلى ذاكرة على معالجات غير المحلية. الوصول للذاكرة المحلية عادة ما يكون أسرع من الوصول إلى الذاكرة غير المحلية.
هندسة الحواسيب التي يكون فيها كل عنصر من الذاكرة الرئيسية متوفرا بنفس المدة والتدفق تعرف بالذاكرة موحدة الوصول (بالإنجليزية: Uniform Memory Access : UMA). لا يمكن أن يتحقق هذا إلا من خلال نظام ذاكرة مشتركة حيث لا وجود لتوزيع مادي للذاكرة. النظم التي ليس لديها هذه الخاصية تعرف بنظم الذاكرة غير موحدة الوصول (بالإنجليزية: Non-Uniform Memory Access - NUMA). نظم الذاكرة الموزعة هي ذاكرة غير موحدة الوصول.
تستفيد نظم الحاسوب من مخزن صغير وسريع بقرب من المعالج لتخزين مؤقت لنسخ من قيم الذاكرة. أما أنظمة الحواسيب المتوازية فتواجه صعوبات مع هذه المخازن التي قد تخزن القيمة نفسها في أكثر من مكان واحد، مع إمكانية تنفيذ غير صحيح للبرنامج. أجهزة الحاسوب هذه تتطلب نظام تخزين متناسق، والذي يتتبع القيم المخزنة مؤقتا ويعمل على تطهير إستراتيجيا لها، وبالتالي ضمان تنفيذ صحيح للبرنامج. قنوات التطفل هي واحدة من أكثر الطرق شيوعا لتتبع القيم التي يتم الوصول إليها (وبالتالي ينبغي تطهيرها). تصميم نظام تخزين متناسق عالي الكفاءة وكبير هي مشكلة صعبة للغاية في مجال هندسة الحواسيب. ونتيجة لذلك، فإن هندسة الحواسيب بذاكرة مشتركة لا تتناسب جيدا مع أنظمة الذاكرة الموزعة.
يمكن تنفيذ الاتصالات بين الذاكرة والمعالجات وفيما بين المعالجات باستعمال أجهزة بطرق متعددة، بما في ذلك عبر ذاكرة مشتركة أو عارضة تبديل (بالإنجليزية: Crossbar switch) أو  ناقل مشترك أو شبكة ربط لعدد لا يحصى من طبولوجيات بما في ذلك طبولوجيات الطوق والنجمة والشجرة، هايبر مكعب (بالإنجليزية: Hypercube)، هايبر مكعب ضخم (بالإنجليزية: Fat hypercube)؛ أي هايبر مكعب بأكثر من معالج في العقدة الواحدة، أو شبكة من ن-بعد.
تحتاج الحواسيب المتوازية (المبنية على أساس شبكات الربط) إلى نوع من التوجيه لتمكينها من تمرير الرسائل بين العقد التي لا علاقة مباشرة بينها.  من المرجح أن تكون الوسيلة المستخدمة للاتصال بين المعالجات هي التسلسل الهرمي في الأجهزة الكبيرة متعددة المعالجات.

فئات الحواسيب المتوازية

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

الحواسيب المتوازية المتخصصة

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

الحوسبة قابلة لإعادة التشكيل مع FPGA

الحوسبة القابلة لإعادة التشكيل هو استخدام مصفوفات البوابات المنطقية القابلة للبرمجة في الميدان (بالإنجليزية: Field-Programmable Gate Array-FPGA) كمعالج مشارك للأغراض العامة للحاسوب. FPGA في جوهره شريحة حاسوب يمكنها إعادة ربط نفسها لمهمة معينة.
يمكن برمجة FPGA بلغة وصف الأجهزة VHDL أو "فيريلوج". لكن البرمجة بهذه اللغات قد تكون مملة، لهذا تم إنشاء عدة لغات من فئة C to HDL كمحاولة لمحاكاة صياغة ودلالات لغة البرمجة سي، التي اعتاد عليها معظم المطورين. الأكثر شهرة بين لغات C to HDL هي Mitrion-C و Impulse C و DIME-C و Handel-C. كما يوجد مجموعات فرعية معينة من SystemC مبنية على أساس سي++ يمكن أن تستخدم أيضا لهذا الغرض.
قرار أي إم دي بفتح تكنولوجية هيبرترانسبورت للمطورين العاديين فتح المجال لتكنولوجيا لإعادة تشكيل الحوسبة عالية الأداء. وفقا إلى مايكل ر. دامور، الرئيس التنفيذي للعمليات في شركة DRC للحوسبة: "في الأول عندما كنا نسير نحو أي إم دي، وصفونا بسارقي المأخذ. والآن يسموننا بشركائهم".

التطبيقات الخاصة بالدوائر المتكاملة

انقسم نهج عدة تطبيقات من نوع أسيك (ASIC) في التعامل مع البرامج المتوازية.
لأن أسيك (وحسب التعريف) هو خاص بتطبيق معين، فإنه يمكن أن تطويره ليكون الأمثل لهذا التطبيق. وكنتيجة لتطبيق معين، فإن أسيك يميل للتفوق في الحوسبة لأغراض عامة. تصنع أسيك  بتقنية X-ray lithography. وهذه العملية تتطلب قناعا (قد يكون مكلفا للغاية). تكلفة قناع واحد يمكن أن تتجاوز مليون دولار أمريكي. (كلما كانت الترانزستورات أصغر للرقاقة المطلوبة، فإن تكلفة القناع تكون أكبر). وفي الوقت نفسه، يزيد على مر الزمن أداء الحوسبة لأغراض عامة (مثلما يصفها قانون مور) تميل للقضاء على هذه المكاسب في جيل أو جيلين للرقاقة. التكلفة الأولية العالية جعلت أسيك غير مجدية بالنسبة لمعظم تطبيقات الحوسبة المتوازية. ومع ذلك، فقد تم بناء بعضها. ومن الأمثلة على ذلك جهاز  RIKEN MDGRAPE-3 الذي يستخدم أسيك مخصصة لمحاكاة ديناميات الجزيئية.

المعالجات المتجهية

المعالج المتجهي (بالإنجليزية: Vector processor) هو وحدة معالجة مركزية أو حاسوب يمكنه تنفيذ نفس التعليمات على مجموعات كبيرة من البيانات. "للمعالجات المتجهية مستوى عمليات رفيع للعمل على المصفوفات الخطية من الأرقام أو المتجهات. من الأمثلة على العمليات على المتجهات A = B × C، حيث A و B و C متجهات من 64 عنصر لكل منها وأعداد حقيقية 64بت"   ولهذا صلة وثيقة هي  بتصنيف في فلين تعليمة واحدة على بيانات كثيرة.
ما بين سبعينيات وثمانينيات القرن العشرين، أصبحت شركة كراي مشهورة بحواسيبها متجهية المعالجة. ومع ذلك، فإن المعالجات المتجهية مثلها مثل وحدات المعالجة المركزية وأنظمة الحواسيب الكاملة اختفت عموما. مجموعات تعليمات المعالجات الحديثة تشمل بعض التعليمات لمعالجة المتجهات مثلما هو الشأن مع AltiVec و SSE.

لغات البرمجة المتوازية

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

الموازاة التلقائية

استحداث موازاة تلقائيا لبرنامج متسلسل يقوم بها برنامج ترجمة (مترجم-Compiler) هي قمة الحوسبة المتوازية. ورغم مرور عقود من عمل الباحثين على المترجمات، إلا أن الحصول على موازاة تلقائيا سجلت نجاح محدود فقط.
المذهب الأساسي في لغات البرمجة المتوازية يبقى إما توازي صريح أو (في أحسن الأحوال) ضمني جزئيا، حيث يعطي المبرمج التوجيهات للمترجم بالموازاة. يوجد عدد قليل من لغات البرمجة المتوازية ضمنيا، مثل "السيزال"   و"برلال هاسكل"، و(من أجل FPGA) يستعمل Mitrion-C.

برمجيات التدقيق والفحص

الحاسوب الأكبر حجما والأكثر تعقيدا هو الأكثر تعرضا للخطأ والفترة الزمنية المتوسطة بين الإخفاقات فيه هي الأقصر. برمجيات التدقيق والفحص تقنية بموجبها يقوم نظام الحاسوب بأخذ صورة عن حالة برنامج (تسجيل عن كل الموارد الحالية المحجوزة والحالات المتغيرة)، وهي أقرب إلى تفريغ. هذه المعلومات يمكن استخدامها لاستعادة البرنامج في حال فشل الحاسوب. التدقيق والفحص يعني أن البرنامج يعاد تشغيله من آخر نقطة تدقيق فقط وليس من البداية. لتطبيق قد يعمل للأشهر فإن الأمر بالغ الأهمية. يمكن استخدام برمجيات التدقيق والفحص  لتسهيل عملية الهجرة.

تاريخ

أصول التوازي الصحيح (عمليات مختلفة على بيانات مختلفة-MIMD) يعود إلى لويجي فيديريكو، كونت Menabrea  وما قدمه في "وصف مقتضب للمحرك التحليلي الذي اخترعه تشارلز باباج. أدخلت شركة آي بي إم حاسوب 704 في عام 1954، من خلال المشروع الذي كان جين أمدال أحد المهندسين الرئيسيين فيه. ليصبح أول حاسوب تجاري متاح لاستخدام  مجموعة كاملة من الأوامر الحسابية بطريقة تلقائية.
في أبريل 1958، ناقش س. جيل (فيرانتي) البرمجة المتوازية، والحاجة إلى التفرع والانتظار. في عام 1958، ناقش الباحثان جون كوك ودانيال سلوتنيك (العاملين في شركة آي بي إم) استخدام التوازي في العمليات الحسابية العددية للمرة الأولى. أدرجت شركة بوروز (بالإنجليزية: Burroughs Corporation) معالج D825 في سنة 1962، وهو معالج حواسيب رباعي يمكنه الوصول إلى 16 وحدات ذاكرة من خلال العارضة التبديل  في عام 1967، نشر سلوتنيك وأمدال نقاشا حول جدوى المعالجة المتوازية في مؤتمر جمعيات الاتحاد الأمريكي للمعالجة المعلومات. ومن خلال هذه المناقشة صيغ قانون أمدال لتحديد الحد الأقصى للسرعة المكتسبة من عملية الموازاة.
في عام 1969، قدمت الشركة الأمريكية هونيويل نظامها الأول  مالتيكس، وهو نظام متعدد المعالجات المتماثلة قادر على تشغيل ما يصل إلى ثمانية معالجات بالتوازي. مشروع C.mmp في سبعينيات القرن العشرين التابع لجامعة كارنيجي ميلون هو أول متعدد المعالجات بمعالجات قليلة". "إن أول ناقل لوصل عدة معالجات مع مخابئ التطفل (بالإنجليزية: Snooping caches) هو  Synapse N+1 كان ذلك في عام 1984." 
ويمكن إرجاع الحواسيب المتوازية (تعليمة واحدة على بيانات مختلفة) إلى سبعينيات القرن العشرين. كان الدافع وراء هذا النوع من الحواسيب في وقت مبكر هو توزيع تأخير بوابة التحكم لوحدة المعالجة على تعليمات متعددة. في عام 1964، اقترح "سلوتنيك" بناء حاسوب متوازية على نطاق واسع لمختبر لورانس ليفرمور الوطني. موّل التصميم، الذي كان من أوائل الحواسيب المتوازية، من قبل سلاح الجو الأمريكي، وسمي "ILLIAC 4". المفتاح في تصميمه كان التوازي العالي نوعا ما، مع ما يصل إلى 256 معالج، والتي تسمح للآلة بالعمل على مجموعات كبيرة من البيانات في ما عرف لاحقا بالمعالجة المتجهية. ومع ذلك، 4 ILLIAC سمي "أكثر الحواسيب العملاقة المجهولة"، وذلك لأن المشروع لم يكن سوى أحد الأربعة اكتمالا، ولكن استغرق 11 سنوات، وتكلفة فاقت أربع مرات تقريبا عن التقديرات الأصلية. وأخيرا عندما صار على استعداد للتشغيل الحقيقي في التطبيق الأول في عام 1976، كانت قد تفوقت عليه حواسيب عملاقة تجارية مثل كراي 1.