پیش‌بینی‌کننده پرش - ویکی‌پدیا، دانشنامهٔ آزاد

در معماری کامپیوتر، پیش‌بینی پرش یک مدار دیجیتال است که تلاش می‌کند حدس بزند که یک پرش چه راهی (برای مثال ساختار if-then-else) می‌رود قبل از اینکه به‌طور قطعی شناخته شود. مقصود از پیش‌بینی پرش بهبود جریان در دستورات خط لوله است. پیش‌بینی‌های پرش نقش اساسی در دست یابی به کارایی مؤثر بالا در خیلی از معماری‌های ریزپردازنده‌های جدید مثل x86 ایفا می‌کند.

پرش دوراهه معمولاً با دستور پرش شرطی پیاده‌سازی می‌شود. شرط پرش می‌تواند هم "not-taken” باشد و اجرا را با اولین پرش کد بلافاصله بعد از پرش شرطی است ادامه دهد یا می‌تواند "taken " شود و به مکان متفاوتی در حافظه برنامه پرش کند، جایی که دومین پرش کد ذخیره شده‌است. به‌طور دقیق مشخص نیست که آیا پرش شرطی taken یا not-taken خواهد شد تا وقتی که محاسبه شود و پرش شرطی از قسمت اجرا در خط لوله عبور می‌کند. (شکل یک) بدون پیش‌بینی پرش، پردازنده باید تا زمانی که دستور پرش شرطی از حالت اجرا عبور کند، قبل از اینکه دستور بعدی بتواند وارد حالت fetch در خط لوله شود، صبر کند. پیش‌بینی پرش تلاش می‌کند تا از اتلاف زمان اجتناب کند با تلاش کردن اینکه حدس بزند که آیا پرش شرطی احتمال دارد taken یا not taken شود. پرش که حدس زده شود به احتمال زیاد fetch می‌شود و به صورت حدسی اجرا می‌شود. اگر بعداً مشخص شود که حدس غلط بوده سپس اجرای حدسی یا اجرای بخشی از دستورات اجرا شده نادیده گرفته می‌شوند و خط لوله دوباره شروع می‌کند با پرش صحیح، تحمیل تأخیر

زمانی که در رابطه با پیش‌بینی غلط به هدر می‌رود برابر است با تعدادی از مراحل در خط لوله. از مرحلهٔ fetch تا مرحلهٔ اجرا. ریزپردازنده‌های جدید تمایل دارند که خط لوله‌های نسبتاً طولانی داشته باشند به‌طوری‌که پیش‌بینی غلط تأخیر بین ۱۰ تا ۲۰ دوره ساعتی اتفاق می‌افتد. در نتیجه، درست کردن خط لوله طولانی‌تر، نیاز پیش‌بینی پرش پیشرفته تر را افزایش می‌دهد.

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

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

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

پیاده‌سازی‌های اولیه 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 اصول پیش‌بینی محلی و جهانی را از طریق الحاق تاریخچه‌های پرش‌های محلی و جهانی با یکدیگر ترکیب می‌کند، احتمالاً با چند بیت از شمارنده برنامه همچنین. آزمایش نشان داده‌است که پردازنده VIA Nano ممکن است از این تکنولوژی استفاده کند.^[۲]

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

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

پیش‌بینی‌کنندهٔ 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 است. سایز پشته بافر بازگشتی معمولاً بین ۴ تا ۱۶ ورودی است.^[۲]

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

ریزپردازنده‌های 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 یک بیتی یا ساده اعتماد می‌کند.