مُتنبئ التفرع

يُعدّ التنبؤ الثابت أبسط تقنيات التنبؤ بالتفرعات، لأنه لا يعتمد على معلومات حول تاريخ تنفيذ التعليمات البرمجية. بل يتنبأ بنتيجة التفرع بناءً على تعليمة التفرع فقط. ^{[ 7 ]} استخدمت التطبيقات المبكرة لمعالجات SPARC و MIPS (وهما من أوائل معمارية RISC التجارية ) التنبؤ الثابت بالتفرعات أحادي الاتجاه: إذ تتنبأ دائمًا بعدم تنفيذ القفزة الشرطية، وبالتالي تستجلب دائمًا التعليمة التسلسلية التالية. وعندما يتم تقييم التفرع أو القفزة والتأكد من تنفيذها، يتم تعيين مؤشر التعليمة إلى عنوان غير تسلسلي.

تستجلب كلتا المعالجتين التعليمات في دورة واحدة، وتقيّمان التفرعات في مرحلة فك التشفير. ونتيجةً لذلك، تستغرق دورة تكرار هدف التفرع دورتين، ويستجلب الجهاز دائمًا التعليمات مباشرةً بعد أي تفرع مُتخذ. وتُحدد كلتا البنيتين فترات تأخير التفرع للاستفادة من هذه التعليمات المستجلبة.

يفترض شكلٌ أكثر تطورًا من التنبؤ الثابت أن الفروع العكسية ستُنفذ، بينما لن تُنفذ الفروع الأمامية. (الفرع العكسي هو الفرع الذي يكون عنوانه المستهدف أقل من عنوانه). تزيد هذه القاعدة من دقة التنبؤ في الحلقات، التي يمكن إنشاؤها بفرع عكسي في النهاية يُنفذ غالبًا، أو بفرع أمامي في البداية لا يُنفذ غالبًا. مع المعالجات التي تستخدم طريقة التنبؤ هذه، يُمكن لترتيب التعليمات أن يزيد من دقة التنبؤ بالفروع إلى أقصى حد. توصي مجموعة تعليمات RISC-V بتحسين البرامج المكتوبة لوحدات معالجة RISC-V (خيوط الأجهزة)، أو المُصممة للعمل على وحدات معالجة RISC-V، بافتراض أن الفروع العكسية تُنفذ، بينما لا تُنفذ الفروع الأمامية. (حتى عندما يتضمن المعالج مُتنبئًا أكثر تطورًا يُقلل من القيمة النسبية للتنبؤ الثابت). ^{[ 8 ]}

تقبل بعض المعالجات تلميحات التنبؤ بالتفرع التي تتجاوز التنبؤ الثابت. يقبل معالجا إنتل بنتيوم 4 وبنتيوم 4E تلميحات التنبؤ بالتفرع كبادئات. في ظل وجود التنبؤ الديناميكي، لا يُقدم التنبؤ الثابت أي فائدة تُذكر، وتجاوزه يُقلل من فائدته. تتجاهل معالجات إنتل اللاحقة بنتيوم إم وكور 2 بادئات تلميحات التنبؤ بالتفرع. ^{[ 9 ]} لم يُعد أي مُصنِّع لمعالجات x86 استخدام تلميحات التنبؤ.

تعتمد مُتنبئات الفروع الديناميكية بشكل طبيعي على التنبؤ الثابت بالفروع عندما لا تتوفر لديها معلومات مُخزنة مؤقتًا (مثل أول مرة يتم فيها مواجهة فرع معين). يعتمد كل من معالج Motorola MPC7450 (G4e) ومعالج Intel Pentium 4 على التنبؤ الثابت. ^{[ 10 ]}

في التنبؤ الثابت، يتم اتخاذ جميع القرارات في وقت الترجمة، قبل تنفيذ البرنامج. ^{[ 11 ]}

يستخدم التنبؤ الديناميكي بالفروع ^{[ 2 ]} معلومات حول الفروع التي تم اتخاذها أو لم يتم اتخاذها والتي يتم جمعها في وقت التشغيل للتنبؤ بنتيجة الفرع. ^{[ 1 ]}

