پیش‌بینی‌کننده پرش

پیش‌بینی ایستا

پیش بینی ایستا ساده‌ترین تکنیک پیش‌بینی است به دلیل اینکه در مورد تاریخ دینامیکی اجرای کد بر روی اطلاعات تکیه نمی‌کند. در عوض پیش‌بینی می‌کند نتیجه یک پرش را تنها بر پایهٔ دستورالعمل پرش پیش‌بینی می‌کند.

پیاده‌سازی‌های اولیه SPARC و MIPS (دوتا از اولین معماری‌های RISC تجاری) از پیش‌بینی پرش ایستای جهتی استفاده می‌کند: آن‌ها همیشه پیش‌بینی می‌کنند که پرش شرطی اتفاق نمی‌افتد بنابراین همیشه دستورالعمل سلسه وار بعدی را FETCH می‌کنند. تنها زمانی که پرش ارزیابی می‌شود یا پیدا می‌شود taken می‌شود، اشاره گر دستورالعمل به غیر سری تنظیم می‌شود.

هردوی CPUها پرش‌ها را در مرحله decode کردن و دارا بودن دستورالعمل fetch تک چرخه‌ای ارزیابی می‌کنند. در نتیجه، هدف دوباره اتفاق افتادن پرش طول کشیدن دوتا چرخه است و ماشین همیشه دستورالعمل را فوراً بعد از هرگونه پرشی fetch می‌کند، هر دوی معماری‌ها تأخیر پرش را به منظور استفاده این دستورات fetch شده تعریف می‌کنند.

یک حالت پیچیده تری از پیش‌بینی ایستا فرض می‌کند که پرش‌های رو به عقب اتفاق خواهد افتاد و پرش‌های رو به جلو اتفاق نمی‌افتند. یک پرش رو به عقب پرشی است که به آدرس هدف را که کمتر از آدرس خودش است پرش کن. این تکنیک می‌تواند به دقت پیش‌بینی حلقه‌ها کمک کند، که معمولاً پرش‌های رو به عقب هستند و بیشتر اتفاق می‌افتند.

برخی پردازنده‌ها اجازه می‌دهند که پیش‌بینی پرش به قرار دادن در کد به منظور ایمکه مشخص شود که آیا پیش‌بینی ایستا باید taken یا not taken شود اشاره بکند. Pentium 4 تلاش می‌کند پیش‌بینی پرش اشاره بکند در حالی که این مشخصه در پردازنده‌های اخیر کمیاب است.

پیش بینی ایستا به عنوان تکنیک رو به عقب در برخی از پردازنده‌ها با پیش‌بینی پرشی دینامیکی استفاده می‌شود زمانی که هیچ اطلاعاتی از پیش بینی‌کننده‌های دینامیکی برای استفاده وجود ندارد. هر دوی MPC7450 و Pentium 4 از این تکنیک استفاده می‌کنند.

پیش بینی‌کننده خط بعدی

برخی از پردازنده‌های فوق عددی MIPS , Alpha 21264, هر خطی از دستورالعمل را با یک اشاره‌کننده به خط بعدی fetch می‌کنند. این پیش بینی‌کننده خط بعدی، پیش‌بینی هدف پرش را، همچنین پیش‌بینی جهت پرش را مدیریت می‌کنند

زمانی که پیش بینی‌کننده خط بعدی به دستورات گروه ۲و۴ یا ۸ اشاره می‌کند، هدف پرش معمولاً اولین دستورالعمل fetch شده نخواهد بود، و بنابراین دستورالعمل‌های اولیهٔ fetch شده هدر می‌روند. با فرض اینکه برای سادگی یک توزیع یکنواخت از هدف‌های پرشی، به صورت ۰٫۵, ۱٫۵, ۳٫۵ دستورالعمل‌های fetch شده را در نظر نمی‌گیرند

به دلیل اینکه پرش به خودی خود آخرین دستورالعمل در یک گروه موازی نیست، دستورالعمل‌های بعد از پرش taken (یا تأخیر) نادیده گرفته می‌شوند. دوباره با فرض اینکه توزیع یکنواخت دستورالعمل پرشی ۰٫۵٬۱٫۵٬۳٫۵ دستورات fetch شده نادیده گرفته می‌شوند.

