Розмотування циклу англ loop unrolling loop unwinding спосіб в який намагаються оптимізувати швидкодію програми за рахун

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

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

Переваги

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

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

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

Недоліки

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

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

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

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

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

Звичайний цикл	Після розмотування
int x; for (x = 0; x < 100; x++) { delete(x); } //. //. //. //.	int x; for (x = 0; x < 100; x += 5) { 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 % менш часто.

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

Примітки

Ullman, Jeffrey D.; Aho, Alfred V. (1977). Principles of compiler design. Reading, Mass: Addison-Wesley Pub. Co. с. 471–2. ISBN .
Petersen, W.P., Arbenz, P. (2004). Introduction to Parallel Computing. Oxford University Press. с. 10.
Nicolau, Alexandru (1985). Loop Quantization: Unwinding for Fine-Grain Parallelism Exploitation. Dept. of Computer Science Technical Report. Ithaca, NY: Cornell University. OCLC 14638257.
Sarkar, Vivek (2001). Optimized Unrolling of Nested Loops. International Journal of Parallel Programming. 29 (5): 545—581. doi:10.1023/A:1012246031671.^{[недоступне посилання]}

Джерела

[1] Ullman, Jeffrey D.; Aho, Alfred V. (1977). Principles of compiler design. Reading, Mass: Addison-Wesley Pub. Co. с. 471–2. ISBN .

[2] Petersen, W.P., Arbenz, P. (2004). Introduction to Parallel Computing. Oxford University Press. с. 10.

[3] Nicolau, Alexandru (1985). Loop Quantization: Unwinding for Fine-Grain Parallelism Exploitation. Dept. of Computer Science Technical Report. Ithaca, NY: Cornell University. OCLC 14638257.

[4] Sarkar, Vivek (2001). Optimized Unrolling of Nested Loops. International Journal of Parallel Programming. 29 (5): 545—581. doi:10.1023/A:1012246031671.^{[недоступне посилання]}