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

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

Например, си-код:

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

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

int 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]);
}

Подобный вид оптимизации изучен в 1998 году^[1], и показано, что совместно с расщеплением тела цикла при определённых условиях (в частности, при отсутствии зависимостей по данным между инструкциями в новом цикле) позволяет выполнять цикл на нескольких процессорах.

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

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

Альтернативным размотке способом оптимизации является прямое распараллеливание цикла.

Примечания

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

Ссылки

• Техника оптимизации под Linux (часть 3 — оптимизация циклов)  (недоступная ссылка — история, копия)
• Intel® C++ Compiler 11.0 Professional Edition for Linux  (недоступная ссылка — история, копия)