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

📅 آخر تحديث: ١٧ يوليو ٢٠٢٦
✍️ نُشر في: ١٧ يوليو ٢٠٢٦
الموسوعة الحرة

يشير التوازي التلقائي ، أو التوازي التلقائي ، إلى تحويل التعليمات البرمجية المتسلسلة إلى تعليمات برمجية متعددة الخيوط و/أو متجهة ، وذلك لاستخدامها في وقت واحد على معالجات متعددة في جهاز متعدد المعالجات ذي ذاكرة مشتركة ( SMP ). [ 1 ] يُعدّ التوازي التلقائي الكامل للبرامج المتسلسلة تحديًا، لأنه يتطلب تحليلًا معقدًا للبرنامج ، وقد يعتمد أفضل نهج على قيم معلمات غير معروفة وقت الترجمة. [ 2 ]

تُعدّ الحلقات من أهمّ هياكل التحكم البرمجية التي يُركّز عليها التوازي التلقائي ، لأنّ معظم وقت تنفيذ البرنامج يتمّ داخل حلقة ما. يوجد منهجان رئيسيان لتوازي الحلقات: تعدد الخيوط المتسلسل وتعدد الخيوط الدوري. [ 3 ] على سبيل المثال، لنفترض حلقة تُطبّق في كلّ تكرار مئة عملية، وتستمرّ لألف تكرار. يمكن اعتبارها شبكةً من 100 عمود و1000 صف، أي ما مجموعه 100,000 عملية. يُخصّص تعدد الخيوط الدوري كلّ صفّ لخيط مختلف، بينما يُخصّص تعدد الخيوط المتسلسل كلّ عمود لخيط مختلف.

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

تحليل

هذه هي المرحلة الأولى حيث يقوم الماسح الضوئي بقراءة ملفات المصدر المدخلة لتحديد جميع الاستخدامات الثابتة والخارجية. يتم فحص كل سطر في الملف مقابل أنماط محددة مسبقًا لفصله إلى رموز . تُخزن هذه الرموز في ملف يستخدمه محرك القواعد النحوية لاحقًا. يتحقق محرك القواعد النحوية من أنماط الرموز التي تتطابق مع قواعد محددة مسبقًا لتحديد المتغيرات والحلقات وعبارات التحكم والدوال وما إلى ذلك في الكود.

تحليل

يُستخدم المحلل لتحديد أجزاء التعليمات البرمجية التي يمكن تنفيذها بالتزامن. ويعتمد المحلل على معلومات البيانات الثابتة التي يوفرها الماسح الضوئي-المحلل. يبدأ المحلل بالعثور على جميع الدوال المستقلة تمامًا ويصنفها كمهام فردية. ثم يحدد المهام التي تعتمد على بعضها البعض.

جدول

سيقوم المجدول بإدراج جميع المهام وعلاقات التبعية بينها من حيث أوقات التنفيذ والبدء. وسيقوم المجدول بإنتاج الجدول الأمثل من حيث عدد المعالجات المستخدمة أو إجمالي وقت تنفيذ التطبيق.

توليد الكود

سيقوم المجدول بإنشاء قائمة بجميع المهام وتفاصيل النوى التي ستُنفذ عليها ، بالإضافة إلى مدة تنفيذها. وسيقوم مُولِّد الشفرة بإدراج بنيات خاصة في الشفرة، يقرأها المجدول أثناء التنفيذ. وستُحدد هذه البنيات للمجدول النواة التي ستُنفذ عليها كل مهمة، بالإضافة إلى وقتي البدء والانتهاء.

تعدد الخيوط الدوري

يحاول المترجم المتوازي متعدد الخيوط الدوري تقسيم الحلقة بحيث يمكن تنفيذ كل تكرار على معالج منفصل في وقت واحد.

تحليل التوازي في المترجم

يقوم المترجم عادةً بإجراء عمليتي تحليل قبل التوازي الفعلي لتحديد ما يلي:

  • هل من الآمن تنفيذ الحلقة بالتوازي؟ تتطلب الإجابة على هذا السؤال تحليلًا دقيقًا للتبعيات وتحليلًا للأسماء المستعارة.
  • هل من المجدي موازاته؟ تتطلب هذه الإجابة تقديرًا موثوقًا (نمذجة) لعبء عمل البرنامج وقدرة النظام المتوازي.

