4. Основи планування завантаження конвеєра й розгортання циклів

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

Команда, що виробляє результат	Команда, що використає результат	Затримка в тактах
Операція АЛУ із ПК	Інша операція АЛУ із ПК	3
Операція АЛУ із ПК	Запис подвійного слова	2
Завантаження подвійного слова	Інша операція АЛУ із ПК	1
Завантаження подвійного слова	Запис подвійного слова	0

Рис. 2.

У даному короткому розділі ми розглянемо питання про те, яким чином компілятор може збільшити ступінь паралелізму рівня команд шляхом розгортання циклів. Для ілюстрації цих методів ми будемо використати простий цикл, що додає скалярну величину до вектора в пам'яті; це паралельний цикл, оскільки залежність між ітераціями циклу відсутній. Ми припускаємо, що спочатку в регістрі R1 перебуває адреса останнього елемента вектора (наприклад, елемент із найбільшою адресою), а в регістрі F2 - скалярна величина, що повинна додаватися до кожного елемента вектора. Програма для машини, не розрахована на використання конвеєра, буде виглядати приблизно так:

Loop: LD F0,0(R1) ;F0=елемент вектора

ADDD F4,F0,F2 ;додає скаляр з F2

SD 0(R1),F4 ;запис результату

SUBI R1,R1,#8 ;перерахувати покажчик

;8 байт (у подвійному слові)

BNEZ R1, Loop ;перехід R1!=нулю

Для спрощення ми припускаємо, що масив починається з комірки 0. Якби він перебував у будь-якому іншому місці, цикл зажадав би наявності однієї додаткової цілочисельнї команди для виконання порівняння з регістром R1.

Розглянемо роботу цього циклу при виконанні на простому конвеєрі із затримками, показаними на рис. 2.

Якщо не робити ніякого планування, робота циклу буде виглядати в такий спосіб:

Такт видачі

Loop: LD F0,0(R1) 1

припинення 2

ADDD F4,F0,F2 3

припинення 4

припинення 5

SD 0(R1),F4 6

SUBI R1,R1,#8 7

BNEZ R1,Loop 8

припинення 9

Для його виконання буде потрібно 9 тактів на ітерацію: одне припинення для команди LD, дві для команди ADDD, і одна для затриманого переходу. Ми можемо спланувати цикл так, щоб одержати

Loop: LD F0,0(R1) 1

припинення 2

ADDD F4,F0,F2 3

SUBI R1,R1,#8 4

BNEZ R1,Loop ;затриманий перехід 5

SD 8(R1),F4 ;команда змінюється, коли 6

;чергується місцями з командою SUB1

Час виконання зменшився з 9 до 6 тактів.

Помітимо, що для планування затриманого переходу компілятор повинен визначити, що він може поміняти місцями команди SUB1 і SD шляхом зміни адреси в команді запису SD: Адреса була дорівнює 0(R1), а тепер дорівнює 8(R1). Це не тривіальне завдання, оскільки більшість компіляторів будуть бачити, що команда SD залежить від SUB1, і відмовляться від такої перестановки місць. Більше витончений компілятор зміг би розрахувати відносини й виконати перестановку. Ланцюжок залежностей від команди LD до команди ADDD і далі до команди SD визначає кількість тактів, необхідне для даного циклу.

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

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

Уявіть тепер цей цикл розгорнутим так, що є чотири копії тіла циклу, припускаючи, що R1 спочатку кратно 4. Усунемо при цьому будь-які очевидні зайві обчислення й не будемо користуватися повторно ніякими регістрами.

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

Loop: LD F0,0(R1)

ADDD F4,F0,F2

SD 0(R1),F4 ;викидається SUB1 і BNEZ

LD F6,-8(R1)

ADDD F8,F6,F2

SD -8(R1),F8 ;викидається SUB1 і BNEZ

LD F10,-16(R1)

ADDD F12,F10,F2

SD -16(R1),F12 ;викидається SUB1 і BNEZ

LD F14,-24(R1)

ADDD F16,F14,F2

SD -24(R1),F16

SUB1 R1,R1,#32

BNEZ R1, Loop

Ми ліквідували три умовних переходи й три операції декрементування R1. Адреси команд завантаження й записи були скоректовані так, щоб дозволити злити команди SUB1 в одну команду по регістру R1. При відсутності планування за кожною командою тут йде залежна команда і це буде призводити до призупинки конвеєра. Цей цикл буде виконуватися за 27 тактів (на кожну команду LD буде потрібно 2 такти, на кожну команду ADDD - 3, на умовний перехід - 2 і на всі інші команди 1 такт) або по 6.8 такту на кожний із чотирьох елементів. Хоча ця розгорнута версія в такій редакції повільніше, ніж оптимізована версія вихідного циклу, після оптимізації самого розгорнутого циклу ситуація зміниться. Звичайне розгортання циклів виконується на більше ранніх стадіях процесу компіляції, так що надлишкові обчислення можуть бути виявлені й усунуті оптимізатором.

У реальних програмах ми звичайно не знаємо верхньої границі циклу. Припустимо, що вона дорівнює n і ми хотіли б розгорнути цикл так, щоб мати k копій тіла циклу. Замість єдиного розгорнутого циклу ми генеруємо пару циклів. Перший з них виконується (n mod k) раз і має тіло первісного циклу. Розгорнута версія циклу оточується зовнішнім циклом, що виконується (n div k) раз.

У вищенаведеному прикладі розгортання циклу збільшує продуктивність цього циклу шляхом усунення команд, пов'язаних з накладними витратами циклу, хоча воно помітно збільшує розмір програмного коду. Наскільки збільшиться продуктивність, якщо цикл буде оптимізуватися?

Нижче представлений розгорнутий цикл із попереднього приклада після оптимізації.

Loop: LD F0,0(R1)

LD F6,-8(R1)

LD F10,-16(R1)

LD F14,-24(R1)

ADDD F4,F0,F2

ADDD F8,F6,F2

ADDD F12,F10,F2

ADDD F16,F14,F2

SD 0(R1),F4

SD -8(R1),F8

SD -16(R1),F12

SUB1 R1,R1,#32

BNEZ R1, Loop

SD 8(R1),F16 ; 8 - 32 = -24

Час виконання розгорнутого циклу знизилося до 14 тактів або до 3.5 тактів на елемент, у порівнянні з 6.8 тактів на елемент до оптимізації, і в порівнянні з 6 тактами при оптимізації без розгортання циклу.

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

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