دستورات نادیده گرفته شده در یک پرش و خطوط مقصد تقریباً به چرخهٔ fetch کامل اضافه می‌شوند، حتی پیش‌بینی خط بعدی تک چرخه‌ای.

شمارنده اشباع

یک شمارنده اشباع دو بیتی یک ماشین ایستا با چهار حالت است:

Strongly not taken

وقتی یک پرشی ارزیابی می‌شود ماشین ایستای متناظر میز به روزرسانی می‌شود. پرش‌ها به صورت not taken decrement به سمت strongly not taken ارزیابی می‌شوند، و پرش‌ها به صورت taken increment به سمت strongly taken ارزیابی می‌شوند. مزیت شمارندهٔ دو بیتی بر طرح وترهٔ یک بیتی پرش شرطی است که دو مرتبه آن را از آنچه در گذشته قبل از تغییرات پیش‌بینی شده انجام داده است منحرف می‌کند. برای مثال، یک پرش شرطی حلقهٔ بسته یکبار به جای دوبار به اشتباه پیش‌بینی می‌گردد.

پردازنده‌های Intel pentium غیر MMX اصلی یک شمارنده اشباع اگرچه با پیاده‌سازی ناقص مورد استفاده قرار می‌دهد.

در محک‌های SPEC89 هر زمان که هر یک از پرش‌ها به یک شمارندهٔ منحصر به فرد نگاشت می‌شود، پیش بینی‌کننده‌های bimodal بسیار بزرگ در وضعیت صحیح ۹۳٫۵٪ اشباع می‌شوند.

جدول پیش بینی‌کننده، با بیت‌های آدرس دستورالعمل شاخص بندی شده‌اند، به نحوی که پردازشگر می‌تواند یک پیش‌بینی را برای هر دستورالعمل قبل از آنکه دستورالعمل decode گردد، fetch می‌کند.

پیش‌بینی کنند ی انطباقی دو ترازه

اگر عبارت if سه بار اجرا گردد تصمیمی که در اجرای سوم گرفته می‌شوند ممکن است بستگی به این داشته باشد که آیا دو شرط قبلی برقرار بوده‌اند یا خیر. در این چنین سناریوهایی، پیش بینی‌کنندهٔ انطباقی دو ترازه بهتر از یک شمارندهٔ اشباع عمل می‌کنند. پرش‌های شرطی که در هر ثانیه انجام می‌شوند یا برخی دیگر الگوهای تکراری منظم را دارند توسط شمارندهٔ اشباع به خوبی پیش‌بینی نمی‌گردد. یک پیش بینی‌کنندهٔ انطباقی دو ترازه تاریخچهٔ n رویداد پرش را به خاطر می‌سپارد و یک شمارندهٔ اشباع را برای هر یک از دو به توان الگوی تاریخچهٔ ممکن به کار می‌برد. این روش در شکل ۳ توضیح داده شده‌است.

برای مثال n=۲ را در نظر بگیرید. به این معناست که دو رخداد آخر پرش در یک شیفت رجیستر دو بیتی ذخیره گردیده است. این ثبات تاریخچهی پرش می‌توانند ۴ مقدار دودویی داشته باشد: ۰۰و۰۱و۱۰و۱۱ که ۰ به معنای not taken و ۱ به معنای taken است. جدول تاریخچهٔ الگو شامل ۴ ورودی برای هر پرش است، یکی برای هر یک از دو به توان دو که چهار می‌شود تاریخچه‌های ممکن پرش، و هر یک از ورودی‌ها در جدول شامل یک شمارندهٔ دو بیتی مشابه آنچه در شکل ۲ نشان داده شده‌است برای هر پرش می‌باشد. ثبات تاریخچهٔ پرش برای انتخاب اینکه کدام یک از ۴ شمارندهٔ اشباع به کار روند مورد استفاده قرار می‌گیرند. اگر تاریخچه ۰۰ باشد، در این صورت اولین شمارنده به کار می‌رود، اگر تاریخچه ۱۱ باشد، در این صورت آخرین چهار شمارنده به کار می‌رود.

