المتفرعة عن طريق الخطأ المتفرعة يمكن أن تزيد بشكل كبير من وقت تنفيذ البرنامج

المعالجات الحديثة هي superscalar ، أي أنها قادرة على تنفيذ العديد من التعليمات في وقت واحد. على سبيل المثال ، يمكن لبعض المعالجات معالجة من أربعة إلى ستة تعليمات لكل دورة. علاوة على ذلك ، فإن العديد من هذه المعالجات قادرة على بدء التعليمات خارج الترتيب: يمكنهم بدء العمل مع الأوامر الموجودة في الكود في وقت لاحق.

في الوقت نفسه ، يحتوي الرمز غالبًا على فروع ( if–then ). غالبًا ما يتم تطبيق هذه الفروع كـ "انتقالات" ، حيث يواصل المعالج تنفيذ التعليمات أسفل الرمز أو يواصل المسار الحالي.

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

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

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

ماذا يحدث إذا كان من الصعب التكهن؟

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

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

 while (howmany != 0) { out[index] = random(); index += 1; howmany--; } 

يمكننا توليد رقم عشوائي مناسب في المتوسط ​​لمدة 3 دورات. وهذا يعني أن التأخير الكلي لمولد الأرقام العشوائية يمكن أن يساوي 10 دورات. لكن المعالج لدينا هو superscalar ، أي أنه يمكننا إجراء العديد من حسابات الأرقام العشوائية في وقت واحد. لذلك ، سنتمكن من إنشاء رقم عشوائي جديد تقريبًا كل 3 دورات.

دعنا نغير الوظيفة قليلاً حتى تتم كتابة الأرقام الفردية فقط للصفيف:

 while (howmany != 0) { val = random(); if( val is an odd integer ) { out[index] = val; index += 1; } howmany--; } 

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

لقد حددت هاتين الوظيفتين في C ++ على معالج Skylake:


الوظيفة الثانية تعمل حوالي خمس مرات أطول!

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

 while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; } 

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


هل يستطيع المترجم حل هذه المشكلة من تلقاء نفسه؟ بشكل عام ، الجواب هو لا. في بعض الأحيان يكون للمترجمين خيارات لإزالة التفرع بالكامل ، حتى إذا كان هناك عبارة if-then in في الكود المصدري. على سبيل المثال ، يمكن في بعض الأحيان استبدال "المتفرعة" بـ "النقل الشرطي" أو الحيل الحسابية الأخرى. ومع ذلك ، فإن هذه الحيل غير آمنة للاستخدام في المجمعين.

استنتاج مهم: المتفرعة عن طريق الخطأ المتفرعة ليست مشكلة ضئيلة ، بل لها تأثير كبير.

رمز مصدر بلدي هو على جيثب .

إنشاء معايير مهمة صعبة: يتعلم المعالجات التنبؤ بالتفرع

[ملاحظة. الترجمة.: كان هذا الجزء مقالاً منفصلاً عن المؤلف ، لكنني دمجته مع المقال السابق ، لأن لديهم سمة مشتركة.]

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

لماذا استخدمت 64 مليون عدد صحيح ، بدلاً من ، على سبيل المثال ، 2000؟ إذا قمت بإجراء اختبار واحد فقط ، فلن يكون الأمر مهمًا. ومع ذلك ، ماذا سيحدث إذا قمنا بالعديد من المحاولات؟ عدد الفروع التي تم التنبؤ بها عن طريق الخطأ سينخفض ​​بسرعة إلى الصفر. يتحدث أداء معالج Intel Skylake عن نفسه:


كما يتضح من الرسوم البيانية أدناه ، فإن "التدريب" يستمر أكثر. تدريجيا ، تنخفض نسبة الفروع التي تنبأت بالخطأ إلى حوالي 2 ٪.


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

تتعلم أحدث معالجات خادم AMD أن تتنبأ بشكل كامل تقريبًا (بنسبة 0.1٪) في أقل من 10 محاولات.


يختفي هذا التنبؤ المثالي على AMD Rome عندما يزداد عدد القيم في المشكلة من 2000 إلى 10،000: يتغير أفضل التنبؤ من جزء صغير من الأخطاء بنسبة 0.1٪ إلى 33٪.

من المحتمل أن تتجنب وضع معايير مرجعية للكود المتفرغ للمهام الصغيرة.

رمز جيثب بلدي .

شكر وتقدير : AMD Rome القيم المقدمة من Vel Erwan.

قراءة إضافية : حالة للتنبؤ الفرعي بطول التاريخ الهندسي (جزئيًا) (Seznec et al.)