التنبؤ (هندسة الحاسوب)

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

تعتمد معالجات المتجهات ، وبعض مجموعات تعليمات SIMD (مثل AVX2 و AVX-512 )، ووحدات معالجة الرسومات (GPUs) عمومًا، بشكل كبير على التنبؤ، حيث يتم تطبيق بت واحد من متجه القناع الشرطي على العناصر المقابلة في سجلات المتجهات قيد المعالجة، بينما لا يحتاج التنبؤ العددي في مجموعات التعليمات العددية إلا إلى بت واحد للتنبؤ. وتبرز قوة أقنعة التنبؤ في معالجة المتجهات عندما يمكن لمصفوفة من رموز الحالة ، رمز واحد لكل عنصر من عناصر المتجه، أن تُغذي أقنعة التنبؤ التي تُطبق بدورها على تعليمات المتجهات اللاحقة.

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

لحسن الحظ، يوجد حل أكثر أناقة لأحد أنماط البرمجة الشائعة التي تعتمد عادةً على التفرع. انظر إلى الشفرة الزائفة التالية : ^{[ 1 ]}

إذا تحقق الشرط { نفّذ شيئًا ما } وإلا { نفّذ شيئًا آخر }

في نظام يستخدم التفرع الشرطي، قد يترجم هذا إلى تعليمات الآلة التي تبدو مشابهة لما يلي: ^{[ 1 ]}

branch_if_condition_to label1 do_something_else branch_always_to label2 label1 : do_something label2 : ...

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

( شرط ) افعل شيئًا ما ( ليس شرطًا ) افعل شيئًا آخر

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

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

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

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

يتمثل العيب الرئيسي للتنبؤ في زيادة مساحة التشفير. في التطبيقات النموذجية، تحجز كل تعليمة حقل بتات للتنبؤ الذي يحدد الشروط التي يجب أن تُنفذ بموجبها تلك التعليمة. عندما تكون الذاكرة المتاحة محدودة، كما هو الحال في الأجهزة المدمجة ، قد تكون تكلفة هذه المساحة باهظة. مع ذلك، تستطيع بعض البنى، مثل Thumb-2، تجنب هذه المشكلة (انظر أدناه). ومن العيوب الأخرى ما يلي: ^{[ 3 ]}

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

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

كانت التعليمات المُتوقعة شائعة في تصميمات الحواسيب الأوروبية في خمسينيات القرن العشرين، بما في ذلك Mailüfterl (1955)، و Zuse Z22 (1955)، و ZEBRA (1958)، و Electrologica X1 (1958). خصص تصميم IBM ACS-1 لعام 1967 بت "تجاوز" في صيغ تعليماته، وخصص معالج CDC المرن لعام 1976 ثلاثة بتات تنفيذ شرطية في صيغ تعليماته الدقيقة.

تضمنت بنية PA-RISC من هيوليت-باكارد (1986) ميزة تُسمى "التصفير" ، والتي سمحت بتنفيذ معظم التعليمات بناءً على التعليمات السابقة. وتميزت بنية POWER من آي بي إم (1990) بتعليمات النقل الشرطي. وقد تخلت بنية PowerPC (1993) ، خليفة POWER ، عن هذه التعليمات. كما تميزت بنية Alpha من ديجيتال إكويبمنت (1992) بتعليمات النقل الشرطي. واكتسبت MIPS تعليمات النقل الشرطي في عام 1994 مع إصدار MIPS IV؛ وتم توسيع SPARC في الإصدار 9 (1994) بتعليمات النقل الشرطي لكل من سجلات الأعداد الصحيحة وسجلات الفاصلة العائمة. في البداية، لم تكن RISC-V تدعم التنبؤ، ولكن في الإصدار 2.0 من مجموعة تعليمات المعالج غير المميزة، اكتسبت هذه الميزة من خلال امتداد (Zicond) يحتوي على تعليمات تصفير شرطية يمكن من خلالها توليف العمليات الحسابية والاختيارية الشرطية.

في بنية IA-64 من هيوليت-باكارد / إنتل ، تُعتبر معظم التعليمات مُشروطة. تُخزّن الشروط في 64 سجلاً خاصاً بها ؛ ويكون أحد هذه السجلات صحيحاً دائماً، بحيث تكون التعليمات غير المُشروطة ببساطة تعليمات مُشروطة بقيمة صحيحة. يُعدّ استخدام الشروط أساسياً في تطبيق IA-64 لتقنية خطوط الأنابيب البرمجية، لأنه يُغني عن كتابة شيفرة منفصلة للمقدمات والخواتيم.

