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

В программировании, размотка цикла (англ. 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) + 1; i < n; i++) 
{
    a[i] = (i % b[i]);
}

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

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

Недостатки

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

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

Ссылки

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

Отрывок, характеризующий Размотка цикла

– Oui, Sire, [Да, государь.] – отвечал Рапп.
Наполеон взял пастильку, положил ее в рот и посмотрел на часы. Спать ему не хотелось, до утра было еще далеко; а чтобы убить время, распоряжений никаких нельзя уже было делать, потому что все были сделаны и приводились теперь в исполнение.
– A t on distribue les biscuits et le riz aux regiments de la garde? [Роздали ли сухари и рис гвардейцам?] – строго спросил Наполеон.
– Oui, Sire. [Да, государь.]
– Mais le riz? [Но рис?]
Рапп отвечал, что он передал приказанья государя о рисе, но Наполеон недовольно покачал головой, как будто он не верил, чтобы приказание его было исполнено. Слуга вошел с пуншем. Наполеон велел подать другой стакан Раппу и молча отпивал глотки из своего.
– У меня нет ни вкуса, ни обоняния, – сказал он, принюхиваясь к стакану. – Этот насморк надоел мне. Они толкуют про медицину. Какая медицина, когда они не могут вылечить насморка? Корвизар дал мне эти пастильки, но они ничего не помогают. Что они могут лечить? Лечить нельзя. Notre corps est une machine a vivre. Il est organise pour cela, c'est sa nature; laissez y la vie a son aise, qu'elle s'y defende elle meme: elle fera plus que si vous la paralysiez en l'encombrant de remedes. Notre corps est comme une montre parfaite qui doit aller un certain temps; l'horloger n'a pas la faculte de l'ouvrir, il ne peut la manier qu'a tatons et les yeux bandes. Notre corps est une machine a vivre, voila tout. [Наше тело есть машина для жизни. Оно для этого устроено. Оставьте в нем жизнь в покое, пускай она сама защищается, она больше сделает одна, чем когда вы ей будете мешать лекарствами. Наше тело подобно часам, которые должны идти известное время; часовщик не может открыть их и только ощупью и с завязанными глазами может управлять ими. Наше тело есть машина для жизни. Вот и все.] – И как будто вступив на путь определений, definitions, которые любил Наполеон, он неожиданно сделал новое определение. – Вы знаете ли, Рапп, что такое военное искусство? – спросил он. – Искусство быть сильнее неприятеля в известный момент. Voila tout. [Вот и все.]
Рапп ничего не ответил.
– Demainnous allons avoir affaire a Koutouzoff! [Завтра мы будем иметь дело с Кутузовым!] – сказал Наполеон. – Посмотрим! Помните, в Браунау он командовал армией и ни разу в три недели не сел на лошадь, чтобы осмотреть укрепления. Посмотрим!