Затримані переходи

Четверта схема, що використається в деяких машинах називається "затриманим переходом". У затриманому переході такт виконання із затримкою переходу довжиною n є:

Команди 1 - n перебувають у слотах (тимчасових інтервалах) затриманого переходу. Завдання програмного забезпечення полягає в тім, щоб зробити команди, що випливають за командою переходу, дійсними й корисними. Апаратура гарантує реальне виконання цих команд перед виконанням властивого переходу. Тут використаються кілька прийомів оптимізації.

На рис. 3, а показані три випадки, при яких може плануватися затриманий перехід. У верхній частині малюнка для кожного випадку показана вихідна послідовність команд, а в нижній частині - послідовність команд, отримана в результаті планування. У випадку (а) слот затримки заповнюється незалежною командою, що перебуває перед командою умовного переходу. Це найкращий вибір. Стратегії (b) і (c) використовуються, якщо застосування стратегії (a) неможливо.

У послідовностях команд для випадків (b) і (c) використання вмісту регістра R1 як умова переходу перешкоджає переміщенню команди ADD (яка записує результат у регістр R1) за команду переходу. У випадку (b) слот затримки заповнюється командою, що перебуває по цільовій адресі команди переходу. Звичайно таку команду доводиться копіювати, оскільки до неї можливі обіги й з інших частин програми. Стратегії (b) віддається перевага, коли з високою ймовірністю перехід є виконуваним, наприклад, якщо це перехід на початок циклу.

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

Рис. 3 а. Вимоги до переставляэмих команд при плануванні затриманого переходу

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

Розглянутий випадок	Вимоги	Коли збільшується продуктивність
(a)	Команда умовного переходу не повинна залежати від переставляє команды	Завжди
(b)	Виконання команды, що переставляється, повинно бути коректним, навіть якщо перехід не виконується Може знадобитися копіювання команди	Коли перехід виконується. Може збільшувати розмір програми у випадку копіювання команди
(c)	Виконання команды, що переставляється, повинно бути коректним, навіть якщо перехід виконується	Коли перехід не виконується

Рис. 3, б

Планування затриманих переходів ускладнюється (1) наявністю обмежень на команди, розміщення яких планується в слотах затримки й (2) необхідністю передбачати під час компіляції, чи буде умовний перехід виконуваним чи ні. Рис. 4 дає загальне подання про ефективність планування переходів для найпростішого конвеєра з одним слотом затримки переходу при використанні простого алгоритму планування. Він показує, що більше половини слотів затримки переходів виявляються заповненими. При цьому майже 80% заповнених слотов виявляються корисними для виконання програми. Це може здатися дивним, оскільки умовні переходи є виконуваними приблизно в 53% випадків. Високий відсоток використання заповнених слотов пояснюється тим, що приблизно половина з них заповнюється командами, що передували команді умовного переходу (стратегія (a)), виконання яких необхідно незалежно від того, чи виконується перехід, чи ні.

Рис. 4. Частота заповнення одного слота затримки умовного переходу

Є невеликі додаткові витрати апаратур на реалізацію затриманих переходів. Через затриманий ефект умовних переходів, для коректного відновлення стану у випадку появи переривання потрібні кілька лічильників команд (один плюс довжина затримки).