پیشبینی انشعاب
در معماری کامپیوتر پیشبینی انشعاب (به انگلیسی: Branch prediction) تکنولوژی ای است که در آن به کمک مدارهای دیجیتالی به نام پیش بینی گرها (branch predictors) سعی می‌شود حدس زده شود که یک برنچ (مثلاً یک ساختار شرطی) به چه راهی خواهد رفت. هدف پیش بینی گر ارتقاء جریان در خط لولهٔ دستورات (instruction pipeline) می‌باشد. برنچ پردیکشن معمولاً در پرش‌های شرطی اهمیت می‌یابد. یک پرش شرطی می‌تواند به حالت not taken برود و به ترتیب اولین ساختار کد پس از پرش شرطی را اجرا کند یا به حالت taken برود و به مکانی متفاوت در حافظهٔ برنامه که قسمت دوم ساختار کد در آن قرار دارد بپرد.
بدون استفاده از برنچ پردیکشن، پردازنده باید صبر کند تا پرش شرطی مرحلهٔ اجرا در خط لوله را تمام کند و دستور بعدی در آستانهٔ مرحلهٔ fetch قرار بگیرد. پیش بینی گر تلاش می‌کند تا با حدس زدن اینکه یک پرش شرطی به حالت taken یا not taken خواهد رفت؛ از این هدر رفت وقت جلوگیری کند به این صورت که برنچی که بیشتر از همه به نظر می‌آید که به آن پرش خواهد شد؛ fetch و بعد execute می‌شود و اگر بعداً مشخص شد که حدس اشتباه بوده از دستورات اجرا شده صرف نظر می‌شود و خط لوله با برنچ درست شروع به کار می‌کند. میزان وقتی که با پیش بینی‌های غلط هدر می‌رود برابر است با تعداد مراحل موجود از fetch تا execute در خط لوله (امروزه بین ۱۰ تا ۲۰ چرخهٔ کلاک).
اولین باری که یک پرش شرطی اتفاق می‌افتد اطلاعات زیادی در اختیار پیش بینی گر با حدس زدن نیست اما با گذشت زمان، پیش بینی گر یک رکورد از taken یا not taken شدن برنچ‌ها می‌سازد و بر طبق آن حدس‌های دقیق تری می‌زند.
برنچ‌ها
در گذشته از تکنیک‌هایی چون Stalling و predication استفاده می‌شد که این تکنیک‌ها مشکلات بسیار دارند و مناسب نیستند؛ مشکلاتی از قبیل کم بودن برنچ‌ها و مصرف منابع این تکنیک‌ها و همچنین هدر رفتن بخش زیادی از چرخه‌ها با استفاده از این تکنیک‌ها. در حال حاضر راه حل مشکل برنچ‌ها استفاده از Branch Prediction است.
فواید این روش این است که اولاً این روش میزان دستورهای موجود برای Scheduler که می‌تواند انتخاب کند و همچنین میزان ILP (instruction level parallelism) را زیاد می‌کند. دومأ فناوری برنچ پردیکشن در هنگام انتظار برای رفع برنچ اجازه می‌دهد کارهای مفید دیگر انجام شوند.
استراتژی‌های برنچ پردیکشن
این استراتژی‌ها به دو گونه تقسیم می‌شوند: استاتیک و دینامیک. استاتیک: قبل از اجرا (ران تایم) تصمیم‌گیری می‌شود. این استراتژی ساده‌ترین نوع است زیرا به تغییرات پویای اطلاعات در حافظه کاری ندارد و برای پیش بینی تنها به خود دستور برنچ می‌نگرد. مثال‌ها:
- Always-Not Taken
- Always-Taken
- Backwards Taken, Forward Not Taken (BTFNT)
- Profile-driven prediction
دینامیک: تصمیم‌گیری‌ها و راهکارهای پیشبینی در حین اجرای برنامه امکان عوض شدن دارند.
هم بستگی
اساس کار برنچ پردیکشن بر «همبستگی» (correlation) و ارتباط دستورات و داده هاست.
منابع
- Alternative Implementations of Hybrid Branch Predictors
- Po-Yung Chang Eric Hao Yale N. Patt
- S. McFarling Combining Branch Predictors Digital Western Research Lab (WRL) Technical Report, TN-36, 1993:8
- Intro to Branch Prediction By Michele Co ; University of Virginia
- Branch Prediction, Instruction-Window Size, and Cache Size: Performance Trade-offs and Simulation Techniques By: Kevin Skadron, Member, Pritpal S. Ahuja, Margaret Martonosi and Douglas W. Clark
- Fog, Agner (2009). “The microarchitecture of Intel, AMD and VIA CPU”
- Yeh, T. -Y. ; Patt, Y. N. (1991). "Two-Level Adaptive Training Branch Prediction". Proceedings of the 24th annual international symposium on Microarchitecture. Albuquerque, New Mexico, Puerto Rico: ACM. pp. 51–61
- The BiMode Branch Predictor
- Chih-Chieh Lee, I-Cheng K. Chen, and Trevor N. Mudge
- EECS Department, University of Michigan
- A NEW VALUE BASED BRANCH PREDICTOR FOR SMT PROCESSORS LIQIANG HE and ZHIYONG LIU Institute of Computing Technology, Chinese Academy of Sciences