WikiSort.ru - Не сортированное

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

Пример

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

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

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

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

Недостатки

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

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

Примечания

Ссылки

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