Статичне передбачення переходу

Затримка переходу

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

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

Пошук таких команд здійснюється на етапі компіляції програми, а якщо знайдена їх кількість недостатня, то на вільні місця вставляються команди типу «немає операції».

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

На даний час розроблено багато способів передбачення переходу. Залежно від того, на основі чого робиться передбачення, розрізняють статичне та динамічне передбачення переходів.

Статичне передбачення переходів здійснюється на етапі компіляції програми на основі деякої апріорної інформації про неї. Найширше застосування знайшли наступні методи статичного передбачення умовного переходу:

- метод повернення;

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

- результат переходу визначається кодом операції команди переходу;

- результат переходу визначається напрямом переходу.

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

У деяких комп’ютерах ця схема з нездійсненними за прогнозом умовними перехода­ми реалізована шляхом продовження вибірки команд, неначе умовний перехід був зви­чайною командою. Поведінка конвеєра виглядає так, ніби нічого незвичайного не відбу­вається (рис. 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

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

Метод повернення є простим в реалізації і достатньо ефективним для деяких класів програм, тому широко використовується в комп’ютерах, зокрема в МІРS-Х, SuреrSРАRС, I486, М68020, МС88000, УАХ11/780.

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

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

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

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