يعني التنبؤ العشوائي بالفروع التخمين العشوائي لما إذا كان سيتم تنفيذ فرع معين في كل مرة. وتُعد تكلفة مولد الأرقام شبه العشوائية منخفضة مقارنةً بالتقنيات الأخرى. يضمن التنبؤ العشوائي معدل دقة 50%، وهو معدل لا يمكن زيادته أو إنقاصه بأي شكل من الأشكال. (ويجعل هذا التوقيت أكثر عشوائية من الطرق الأخرى). أما التنبؤ الثابت بالفروع (بافتراض تنفيذ الفروع الأمامية وعدم تنفيذ الفروع الخلفية) فيتنبأ بكل فرع بدقة تتراوح بين 0% و100%، مع معدل نجاح إجمالي يقع بينهما. من المرجح جدًا أن يعمل الكود غير المُحسَّن بنسبة نجاح تنبؤ أفضل من 50%، بل قد تصل إلى 90%. إذا قام المُصرِّف بإعادة ترتيب بعض التعليمات، فإن ذلك يزيد من معدل دقة التنبؤ بالفروع مقارنةً بالكود غير المُحسَّن. لقد تفوق التنبؤ الثابت بالفروع على التنبؤ العشوائي بالفروع منذ زمن بعيد. كما تفوق التنبؤ الديناميكي بالفروع على التنبؤ الثابت بالفروع وأصبح شائعًا، على الرغم من التعقيد الإضافي.

تقوم بعض المعالجات فائقة التوازي (MIPS R8000 و Alpha 21264 و Alpha 21464 (EV8)) بجلب كل سطر من التعليمات مع مؤشر إلى السطر التالي. ويتولى هذا المؤشر التنبؤ بالهدف من التفرع بالإضافة إلى التنبؤ باتجاه التفرع.

عندما يشير مُتنبئ السطر التالي إلى مجموعات مُتراصفة من 2 أو 4 أو 8 تعليمات، فإن هدف التفرع عادةً لن يكون أول تعليمة يتم جلبها، وبالتالي تُهدر التعليمات الأولية التي تم جلبها. وبافتراض توزيع مُنتظم لأهداف التفرع، يتم تجاهل 0.5 و1.5 و3.5 تعليمة تم جلبها، على التوالي.

بما أن التفرع نفسه لن يكون عادةً آخر تعليمة في مجموعة مُحاذية، فسيتم تجاهل التعليمات التي تلي التفرع المُنفذ (أو خانة التأخير الخاصة به). ومرة ​​أخرى، بافتراض توزيع منتظم لمواضع تعليمات التفرع، يتم تجاهل 0.5 و1.5 و3.5 تعليمة التي تم جلبها.

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

يستخدم مُتنبئ التفرع ثنائي المستوى، والذي يُشار إليه أيضًا باسم مُتنبئ التفرع القائم على الارتباط، جدولًا ثنائي الأبعاد للعدادات، يُسمى أيضًا "جدول تاريخ الأنماط". مدخلات الجدول عبارة عن عدادات ثنائية البت.

نموذج تنبؤي تكيفي ثنائي المستوى

إذا ifنُفِّذَت عبارةٌ ثلاث مرات، فقد يعتمد القرار المتخذ في التنفيذ الثالث على ما إذا نُفِّذَت العبارتان السابقتان أم لا. في مثل هذه الحالات، يعمل مُتنبئ تكيفي ثنائي المستوى بكفاءةٍ أعلى من عداد التشبع. لا يتنبأ عداد التشبع جيدًا بالقفزات الشرطية التي تُنفَّذ كل مرتين أو التي لها نمطٌ متكررٌ بانتظام. يتذكر المُتنبئ التكيفي ثنائي المستوى تاريخ آخر n من مرات حدوث الفرع، ويستخدم عداد تشبع واحدًا لكل نمطٍ من أنماط التاريخ المحتملة البالغ عددها 2n ^. يوضح الشكل 3 هذه الطريقة.

لنأخذ مثال n  = 2. هذا يعني أن آخر ظهورين للتفرع يُخزّنان في مسجل إزاحة ثنائي البت . يمكن أن يحتوي مسجل تاريخ التفرع هذا على أربع قيم ثنائية مختلفة : 00، 01، 10، و11، حيث يعني الصفر "غير مُنفّذ" والواحد "مُنفّذ". يحتوي جدول تاريخ النمط على أربعة مدخلات لكل تفرع، مدخل واحد لكل من تواريخ التفرع الأربعة الممكنة (2² ⁼  4)، ويحتوي كل مدخل في الجدول على عداد تشبع ثنائي البت من نفس النوع الموضح في الشكل 2 لكل تفرع. يُستخدم مسجل تاريخ التفرع لاختيار أي من عدادات التشبع الأربعة سيتم استخدامه. إذا كان التاريخ 00، فسيتم استخدام العداد الأول؛ وإذا كان التاريخ 11، فسيتم استخدام العداد الأخير من بين العدادات الأربعة.