برای مثال فرض کنید که یک پرش شرطی در هر سه زمان اتفاق می‌افتد. پرش حاصله عبارت است از: …۰۰۱۰۰۱۰۰۱ در این مورد عدد ورودی ۰۰ در جدول تاریخچهٔ الگو معرف “strongly taken” است، که نشان‌دهندهٔ این است که بعد از دوتا صفر، ۱ می‌آید. عدد ورودی ۰۱ به معنای strongly not taken است که نشان‌دهندهٔ این است که پس از ۰۱، یک ۰ می‌آید. همین شرایط برای عدد ورودی ۱۰ صادق است در حالی که عدد ۱۱ هیچ وقت مورد استفاده قرار نمی‌گیرد زیرا دو عدد یک متوالی وجود ندارند.

قانون کلی برای یک پیش بینی‌کننده انطباقی دو ترازه با تاریخچهٔ n بیتی این است که می‌تواند هر ترتیب تکراری با هر تناوبی را، اگر همهٔ زیر توالی‌های n بیتی متفاوت باشند، پیش‌بینی کند.

مزیت پیش بینی‌کنندهٔ انطباقی دو ترازه این است که به سرعت می‌تواند یاد بگیرد تا هر الگوی تکراری دلخواهی را پیش‌بینی نماید. این روش توسط T.Y Yelho patt در دانشگاه میشیگان ابداع شد. از زمان چاپ اولیهٔ مقاله‌شان در سال ۱۹۹۱، این روش بسیار رایج گردیده است. واریانس این روش پیش‌بینی در بیشتر ریزپردازنده‌های مدرن استفاده می‌گردد.

پیش بینی‌کنندهٔ پرش محلی

یک پیش بینی‌کنندهٔ پرش محلی یک حافظهٔ تاریخچهٔ جداگانه برای هر یک از دستورالعمل‌های پرش مشروط دارد و ممکن است یک پیش بینی‌کنندهٔ انطباقی دو ترازه را به کار برد.

.

پیش بینی‌کننده پرش سراسری

یک پیش بینی‌کنندهٔ پرش سراسری، یک تاریخچهٔ جداگانه را برای هر یک از پرش‌های شرطی حفظ نمی‌کند در عوض یک تاریخچهٔ اشتراکی را برای همهٔ پرش‌های شرطی به کار می‌برد. مزیت تاریخچهٔ اشتراکی این است که هرگونه ارتباط بین پرش‌های شرطی مختلف بخشی از روند پیش‌بینی هاست. عیبش این است که تاریخچه به وسیلهٔ اطلاعات غیرمرتبط رقیق می‌شود اگر پرش‌های شرطی مختلف ناهمبسته باشند و اینکه ممکن است بافر شامل هیچ بیتی از پرش مشابه نباشد اگر تعدا زیادی پرش این وسط باشند.

این طرح فقط از طرح پرش اشباع برای جداول با سایز بزرگ بهتر است و به ندرت به خوبیه پیش بینی‌کننده محلی می‌باشد. به منظور یک پیش‌بینی خوب، بافر باید طویل تر باشد. سایز جدول الگو و سایز بافر به صورت نمایی رشد می‌کند. با این حال، الگوی بزرگ جدول باید در بین تمام پرش‌های شرطی تسهیم شود.

پیش بینی‌کنندهٔ انطباقی دو ترازه با بافر تقسیم شدهٔ سراسری و جدول پیش بینی‌کننده، "gshare" نامیده می‌شود اگر که پرش pc و تاریخچهٔ جهانی را xor کند، "gselect" نامیده می‌شود که آن‌ها را به هم می‌چسباند. پیش بینی‌کنندهٔ پرش سراسری در پردازنده‌های AMD استفاده می‌شود. همچنین در intel Pentium M, Core , Core 2, Silvermont کاربرد دارد .

پیش بینی‌کنندهٔ پرش Alloyed

یک پیش بینی‌کنندهٔ پرش Alloyed اصول پیش‌بینی محلی و جهانی را از طریق الحاق تاریخچه‌های پرش‌های محلی و جهانی با یکدیگر ترکیب می‌کند، احتمالاً با چند بیت از شمارنده برنامه همچنین. آزمایش نشان داده است که پردازنده VIA Nano ممکن است از این تکنولوژی استفاده کند.

پیش بینی‌کننده توافقی

