logo
AOM / Мельник А

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

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

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

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

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

Метод повернення грунтується на передбаченні, що перехід не відбувається ніколи,

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.

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

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

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