Оптимізація циклів

У теорії компіляторів оптимізація циклів — це процес збільшення швидкості виконання та зменшення витрат, пов'язаних із циклами.

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

Представлення обчислень і перетворень

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

Оптимізація за допомогою послідовності перетворень циклів

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

До поширених перетворень циклів належать:

• Розділення або розбиття — спроба розбити цикл на кілька циклів на одному діапазоні індексів, але щоб кожен з нових циклів містив лише частину тіла початкового циклу. Це може покращити локальність посилань, як на дані, які доступні в циклі, так і на код у тілі циклу.
• Злиття або об'єднання — полягає в об'єднанні тіл двох сусідніх циклів, які повторюються однакову кількість разів (незалежно від того, чи відоме це число під час компіляції), якщо вони не посилаються на дані один одного.
• Обмін або перестановка — обмін місцями внутрішнього та зовнішнього циклів. Коли змінні циклу індексують масив, таке перетворення може покращити локальність посилань, залежно від структури масиву.
• Інверсія — метод, за якого цикл з передумовою замінюють циклом з післяумовою, вкладений в умовний оператор, зменшуючи кількість переходів на два для випадків, коли цикл виконується. При цьому дублюється перевірка умови (зростає обсяг коду), але зростає ефективність, оскільки стрибки зазвичай викликають зупинку конвеєра. Крім того, якщо початкова умова відома під час компіляції, і відомо, що немає побічних ефектів, початкову перевірку умови можна опустити.
• Винесення інваріантного коду за межі циклу — можна значно підвищити ефективність, прибравши з тіла циклу і розмістивши перед циклом обчислення величин, однакових для кожної ітерації циклу (тобто інваріантів циклу). Це особливо важливо для виразів для обчислення адреси, використовуваних у циклах за масивами. Для правильної реалізації цей прийом слід використовувати з інверсією, оскільки не весь код безпечно переміщати за межі циклу.
• Розпаралелювання — це окремий випадок автоматичного розпаралелювання, що фокусується на циклах, змінюючи їх для ефективної роботи в багатопроцесорних системах. Це можна зробити автоматично компіляторами (автоматичне розпаралелювання) або вручну (вставляючи директиви розпаралелювання, такі як OpenMP).
• Розворот — тонка оптимізація, яка змінює порядок, у якому значення присвоюються змінній індексу. Це може допомогти усунути залежності і таким чином уможливити інші оптимізації. Деякі архітектури використовують циклічні конструкції на рівні збірки, в яких відлік ведеться лише в одному напрямку (наприклад, decrement-jump-if-not-zero [DJNZ]).
• Планування — це поділ циклу на кілька частин, які можуть виконуватися одночасно на кількох процесорах.
• Перекос — ця техніка застосовується до вкладеного циклу, що виконує ітерацію за багатовимірним масивом, де кожна ітерація внутрішнього циклу залежить від попередніх ітерацій, і змінює порядок доступу до масиву так, щоб залежності були лише між ітераціями зовнішнього циклу.
• Програмний конвеєр — тип позачергового виконання ітерацій циклу, щоб приховати затримки функціональних блоків процесора.
• Розщеплення або злущення — це спроба спростити цикл або усунути залежності, розбивши його на кілька циклів, які мають однакові тіла, але перебирають різні частини діапазону індексів. Окремий випадок — це злущення циклу, яке дозволяє спростити цикл із проблемною першою ітерацією, виконавши цю ітерацію окремо перед входом у цикл.
• Гніздова оптимізація — реорганізує цикл для опрацювання блоків даних, які поміщаються в кеш.
• Векторизація — спроба одночасно запустити якомога більше ітерацій циклу в системі SIMD.
• Розмотування — дублює тіло циклу кілька разів, щоб зменшити кількість перевірок умови циклу та кількість стрибків, які можуть знизити продуктивність через погіршення роботи конвеєра інструкцій. Повне розмотування циклу усуває всі накладні витрати (крім вибірки кількох інструкцій і збільшення часу завантаження програми), але вимагає, щоб кількість ітерацій була відомою під час компіляції (крім випадку JIT-компіляції). Необхідно також подбати про те, щоб багаторазовий перерахунок індексованих змінних не вимагав більших витрат, ніж просування покажчиків у початковому циклі.
• Розмикання — переміщує умовний оператор з тіла циклу назовні, копіюючи тіло циклу та розміщуючи його версію в кожній з гілок якщо та інакше.
• Секціювання або стрип-майнінг — запроваджене для векторних процесорів, секціювання циклу є технікою його перетворення для уможливлення SIMD-кодування циклів і підвищення продуктивності пам'яті. Це забезпечує, що кожна векторна операція виконується над вектором, розмір якого менший або рівний найбільшій довжині вектора даної векторної машини.

Схема унімодулярного перетворення

Унімодулярне перетворення використовує одну унімодулярну матрицю для опису комбінованого результату послідовності багатьох з перелічених вище перетворень. Центральним у цьому підході є погляд на множину всіх виконань оператора в межах n циклів як на набір цілих точок у n-вимірному просторі, причому точки виконуються в лексикографічному порядку. Наприклад, виконання оператора, вкладеного в зовнішній цикл з індексом i та внутрішній цикл з індексом j, можна пов'язати з парами цілих чисел $(i,j)$. Застосування унімодулярного перетворення відповідає множенню точок у цьому просторі на матрицю. Наприклад, заміна двох циклів відповідає матриці ${\begin{bmatrix}0&1\\1&0\end{bmatrix}}$.

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

Багатогранна схема або схема на основі обмежень

Поліедральна модель опрацьовує ширший клас програм і перетворень, ніж унімодулярна схема. Множина виконань набору операторів у межах, можливо, неідеально вкладеного набору циклів, розглядається як об'єднання набору політопів, які подають виконання операторів. До цих політопів застосовують афінні перетворення, які дають опис нового порядку виконання. Межі політопів, залежності даних і перетворення часто описуютья за допомогою систем обмежень, і цей підхід часто називають підходом до оптимізації циклів на основі обмежень. Наприклад, один оператор у зовнішньому циклі 'for i := 0 to n ' і внутрішньому циклі 'for j := 0 to i+2 ' виконується один раз для кожної пари (i, j) так, що 0 <= i <= n і 0 <= j <= i+2.

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

Див. також

• Масштабований паралелізм