تُجري المرحلة الأولى من المُصرّف تحليلًا لاعتمادية البيانات في الحلقة لتحديد ما إذا كان بالإمكان تنفيذ كل تكرار من تكرارات الحلقة بشكل مستقل عن التكرارات الأخرى. يمكن أحيانًا التعامل مع اعتمادية البيانات، ولكن قد يُؤدي ذلك إلى تكاليف إضافية في شكل تمرير الرسائل ، أو مزامنة الذاكرة المشتركة ، أو أي طريقة أخرى للتواصل بين المعالجات.

تحاول المرحلة الثانية تبرير جهد التوازي من خلال مقارنة وقت التنفيذ النظري للبرنامج بعد التوازي بوقت تنفيذه التسلسلي. وعلى عكس المتوقع، لا يستفيد البرنامج دائمًا من التنفيذ المتوازي. فالعبء الإضافي المصاحب لاستخدام معالجات متعددة قد يقلل من التسارع المحتمل للبرنامج المتوازي.

مثال

تُسمى الحلقة DOALL إذا كان من الممكن تنفيذ جميع تكراراتها، في أي استدعاء معين، بشكل متزامن.

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

كرر من i = 1 إلى n ، ثم اجعل z ( i ) = x ( i ) + y ( i ) نهاية التكرار

توجد العديد من المشكلات المتوازية التي تتضمن حلقات DOALL. على سبيل المثال، عند عرض فيلم بتقنية تتبع الأشعة، يمكن عرض كل إطار من الفيلم بشكل مستقل، ويمكن عرض كل بكسل من إطار واحد بشكل مستقل أيضًا.

من ناحية أخرى، لا يمكن تنفيذ الكود التالي بالتوازي التلقائي، لأن قيمة z(i)تعتمد على نتيجة التكرار السابق z(i - 1).

كرر من i = 2 إلى n ، ثم اجعل z ( i ) = z ( i - 1 ) * 2 .

هذا لا يعني أن الكود لا يمكن تنفيذه بالتوازي. في الواقع، إنه مكافئ لحلقة DOALL.

كرر من i = 2 إلى n ، ثم z ( i ) = z ( 1 ) * 2 ** ( i - 1 ) انتهى التكرار

ومع ذلك، فإن المترجمات المتوازية الحالية ليست قادرة عادة على إظهار هذه التوازيات تلقائيًا، ومن المشكوك فيه ما إذا كان هذا الكود سيستفيد من التوازي في المقام الأول.

المعالجة المتعددة المتوازية

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

هناك العديد من المشاكل المتوازية بشكل مُرضٍ والتي تحتوي على كتل برمجية مستقلة نسبيًا، وخاصة الأنظمة التي تستخدم الأنابيب والمرشحات .

على سبيل المثال، عند إنتاج بث تلفزيوني مباشر، يجب تنفيذ المهام التالية عدة مرات في الثانية:

  1. قراءة إطار من بيانات البكسل الخام من مستشعر الصورة،
  2. قم بإجراء تعويض حركة MPEG على البيانات الأولية،
  3. تعمل الإنتروبيا على ضغط متجهات الحركة والبيانات الأخرى،
  4. قسّم البيانات المضغوطة إلى حزم،
  5. أضف تصحيح الأخطاء المناسب وقم بإجراء تحويل فورييه السريع (FFT) لتحويل حزم البيانات إلى إشارات COFDM ، و
  6. إرسال إشارات COFDM عبر هوائي التلفزيون.

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

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

الصعوبات

يُعدّ التوازي التلقائي بواسطة المترجمات أو الأدوات أمرًا صعبًا للغاية للأسباب التالية: [ 6 ]

  • يُعد تحليل التبعية صعبًا بالنسبة للتعليمات البرمجية التي تستخدم العنونة غير المباشرة أو المؤشرات أو الاستدعاءات المتكررة أو استدعاءات الدوال غير المباشرة لأنه من الصعب اكتشاف هذه التبعيات في وقت الترجمة؛
  • تحتوي الحلقات على عدد غير معروف من التكرارات؛
  • يصعب تنسيق الوصول إلى الموارد العالمية من حيث تخصيص الذاكرة، والإدخال/الإخراج، والمتغيرات المشتركة؛
  • [ 7 ] تتداخل الخوارزميات غير المنتظمة التي تستخدم التوجيه غير المباشر المعتمد على المدخلات مع التحليل والتحسين في وقت الترجمة.

حل بديل

