Розмотування циклу

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Розмотування циклу (англ. loop unrolling, loop unwinding) — спосіб, в який намагаються оптимізувати швидкодію програми за рахунок розміру двійкового файлу. Зміни в програмі може робити програміст або оптимізуючий компілятор.

Метою розмотування циклу є збільшення швидкодії програми шляхом зменшення (або виключення) інструкцій контролю за циклом, таких як арифметика вказівників і перевірка на завершення циклу на кожній ітерації;[1] зменшення витрат на галуження; а також «приховування латентності, особливо, затримку в читанні даних з пам'яті».[2] Цикли можуть бути перезаписані як послідовності подібних незалежних інструкцій, і таким чином можуть бути усунені накладні витрати обчислення.[3]

Переваги[ред.ред. код]

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

  • Значну користь можна отримати якщо покращення в виконанні інструкцій з лишком компенсує будь-яке зменшення швидкодії спричинене збільшенням розміру програми.
  • Витрати на галуження мінімізовані.
  • Якщо операції в циклі незалежні одна від одної (тобто коли операція, що зусрічається раніше в циклі не впливає на на наступні операції), операції можуть потенційно виконуватись паралельно.
  • Може бути реалізоване динамічно, якщо кількість елементів масиву невідома впід час компіляції.

Оптимізуючи компілятори іноді можуть виконувати розмотування циклу автоматично або за запитом.

Недоліки[ред.ред. код]

  • Розмір програми в результаті розмотування збільшується, що небажано, особливо для вбудованих застосунків.
  • Збільшення коду також може призвести до збільшення промахів кешу, що шкідливо діє на виконання.
  • Якщо тіки розмотування не виконується компілятором, код може стати менш зрозумілим.
  • Якщо код в тілі циклу містить виклики функцій, може бути неможливим поєднати розмотування з інлайнингом, бо збільшення розміру може стати надмірним. Тож треба шукати компроміс між двома оптимізаціями.
  • Можливе збільшення використання регістрів в кожній ітерації для збереження тимчасових змінних, що може зменшити швидкодію (хоча багато залежить від можливих оптимізацій).[4]

Статичне/Ручне розмотування циклу[ред.ред. код]

Ручне (або статичне) розмотування циклу вимагає від програміста розбору циклу і перетворення ітерацій як послідовність інструкцій, які зменшать накладні витрати циклу. Динаміне розмотування виконується компілятором.

Простий приклад ручного розмотування в Сі[ред.ред. код]

Підпрограма видаляє 100 елементів з колекції.

Звичайний цикл Після розмотування
 int x;
 for (x = 0; x < 100; x++)
 {
     delete(x);
 }
 //.
 //.
 //.
 //.
 int x; 
 for (x = 0; x < 100; x++)
 {
     delete(x);
     delete(++x);
     delete(++x);
     delete(++x);
     delete(++x);
 }

Розмотування WHILE циклів[ред.ред. код]

Звичайний цикл Після розмотування Розмотаний цикл із «вивертом»
  WHILE (condition) DO
         action
  ENDWHILE
.
.
.
.
.
.
  WHILE (condition) DO
         action
         IF NOT(condition) THEN GOTO break
         action
         IF NOT(condition) THEN GOTO break
         action
 ENDWHILE
 LABEL break:
.
 IF (condition) THEN
  REPEAT {
         action
         IF NOT(condition) THEN GOTO break
         action
         IF NOT(condition) THEN GOTO break
          action
         } WHILE (condition)
 LABEL break:

Розмотаний швидше, бо ENDWHILE (який буде скомпільований в перехід на початок циклу) буде виконуватись на 66% менш часто.

Навіть краще, приклад із «вивертом», який може бути виконаний деякими оптимізуючими компіляторами автоматично, виключає всі безумовні переходи.

Примітки[ред.ред. код]

  1. Ullman, Jeffrey D.; Aho, Alfred V. (1977). Principles of compiler design. Reading, Mass: Addison-Wesley Pub. Co. с. 471–2. ISBN 0-201-10073-8. 
  2. Petersen, W.P., Arbenz, P. (2004). Introduction to Parallel Computing. Oxford University Press. с. 10. 
  3. Nicolau, Alexandru Loop Quantization: Unwinding for Fine-Grain Parallelism Exploitation (1985).
  4. Sarkar, Vivek Optimized Unrolling of Nested Loops // International Journal of Parallel Programming. — 29 (2001) (5) С. 545–581. DOI:10.1023/A:1012246031671.