Войти
Развертывание цикла, также известное как разворачивание цикла, представляет собой метод преобразования цикла, который пытается оптимизировать скорость выполнения программы за счет ее двоичного размера, что является подходом, известным как компромисс между пространством и временем. Преобразование может быть выполнено вручную программистом или оптимизирующим компилятором. На современных процессорах разворачивание цикла часто приводит к обратным результатам, поскольку увеличенный размер кода может вызвать большее количество промахов в кэше; ср. Устройство Даффа.
Целью раскручивания цикла является увеличение скорости программы за счет сокращения или исключения инструкций, управляющих циклом, таких как арифметические операции с указателями и тесты «конца цикла» на каждой итерации; снижение отраслевых штрафов; а также сокрытие задержек, включая задержку чтения данных из памяти. Чтобы устранить эти вычислительные издержки, циклы можно переписать как повторяющуюся последовательность подобных независимых операторов.
Развертывание цикла также является частью некоторых формальных методов проверки, в частности проверки ограниченной модели.
Накладные расходы в «плотных» циклах часто состоят из инструкций по увеличению указателя или индекса до следующего элемента в массиве ( арифметика указателя ), а также из тестов «конца цикла». Если оптимизирующий компилятор или ассемблер может предварительно вычислить смещения для каждой отдельной переменной массива, на которую ссылаются, они могут быть встроены в инструкции машинного кода напрямую, поэтому не требуется дополнительных арифметических операций во время выполнения.
Оптимизирующие компиляторы иногда выполняют развертывание автоматически или по запросу.
При ручном (или статическом) развертывании цикла программист анализирует цикл и интерпретирует итерации в последовательность инструкций, что снижает накладные расходы на цикл. Это контрастирует с динамическим развертыванием, которое выполняется компилятором.
Процедура в компьютерной программе заключается в удалении 100 элементов из коллекции. Обычно это выполняется с помощью for цикла, который вызывает функцию delete (item_number). Если эта часть программы должна быть оптимизирована, а накладные расходы цикла требуют значительных ресурсов по сравнению с таковыми для функции delete (x), для его ускорения можно использовать раскрутку.
| Нормальный цикл | После разворачивания цикла |
|---|---|
int x; for (x = 0; x lt; 100; x++) { delete(x); } | int x; for (x = 0; x lt; 100; x += 5) { delete(x); delete(x + 1); delete(x + 2); delete(x + 3); delete(x + 4); } |
В результате этой модификации новая программа должна сделать только 20 итераций вместо 100. После этого необходимо выполнить только 20% переходов и условных переходов, что представляет собой, на протяжении многих итераций, потенциально значительное уменьшение накладные расходы на администрирование цикла. Для получения оптимального результата в развернутом коде не следует указывать переменные, требующие арифметики указателей. Обычно для этого требуется адресация « основание плюс смещение», а не индексированная ссылка.
С другой стороны, это ручное развертывание цикла увеличивает размер исходного кода с 3 строк до 7, которые должны быть созданы, проверены и отлажены, и компилятору, возможно, придется выделить больше регистров для хранения переменных в расширенной итерации цикла. Кроме того, переменные управления циклом и количество операций внутри развернутой структуры цикла должны быть тщательно выбраны, чтобы результат действительно был таким же, как и в исходном коде (при условии, что это более поздняя оптимизация уже работающего кода). Например, рассмотрите последствия, если количество итераций не делится на 5. Требуемые ручные поправки также становятся несколько более сложными, если условия теста являются переменными. См. Также устройство Даффа.
В простом случае управление циклом - это просто административные накладные расходы, которые организуют продуктивные операторы. Сам цикл не вносит никакого вклада в желаемые результаты, просто избавляя программиста от утомительного повторения кода сотни раз, что можно было бы сделать с помощью препроцессора, генерирующего репликации, или текстового редактора. Точно так же if операторы -statements и другие операторы управления потоком могут быть заменены репликацией кода, за исключением того, что результатом может быть раздувание кода. Компьютерные программы легко отслеживают комбинации, но программисты считают это повторение скучным и допускают ошибки. Рассматривать:
| Нормальный цикл | После разворачивания цикла |
|---|---|
for i := 1:8 do if i mod 2 = 0 then do_even_stuff(i) else do_odd_stuff(i); next i; | do_odd_stuff(1); do_even_stuff(2); do_odd_stuff(3); do_even_stuff(4); do_odd_stuff(5); do_even_stuff(6); do_odd_stuff(7); do_even_stuff(8); |
Но, конечно, выполняемый код не обязательно должен быть вызовом процедуры, и в следующем примере в вычислении используется индексная переменная:
| Нормальный цикл | После разворачивания цикла |
|---|---|
x(1) := 1; For i := 2:9 do x(i) := x(i - 1) * i; print i, x(i); next i; | x(1) := 1; x(2) := x(1) * 2; print 2, x(2); x(3) := x(2) * 3; print 3, x(3); x(4) := x(3) * 4; print 4, x(4);... etc. |
который в случае компиляции может привести к появлению большого количества кода ( печально известны операторы печати ), но возможна дальнейшая оптимизация. В этом примере делается ссылка только на x (i) и x (i - 1) в цикле (последний только для разработки нового значения x (i) ), поэтому, учитывая, что нет более поздней ссылки на массив x, разработанный здесь, его использование может быть заменено простой переменной. Однако такое изменение будет означать простую переменную, значение которой изменяется, тогда как, оставаясь с массивом, анализ компилятора может отметить, что значения массива являются постоянными, каждое из которых получено из предыдущей константы, и поэтому переносит постоянные значения так, чтобы код становится
print 2, 2; print 3, 6; print 4, 24;...etc.
В общем, содержимое цикла может быть большим, включая сложную индексацию массивов. Эти случаи, вероятно, лучше всего оставить для развертывания оптимизирующим компиляторам. Репликация самых внутренних циклов может позволить множество возможных оптимизаций, но даст лишь небольшой выигрыш, если n не велико.
Рассмотрим цикл псевдокода 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% реже.
Еще лучше, пример «настроенного» псевдокода, который может выполняться автоматически некоторыми оптимизирующими компиляторами, полностью исключая безусловные переходы.
Поскольку преимущества развертывания цикла часто зависят от размера массива, который часто может быть неизвестен до времени выполнения, JIT- компиляторы (например) могут определить, вызывать ли «стандартную» последовательность цикла или вместо этого генерировать (относительно короткий) последовательность индивидуальных инструкций для каждого элемента. Такая гибкость является одним из преимуществ своевременных методов по сравнению со статической или ручной оптимизацией в контексте развертывания цикла. В этой ситуации часто бывает с относительно небольшими значениями n, когда экономия по-прежнему полезна - требуется довольно небольшое (если вообще есть) общее увеличение размера программы (которое может быть включено только один раз как часть стандартной библиотеки).
Программисты на языке ассемблера (в том числе оптимизирующие составители компиляторов) также могут извлечь выгоду из техники динамического разворачивания цикла, используя метод, аналогичный тому, который используется для эффективных таблиц переходов. Здесь преимущество наиболее велико, когда максимальное смещение любого поля, на которое имеется ссылка в конкретном массиве, меньше максимального смещения, которое может быть указано в машинной инструкции (которое будет отмечено ассемблером, если оно превышено).
Этот пример предназначен для ассемблеров IBM / 360 или Z / Architecture и предполагает, что поле размером 100 байтов (при нулевом смещении) должно быть скопировано из массива FROM в массив TO - оба имеют 50 записей с длиной элемента 256 байтов каждая.
* The return address is in R14. * Initialize registers R15, R0, R1, and R2 from data defined at the end of * the program starting with label INIT/MAXM1. LM R15,R2,INIT Set R15 = maximum number of MVC * instructions (MAXM1 = 16), * R0 = number of entries of array, * R1 = address of 'FROM' array, and * R2 = address of 'TO' array. * * The loop starts here. LOOP EQU * Define LOOP label. * At this point, R15 will always contain the number 16 (MAXM1). SR R15,R0 Subtract the remaining number of * entries in the array (R0) from R15. BNP ALL If R15 is not positive, meaning we * have more than 16 remaining entries * in the array, jump to do the entire * MVC sequence and then repeat. * * Calculate an offset (from start of MVC sequence) for unconditional branch to * the 'unwound' MVC loop below. * If the number of remaining entries in the arrays is zero, R15 will be 16, so * all the MVC instructions will be bypassed. MH R15,=AL2(ILEN) Multiply R15 by the length of one * MVC instruction. B ALL(R15) Jump to ALL+R15, the address of the * calculated specific MVC instruction * with drop through to the rest of them. * * MVC instruction 'table'. * First entry has maximum allowable offset with single register = hexadecimal F00 * (15*256) in this example. * All 16 of the following MVC ('move character') instructions use base-plus-offset * addressing and each to/from offset decreases by the length of one array element * (256). This avoids pointer arithmetic being required for each element up to a * maximum permissible offset within the instruction of hexadecimal FFF * (15*256+255). The instructions are in order of decreasing offset, so the last * element in the set is moved first. ALL MVC 15*256(100,R2),15*256(R1) Move 100 bytes of 16th entry from * array 1 to array 2 (with * drop-through). ILEN EQU *-ALL Set ILEN to the length of the previous * MVC instruction. MVC 14*256(100,R2),14*256(R1) Move 100 bytes of 15th entry. MVC 13*256(100,R2),13*256(R1) Move 100 bytes of 14th entry. MVC 12*256(100,R2),12*256(R1) Move 100 bytes of 13th entry. MVC 11*256(100,R2),11*256(R1) Move 100 bytes of 12th entry. MVC 10*256(100,R2),10*256(R1) Move 100 bytes of 11th entry. MVC 09*256(100,R2),09*256(R1) Move 100 bytes of 10th entry. MVC 08*256(100,R2),08*256(R1) Move 100 bytes of 9th entry. MVC 07*256(100,R2),07*256(R1) Move 100 bytes of 8th entry. MVC 06*256(100,R2),06*256(R1) Move 100 bytes of 7th entry. MVC 05*256(100,R2),05*256(R1) Move 100 bytes of 6th entry. MVC 04*256(100,R2),04*256(R1) Move 100 bytes of 5th entry. MVC 03*256(100,R2),03*256(R1) Move 100 bytes of 4th entry. MVC 02*256(100,R2),02*256(R1) Move 100 bytes of 3rd entry. MVC 01*256(100,R2),01*256(R1) Move 100 bytes of 2nd entry. MVC 00*256(100,R2),00*256(R1) Move 100 bytes of 1st entry. * S R0,MAXM1 Reduce the number of remaining entries * to process. BNPR R14 If no more entries to process, return * to address in R14. AH R1,=AL2(16*256) Increment 'FROM' array pointer beyond * first set. AH R2,=AL2(16*256) Increment 'TO' array pointer beyond * first set. L R15,MAXM1 Reload the maximum number of MVC * instructions per batch into R15 * (destroyed by the calculation in the * first instruction of the loop). B LOOP Execute loop again. * * Static constants and variables (these could be passed as parameters, except * MAXM1). INIT DS 0A 4 addresses (pointers) to be * pre-loaded with the 'LM' instruction * in the beginning of the program. MAXM1 DC A(16) Maximum number of MVC instructions * executed per batch. N DC A(50) Number of actual entries in array (a * variable, set elsewhere). DC A(FROM) Address of start of array 1 * ("pointer"). DC A(TO) Address of start of array 2 * ("pointer"). * * Static arrays (these could be dynamically acquired). FROM DS 50CL256 Array of 50 entries of 256 bytes each. TO DS 50CL256 Array of 50 entries of 256 bytes each. В этом примере для «обычного» цикла (50 итераций) потребуется приблизительно 202 инструкции, тогда как для приведенного выше динамического кода потребуется всего около 89 инструкций (или примерно 56% экономии). Если бы массив состоял только из двух записей, он все равно выполнялся бы примерно за то же время, что и исходный развернутый цикл. Увеличение размера кода составляет всего около 108 байт, даже если в массиве тысячи записей.
Конечно, аналогичные методы могут использоваться, когда задействовано несколько инструкций, при условии, что длина объединенных инструкций регулируется соответствующим образом. Например, в этом же примере, если требуется очистить оставшуюся часть каждой записи массива до нулей сразу после копирования 100-байтового поля XC xx*256+100(156,R1),xx*256+100(R2), можно добавить дополнительную инструкцию очистки сразу после каждого MVC в последовательности (где xx соответствует значение в MVC над ним).
Конечно, вполне возможно сгенерировать приведенный выше код «в строке» с помощью одного оператора макроса ассемблера, указав всего четыре или пять операндов (или, альтернативно, превратить его в библиотечную подпрограмму, доступ к которой осуществляется простым вызовом, передавая список параметры), что делает оптимизацию доступной.
Следующий пример демонстрирует динамическое разворачивание петли для простой программы, написанной на C. В отличие от приведенного выше примера ассемблера, арифметика указателя / индекса все еще генерируется компилятором в этом примере, потому что переменная (i) все еще используется для адресации элемента массива. Полная оптимизация возможна только в том случае, если в операторах замены используются абсолютные индексы.
#include lt;stdio.hgt; /* The number of entries processed per loop iteration. */ /* Note that this number is a 'constant constant' reflecting the code below. */ #define BUNCHSIZE (8) int main(void) { int i = 0; /* counter */ int entries = 50; /* total number to process */ int repeat; /* number of while repetitions*/ int left = 0; /* remainder (process later) */ /* If the number of elements is not be divisible by BUNCHSIZE, */ /* get repeat times required to do most processing in the while loop */ repeat = (entries / BUNCHSIZE); /* number of times to repeat */ left = (entries % BUNCHSIZE); /* calculate remainder */ /* Unroll the loop in 'bunches' of 8 */ while (repeat--) { printf("process(%d)\n", i ); printf("process(%d)\n", i + 1); printf("process(%d)\n", i + 2); printf("process(%d)\n", i + 3); printf("process(%d)\n", i + 4); printf("process(%d)\n", i + 5); printf("process(%d)\n", i + 6); printf("process(%d)\n", i + 7); /* update the index by amount processed in one go */ i += BUNCHSIZE; } /* Use a switch statement to process remaining by jumping to the case label */ /* at the label that will then drop through to complete the set */ switch (left) { case 7: printf("process(%d)\n", i + 6); /* process and rely on drop through */ case 6: printf("process(%d)\n", i + 5); case 5: printf("process(%d)\n", i + 4); case 4: printf("process(%d)\n", i + 3); case 3: printf("process(%d)\n", i + 2); case 2: printf("process(%d)\n", i + 1); /* two left */ case 1: printf("process(%d)\n", i); /* just one left to process */ case 0: ; /* none left */ } } Дублирования кода можно было избежать, записав две части вместе, как в устройстве Даффа.
В следующем примере будет вычислено скалярное произведение двух векторов типа A и B со 100 элементами double. Вот код на C:
double dotProduct = 0; for (int i = 0; i lt; 100; i++) { dotProduct += A[i]*B[i]; } Ниже приведен ассемблерный код MIPS, который вычисляет скалярное произведение двух векторов из 100 входов, A и B, перед реализацией развертывания цикла. В приведенном ниже коде отсутствуют инициализации цикла:
A[i] указатель ($ 5) на базовый адрес A.B[i] указатель ($ 6) на базовый адрес B. Обратите внимание, что размер одного элемента массивов (а double) составляет 8 байтов.
loop3: l.d $f10, 0($5) ; $f10 ← A[i] l.d $f12, 0($6) ; $f12 ← B[i] mul.d $f10, $f10, $f12 ; $f10 ← A[i]*B[i] add.d $f8, $f8, $f10 ; $f8 ← $f8 + A[i]*B[i] addi $5, $5, 8 ; increment pointer for A[i] by the size ; of a double. addi $6, $6, 8 ; increment pointer for B[i] by the size ; of a double. addi $7, $7, -1 ; decrement loop count test: bgtz $7, loop3 ; Continue if loop count gt; 0
Далее следует то же самое, что и выше, но с реализацией развертывания цикла с коэффициентом 4. Еще раз обратите внимание, что размер одного элемента массивов (a double) составляет 8 байтов; таким образом, 0, 8, 16, 24 смещения и 32 смещения на каждой петле.
loop3: l.d $f10, 0($5) ; iteration with displacement 0 l.d $f12, 0($6) mul.d $f10, $f10, $f12 add.d $f8, $f8, $f10 l.d $f10, 8($5) ; iteration with displacement 8 l.d $f12, 8($6) mul.d $f10, $f10, $f12 add.d $f8, $f8, $f10 l.d $f10, 16($5) ; iteration with displacement 16 l.d $f12, 16($6) mul.d $f10, $f10, $f12 add.d $f8, $f8, $f10 l.d $f10, 24($5) ; iteration with displacement 24 l.d $f12, 24($6) mul.d $f10, $f10, $f12 add.d $f8, $f8, $f10 addi $5, $5, 32 addi $6, $6, 32 addi $7, $7, -4 test: bgtz $7, loop3 ; Continue loop if $7 gt; 0
