Loop unrolling , также известный как loop unwinding , — это метод преобразования цикла , который пытается оптимизировать скорость выполнения программы за счет ее двоичного размера, что является подходом, известным как компромисс между пространством и временем . Преобразование может быть выполнено вручную программистом или оптимизирующим компилятором . На современных процессорах loop unrolling часто контрпродуктивен, так как увеличенный размер кода может привести к большему количеству промахов кэша; см. устройство Даффа . [1]
Целью разматывания цикла является увеличение скорости программы за счет сокращения или устранения инструкций, которые управляют циклом, таких как арифметика указателей и проверки «конца цикла» на каждой итерации; [2] уменьшение штрафов за переходы; а также скрытие задержек, включая задержку при чтении данных из памяти. [3] Чтобы устранить эти вычислительные издержки , циклы можно переписать как повторяющуюся последовательность похожих независимых операторов. [4]
Развертывание цикла также является частью некоторых формальных методов проверки , в частности, проверки ограниченной модели . [5]
Накладные расходы в «плотных» циклах часто состоят из инструкций по увеличению указателя или индекса на следующий элемент в массиве ( арифметика указателей ), а также из проверок «конца цикла». Если оптимизирующий компилятор или ассемблер способен предварительно вычислять смещения для каждой индивидуально указанной переменной массива, их можно напрямую встроить в инструкции машинного кода , поэтому не требуется дополнительных арифметических операций во время выполнения.
Оптимизирующие компиляторы иногда выполняют развертывание автоматически или по запросу.
Ручная (или статическая) развертка цикла включает в себя анализ цикла программистом и интерпретацию итераций в последовательность инструкций, которые уменьшат накладные расходы цикла. Это отличается от динамической развертки, которая выполняется компилятором.
Процедура в компьютерной программе заключается в удалении 100 элементов из коллекции. Обычно это выполняется с помощью for-loop, который вызывает функцию delete(item_number) . Если эта часть программы должна быть оптимизирована, а накладные расходы цикла требуют значительных ресурсов по сравнению с таковыми для функции delete(x) , для ускорения можно использовать раскручивание.
В результате этой модификации новая программа должна сделать только 20 итераций вместо 100. После этого нужно будет сделать только 20% переходов и условных ветвей, что представляет собой, на протяжении многих итераций, потенциально значительное снижение накладных расходов на администрирование цикла. Для получения оптимального преимущества в развернутом коде не следует указывать переменные, требующие арифметики указателей . Обычно для этого требуется адресация « база плюс смещение», а не индексированные ссылки.
С другой стороны, это ручное развертывание цикла увеличивает размер исходного кода с 3 до 7 строк, которые необходимо создать, проверить и отладить, а компилятору, возможно, придется выделить больше регистров для хранения переменных в расширенной итерации цикла [ сомнительно – обсудить ] . Кроме того, переменные управления циклом и количество операций внутри развернутой структуры цикла должны быть тщательно выбраны, чтобы результат был действительно таким же, как в исходном коде (предполагая, что это более поздняя оптимизация уже работающего кода). Например, рассмотрим последствия, если количество итераций не делится на 5. Требуемые ручные поправки также становятся несколько сложнее, если условия теста являются переменными. См. также устройство Даффа .
В простом случае управление циклом — это просто административные накладные расходы, которые упорядочивают продуктивные операторы. Сам цикл ничего не добавляет к желаемым результатам, просто избавляя программиста от утомительного копирования кода сто раз, что могло бы быть сделано препроцессором, генерирующим репликации, или текстовым редактором. Аналогично, if-statements и другие операторы управления потоком могут быть заменены репликацией кода, за исключением того, что результатом может быть раздувание кода . Компьютерные программы легко отслеживают комбинации, но программисты считают это повторение скучным и делают ошибки. Рассмотрим:
Но, конечно, выполняемый код не обязательно должен быть вызовом процедуры, и в следующем примере в вычислениях задействована индексная переменная:
который, если скомпилирован, может произвести много кода ( печатные операторы печально известны), но возможна дальнейшая оптимизация. Этот пример ссылается только на x(i) и x(i - 1) в цикле (последний только для разработки нового значения x(i) ), поэтому, учитывая, что нет более поздней ссылки на массив x, разработанный здесь, его использование можно заменить простой переменной. Такое изменение, однако, означало бы простую переменную , значение которой изменяется , тогда как если бы мы оставались с массивом, анализ компилятора мог бы отметить, что значения массива являются константами, каждое из которых получено из предыдущей константы, и поэтому переносит константные значения вперед, так что код становится
печать 2, 2;печать 3, 6;печать 4, 24;...и т. д.
В общем случае содержимое цикла может быть большим, включая сложную индексацию массива. Такие случаи, вероятно, лучше оставить для раскручивания оптимизирующим компиляторам. Репликация самых внутренних циклов может допустить множество возможных оптимизаций, но дать лишь небольшой выигрыш, если n не велико.
Рассмотрим псевдокод цикла WHILE, подобный следующему:
В этом случае развертывание происходит быстрее, поскольку ENDWHILE (переход к началу цикла) будет выполняться на 66% реже.
А еще лучше — пример «измененного» псевдокода, который может автоматически выполняться некоторыми оптимизирующими компиляторами, полностью исключая безусловные переходы.
Поскольку преимущества развертывания цикла часто зависят от размера массива, который часто может быть неизвестен до времени выполнения, JIT- компиляторы (например) могут определить, следует ли вызывать «стандартную» последовательность цикла или вместо этого генерировать (относительно короткую) последовательность отдельных инструкций для каждого элемента. Эта гибкость является одним из преимуществ методов just-in-time по сравнению со статической или ручной оптимизацией в контексте развертывания цикла. В этой ситуации часто при относительно небольших значениях n экономия все еще полезна — требуя довольно небольшого (если вообще) общего увеличения размера программы (который может быть включен только один раз, как часть стандартной библиотеки).
Программисты на языке ассемблера (включая оптимизирующих авторов компиляторов) также могут извлечь выгоду из техники динамического развертывания цикла, используя метод, аналогичный тому, который используется для эффективных таблиц ветвлений . Здесь преимущество становится наибольшим, когда максимальное смещение любого указанного поля в определенном массиве меньше максимального смещения, которое может быть указано в машинной инструкции (которое будет отмечено ассемблером, если будет превышено).
Этот пример предназначен для ассемблеров IBM/360 или Z/Architecture и предполагает, что поле размером 100 байт (со смещением ноль) должно быть скопировано из массива FROM в массив TO — оба имеют по 50 записей с длиной элементов 256 байт каждая.
* Обратный адрес указан в формате R14.* Инициализируем регистры R15, R0, R1 и R2 из данных, определенных в конце * программа начинается с метки INIT/MAXM1. LM R15,R2,INIT Установить R15 = максимальное количество MVC* инструкции (MAXM1 = 16), * R0 = количество записей массива,* R1 = адрес массива «FROM», и* R2 = адрес массива «TO».** Цикл начинается здесь.LOOP EQU * Определить метку LOOP.* На этом этапе R15 всегда будет содержать число 16 (MAXM1). SR R15,R0 Вычтите оставшееся число * записи в массиве (R0) из R15. BNP ALL Если R15 не положительный, это значит, что мы* осталось более 16 записей* в массиве, перейти к выполнению всего* Последовательность MVC и затем повторите.** Вычислить смещение (от начала последовательности MVC) для безусловного перехода к * «развернутый» цикл MVC ниже.* Если количество оставшихся записей в массивах равно нулю, R15 будет равен 16, поэтому * все инструкции MVC будут пропущены. MH R15,=AL2(ILEN) Умножаем R15 на длину одного* Инструкция MVC. B ALL(R15) Перейти к ALL+R15, адресу* рассчитанная конкретная инструкция MVC * с переходом к остальным.** Инструкция MVC «таблица». * Первая запись имеет максимально допустимое смещение с одним регистром = шестнадцатеричный F00* (15*256) в этом примере.* Все 16 из следующих инструкций MVC («переместить символ») используют базу плюс смещение * адресация и каждое смещение to/from уменьшается на длину одного элемента массива* (256). Это позволяет избежать необходимости арифметики указателей для каждого элемента вплоть до * максимально допустимое смещение в пределах инструкции шестнадцатеричного FFF * (15*256+255). Инструкции идут в порядке уменьшения смещения, поэтому последняя * элемент в наборе перемещается первым.ALL MVC 15*256(100,R2),15*256(R1) Переместить 100 байт 16-й записи из * массив 1 в массив 2 (с * сквозной).ILEN EQU *-ALL Установить ILEN на длину предыдущего* Инструкция MVC. MVC 14*256(100,R2),14*256(R1) Переместить 100 байт 15-й записи. MVC 13*256(100,R2),13*256(R1) Переместить 100 байт 14-й записи. MVC 12*256(100,R2),12*256(R1) Переместить 100 байт 13-й записи. MVC 11*256(100,R2),11*256(R1) Переместить 100 байт 12-й записи. MVC 10*256(100,R2),10*256(R1) Переместить 100 байт 11-й записи. MVC 09*256(100,R2),09*256(R1) Переместить 100 байт 10-й записи. MVC 08*256(100,R2),08*256(R1) Переместить 100 байт 9-й записи. MVC 07*256(100,R2),07*256(R1) Переместить 100 байт 8-й записи. MVC 06*256(100,R2),06*256(R1) Переместить 100 байт 7-й записи. MVC 05*256(100,R2),05*256(R1) Переместить 100 байт 6-й записи. MVC 04*256(100,R2),04*256(R1) Переместить 100 байт 5-й записи. MVC 03*256(100,R2),03*256(R1) Переместить 100 байт 4-й записи. MVC 02*256(100,R2),02*256(R1) Переместить 100 байт 3-й записи. MVC 01*256(100,R2),01*256(R1) Переместить 100 байт 2-й записи. MVC 00*256(100,R2),00*256(R1) Переместить 100 байт первой записи.* S R0,MAXM1 Уменьшить количество оставшихся записей* обрабатывать. BNPR R14 Если больше нет записей для обработки, вернуть* по адресу в R14. AH R1,=AL2(16*256) Увеличить указатель массива 'FROM' за пределы* первый сет. AH R2,=AL2(16*256) Увеличить указатель массива «TO» за пределы* первый сет. L R15,MAXM1 Перезагрузить максимальное количество MVC * инструкции по партии в R15* (уничтожено расчетом в * первая инструкция цикла). B LOOP Выполнить цикл еще раз.** Статические константы и переменные (могут передаваться как параметры, за исключением * МАКСИМ1).INIT DS 0A 4 адреса (указателя) должны быть * предварительно загружена инструкция «LM»* в начале программы.MAXM1 DC A(16) Максимальное количество инструкций MVC* выполняется для каждой партии.N DC A(50) Количество фактических записей в массиве (a * переменная, заданная в другом месте). DC A(FROM) Адрес начала массива 1 * («указатель»). DC A(TO) Адрес начала массива 2 * («указатель»).** Статические массивы (их можно получать динамически).ИЗ DS 50CL256 Массив из 50 записей по 256 байт каждая.TO DS 50CL256 Массив из 50 записей по 256 байт каждая.В этом примере потребовалось бы около 202 инструкций с "обычным" циклом (50 итераций), тогда как приведенный выше динамический код потребовал бы всего около 89 инструкций (или экономия около 56%). Если бы массив состоял только из двух записей, он все равно выполнялся бы примерно за то же время, что и исходный развернутый цикл. Увеличение размера кода составляет всего около 108 байт — даже если в массиве тысячи записей.
Подобные методы, конечно, можно использовать, когда задействовано несколько инструкций, при условии, что длина объединенной инструкции соответствующим образом скорректирована. Например, в этом же примере, если требуется очистить остаток каждой записи массива до нулей сразу после копирования 100-байтового поля, XC xx*256+100(156,R1),xx*256+100(R2)можно добавить дополнительную инструкцию очистки, , сразу после каждого MVC в последовательности (где xxсоответствует значению в MVC выше).
Конечно, вполне возможно сгенерировать приведенный выше код «встроенным» способом, используя один оператор макроса ассемблера , указав всего четыре или пять операндов (или, в качестве альтернативы, превратить его в библиотечную подпрограмму, доступ к которой осуществляется простым вызовом с передачей списка параметров), что делает оптимизацию легкодоступной.
Следующий пример демонстрирует динамическую развертку цикла для простой программы, написанной на языке C. В отличие от примера на ассемблере выше, в этом примере арифметика указателя/индекса по-прежнему генерируется компилятором, поскольку переменная (i) по-прежнему используется для адресации элемента массива. Полная оптимизация возможна только в том случае, если в операторах замены используются абсолютные индексы.
#include <stdio.h> /* Количество записей, обработанных за одну итерацию цикла. */ /* Обратите внимание, что это число является «постоянной константой», отражающей код ниже. */ #define BUNCHSIZE (8)int main ( void ) { int i = 0 ; /* счетчик */ int entry = 50 ; /* общее количество для обработки */ int repeat ; /* количество повторений while */ int left = 0 ; /* остаток (обработка позже) */ /* Если количество элементов не делится на BUNCHSIZE, */ /* получаем количество повторений, необходимое для выполнения большей части обработки в цикле while */ повтор = ( записи / BUNCHSIZE ); /* количество повторений */ left = ( записи % BUNCHSIZE ); /* вычислить остаток */ /* Разворачиваем цикл на 'группы' по 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 ); /* обновить индекс по количеству обработанных за один раз */ i += BUNCHSIZE ; } /* Используйте оператор switch для обработки оставшихся элементов, перейдя к метке case */ /* на метке, которая затем будет пропущена для завершения набора */ switch ( left ) { case 7 : printf ( "process(%d) \n " , i + 6 ); /* обрабатываем и полагаемся на пропущенный элемент */ 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 ); /* осталось два элемента */ case 1 : printf ( "process(%d) \n " , i ); /* осталось обработать только один */ case 0 : ; /* не осталось ни одного */ } } Дублирования кода можно было бы избежать, если бы обе части были написаны вместе, как в устройстве Даффа .
Следующий пример вычислит скалярное произведение двух 100-элементных векторов A и B типа double. Вот код на языке C:
двойной dotProduct = 0 ; для ( int i = 0 ; i < 100 ; i ++ ) { dotProduct += A [ i ] * B [ i ]; }Ниже приведен код ассемблера MIPS, который вычислит скалярное произведение двух 100-элементных векторов, A и B, перед реализацией разворачивания цикла. В приведенном ниже коде пропущены инициализации цикла:
A[i]указатель ($5) по базовому адресу A.B[i]указатель ($6) по базовому адресу B.Обратите внимание, что размер одного элемента массивов (a double) составляет 8 байт.
петля3: ld $f10 , 0 ( $5 ) ; $f10 ← А[я] ld $f12 , 0 ( $6 ) ; $f12 ← B[i] мул.д $f10 , $f10 , $f12 ; $f10 ← A[i]*B[i] добавить.d $f8 , $f8 , $f10 ; $f8 ← $f8 + A[i]*B[i] addi $5 , $5 , 8 ; увеличить указатель для A[i] на размер ; двойного. addi $6 , $6 , 8 ; увеличить указатель для B[i] на размер ; двойного. addi $7 , $7 , -1 ; уменьшить количество циклов тест: bgtz $7 , loop3 ; Продолжить, если количество циклов > 0 Далее следует то же самое, что и выше, но с развертыванием цикла, реализованным с коэффициентом 4. Обратите внимание еще раз, что размер одного элемента массивов (a double) составляет 8 байт; таким образом, смещения 0, 8, 16, 24 и смещение 32 на каждом цикле.
петля3: ld $f10 , 0 ( $5 ) ; итерация со смещением 0 лд $f12 , 0 ( $6 ) мульч.д $f10 , $f10 , $f12 добавить.d $f8 , $f8 , $f10 ld $f10 , 8 ( $5 ) ; итерация со смещением 8 лд $f12 , 8 ( $6 ) мульч.д $f10 , $f10 , $f12 добавить.d $f8 , $f8 , $f10 ld $f10 , 16 ( $5 ) ; итерация со смещением 16 лд $f12 , 16 ( $6 ) мульч.д $f10 , $f10 , $f12 добавить.d $f8 , $f8 , $f10 ld $f10 , 24 ( $5 ) ; итерация со смещением 24 лд $f12 , 24 ( $6 ) мульч.д $f10 , $f10 , $f12 добавить.d $f8 , $f8 , $f10 добавить $5 , $5 , 32 добавить $6 , $6 , 32 добавить $7 , $7 , -4 тест: bgtz $7 , loop3 ; Продолжить цикл, если $7 > 0 Геттис дает замечательное объяснение этого эффекта в X-сервере. Оказывается, что с учетом предсказаний ветвлений и относительной скорости ЦП и памяти, изменившейся за последнее десятилетие, развертывание цикла практически бессмысленно. Фактически, удалив все экземпляры Duff's Device с сервера XFree86 4.0, сервер уменьшился в размере на _половину_ _a_ _megabyte_ (!!!) и стал быстрее загружаться, потому что удаление всего этого лишнего кода означало, что X-сервер не так сильно загружал строки кэша.
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ){{cite journal}}: Цитировать журнал требует |journal=( помощь )12.11 Развертывание цикла