پیش بینی‌کنندهٔ توافقی یک پیش بینی‌کنندهٔ انطباقی دو ترازه با حافظهٔ تاریخی اشتراکی جهانی و الگوی تاریخچه به صورت جدول و یک شمارندهٔ محلی اشباع است. خروجی‌های پیش بینی‌کننده‌های محلی و جهانی XORed هستند که هریک پیش‌بینی نهایی را می‌دهند. هدف کاهش مشاجره در جدول تاریخچهٔ الگو است که دو پرش با پیش‌بینی مخالف برای تسهیم ورودی مشابه در جدول تاریخچه الگو اتفاق می‌افتد.

پیش بینی توافقی در اولین نسخهٔ Pentium 4 استفاده شد. اما بعداً دیگر استفاده نشد.

پیش‌بینی Hybrid

پیش بینی‌کنندهٔ Hybrid که پیش بینی‌کنندهٔ ترکیبی نیز نامیده می‌شود بیش از یک مکانیزم پیش‌بینی را پیاده‌سازی می‌کند. پیش‌بینی نهایی یا بر اساس meta predictor است که به خاطر می‌سپارد کدام یک از پیش بینی‌کننده‌ها بهترین پیش بینی‌ها را در گذشته انجام داده‌اند، یا یک تابع رای اکثریت بر اساس عدد فرد پیش بینی‌های مختلف..

در ارزیاب SPEC89 چنین پیش بینی‌کننده‌ای به خوبیه پیش بینی‌کننده محلی است.

پیش بینی‌کننده‌هایی مثل gshare از چندین ورودی جدول برای ردیابی رفتار هر پرش بخصوصی استفاده می‌کنند. این تکثیر ورودی‌ها باعث شده‌است که احتمال اینکه دو پرش به یک جدول (که این موقعیت aliasing نامیده می‌شود) یکسان نگاشت شود زیاد شود، که به نوبهٔ خود، احتمال اینکه دقت پیش‌بینی برای آن پرش‌ها رنج برد را بالا می‌برد. وقتی که شما چندین پیش بینی‌کننده دارید، سودمند است که هر پیش بینی‌کننده‌ای که الگوی aliasing متفاوتی دارد منظم شود، بنابراین حداقل یک پیش بینی‌کننده هیچ aliasing نداشته باشد بالا می‌رود. پیش بینی‌کننده‌های ترکیبی با توابع فهرست‌کننده متفاوت برای پیش بینی‌کننده‌های متفاوت. پیش بینی‌کننده gskew نامیده می‌شود و مشابه skewd associative cachesهای استفاده شده برای کش داده و دستورالعمل است.

پیش‌بینی حلقه‌ای

یک پرش مشروط که حلقه‌ای را کنترل می‌کند با یک پیش بینی‌کنندهٔ ویژه به بهترین نحو پیش‌بینی می‌گردد. پرش مشروط در کف حلقه که N مرتبه تکرار می‌گردد، N-1 مرتبه taken می‌شود و یک مرتبه not taken می‌گردد. اگر پرش مشروط در بالای حلقه قرار گیرد و N-1 مرتبه not taken و یک مرتبه taken می‌گردد. پرش مشروطی که مرتبه‌های زیادی در یک مسیر و تنها یک مرتبه در مسیر دیگر آشکارسازی می‌گردد، رفتار حلقه‌ای از خود نشان می‌دهد. مانند پرش شرطی که می‌تواند به آسانی با یک شمارنده ساده پیش‌بینی شود. پیش بینی‌کنندهٔ حلقه‌ای یک قسمتی از پیش بینی‌کنندهٔ Hybrid آیت که meta-perdictor کشف می‌کند که آیا پرش شرطی رفتار حلقه‌ای دارد.

خیلی از پردازنده‌ها امروزه پیش بینی‌کنندهٔ حلقه‌ای دارند.

پیش‌بینی پرش‌های غیر مستقیم

دستورالعمل یک پرش غیر مستقیم می‌تواند بین دو پرش انتخاب نماید. پردازنده‌های جدیدتر Intel و AMD می‌تواند پرش‌های غیر مستقیم را با استفاده از پیش بینی‌کنندهٔ انطباقی دو ترازه پیش‌بینی نماید. این نوع دستور بیشتر از یک بیت در تاریخچهٔ بافر شرکت دارد

پردازنده‌ها بدون این مکانیزم به آسانی پرش غیر مستقیم برای رفتن به هدف مشابه را پیش‌بینی می‌کنند همان‌طور که آخرین بار انجام داد.

