ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6833
Скачиваний: 22
Метод повернення грунтується на передбаченні, що перехід не відбувається ніколи,
184
або що перехід відбувається завжди. В першому випадку умовний перехід прогнозується як нездійсненний. При цьому апаратура повинна просто продовжувати виконання програми, неначебто умовний перехід зовсім не виконувався. В цьому випадку необхідно поклопотатися про те, щоб не змінити стан комп'ютера до тих пір, поки напрям переходу не стане остаточно відомим.
У деяких комп'ютерах ця схема з нездійсненними за прогнозом умовними переходами реалізована шляхом продовження вибірки команд, неначе умовний перехід був звичайною командою. Поведінка конвеєра виглядає так, ніби нічого незвичайного не відбувається (рис. 5.17а). Проте, якщо умовний перехід насправді виконується, то необхідно просто очистити конвеєр від команд, вибраних слідом за командою умовного переходу, і заново повторити вибірку команд (рис. 5.17b). Розглянемо фрагмент програми loop:
lw r2,0(rl)
lw r3,20(rl)
addi rl,rl,#4
subi r4,rl,#16
add r2,r2,r3
sw 36(rl),r2
bnez r4,loop
xor r7,r8,r5
and r2,rl,r5
add r3,r8,r2
trap 0
185
Альтернативна схема прогнозує перехід як здійсненний. Як тільки команда умовного переходу декодована і обчислена цільова адреса переходу, припускається, що перехід здійсненний, і проводиться вибірка команд та їх виконання, починаючи з цільової адреси.
Метод повернення є простим в реалізації і достатньо ефективним для деяких класів програм, тому широко використовується в комп'ютерах, зокрема в MIPS-X, SuperSPARC, I486, М68020, МС88000, VAX11/780.
Під профілюванням розуміється виконання програми для деякого еталонного набору вихідних даних, в процесі якого збирається інформація про результат кожної команди умовного переходу. Тобто тут прогноз переходів базується на інформації про профіль виконання програми, зібраної під час попередніх її проходжень. Ключовим моментом тут є те, що поведінка переходів при виконанні програми часто повторюється. Ті команди, які частіше закінчуються переходом, прогнозуються як здійсненні, інші - як нездійсненні. Вибір фіксується в спеціальному розряді команди. При виконанні програми конвеєр команд враховує значення цього розряду. Проведені дослідження показують. достатньо успішне прогнозування переходів з використанням цієї стратегії.
Іще одним досить простим і ефективним є метод статичного передбачення умовного переходу за кодом операції команди переходу. Тут одні команди прогнозуються як здійсненні, наприклад "більше нуля" а інші - як нездійсненні, наприклад "переповненої"
Перехід в програмі може відбутися в двох напрямках - вперед або назад, залежно від того, більша адреса переходу від вмісту програмного лічильника чи менша. Логічно передбачити, що команди з напрямком переходу назад є більш імовірними, ніж команди переходу вперед, оскільки більшість команд переходу використовується для організації циклів, коли відбуваються переходи до початку циклу. Ця стратегія і покладена в основу методу передбачення результату переходу за напрямом переходу.
5.3.3.5. Динамічне передбачення переходу
Динамічне передбачення переходу здійснюється в ході обчислень, виходячи з інформації про попередні переходи. Порівняно зі статичним динамічне передбачення має вищу точність, тобто більше припущень є правильними, але є значно складнішим.
При реалізації методів динамічного передбачення створюється таблиця історії переходів.
Найпростішим варіантом є однорозрядна таблиця історії переходів, в якій зберігається результат останнього виконання команди переходу. Якщо ця команда завершилася переходом, то у відповідну комірку таблиці записується одиниця, в іншому випадку -нуль. Передбачення переходу для чергової команди збігається із здійснимим переходом попередньої. Після виконання цієї команди, якщо передбачення не здійснилося, вміст комірки таблиці коригується.
Таблиця історії переходів реалізується в складі буфера адрес переходу (рис. 5.12). Кожен рядок буфера адрес переходу включає адресу команди переходу, прогнозовану адресу наступної команди (адресу переходу) і передісторію команди переходу (рис. 5.18). Біти передісторії є інформацією про виконання або невиконання умов переходу даної команди у минулому. Звернення до буфера адрес переходу (порівняння з полями адрес команд переходу) проводиться за допомогою поточного значення програмного лічильника на етапі вибірки чергової команди. За передісторією команди прогнозується виконання або
186
невиконання умов команди переходу і проводиться вибірка та дешифрування команд із прогнозованої гілки програми. При цьому, якщо виявлений збіг, то дана команда є командою умовного переходу, і адреса переходу має бути використаною в якості наступного значення програмного лічильника, якщо збігу немає, то команда не є командою переходу.
Більш ефективним є використання таблиці історії переходів з більшою розрядністю комірок. Практичне використання знайшли таблиці з дво- та трирозрядними комірками. Вважається, що передісторія переходу, що містить інформацію про два попередні випадки виконання цієї команди, дозволяє прогнозувати розвиток подій з цілком достатньою вірогідністю. При надходженні команди умовного переходу в конвеєр відбувається звернення до таблиці історії переходів та, залежно від вмісту відповідної комірки, робиться прогноз, який визначає подальший порядок читання команд програми. Після визначення фактичного результату переходу до вмісту комірки додається одиниця, якщо перехід відбувся, та віднімається одиниця, якщо перехід не відбувся.
В якості адреси таблиці історії переходів може бути використана адреса команди умовного переходу, вміст регістру локальної історії або регістру глобальної історії, та комбінація вказаних даних. Цим визначається вибрана стратегія динамічного передбачення.
Якщо в якості адреси таблиці історії переходів використовується адреса команди умовного переходу, тобто вміст програмного лічильника, як це показано на рис.5.18, то такий підхід дозволяє враховувати поведінку кожної команди умовного переходу, яка в більшості випадків є, як правило, здійсненною або, зазвичай, нездійсненною. Використання таблиці історії переходів дозволяє розділити команди із здійсненним і з нездійсненним умовним переходом. Функціонування цього способу формування коду передбачення, який має назву однорівневої схеми передбачення, для випадку, коли таблиця історії переходів є кількарозрядною, показано на рис. 5.19а.
187
Вміст комірки, зчитаний з таблиці історії переходів за адресою з програмного лічильника, записується в лічильник, в якому здійснюється додавання або віднімання одиниці. Лічильник працює в режимі насичення, тобто його вміст не змінюється при додаванні одиниці, коли він має максимальне значення, та не змінюється при відніманні одиниці, коли він має нульове значення. В якості передбачення використовується старший розряд лічильника. Якщо він рівний одиниці, то передбачається, що перехід є здійсненний, якщо нуль - нездійсненний. Значення цього розряду надходить в конвеєр для керування вибіркою подальших команд, а вміст лічильника після модифікації повертається за тією ж адресою в таблицю.
Описаний підхід забезпечує високу імовірність передбачення для багатократно виконуваних команд переходу. Однак для одноразово виконуваних команд переходу цей підхід не діє. Тому для таких команд переходу потрібно врахувати результати переходу попередніх команд, оскільки між ними є взаємозалежність, і це дозволяє підвищити кількість правильних передбачень. Для забезпечення врахування результатів переходу попередніх команд до схеми передбачення вводиться регістр глобальної історії, вміст якого відображає історію виконання п останніх команд умовного переходу, де п - роз-рядність регістра. Це є зсувний регістр, вміст якого зсувається на один розряд після кожного виконання команди умовного переходу, а до звільненого розряду заноситься одиниця або нуль залежно від наявності чи відсутності переходу відповідно. Кожному значенню регістра відповідає своя комірка в таблиці історії (рис. 5.196). Вміст цієї комірки модифікується як і в попередньому способі, а її старший розряд передбачає результат команди переходу.
Підвищення точності передбачення досягається одночасним врахуванням як результатів попереднього виконання даної команди переходу, так і результатів виконання інших команд переходу. Це реалізується формуванням адреси таблиці історії переходів