Динамічне передбачення переходу

Динамічне передбачення переходу здійснюється в ході обчислень, виходячи з ін­формації про попередні переходи. Порівняно зі статичним динамічне передбачення має вищу точність, тобто більше припущень є правильними, але є значно складнішим.

При реалізації методів динамічного передбачення створюється таблиця історії пере­ходів.

Найпростішим варіантом є однорозрядна таблиця історії переходів, в якій зберіга­ється результат останнього виконання команди переходу. Якщо ця команда завершила­ся переходом, то у відповідну комірку таблиці записується одиниця, в іншому випадку - нуль. Передбачення переходу для чергової команди збігається із здійснимим переходом попередньої. Після виконання цієї команди, якщо передбачення не здійснилося, вміст комірки таблиці коригується.

Таблиця історії переходів реалізується в складі буфера адрес переходу (рис. 5.12). Ко­жен рядок буфера адрес переходу включає адресу команди переходу, прогнозовану адре­су наступної команди (адресу переходу) і передісторію команди переходу (рис. 5.18). Біти передісторії є інформацією про виконання або невиконання умов переходу даної коман­ди у минулому. Звернення до буфера адрес переходу (порівняння з полями адрес команд переходу) проводиться за допомогою поточного значення програмного лічильника на етапі вибірки чергової команди. За передісторією команди прогнозується виконання або невиконання умов команди переходу і проводиться вибірка та дешифрування команд із прогнозованої гілки програми. При цьому, якщо виявлений збіг, то дана команда є командою умовного переходу, і адреса переходу має бути використаною в якості наступ­ного значення програмного лічильника, якщо збігу немає, то команда не є командою переходу.

Більш ефективним є використання таблиці історії переходів з більшою розрядністю комірок. Практичне використання знайшли таблиці з дво- та трирозрядними комірка­ми. Вважається, що передісторія переходу, що містить інформацію про два попередні випадки виконання цієї команди, дозволяє прогнозувати розвиток подій з цілком до­статньою вірогідністю. При надходженні команди умовного переходу в конвеєр відбува­ється звернення до таблиці історії переходів та, залежно від вмісту відповідної комірки, робиться прогноз, який визначає подальший порядок читання команд програми. Піс­ля визначення фактичного результату переходу до вмісту комірки додається одиниця, якщо перехід відбувся, та віднімається одиниця, якщо перехід не відбувся.

В якості адреси таблиці історії переходів може бути використана адреса команди умовного переходу, вміст регістру локальної історії або регістру глобальної історії, та комбінація вказаних даних. Цим визначається вибрана стратегія динамічного перед­бачення.

Якщо в якості адреси таблиці історії переходів використовується адреса команди умовного переходу, тобто вміст програмного лічильника, як це показано на рис.5.18, то такий підхід дозволяє враховувати поведінку кожної команди умовного переходу, яка в більшості випадків є, як правило, здійсненною або, зазвичай, нездійсненною. Викорис­тання таблиці історії переходів дозволяє розділити команди із здійсненним і з нездій­сненним умовним переходом. Функціонування цього способу формування коду перед­бачення, який має назву однорівневої схеми передбачення, для випадку, коли таблиця історії переходів є кількарозрядною, показано на рис. 5.19а.

Вміст комірки, зчитаний з таблиці історії переходів за адресою з програмного лічиль­ника, записується в лічильник, в якому здійснюється додавання або віднімання одиниці. Лічильник працює в режимі насичення, тобто його вміст не змінюється при додаванні одиниці, коли він має максимальне значення, та не змінюється при відніманні одиниці, коли він має нульове значення. В якості передбачення використовується старший роз­ряд лічильника. Якщо він рівний одиниці, то передбачається, що перехід є здійсненний, якщо нуль - нездійсненний. Значення цього розряду надходить в конвеєр для керування вибіркою подальших команд, а вміст лічильника після модифікації повертається за тією ж адресою в таблицю.

Описаний підхід забезпечує високу імовірність передбачення для багатократно ви­конуваних команд переходу. Однак для одноразово виконуваних команд переходу цей підхід не діє. Тому для таких команд переходу потрібно врахувати результати перехо­ду попередніх команд, оскільки між ними є взаємозалежність, і це дозволяє підвищити кількість правильних передбачень. Для забезпечення врахування результатів переходу попередніх команд до схеми передбачення вводиться регістр глобальної історії, вміст якого відображає історію виконання n останніх команд умовного переходу, де n - розрядність регістра. Це є зсувний регістр, вміст якого зсувається на один розряд після кожного виконання команди умовного переходу, а до звільненого розряду заноситься одиниця або нуль залежно від наявності чи відсутності переходу відповідно. Кожному значенню регістра відповідає своя комірка в таблиці історії (рис. 5.196). Вміст цієї комір­ки модифікується як і в попередньому способі, а її старший розряд передбачає результат команди переходу.

Підвищення точності передбачення досягається одночасним врахуванням як ре­зультатів попереднього виконання даної команди переходу, так і результатів виконання інших команд переходу. Це реалізується формуванням адреси таблиці історії переходів шляхом об’єднання адреси команди переходу та вмісту регістру глобальної історії. Для такого об’єднання використовується або операція конкатенації (зчеплення) (рис. 5.19в), або операція додавання за модулем 2. При цьому можуть використовуватися як всі роз­ряди адреси команди переходу та вмісту регістру глобальної історії, так і лише деяка їх кількість.

Потрібно відзначити, що в якості таблиці історії переходів зазвичай використовуєть­ся асоціативна пам’ять, що дозволяє суттєво прискорити пошук коду переходу.

Наведені схеми названі однорівневими, оскільки в них задіяно один рівень таблиць. Такі схеми передбачення використані в наступних комп’ютерах: Alpha 21064 та 21064, AMD К5, R10000, Power РС620, UltraSPARC та інших.

Для врахування конкретних результатів переходів кожної команди переходу часто використовується таблиця локальної історії, яка складається з регістрів, у кожному з яких подібно до регістру глобальної історії фіксуються результати переходів конкретної команди. Дворівнева схема передбачення переходу, яка реалізує цей підхід, показана на рис. 5.20.

Для різних програм різні стратегії передбачення дають різну точність. Тому в ряді комп’ютерів застосовуються гібридні схеми передбачення переходів, коли в кожному конкретному випадку застосовується та схема передбачення, від якої очікується найви­ща точність передбачення. Структура такої гібридної схеми показана на рис. 5.21.

Адресування конкретної схеми передбачення переходу та вибір схеми передбачення переходу здійснюються від програмного лічильника, тобто адресою команди, для якої здійснюється передбачення. Оновлення таблиць історії проводиться за раніше описа­ним правилом. Такі схеми передбачення є досить складними, але забезпечують найвищу точність передбачення.

Дата добавления: 2014-11-25