في بنية x86 ، أُضيفت مجموعة من تعليمات النقل الشرطي ( CMOVو ) إلى البنية بواسطة معالج Intel Pentium Pro (1995). تقوم هذه التعليمات بنسخ محتويات سجل المصدر إلى سجل الوجهة بناءً على شرط مُحدد بواسطة قيمة سجل الرايات.FCMOVCMOV

في معمارية ARM ، توفر مجموعة التعليمات الأصلية ذات 32 بت ميزة تُسمى التنفيذ الشرطي ، والتي تسمح بتنفيذ معظم التعليمات بناءً على أحد الشروط الثلاثة عشر المُحددة، والتي تعتمد على توليفة من رموز الشروط الأربعة التي تُحددها التعليمات السابقة. تخلت مجموعة تعليمات Thumb من ARM (1994) عن التنفيذ الشرطي لتقليل حجم التعليمات لتتناسب مع 16 بت، لكن خليفتها Thumb-2 (2003) تغلبت على هذه المشكلة باستخدام تعليمة خاصة لا تُؤثر إلا بتوفير الشروط للتعليمات الأربع التالية. أما مجموعة التعليمات ذات 64 بت، التي طُرحت في ARMv8-A (2011)، فقد استبدلت التنفيذ الشرطي بتعليمات الاختيار الشرطي.

تتمتع بعض مجموعات تعليمات SIMD داخل المسجل (SWAR)، مثل AVX2، بالقدرة على استخدام قناع منطقي لتحميل/تخزين القيم في الذاكرة بشكل مشروط، في شكل متوازٍ من النقل المشروط. كما يمكنها تطبيق بتات قناع فردية على وحدات حسابية فردية تُنفذ عملية متوازية. يتوفر بت قناع واحد لكل كلمة فرعية من مسجل SWAR أو لكل قيمة تحميل/تخزين. يُستخدم هذا النوع من التنبؤ متعدد البتات أيضًا في معالجات المتجهات على مستوى العنصر (المرادف للكلمات الفرعية في SWAR).

لكل كلمة فرعية ( i ) من سجل SWAR ( أو Vector ) ( شرط - قناع البت i ) نفّذ شيئًا ما ( الكلمة الفرعية i ) ( ليس شرط - قناع البت i ) نفّذ شيئًا آخر ( الكلمة الفرعية i )

يُعدّ الإخفاء جزءًا لا يتجزأ من معالجات المصفوفات مثل ILLIAC IV . تُعرف معالجات المصفوفات اليوم باسم "تعليمات مفردة، خيوط متعددة " (SIMT)، حيث يُستخدم بتّ مُؤشِّر لكل عنصر معالجة (PE) لتفعيل أو تعطيل كل عنصر معالجة. عندما لا يحتوي عنصر المعالجة على تعليمات SIMD ضمن تعليمات السجل ، يمكن تهيئة كل عنصر معالجة على حدة.

لكل ( PE j ) // من مصفوفة غير SWAR المتزامنة المتزامنة ( البت النشط - القناع j ) بث_التعليمات_القياسية_إلى ( PE j )

تستخدم وحدات معالجة الرسومات الحديثة SIMT (أو كانت تستخدم، ولكن وثائق ILLIAC IV أطلقت عليها اسم "التفرع" ) التنبؤ لتمكين / تعطيل عناصر المعالجة الفردية ، وبشكل منفصل، بالإضافة إلى ذلك، لإخفاء الكلمات الفرعية داخل وحدة SWAR ALU الخاصة بأي عنصر معالجة معين.

لكل ( PE j ) من مصفوفة SIMT المتزامنة ( active - maskbit j ) { // البث فقط إلى وحدات SWAR النشطة لكل ( sub - word i ) من سجل SWAR في ( PE j ) ( condition - maskbit i ) do_something ( sub - word i ) ( not condition - maskbit i ) do_something_else ( sub - word i ) }

تنطبق جميع تقنيات ومزايا وعيوب التنبؤ القياسي الأحادي بنفس القدر على حالة المعالجة المتوازية، حيث تصبح المشكلات المرتبطة بالتفرع أكثر تعقيدًا بكثير. ^{[ 5 ]}

• كليمنتس، آلان (2013). "8.3.7 التنبؤ" . تنظيم وبنية الحاسوب: موضوعات وتنوعات . سينجايج ليرنينج. ص 532-539 . ISBN  978-1-285-41542-0.