لنفترض، على سبيل المثال، أن قفزة شرطية تُنفذ كل ثلاث مرات. تسلسل التفرع هو 001001001... في هذه الحالة، سينتقل المدخل رقم 00 في جدول سجل النمط إلى حالة "منفذ بقوة"، مما يشير إلى وجود واحد بعد صفرين. سينتقل المدخل رقم 01 إلى حالة "غير منفذ بقوة"، مما يشير إلى وجود صفر بعد 01. وينطبق الأمر نفسه على المدخل رقم 10، بينما لا يُستخدم المدخل رقم 11 مطلقًا لعدم وجود واحدين متتاليين.

القاعدة العامة للمتنبئ التكيفي ثنائي المستوى ذي التاريخ المكون من n بت هي أنه يستطيع التنبؤ بأي تسلسل متكرر بأي فترة إذا كانت جميع التسلسلات الفرعية المكونة من n بت مختلفة. ^{[ 9 ]}

تتميز خوارزمية التنبؤ التكيفية ثنائية المستوى بقدرتها على تعلم التنبؤ بنمط متكرر عشوائي بسرعة. وقد ابتكر هذه الطريقة كل من تي-واي ييه وييل بات في جامعة ميشيغان . ^{[ 14 ]} ومنذ نشرها لأول مرة عام 1991، لاقت هذه الطريقة رواجًا كبيرًا، حيث استُخدمت في معالجات بنتيوم اللاحقة، مثل بنتيوم إم إم إكس. ^{[ 15 ]} وتُستخدم نسخ معدلة من هذه الطريقة في معظم المعالجات الدقيقة الحديثة.

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

تحتوي معالجات Intel Pentium MMX و Pentium II و Pentium III على متنبئات تفرع محلية مع سجل تاريخي محلي مكون من 4 بتات وجدول تاريخ نمط محلي يحتوي على 16 مدخلاً لكل قفزة شرطية.

في معايير SPEC '89، تصل دقة التنبؤات المحلية الكبيرة جدًا إلى حد التشبع عند 97.1%. ^{[ 12 ] : 6}

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

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

يُطلق على المُتنبئ التكيفي ثنائي المستوى، الذي يستخدم مخزنًا مؤقتًا للتاريخ وجدولًا لتاريخ الأنماط بشكل مشترك عالميًا، اسم "مُتنبئ gshare" إذا كان يُجري عملية XOR بين التاريخ العالمي وعداد البرنامج الخاص بالفروع، و"مُتنبئ gselect" إذا كان يُدمجهما . يُستخدم التنبؤ بالفروع العالمي في معالجات AMD ، وفي معالجات Intel Pentium M و Core و Core 2 و Atom المبنية على معمارية Silvermont .

يجمع مُتنبئ التفرعات المُدمج ^{[ 17 ]} بين مبادئ التنبؤ المحلية والعالمية من خلال دمج سجلات التفرعات المحلية والعالمية، وربما مع بعض البتات من عداد البرنامج أيضًا. تشير الاختبارات إلى أن معالج VIA Nano قد يستخدم هذه التقنية. ^{[ 9 ]}

المتنبئ المتفق هو متنبئ تكيفي ثنائي المستوى، مزود بمخزن بيانات تاريخي مشترك عالميًا وجدول تاريخ أنماط، بالإضافة إلى عداد تشبع محلي إضافي. تُجرى عملية XOR بين مخرجات المتنبئين المحلي والعالمي للحصول على التنبؤ النهائي. والهدف من ذلك هو تقليل التنازع في جدول تاريخ الأنماط، حيث يتشارك فرعان بتنبؤات متعاكسة نفس المدخل في الجدول. ^{[ 18 ]}

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

اقترح سكوت مكفارلينج التنبؤ المشترك بالفروع في ورقته البحثية عام 1993. ^{[ 12 ]}

في معايير SPEC'89، يكون هذا المتنبئ جيدًا تقريبًا مثل المتنبئ المحلي.

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

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

يمكن لتعليمات القفز غير المباشر الاختيار بين أكثر من فرعين. تحتوي بعض المعالجات على مُتنبئات مُخصصة للفروع غير المباشرة. ^{[ 19 ] [ 20 ]} تستطيع المعالجات الأحدث من إنتل ^{[ 21 ]} وإيه إم دي ^{[ 22 ]} التنبؤ بالفروع غير المباشرة باستخدام مُتنبئ تكيفي ثنائي المستوى. يُساهم هذا النوع من التعليمات بأكثر من بت واحد في مُخزن التاريخ. تدعم معالجات zEC12 والمعالجات اللاحقة من معمارية z/Architecture من آي بي إم تعليمة BRANCH PREDICTION PRELOAD التي تُحمّل مُدخل مُتنبئ الفرع لتعليمات مُعينة بعنوان هدف الفرع المُنشأ عن طريق إضافة مُحتويات مُسجل للأغراض العامة إلى قيمة إزاحة فورية. ^{[ 23 ] [ 24 ]}

