Развертывание цикла , также известное как разматывание цикла , представляет собой метод преобразования цикла , который пытается оптимизировать скорость выполнения программы за счет ее двоичного размера, что представляет собой подход, известный как компромисс между пространством и временем . Преобразование может быть выполнено вручную программистом или оптимизирующим компилятором . На современных процессорах развертывание цикла часто является контрпродуктивным, поскольку увеличенный размер кода может привести к большему количеству промахов в кэше; ср. Устройство Даффа . [1]
Целью раскручивания цикла является увеличение скорости программы за счет сокращения или исключения инструкций, управляющих циклом, таких как арифметика указателей и тесты «конца цикла» на каждой итерации; [2] снижение отраслевых штрафов; а также сокрытие задержек, в том числе задержки чтения данных из памяти. [3] Чтобы устранить эти вычислительные накладные расходы , циклы можно переписать как повторяющуюся последовательность аналогичных независимых операторов. [4]
Развертывание цикла также является частью некоторых формальных методов проверки, в частности проверки ограниченной модели . [5]
Накладные расходы в «жестких» циклах часто состоят из инструкций по увеличению указателя или индекса до следующего элемента в массиве ( арифметика указателей ), а также тестов «конца цикла». Если оптимизирующий компилятор или ассемблер способен предварительно вычислить смещения для каждой отдельной переменной массива, на которую ссылаются, они могут быть встроены непосредственно в инструкции машинного кода , поэтому не требуется никаких дополнительных арифметических операций во время выполнения.
Оптимизирующие компиляторы иногда выполняют развертывание автоматически или по запросу.
Ручное (или статическое) развертывание цикла предполагает, что программист анализирует цикл и интерпретирует итерации в последовательность инструкций, что снижает накладные расходы цикла. В этом отличие от динамического развертывания, которое выполняется компилятором.
Процедура компьютерной программы заключается в удалении 100 элементов из коллекции. Обычно это достигается с помощью forцикла -loop, который вызывает функцию delete(item_number) . Если эту часть программы необходимо оптимизировать, а накладные расходы цикла требуют значительных ресурсов по сравнению с ресурсами для функции delete(x) , для ускорения ее можно использовать раскрутку.
В результате этой модификации новой программе приходится делать всего 20 итераций вместо 100. После этого необходимо выполнить только 20% переходов и условных переходов, что представляет собой за многие итерации потенциально значительное уменьшение накладные расходы на администрирование цикла. Чтобы получить оптимальную выгоду, в развернутом коде не следует указывать переменные, требующие арифметики указателей . Обычно для этого требуется адресация « база плюс смещение», а не индексированная ссылка.
С другой стороны, эта ручная развертка цикла увеличивает размер исходного кода с 3 до 7 строк, которые необходимо создавать, проверять и отлаживать, и компилятору, возможно, придется выделить больше регистров для хранения переменных в итерации расширенного цикла [ сомнительно - обсуждать ] . Кроме того, переменные управления циклом и количество операций внутри развернутой структуры цикла должны выбираться тщательно, чтобы результат действительно был таким же, как в исходном коде (при условии, что это более поздняя оптимизация уже работающего кода). Например, рассмотрим последствия, если количество итераций не делится на 5. Требуемые вручную поправки также становятся несколько более сложными, если условия тестирования являются переменными. См. также устройство Даффа .
В простом случае управление циклом — это просто административные издержки, которые упорядочивают продуктивные операторы. Сам по себе цикл ничего не дает для достижения желаемых результатов, а просто избавляет программиста от утомительного повторения кода сто раз, что можно было бы сделать с помощью препроцессора, генерирующего репликации, или текстового редактора. Аналогичным образом, ifоператоры - и другие операторы управления потоком могут быть заменены репликацией кода, за исключением того, что результатом может стать раздувание кода . Компьютерные программы легко отслеживают комбинации, но программисты находят это повторение скучным и допускают ошибки. Учитывать:
Но, конечно, выполняемый код не обязательно должен быть вызовом процедуры, и в следующем примере в вычислении используется индексная переменная:
который, если его скомпилировать, может создать много кода ( пресловутые операторы печати ), но возможна дальнейшая оптимизация. В этом примере в цикле ссылаются только на x(i) и x(i - 1) (последний только для создания нового значения x(i) ), поэтому, учитывая, что более поздних ссылок на массив x, разработанный здесь, нет , его использование можно заменить простой переменной. Однако такое изменение будет означать простую переменную, значение которой изменится , тогда как, если оставить массив, анализ компилятора может заметить, что значения массива являются постоянными, каждое из которых получено из предыдущей константы, и, следовательно, переносит постоянные значения, так что код становится
выведите 2, 2;распечатайте 3, 6;выведите 4, 24;...и т. д.
В общем случае содержимое цикла может быть большим и включать сложную индексацию массива. В этих случаях, вероятно, лучше всего оставить оптимизацию компиляторов для развертывания. Репликация самых внутренних циклов может позволить множество возможных оптимизаций, но даст лишь небольшой выигрыш, если n не велико.
Рассмотрим псевдокод цикла WHILE, подобный следующему:
В этом случае развертывание происходит быстрее, поскольку ENDWHILE (переход к началу цикла) будет выполняться на 66% реже.
Еще лучше, «измененный» пример псевдокода, который может выполняться автоматически некоторыми оптимизирующими компиляторами, полностью исключая безусловные переходы.
Поскольку преимущества развертывания цикла часто зависят от размера массива (который часто может быть неизвестен до времени выполнения), JIT- компиляторы (например) могут определить, следует ли вызывать «стандартную» последовательность цикла или вместо этого генерировать (относительно короткую) последовательность циклов. ) последовательность отдельных инструкций для каждого элемента. Эта гибкость является одним из преимуществ методов «точно в срок» по сравнению со статической или ручной оптимизацией в контексте развертывания цикла. В этой ситуации зачастую экономия все же полезна при относительно небольших значениях 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 («перемещение символа») используют базовое смещение. * адресация и каждое смещение в/из уменьшаются на длину одного элемента массива*(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 байт девятой записи. MVC 07*256(100,R2),07*256(R1) Переместить 100 байт восьмой записи. MVC 06*256(100,R2),06*256(R1) Переместить 100 байт седьмой записи. MVC 05*256(100,R2),05*256(R1) Переместить 100 байт шестой записи. MVC 04*256(100,R2),04*256(R1) Переместить 100 байт пятой записи. MVC 03*256(100,R2),03*256(R1) Переместить 100 байт четвертой записи. MVC 02*256(100,R2),02*256(R1) Переместить 100 байт третьей записи. MVC 01*256(100,R2),01*256(R1) Переместить 100 байт второй записи. 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 * («указатель»).** Статические массивы (они могут быть получены динамически).FROM 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 РАЗМЕР ПАКЕТА (8)int main ( void ) { int я знак равно 0 ; /* счетчик */ int elements = 50 ; /* общее количество для обработки */ int повтор ; /* количество повторений while*/ int left = 0 ; /* остаток (обработка позже) */ /* Если количество элементов не делится на BUNCHSIZE, */ /* получаем количество повторений, необходимое для выполнения большей части обработки в цикле while */ повтор = ( записи / BUNCHSIZE ); /* количество повторений */ left = ( записи % BUNCHSIZE ); /* вычисляем остаток */ /* Разворачиваем цикл на «группы» по 8 */ while ( repeat -- ) { printf ( "process(%d) \n " , i ); printf ( "процесс(%d) \n " , я + 1 ); printf ( "процесс(%d) \n " , я + 2 ); printf ( "процесс(%d) \n " , я + 3 ); printf ( "процесс(%d) \n " , я + 4 ); printf ( "процесс(%d) \n " , я + 5 ); printf ( "процесс(%d) \n " , я + 6 ); printf ( "process(%d) \n " , i + 7 ); /* обновляем индекс по сумме, обработанной за один раз */ i += BUNCHSIZE ; } /* Используйте оператор switch для обработки оставшегося набора, перейдя к метке случая */ /* к метке, которая затем будет пропущена для завершения набора */ switch ( left ) { case 7 : printf ( "process(%d) \ п " , я + 6 ); /* обработка и использование пропуска */ case 6 : printf ( "process(%d) \n " , i + 5 ); случай 5 : printf ( "process(%d) \n " , i + 4 ); случай 4 : printf ( "process(%d) \n " , i + 3 ); случай 3 : printf ( "process(%d) \n " , i + 2 ); случай 2 : printf ( "process(%d) \n " , i + 1 ); /* два слева */ case 1 : printf ( "process(%d) \n " , i ); /* осталось обработать только один */ case 0 : ; /* ничего не осталось */ } } Дублирования кода можно было избежать, если записать две части вместе, как в устройстве Даффа .
В следующем примере будет вычислено скалярное произведение двух векторов A и B из 100 элементов типа double. Вот код на C:
двойной dotProduct = 0 ; для ( int я знак равно 0 ; я < 100 ; я ++ ) { 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 ← Б[я] мул.д $f10 , $f10 , $f12 ; $f10 ← A[i]*B[i] add.d $f8 , $f8 , $f10 ; $f8 ← $f8 + A[i]*B[i] добавить $5 , $5 , 8 ; увеличить указатель для A[i] на размер ; из двойника. добавить $6 , $6 , 8 ; увеличить указатель для B[i] на размер ; из двойника. добавить $7 , $7 , -1 ; уменьшить количество циклов тест: бгц $7 , цикл3 ; Продолжить, если количество циклов > 0 Далее происходит то же самое, что и выше, но с развертыванием цикла, реализованным с коэффициентом 4. Еще раз обратите внимание, что размер одного элемента массивов (a double) составляет 8 байт; таким образом, смещения 0, 8, 16, 24 и смещение 32 в каждой петле.
цикл3: ld $f10 , 0 ( $5 ) ; итерация со смещением 0 ld $f12 , 0 ( $6 ) мул.д $f10 , $f10 , $f12 add.d $f8 , $f8 , $f10 ld $f10 , 8 ( $5 ) ; итерация со смещением 8 ld $f12 , 8 ( $6 ) мул.д $f10 , $f10 , $f12 add.d $f8 , $f8 , $f10 ld $f10 , 16 ( $5 ) ; итерация со смещением 16 ld $f12 , 16 ( $6 ) мул.д $f10 , $f10 , $f12 add.d $f8 , $f8 , $f10 ld $f10 , 24 ( $5 ) ; итерация со смещением 24 ld $f12 , 24 ( $6 ) мул.д $f10 , $f10 , $f12 add.d $f8 , $f8 , $f10 добавить $5 , $5 , 32 добавить $6 , $6 , 32 добавить $7 , $7 , -4 тест: бгц $7 , цикл3 ; Продолжить цикл, если $7 > 0 У Джима Геттиса есть замечательное объяснение этого эффекта на X-сервере. Оказывается, что с учетом прогнозов ветвей и изменения относительной скорости процессора по сравнению с памятью за последнее десятилетие, развертывание цикла практически бессмысленно. Фактически, благодаря удалению всех экземпляров Duff's Device с сервера XFree86 4.0 размер сервера уменьшился на _половину_а_ _мегабайт_ (!!!) и стал загружаться быстрее, поскольку удаление всего этого лишнего кода означало, что X-сервер не так сильно терял строки кэша.
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ){{cite journal}}: Требуется цитировать журнал |journal=( помощь )12.11 Развертывание цикла