logo
AOM / Мельник А

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

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

Для виявлення конфліктуючих команд в оптимізуючому компіляторі потрібно реа­лізувати відповідні засоби аналізу команд. Ознаками наявності конфліктів за даними є наступні

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

Статична диспетчеризація послідовності команд у програмі під час компіляції ви­користовувалася, починаючи з 60-х років минулого століття, і викликала підвищений інтерес у 80-х роках, коли конвеєрні машини стали поширенішими

Нехай, наприклад, є послідовність операторів: a=b+c;d=e-f.Нижче наведена не оптимізована програма для виконання цих операторів

LWг2,0(г0)

LW гЗ,4(гО)

ADDг4,г2,гЗ

175

SW 8(r0),r4 LW r5,12(rO) LW r6,16(rO) SUB r7,r5,r6 SW 20(r0),r7

Вхідні дані та результати цієї програми розміщені в комірках пам'яті даних, наведе­них в табл. 5.1.

Таблиця 5.1

Операнд

Адреса комірки пам'яті

a

8

b

0

c

4

d

20

e

12

f

16

Діаграма виконання програми приведена на рис. 5.9. Як видно з рисунка, тут наявні чотири затримки, викликанані залежністю за даними: друга і третя команди - звернення до регістра гЗ, третя і четверта команди - звернення до регістра г4, шоста і сьома коман­ди - звернення до регістра гб, сьома і восьма команди - звернення до регістра г7.

Знаходимо конфліктуючі команди в наведеній вище програмі та розводемо їх в часі. Нижче наведена оптимізована програма для виконання тих же операторів

LWг2,0(г0) LW гЗ,4(гО) LWr5,12(rO)LWr6,16(rO)

ADDг4,г2,гЗ SUB г7,г5,г6 SW8(r0),r4SW20(r0),r7

176

Вхідні дані та результати розміщені в тих же комірках пам'яті, приведених в табл. 5.1. Тоді діаграма виконання програми буде мати вигляд, як це приведено на рис. 5.10 (отри­мана з використанням симулятора WinDLX).

Як наслідок, повністю усунені два блокування (стосовно регістрів гЗ і г4), та в двох блокуваннях (стосовно гб і г7) забрано по одному такту затримки. Тобто в цілому забра­но б тактів. Залежності, які залишилися, можна забрати, використавши схеми обходу.

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

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