نظراً للصعوبات الكامنة في التوازي التلقائي الكامل، توجد عدة طرق أسهل للحصول على برنامج متوازٍ بجودة أعلى. إحدى هذه الطرق هي السماح للمبرمجين بإضافة "تلميحات" إلى برامجهم لتوجيه عملية التوازي في المُصرّف، مثل HPF لأنظمة الذاكرة الموزعة و OpenMP أو OpenHMPP لأنظمة الذاكرة المشتركة . طريقة أخرى هي بناء نظام تفاعلي بين المبرمجين وأدوات/مُصرّفات التوازي. من الأمثلة البارزة على ذلك: Vector Fabrics ' Pareon، وSUIF Explorer (مُصرّف تنسيق جامعة ستانفورد الوسيط)، ومُصرّف Polaris، وParaWise (المعروف سابقاً باسم CAPTools). وأخيراً، هناك طريقة أخرى وهي تعدد الخيوط التخميني المدعوم بالأجهزة .

أدوات ومترجمات التوازي

تعتبر معظم برامج الترجمة البحثية للتوازي التلقائي برامج Fortran ، لأن Fortran توفر ضمانات أقوى بشأن التداخل من لغات مثل C. ومن الأمثلة النموذجية على ذلك:

استخدم أوبيرت، روبيانو، روش، وسيلر [ 8 ] تقنية تحليل التبعية [ 9 ] لتوازي الحلقات تلقائيًا في برامج C.

انظر أيضاً

مراجع

  1. ↑ يهيزكائيل، رافائيل (2000). "تجارب في فصل الخوارزمية الحسابية عن توزيع البرنامج والاتصال" (ملف PDF) . الحوسبة المتوازية التطبيقية. نماذج جديدة للحوسبة عالية الأداء في الصناعة والأوساط الأكاديمية . سلسلة محاضرات في علوم الحاسوب . المجلد  1947. دار نشر سبرينغر . الصفحات 268-278 . doi : 10.1007/3-540-70734-4_32 . ISBN  978-3-540-41729-3.
  2. ↑ فوكس، جيفري؛ ويليامز، روي؛ ميسينا، بول (1994). الحوسبة المتوازية تعمل! مورغان كوفمان . الصفحات 575، 593. ISBN  978-1-55860-253-3.
  3. ↑ كامبانوني، سيمون؛ جونز، تيموثي؛ هولواي، جلين؛ وي، جو-يون؛ بروكس، ديفيد (2012). مشروع HELIX: نظرة عامة وتوجيهات .
  4. ↑ أنانتبور، ج.؛ جوفينداراجان، ر. "حساب التبعية أثناء التشغيل وتنفيذ الحلقات على الأنظمة غير المتجانسة" (ملف PDF) . مؤرشف من الأصل (ملف PDF) في 6 أكتوبر 2015. تم الاطلاع عليه في 5 أكتوبر 2015 .
  5. ↑ تشوانغ، إكس.؛ إيشنبرغر، إيه إي؛ لو، واي.؛ أوبراين، كاثرين كيفن، استغلال التوازي من خلال الجدولة الواعية بالتبعية
  6. ↑ "التوازي التلقائي واعتماد البيانات" . مؤرشف من الأصل في 14 يوليو 2014.
  7. ↑ رونجر، جودولا (2006). "نماذج البرمجة المتوازية للخوارزميات غير المنتظمة". الخوارزميات المتوازية والحوسبة العنقودية . سلسلة محاضرات في علوم وهندسة الحوسبة. 52 : 3-23 . doi : 10.1007/3-540-33541-2_1 . ISBN 978-3-540-33539-9.
  8. ↑ أوبير، كليمنت؛ روبيانو، توماس؛ روش، نيا؛ سيلر، توماس (2023). "توزيع وموازاة الحلقات غير التقليدية". التحقق، والتحقق من النموذج، والتفسير المجرد . سلسلة محاضرات في علوم الحاسوب. المجلد 13881. الصفحات 91-108 . doi : 10.1007/978-3-031-24950-1_1 . ISBN   978-3-031-24949-5.
  9. ↑ مويان، جان إيف؛ روبيانو، توماس؛ سيلر، توماس (2017). "الكشف عن أجزاء شبه ثابتة في الحلقات". التكنولوجيا الآلية للتحقق والتحليل . سلسلة محاضرات في علوم الحاسوب. المجلد 10482. الصفحات 91-108 . doi : 10.1007/978-3-319-68167-2_7 . ISBN   978-3-319-68166-5.

للمزيد من القراءة