Размотка цикла

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

Пример

for ( i = 1; i < n; i++)
{
    a[i] = (i % b[i]);
}

преобразуется в такой код:

for (i = 1; i < n - 3; i += 4)
{
    a[i] = (i % b[i]);
    a[i + 1] = ((i + 1) % b[i + 1]);
    a[i + 2] = ((i + 2) % b[i + 2]);
    a[i + 3] = ((i + 3) % b[i + 3]);
}
 
for (i = 4*(n/4); i < n; i++)  
{
    a[i] = (i % b[i]);
}

Подробно данный вид оптимизации рассмотрен, например, в Generalized Loop-Unrolling^[1]. Он (совместно с loop fission) при определённых условиях (отсутствии зависимостей по данным между инструкциями в новом цикле) позволяет выполнять цикл на нескольких процессорах.

Известен также и необычный способ реализации размотки цикла, называемый «устройством Даффа», — в этой реализации используются малоизвестные и неочевидные возможности синтаксиса языка Си.

Недостатки

Одним из недостатков данного метода оптимизации при его применении совместно с loop fission для дальнейшего распараллеливания является то, что выборка данных из памяти начинает производиться не по порядку следования данных, что может отрицательно сказаться на эффективности работы кэша. Другим, более подходящим видом оптимизации, который позволяет лучше использовать кэш процессоров, является loop parallelization.^{[источник не указан 931 день]}

Кроме того, в ходе раскрутки цикла увеличивается число команд, выполняемых на каждой его итерации. Если данное число превысит емкость кэша команд, то вместо ожидаемого роста эффективности выполнения цикла возможно ее существенное снижение.

Примечания

1. ↑  (англ.) J. C. Huang, T. Leng, Generalized Loop-Unrolling: a Method for Program Speed-Up, 1998

Ссылки

1. http://www.insidepro.com/kk/036r.shtml
2. http://www.intel.com/cd/software/products/asmo-na/eng/compilers/277618.htm#hlo