موضوع مقاله: پیش‌بینی‌کننده پرش | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پیش‌بینی‌کننده پرش | مقدمه: در معماری کامپیوتر، پیش‌بینی پرش یک مدار دیجیتال است که تلاش می‌کند حدس بزند که یک پرش چه راهی (برای مثال ساختار if-then-else) می‌رود قبل از اینکه به‌طور قطعی شناخته شود. | ## بخش 1: پیش‌بینی‌کننده پرش | پیش‌بینی‌های پرش نقش اساسی در دست یابی به کارایی مؤثر بالا در خیلی از معماری‌های ریزپردازنده‌های جدید مثل x86 ایفا می‌کند. جعبه‌های رنگی نشان دهنده دستورالعمل‌ها مستقل از یکدیگر پرش دوراهه معمولاً با دستور پرش شرطی پیاده‌سازی می‌شود. شرط پرش می‌تواند هم "not-taken” باشد و اجرا را با اولین پرش کد بلافاصله بعد از پرش شرطی است ادامه دهد یا می‌تواند "taken " شود و به مکان متفاوتی در حافظه برنامه پرش کند، جایی که دومین پرش کد ذخیره شده‌است. (شکل یک) بدون پیش‌بینی پرش، پردازنده باید تا زمانی که دستور پرش شرطی از حالت اجرا عبور کند، قبل از اینکه دستور بعدی بتواند وارد حالت fetch در خط لوله شود، صبر کند. اگر بعداً مشخص شود که حدس غلط بوده سپس اجرای حدسی یا اجرای بخشی از دستورات اجرا شده نادیده گرفته می‌شوند و خط لوله دوباره شروع می‌کند با پرش صحیح، تحمیل تأخیر زمانی که در رابطه با پیش‌بینی غلط به هدر می‌رود برابر است با تعدادی از مراحل در خط لوله. ریزپردازنده‌های جدید تمایل دارند که خط لوله‌های نسبتاً طولانی داشته باشند به‌طوری‌که پیش‌بینی غلط تأخیر بین ۱۰ تا ۲۰ دوره ساعتی اتفاق می‌افتد. در نتیجه، درست کردن خط لوله طولانی‌تر، نیاز پیش‌بینی پرش پیشرفته تر را افزایش می‌دهد. وقتی که با یک پرش شرطی که چندین بار با آن برخورد کرده مواجه می‌شود می‌تواند پیش‌بینی را بر پایهٔ تاریخ قرار دهد. پیش‌بینی پرش ممکنه برای مثال، تشخیص دهد که پرش شرطی اغلب انجام شده یا خیر، یا اینکه یک در میان انجام شده. پیش‌بینی پرش تلاش می‌کند که تشخیص دهد که آیا پرش شرطی می‌خواهد انجام گیرد یا نه. پیش‌بینی هدف پرش تلاش می‌کند تا حدس بزند یک هدف را از اینکه این پرش شرطی بوده یا غیرشرطی قبل از اینکه با decode کردن محاسبه شود ویا اجرای دستورالعمل‌های خودش. پیاده‌سازی پیش‌بینی ایستا پیش‌بینی ایستا ساده‌ترین تکنیک پیش‌بینی است به دلیل اینکه در مورد تاریخ دینامیکی اجرای کد بر روی اطلاعات تکیه نمی‌کند. در عوض پیش‌بینی می‌کند نتیجه یک پرش را تنها بر پایهٔ دستورالعمل پرش پیش‌بینی می‌کند. پیاده‌سازی‌های اولیه SPARC و MIPS (دوتا از اولین معماری‌های RISC تجاری) از پیش‌بینی پرش ایستای جهتی استفاده می‌کند: آن‌ها همیشه پیش‌بینی می‌کنند که پرش شرطی اتفاق نمی‌افتد بنابراین همیشه دستورالعمل سلسه وار بعدی را FETCH می‌کنند. تنها زمانی که پرش ارزیابی می‌شود یا پیدا می‌شود taken می‌شود، اشاره گر دستورالعمل به غیر سری تنظیم می‌شود. در نتیجه، هدف دوباره اتفاق افتادن پرش طول کشیدن دوتا چرخه است و ماشین همیشه دستورالعمل را فوراً بعد از هرگونه پرشی fetch می‌کند، هر دوی معماری‌ها تأخیر پرش را به منظور استفاده این دستورات fetch شده تعریف می‌کنند. یک حالت پیچیده تری از پیش‌بینی ایستا فرض می‌کند که پرش‌های رو به عقب اتفاق خواهد افتاد و پرش‌های رو به جلو اتفاق نمی‌افتند. این تکنیک می‌تواند به دقت پیش‌بینی حلقه‌ها کمک کند، که معمولاً پرش‌های رو به عقب هستند و بیشتر اتفاق می‌افتند. Pentium 4 تلاش می‌کند پیش‌بینی پرش اشاره بکند در حالی که این مشخصه در پردازنده‌های اخیر کمیاب است. پیش‌بینی ایستا به عنوان تکنیک رو به عقب در برخی از پردازنده‌ها با پیش‌بینی پرشی دینامیکی استفاده می‌شود زمانی که هیچ اطلاعاتی از پیش‌بینی‌کننده‌های دینامیکی برای استفاده وجود ندارد. این پیش‌بینی‌کننده خط بعدی، پیش‌بینی هدف پرش را، همچنین پیش‌بینی جهت پرش را مدیریت می‌کنند زمانی که پیش‌بینی‌کننده خط بعدی به دستورات گروه ۲و۴ یا ۸ اشاره می‌کند، هدف پرش معمولاً اولین دستورالعمل fetch شده نخواهد بود، و بنابراین دستورالعمل‌های اولیهٔ fetch شده هدر می‌روند. | ## بخش 2: پیش‌بینی‌کننده پرش | با فرض اینکه برای سادگی یک توزیع یکنواخت از هدف‌های پرشی، به صورت ۰٫۵, ۱٫۵, ۳٫۵ دستورالعمل‌های fetch شده را در نظر نمی‌گیرند به دلیل اینکه پرش به خودی خود آخرین دستورالعمل در یک گروه موازی نیست، دستورالعمل‌های بعد از پرش taken (یا تأخیر) نادیده گرفته می‌شوند. دوباره با فرض اینکه توزیع یکنواخت دستورالعمل پرشی ۰٫۵٬۱٫۵٬۳٫۵ دستورات fetch شده نادیده گرفته می‌شوند. دستورات نادیده گرفته شده در یک پرش و خطوط مقصد تقریباً به چرخهٔ fetch کامل اضافه می‌شوند، حتی پیش‌بینی خط بعدی تک چرخه‌ای. مزیت شمارندهٔ دو بیتی بر طرح وترهٔ یک بیتی پرش شرطی است که دو مرتبه آن را از آنچه در گذشته قبل از تغییرات پیش‌بینی شده انجام داده‌است منحرف می‌کند. برای مثال، یک پرش شرطی حلقهٔ بسته یکبار به جای دوبار به اشتباه پیش‌بینی می‌گردد. در محک‌های SPEC89 هر زمان که هر یک از پرش‌ها به یک شمارندهٔ منحصر به فرد نگاشت می‌شود، پیش‌بینی‌کننده‌های bimodal بسیار بزرگ در وضعیت صحیح ۹۳٫۵٪ اشباع می‌شوند.S. اگر عبارت if سه بار اجرا گردد تصمیمی که در اجرای سوم گرفته می‌شوند ممکن است بستگی به این داشته باشد که آیا دو شرط قبلی برقرار بوده‌اند یا خیر. در این چنین سناریوهایی، پیش‌بینی‌کنندهٔ انطباقی دو ترازه بهتر از یک شمارندهٔ اشباع عمل می‌کنند. پرش‌های شرطی که در هر ثانیه انجام می‌شوند یا برخی دیگر الگوهای تکراری منظم را دارند توسط شمارندهٔ اشباع به خوبی پیش‌بینی نمی‌گردد. یک پیش‌بینی‌کنندهٔ انطباقی دو ترازه تاریخچهٔ n رویداد پرش را به خاطر می‌سپارد و یک شمارندهٔ اشباع را برای هر یک از دو به توان الگوی تاریخچهٔ ممکن به کار می‌برد. جدول تاریخچهٔ الگو شامل ۴ ورودی برای هر پرش است، یکی برای هر یک از دو به توان دو که چهار می‌شود تاریخچه‌های ممکن پرش، و هر یک از ورودی‌ها در جدول شامل یک شمارندهٔ دو بیتی مشابه آنچه در شکل ۲ نشان داده شده‌است برای هر پرش می‌باشد. ثبات تاریخچهٔ پرش برای انتخاب اینکه کدام یک از ۴ شمارندهٔ اشباع به کار روند مورد استفاده قرار می‌گیرند. اگر تاریخچه ۰۰ باشد، در این صورت اولین شمارنده به کار می‌رود، اگر تاریخچه ۱۱ باشد، در این صورت آخرین چهار شمارنده به کار می‌رود. همین شرایط برای عدد ورودی ۱۰ صادق است در حالی که عدد ۱۱ هیچ وقت مورد استفاده قرار نمی‌گیرد زیرا دو عدد یک متوالی وجود ندارند. قانون کلی برای یک پیش‌بینی‌کننده انطباقی دو ترازه با تاریخچهٔ n بیتی این است که می‌تواند هر ترتیب تکراری با هر تناوبی را، اگر همهٔ زیر توالی‌های n بیتی متفاوت باشند، پیش‌بینی کند. مزیت پیش‌بینی‌کنندهٔ انطباقی دو ترازه این است که به سرعت می‌تواند یاد بگیرد تا هر الگوی تکراری دلخواهی را پیش‌بینی نماید. پیش‌بینی‌کنندهٔ پرش محلی یک پیش‌بینی‌کنندهٔ پرش محلی یک حافظهٔ تاریخچهٔ جداگانه برای هر یک از دستورالعمل‌های پرش مشروط دارد و ممکن است یک پیش‌بینی‌کنندهٔ انطباقی دو ترازه را به کار برد. مزیت تاریخچهٔ اشتراکی این است که هرگونه ارتباط بین پرش‌های شرطی مختلف بخشی از روند پیش‌بینی هاست. عیبش این است که تاریخچه به وسیلهٔ اطلاعات غیرمرتبط رقیق می‌شود اگر پرش‌های شرطی مختلف ناهمبسته باشند و اینکه ممکن است بافر شامل هیچ بیتی از پرش مشابه نباشد اگر تعدا زیادی پرش این وسط باشند. این طرح فقط از طرح پرش اشباع برای جداول با سایز بزرگ بهتر است و به ندرت به خوبیه پیش‌بینی‌کننده محلی می‌باشد. پیش‌بینی‌کنندهٔ پرش Alloyed یک پیش‌بینی‌کنندهٔ پرش Alloyed اصول پیش‌بینی محلی و جهانی را از طریق الحاق تاریخچه‌های پرش‌های محلی و جهانی با یکدیگر ترکیب می‌کند، احتمالاً با چند بیت از شمارنده برنامه همچنین. | ## بخش 3: پیش‌بینی‌کننده پرش | پیش‌بینی‌کننده توافقی پیش‌بینی‌کنندهٔ توافقی یک پیش‌بینی‌کنندهٔ انطباقی دو ترازه با حافظهٔ تاریخی اشتراکی جهانی و الگوی تاریخچه به صورت جدول و یک شمارندهٔ محلی اشباع است. خروجی‌های پیش‌بینی‌کننده‌های محلی و جهانی XORed هستند که هریک پیش‌بینی نهایی را می‌دهند. هدف کاهش مشاجره در جدول تاریخچهٔ الگو است که دو پرش با پیش‌بینی مخالف برای تسهیم ورودی مشابه در جدول تاریخچه الگو اتفاق می‌افتد. پیش‌بینی نهایی یا بر اساس meta predictor است که به خاطر می‌سپارد کدام یک از پیش‌بینی‌کننده‌ها بهترین پیش‌بینی‌ها را در گذشته انجام داده‌اند، یا یک تابع رای اکثریت بر اساس عدد فرد پیش‌بینی‌های مختلف.. پیش‌بینی‌کننده‌هایی مثل gshare از چندین ورودی جدول برای ردیابی رفتار هر پرش بخصوصی استفاده می‌کنند. این تکثیر ورودی‌ها باعث شده‌است که احتمال اینکه دو پرش به یک جدول (که این موقعیت aliasing نامیده می‌شود) یکسان نگاشت شود زیاد شود، که به نوبهٔ خود، احتمال اینکه دقت پیش‌بینی برای آن پرش‌ها رنج برد را بالا می‌برد. پیش‌بینی‌کننده‌های ترکیبی با توابع فهرست‌کننده متفاوت برای پیش‌بینی‌کننده‌های متفاوت. پیش‌بینی حلقه‌ای یک پرش مشروط که حلقه‌ای را کنترل می‌کند با یک پیش‌بینی‌کنندهٔ ویژه به بهترین نحو پیش‌بینی می‌گردد. پرش مشروطی که مرتبه‌های زیادی در یک مسیر و تنها یک مرتبه در مسیر دیگر آشکارسازی می‌گردد، رفتار حلقه‌ای از خود نشان می‌دهد. پیش‌بینی پرش‌های غیر مستقیم دستورالعمل یک پرش غیر مستقیم می‌تواند بین دو پرش انتخاب نماید. پردازنده‌های جدیدتر Intel و AMD می‌تواند پرش‌های غیر مستقیم را با استفاده از پیش‌بینی‌کنندهٔ انطباقی دو ترازه پیش‌بینی نماید. این نوع دستور بیشتر از یک بیت در تاریخچهٔ بافر شرکت دارد پردازنده‌ها بدون این مکانیزم به آسانی پرش غیر مستقیم برای رفتن به هدف مشابه را پیش‌بینی می‌کنند همان‌طور که آخرین بار انجام داد. پیش‌بینی بازگشت‌های تابع یک تابع معمولاً به جایی که فراخوانده شده‌است بازمی‌گردد. بسیاری از ریزپردازنده‌ها مکانیزم‌های پیش‌بینی جداگانه‌ای برای دستورالعمل‌های بازگشتی دارند. پیش‌بینی overriding ارزیابی بین پیش‌بینی پرش سریع و پیش‌بینی پرش خوب گاهی اوقات باعث می‌شود که دو پیش‌بینی‌کننده پرش وجود داشته باشه. اولین پیش‌بینی‌کننده پرش سریع و ساده است و دومی کندتر، پیچیده‌تر و با جدول‌های بزرگتر می‌باشد که پیش‌بینی احتمالاً غلطی که توسط اولین پیش‌بینی حاصل شده‌است را باطل می‌کند. ریزپردازنده‌های Alpha 21264 , Alpha EV8 از پیش‌بینی‌کنندهٔ خط بعدی تک چرخه‌ای سریع برای ادارهٔ بازگشت هدف پرش و تهیهٔ پیش‌بینی سریع و ساده استفاده می‌کنند. به دلیل اینکه پیش‌بینی‌کنندهٔ خط بعدی غیر دقیق است، و بازگشت کیفیت پرش خیلی طول می‌کشد، هر دو هسته دو پیش‌بینی‌کنندهٔ پرش ثانوی دو چرخه‌ای دارند که می‌توانند پیش‌بینی پیش‌بینی‌کنندهٔ خط بعدی را در هزینهٔ یک چرخه fetch باطل کنند. مزیت اصلی پیش‌بینی‌کنندهٔ عصبی در توانایی آن برای شناسایی تاریخچه‌های بلند مدت است در حالی که تمها رشد خطی منبع را لازم دارد. پردازنده‌های ریز برنامه که از دههٔ ۱۹۶۰ تا دههٔ ۱۹۸۰ و پس از آن رایج بودند چندین چرخه برای هر دستورالعمل به کار می‌برند؛ و به تدریج در نسخه‌های جدیدتر نیاز به پیش‌بینی نداشتند. | ## جمع‌بندی | وضعیت تاریخچهٔ پرش B4900 در دستورالعمل‌های حافظهٔ آن در طول اجرای برنامه ذخیره می‌گردد.