پیش‌بینی بازگشت‌های تابع

یک تابع معمولاً به جایی که فراخوانده شده‌است بازمی‌گردد. دستورالعمل بازگشت یک پرش غیر مستقیم است که آدرس هدف خود را از call stack می‌خواند. بسیاری از ریزپردازنده‌ها مکانیزم‌های پیش‌بینی جداگانه‌ای برای دستورالعمل‌های بازگشتی دارند. این مکانیزم بر اساس return stack buffer است که آیینه محلی از call stack است. سایز پشته بافر بازگشتی معمولاً بین ۴ تا ۱۶ ورودی است.

پیش‌بینی overriding

ارزیابی بین پیش‌بینی پرش سریع و پیش‌بینی پرش خوب گاهی اوقات باعث می‌شود که دو پیش بینی‌کننده پرش وجود داشته باشه. اولین پیش بینی‌کننده پرش سریع و ساده است و دومی کندتر، پیچیده‌تر و با جدول‌های بزرگتر می‌باشد که پیش‌بینی احتمالاً غلطی که توسط اولین پیش‌بینی حاصل شده‌است را باطل می‌کند.

ریزپردازنده‌های Alpha 21264 , Alpha EV8 از پیش بینی‌کنندهٔ خط بعدی تک چرخه‌ای سریع برای ادارهٔ بازگشت هدف پرش و تهیهٔ پیش‌بینی سریع و ساده استفاده می‌کنند. به دلیل اینکه پیش بینی‌کنندهٔ خط بعدی غیر دقیق است، و بازگشت کیفیت پرش خیلی طول می‌کشد، هر دو هسته دو پیش بینی‌کنندهٔ پرش ثانوی دو چرخه‌ای دارند که می‌توانند پیش‌بینی پیش بینی‌کنندهٔ خط بعدی را در هزینهٔ یک چرخه fetch باطل کنند.

Core i7 دو بافر هدف پرش دارد و ممکن است دو یا بیشتر پیش بینی‌کننده داشته باشد.

پیش‌بینی پرش عصبی

یادگیری ماشین برای پیش‌بینی پرش با استفاده از LVQ و multi-layer perceptrons پیش‌بینی پرش عصبی نامیده می‌شود که توسط پروفسور Vintan و سپس پروفسور jimenez در سال ۲۰۰۱ گسترش پیدا کرد. مزیت اصلی پیش بینی‌کنندهٔ عصبی در توانایی آن برای شناسایی تاریخچه‌های بلند مدت است در حالی که تمها رشد خطی منبع را لازم دارد. پیش بینی‌کننده‌های کلاسیک رشد منبع نمایی را لازم داشتند. نقطه ضعف عمدهٔ پیش بینی‌کننده‌های perceptrons تأخیر بالای آن است.

پیش بینی‌کننده‌های دو بیتی توسط Tom McWilliams و curt middoes در سال ۱۹۷۷ و به‌طور جداگانه توسط jim smith معرفی شدند. پردازنده‌های ریز برنامه که از دههٔ ۱۹۶۰ تا دههٔ ۱۹۸۰ و پس از آن رایج بودند چندین چرخه برای هر دستورالعمل به کار می‌برند؛ و به تدریج در نسخه‌های جدیدتر نیاز به پیش‌بینی نداشتند.

The Burroughs B4900 ماشین ریزبرنامهٔ کوبل که در سال ۱۹۸۲ ابداع شد از خط لوله پیش‌بینی پرش استفاده نمود. وضعیت تاریخچهٔ پرش B4900 در دستورالعمل‌های حافظهٔ آن در طول اجرای برنامه ذخیره می‌گردد.

VAX9000 که در سال ۱۹۸۹ ابداع شد، هم ریزبرنامه و هم خط لوله شده‌است و پیش‌بینی پرشی را اجرا می‌کند.

از دیگر موارد ابداع شده می‌توان به MIPS-R2000 و R3000و R4000 اشاره نمود. سپس پیش‌بینی پرشی نظیر Intel Pentium, Alpha,R8000,IBM POWER با معرفی پردازشگرهای Superscalar خط لوله اهمیت بیشتری پیدا کرد و این پردازشگرها با پیش بینی‌کننده‌های bimodal یک بیتی یا ساده اعتماد می‌کند.