7. Методика планування компілятора для усунення конфліктів за даними

Багато типів припинень конвеєра можуть відбуватися досить часто. Наприклад, для оператора А = B + С компілятор швидше за все згенерує наступну послідовність команд (рис.8):

LW R1,В	IF	ID	EX	MEMWB
LW R2,С		IF	ID	EXMEMWB
ADD R3,R1,R2			IF	IDstallEXMEMWB
SW A,R3				IF stallIDEXMEMWB

Рис. 8. Конвеєрне виконання оператора А = В + С

Очевидно, виконання команди ADD повинне бути припинене доти, доки не стане доступним надходячий з пам'яті операнд C. Додаткової затримки виконання команди SW не відбудеться у випадку застосування ланцюгів обходу для пересилання результату операції АЛУ безпосередньо в регістр дані пам'яті для наступного запису.

Для даного простого приклада компілятор ніяк не може поліпшити ситуацію, однак у ряді більше загальних випадків він може реорганізувати послідовність команд так, щоб уникнути припинень конвеєра. Ця техніка, називана плануванням завантаження конвеєра (pipeline scheduling) або плануванням потоку команд (instruction scheduling), використалася починаючи з 60-х років і стала особливою областю інтересу в 80-х роках, коли конвеєрні машини стали більше розповсюдженими.

Нехай, наприклад, є послідовність операторів: a = b + c; d = e - f;

Як згенерувати код, що не викликає зупинок конвеєра? Передбачається, що затримка завантаження з пам'яті становить один такт. Відповідь очевидна (рис. 9):

Неоптимізована послідовність команд	Оптимізована послідовність команд
LW Rb,b	LW Rb,b
LW Rc,c	LW Rc,c
ADD Ra,Rb,Rc	LW Re,e
SW a,Ra	ADD Ra,Rb,Rc
LW Re,e	LW Rf,f
LW Rf,f	SW a,Ra
SUB Rd,Re,Rf	SUB Rd,Re,Rf
SW d,Rd	SW d,Rd

Рис. 9. Приклад усунення конфліктів компілятором

У результаті усунуті обидва блокування (командою LW R_c,c команди ADD R_a,R_b,R_c і командою LW R_f,f команди SUB R_d,R_e,R_f). Є залежність між операцією АЛУ й операцією запису на згадку, але структура конвеєра допускає пересилання результату за допомогою ланцюгів "обходу". Помітимо, що використання різних регістрів для першого й другого операторів було досить важливим для реалізації такого правильного планування. Зокрема, якщо змінна e була б завантажена в той же самий регістр, що b або c, таке планування не було б коректним. У загальному випадку планування конвеєра може вимагати збільшеної кількості регістрів. Таке збільшення може виявитися особливо істотним для машин, які можуть видавати на виконання кілька команд в одному такті.

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

На щастя, існують апаратні методи, що дозволяють змінити порядок виконання команд програми так, щоб мінімізувати припинення конвеєра. Ці методи одержали загальну назву методів динамічної оптимізації (в англомовній літературі останнім часом часто застосовуються також терміни "out-of-order execution" - неупорядковане виконання й "out-of-order issue" - неупорядкована видача). Основними засобами динамічної оптимізації є:

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

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

3. Відповідна організація комутуючих магістралей, що забезпечує засилання результату операції безпосередньо в буфер, що зберігає логічно залежну команду, затриману через конфлікт, або безпосередньо на вхід функціонального пристрою до того, як цей результат буде записаний у регістровий файл або на згадку (short-circuiting, data forwarding, data bypassing - методи, які були розглянуті раніше).

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

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

У процесі виконання програми генерується безліч тимчасових регістрових результатів. Ці тимчасові значення записуються в регістрові файли разом з постійними значеннями. Тимчасове значення стає новим постійним значенням, коли завершується виконання команди (фіксується її результат). У свою чергу, завершення виконання команди відбувається, коли всі попередні команди успішно завершилися в заданому програмою порядку.

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

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