3. Статичне прогнозування умовних переходів: використання технології компіляторів

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

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

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

Контрольні запитання

1. Чому конфлікти по керуванню викликають відчутні втрати продуктивності процесора?

2. Яким способами може бути зменшено число втрачених тактів процесора через умовні переходи?

3. Які існують методи скорочення припинень конвеєра через затримки виконання умовних переходів засобами компілятора?

4. У чому полягає прогнозування умовних переходів з використанням технології компіляторів?

Рекомендована література

1. Самофалов и др. Основы теории многоуровневых конвеерных вычислительных систем. – К.,”Техніка”, 1980.

2. Корнеев В.В., Киселев А.В. Современные микропроцессоры. – М., „Нолидж”, 1998.

Лекція 7. Проблеми реалізації точного переривання в конвеєрі

План лекції

1. Проблеми реалізації точного переривання в конвеєрі.

2. Обробка багатотактних операцій і механізмів обходів у довгих конвеєрах.

3. Конфлікти й прискорені пересилання в довгих конвеєрах.

4. Підтримка точних переривань.

Виклад лекції

1. Проблеми реалізації точного переривання в конвеєрі

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

Як і в неконвеєрних машинах двома основними проблемами при реалізації переривань є: (1) переривання виникають у процесі виконання деякої команди; (2) необхідний механізм повернення з переривання для продовження виконання програми. Наприклад, для нашого найпростішого конвеєра переривання по відсутності сторінки віртуальної пам'яті при вибірці даних не може відбутися до етапу вибірки з пам'яті (MEM). У момент виникнення цього переривання в процесі обробки вже будуть перебувати кілька команд. Оскільки подібне переривання повинне забезпечити повернення для продовження програми й вимагає перемикання на інший процес (операційну систему), необхідно надійно очистити конвеєр і зберегти стан машини таким, щоб повторне виконання команди після повернення з переривання здійснювалося при коректному стані машини. Звичайно це реалізується шляхом збереження адреси команди (PC), що викликала переривання. Якщо обрана після повернення з переривання команда не є командою переходу, то зберігається звичайна послідовність вибірки й обробки команд у конвеєрі. Якщо ж це команда переходу, то ми повинні оцінити умову переходу й залежно від обраного напрямку почати вибірку або по цільовій адресі команди переходу, або наступної за переходом команди. Коли відбувається переривання, для коректного збереження стану машини необхідно виконати наступні кроки:

1. У послідовність команд, що надходять на обробку в конвеєр, примусово вставити команду переходу на переривання.

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

3. Після передачі керування підпрограмі обробки переривань операційної системи, вона негайно повинна зберегти значення адреси команди (PC), що викликала переривання. Це значення буде використовуватися пізніше для організації повернення з переривання.

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

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

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

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

Щабель конвеєра	Причина переривання
IF	Помилка при звертанні до сторінки пам'яті при вибірці команди; невирівняне звертання до пам'яті; порушення захисту пам'яті
ID	Невизначений або заборонений код операції
EX	Арифметичне переривання
MEM	Помилка при звертанні до сторінки пам'яті при вибірці даних; невирівняне звертання до пам'яті; порушення захисту пам'яті
WB	Відсутній

Рис. 1. Причини переривань у найпростішому конвеєрі