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

У [[Компілятор|теорії компіляторів]] '''оптимізація циклів'''&nbsp;— це процес збільшення швидкості виконання та зменшення витрат, пов'язаних із [[Потік керування|циклами]].

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

== Представлення обчислень і перетворень ==
Оскільки інструкції всередині циклів можуть виконуватися багаторазово, часто неможливо встановити межу кількості виконання інструкцій, на які вплине оптимізація циклу. Це створює проблеми під час оцінювання правильності й переваг оптимізації циклів, зокрема подання оптимізованого обчислення та виконуваної оптимізації<ref name="Collard">У книзі ''[https://books.google.com/books?id=8FbTZc4pa-cC&printsec=frontcover#v=snippet&q=%22loop%20optimization%22&f=false Reasoning About Program Transformations]'', Жан-Франсуа Коллар докладно обговорює загальні питання подання виконання програм, а не тексту програми в контексті статичної оптимізації.</ref>.

== Оптимізація за допомогою послідовності перетворень циклів ==
Оптимізацію циклів можна розглядати як застосування послідовності певних '''перетворень циклів''' (перерахованих нижче або в документі ''Перетворення компілятора для високопродуктивних обчислень''<ref name="UCB">David F. Bacon, [[Susan L. Graham]], and Oliver J. Sharp. ''Compiler transformations for high-performance computing''. Report No. UCB/CSD 93/781, Computer Science Division-EECS, University of California, Berkeley, Berkeley, California 94720, November 1993 (доступна на [[CiteSeer]]). Наведено аналіз компілятора, такий як аналіз залежності даних і міжпроцедурний аналіз, а також дуже повний список перетворень циклів.</ref>) до [[Початковий код|сирцевого коду]] або {{Нп|Проміжне подання|проміжного подання|en|Intermediate representation}}, при цьому кожне перетворення має відповідний тест валідності. Перетворення (або послідовність перетворень) загалом має зберігати часову послідовність усіх [[Залежність даних|залежностей]], щоб не змінити результату роботи програми (тобто бути валідним перетворенням). В рамках цього підходу оцінити переваги перетворення або послідовності перетворень буває досить складно, оскільки застосування одного корисного перетворення може вимагати попереднього застосування одного або кількох інших перетворень, які самі по собі призводять до зниження продуктивності.

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

* {{Нп|Розділення і злиття циклів|Розділення|en|Loop fission and fusion}} або розбиття&nbsp;— спроба розбити цикл на кілька циклів на одному діапазоні індексів, але щоб кожен з нових циклів містив лише частину [[Цикл (програмування)#Визначення|тіла]] початкового циклу. Це може покращити {{Нп|локальність посилань|3=en|4=Locality of reference}}, як на дані, які доступні в циклі, так і на код у тілі циклу.
* {{Нп|Розділення і злиття циклів|Злиття|en|Loop fission and fusion}} або об'єднання&nbsp;— полягає в об'єднанні тіл двох сусідніх циклів, які повторюються однакову кількість разів (незалежно від того, чи відоме це число під час компіляції), якщо вони не посилаються на дані один одного.
* {{Нп|Перестановка циклів|Обмін|en|Loop interchange}} або перестановка&nbsp;— обмін місцями внутрішнього та зовнішнього циклів. Коли змінні циклу індексують масив, таке перетворення може покращити локальність посилань, залежно від структури масиву.
* [[Інверсія циклу|Інверсія]]&nbsp;— метод, за якого [[Цикл (програмування)#Цикл з передумовою|цикл з передумовою]] замінюють [[Цикл (програмування)#Цикл%20з%20післяумовою|циклом з післяумовою]], вкладений в умовний оператор, зменшуючи кількість переходів на два для випадків, коли цикл виконується. При цьому дублюється перевірка умови (зростає обсяг коду), але зростає ефективність, оскільки стрибки зазвичай викликають {{Нп|Зупинка конвеєра|зупинку конвеєра|en|Pipeline stall}}. Крім того, якщо початкова умова відома під час компіляції, і відомо, що немає [[Побічний ефект (програмування)|побічних ефектів]], початкову перевірку умови можна опустити.
* {{Нп|Винесення інваріантного коду|Винесення інваріантного коду за межі циклу|en|Loop-invariant code motion}}&nbsp;— можна значно підвищити ефективність, прибравши з тіла циклу і розмістивши перед циклом обчислення величин, однакових для кожної ітерації циклу (тобто інваріантів циклу). Це особливо важливо для виразів для обчислення адреси, використовуваних у циклах за масивами. Для правильної реалізації цей прийом слід використовувати з інверсією, оскільки не весь код безпечно переміщати за межі циклу.
* {{Нп|Розпаралелювання циклів|Розпаралелювання|en|Loop-level parallelism}}&nbsp;— це окремий випадок [[Автоматичне розпаралелення|автоматичного розпаралелювання, що]] фокусується на циклах, змінюючи їх для ефективної роботи в багатопроцесорних системах. Це можна зробити автоматично компіляторами ([[Автоматичне розпаралелення|автоматичне розпаралелювання]]) або вручну (вставляючи директиви розпаралелювання, такі як [[OpenMP]]).
* Розворот&nbsp;— тонка оптимізація, яка змінює порядок, у якому значення присвоюються змінній індексу. Це може допомогти усунути {{Нп|Аналіз залежностей|залежності|en|Dependence analysis}} і таким чином уможливити інші оптимізації. Деякі архітектури використовують циклічні конструкції на [[Мова асемблера|рівні збірки]], в яких відлік ведеться лише в одному напрямку (наприклад, decrement-jump-if-not-zero [DJNZ]<ref>{{Cite web|url=https://www.win.tue.nl/~aeb/comp/8051/set8051.html-orig#51djnz|title=8051 Instruction Set|website=www.win.tue.nl|accessdate=2019-12-09}}</ref>).
* {{Нп|Планування циклу|Планування|en|Loop scheduling}}&nbsp;— це поділ циклу на кілька частин, які можуть виконуватися одночасно на кількох процесорах.
* {{Нп|Політопна модель|Перекос|en|Polytope model}}&nbsp;— ця техніка застосовується до вкладеного циклу, що виконує ітерацію за багатовимірним масивом, де кожна ітерація [[Цикл (програмування)#Вкладені цикли|внутрішнього циклу]] залежить від попередніх ітерацій, і змінює порядок доступу до масиву так, щоб залежності були лише між ітераціями зовнішнього циклу.
* {{Нп|Програмний конвеєр|3=en|4=Software pipelining}}&nbsp;— тип [[Позачергове виконання|позачергового виконання]] ітерацій циклу, щоб приховати затримки функціональних блоків процесора.
* [[Розщеплення циклу|Розщеплення]] або злущення&nbsp;— це спроба спростити цикл або усунути залежності, розбивши його на кілька циклів, які мають однакові тіла, але перебирають різні частини діапазону індексів. Окремий випадок&nbsp;— ''це злущення циклу'', яке дозволяє спростити цикл із проблемною першою ітерацією, виконавши цю ітерацію окремо перед входом у цикл.
* {{Нп|Гніздова оптимізація циклів|Гніздова оптимізація|en|Loop nest optimization}}&nbsp;— реорганізує цикл для опрацювання блоків даних, які поміщаються в кеш.
* {{Нп|Автоматична векторизація|Векторизація|en|Automatic vectorization}}&nbsp;— спроба одночасно запустити якомога більше ітерацій циклу в системі [[SIMD]].
* [[Розмотування циклу|Розмотування]]&nbsp;— дублює тіло циклу кілька разів, щоб зменшити кількість перевірок умови циклу та кількість стрибків, які можуть знизити продуктивність через погіршення роботи конвеєра інструкцій. Повне розмотування циклу усуває всі накладні витрати (крім вибірки кількох інструкцій і збільшення часу завантаження програми), але вимагає, щоб кількість ітерацій була відомою під час компіляції (крім випадку [[JIT-компіляція|JIT-компіляції]]). Необхідно також подбати про те, щоб багаторазовий перерахунок індексованих змінних не вимагав більших витрат, ніж просування покажчиків у початковому циклі.
* {{Не перекладено|Розмикання циклу|Розмикання|en|Loop unswitching}}&nbsp;— переміщує [[Умовний перехід|умовний оператор]] з тіла циклу назовні, копіюючи тіло циклу та розміщуючи його версію в кожній з гілок ''якщо'' та ''інакше''.
* {{Нп|Секціювання циклу|Секціювання|en|Loop sectioning}} або стрип-майнінг&nbsp;— запроваджене для [[Векторний процесор|векторних процесорів]], секціювання циклу є технікою його перетворення для уможливлення [[SIMD]]-кодування циклів і підвищення продуктивності пам'яті. Це забезпечує, що кожна векторна операція виконується над вектором, розмір якого менший або рівний найбільшій довжині вектора даної векторної машини<ref>{{Cite web|url=http://software.intel.com/en-us/articles/strip-mining-to-optimize-memory-use-on-32-bit-intel-architecture/|title=Intel Developer Zone}}</ref><ref>{{Cite web|url=http://download.oracle.com/docs/cd/E19205-01/819-5262/aeugr/index.html|title=7.6.3.1 Strip-Mining (Sun Studio 12: Fortran Programming Guide)}}</ref>.

=== Схема унімодулярного перетворення ===
Унімодулярне перетворення<ref name="Muchnick">Steven S. Muchnick, ''[https://books.google.com/books?id=Pq7pHwG1_OkC&printsec=frontcover#v=snippet&q=%22unimodular%20transformation%22&f=false Advanced Compiler Design and Implementation]'', 1997 Morgan Kaufmann. В розділі 20.4.2 обговорюється оптимізація циклів.</ref> використовує одну [[Унімодулярна матриця|унімодулярну матрицю]] для опису комбінованого результату послідовності багатьох з перелічених вище перетворень. Центральним у цьому підході є погляд на множину всіх виконань оператора в межах ''n'' циклів як на набір цілих точок у ''n''-вимірному просторі, причому точки виконуються в [[Лексикографічний порядок|лексикографічному порядку]]. Наприклад, виконання оператора, вкладеного в зовнішній цикл з індексом ''i'' та внутрішній цикл з індексом ''j'', можна пов'язати з парами цілих чисел {{Tmath|(i, j)}}. Застосування унімодулярного перетворення відповідає множенню точок у цьому просторі на матрицю. Наприклад, заміна двох циклів відповідає матриці <math>\begin{bmatrix}0&1\\1&0\end{bmatrix}</math>.

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

=== Багатогранна схема або схема на основі обмежень ===
{{Нп|Поліедральна модель|3=en|4=Polytope model}}<ref name="AK">R. Allen and K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann, 2002.</ref> опрацьовує ширший клас програм і перетворень, ніж унімодулярна схема. Множина виконань набору операторів у межах, можливо, неідеально вкладеного набору циклів, розглядається як об'єднання набору політопів, які подають виконання операторів. До цих політопів застосовують [[Афінне перетворення|афінні перетворення]], які дають опис нового порядку виконання. Межі політопів, залежності даних і перетворення часто описуютья за допомогою систем обмежень, і цей підхід часто називають підходом до оптимізації циклів '''на основі обмежень'''. Наприклад, один оператор у зовнішньому циклі '{{Моно|1=for i := 0 to n}} ' і внутрішньому циклі '{{Моно|1=for j := 0 to i+2}} ' виконується один раз для кожної пари {{Моно|(i, j)}} так, що {{Моно|1=0 <= i <= n}} і {{Моно|1=0 <= j <= i+2}}.

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

== Див. також ==
* [[Масштабований паралелізм]]

== Примітки ==
{{примітки|2}}
{{Бібліоінформація}}
[[Категорія:Оптимізації компілятора]]