المعالجات التي لا تحتوي على هذه الآلية ستتوقع ببساطة أن القفزة غير المباشرة ستذهب إلى نفس الهدف الذي ذهبت إليه في المرة السابقة. ^{[ 9 ]}

عادةً ما تعود الدالة إلى المكان الذي استُدعيت منه. تُعدّ تعليمة الإرجاع قفزة غير مباشرة تقرأ عنوان الوجهة من مكدس الاستدعاءات . تمتلك العديد من المعالجات الدقيقة آلية تنبؤ منفصلة لتعليمات الإرجاع. تعتمد هذه الآلية على ما يُسمى بمخزن مؤقت لمكدس الإرجاع ، وهو نسخة محلية من مكدس الاستدعاءات. يتراوح حجم مخزن مكدس الإرجاع عادةً بين 4 و16 مدخلاً. ^{[ 9 ]}

يُعالج التوازن بين سرعة التنبؤ بالفروع وجودة التنبؤ بها أحيانًا باستخدام مُتنبئين للفروع. الأول سريع وبسيط، أما الثاني، وهو أبطأ وأكثر تعقيدًا ويستخدم جداول بيانات أكبر، فيُمكنه تجاوز أي تنبؤ خاطئ قد يُصدره المُتنبئ الأول.

استخدمت المعالجات الدقيقة Alpha 21264 و Alpha EV8 مُتنبئًا سريعًا أحادي الدورة للخط التالي للتعامل مع تكرار هدف التفرع وتوفير تنبؤ بسيط وسريع للتفرع. ولأن مُتنبئ الخط التالي غير دقيق، ولأن تكرار حل التفرع يستغرق وقتًا طويلاً، فإن كلا النواتين تحتويان على مُتنبئين ثانويين للتفرع يعملان بدورتين، ويمكنهما تجاوز تنبؤ مُتنبئ الخط التالي مقابل فقدان دورة جلب واحدة.

يحتوي معالج Intel Core i7 على مخزنين مؤقتين لأهداف التفرع ، وربما اثنين أو أكثر من متنبئات التفرع. ^{[ 25 ]}

اقترح لوسيان فينتان ( جامعة لوسيان بلاغا في سيبيو ) استخدام التعلم الآلي للتنبؤ بالتفرعات باستخدام LVQ والشبكات العصبية متعددة الطبقات ، والذي يُعرف باسم " التنبؤ العصبي بالتفرعات". ^{[ 26 ]} وبعد عام، طوّر مُتنبئ التفرعات باستخدام الشبكات العصبية. ^{[ 27 ]} ثمّ طوّر دانيال خيمينيز أبحاث التنبؤ العصبي بالتفرعات بشكل كبير. ^{[ 28 ]} وفي عام 2001، ^{[ 28 ]} عُرض أول مُتنبئ شبكات عصبية قابل للتطبيق عمليًا في الأجهزة. وكان أول تطبيق تجاري لمُتنبئ التفرعات باستخدام الشبكات العصبية في بنية Piledriver الدقيقة من AMD . ^{[ 29 ]}

تتمثل الميزة الرئيسية للمتنبئ العصبي في قدرته على استغلال البيانات التاريخية الطويلة مع الحاجة إلى نمو خطي للموارد فقط، بينما تتطلب المتنبئات التقليدية نموًا أُسّيًا للموارد. وقد أفاد خيمينيز بتحقيق تحسن شامل بنسبة 5.7% مقارنةً بمتنبئ هجين من نوع ماكفارلينغ. ^{[ 30 ]} كما استخدم أيضًا نموذج gshare/perceptron لتجاوز المتنبئات الهجينة. ^{[ 30 ]}

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

تستخدم معظم برامج التنبؤ بالتفرعات الحديثة نموذج التنبؤ بالبيرسيبترون (انظر "مسابقة إنتل للتنبؤ بالتفرعات" ^{[ 31 ]} ). وقد طبقت إنتل هذه الفكرة بالفعل في أحد برامج محاكاة معالج IA-64 (2003). ^{[ 32 ]}

تتضمن معالجات AMD Ryzen ^[ 33 ^{] [ 34 ] [ 35 ]} متعددة النوى Infinity Fabric ومعالجات Samsung Exynos ^تنبؤات الفروع العصبية القائمة على perceptron.