Что такое разворачивание цикла

Большая часть времени исполнения программы приходится на циклы: это могут быть вычисления, прием и обработка информации и т.д. Правильное применение техник оптимизации циклов позволит увеличить скорость работы программы. Но прежде, чем приступать к оптимизациям необходимо выделить «узкие» места программы и попытаться найти причины падения быстродействия.

Время исполнения кода в циклах зависит от организации памяти, архитектуры процессора, в том числе, поддерживаемого набора инструкций, конвейеров, кэшей и опыта программиста.

Рассмотрим некоторые методы оптимизаций циклов: развертка циклов (loop unrolling), объединение циклов (loop fusion), разрезание циклов (loop distribution), выравнивание циклов (loop alignment), перестановка циклов (loop interchange), разделение на блоки (loop blocking).

Перед применением какой-либо оптимизации сделайте самое простое: вынесите из цикла все переменные, которые в нем не изменяются.

Какие причины могут привести к уменьшению скорости работы программы в циклах?

Итерации цикла зависимы и не могут исполняться параллельно.
Тело цикла большое и требуется слишком много регистров.
Тело цикла или количество итераций мало и выгоднее совсем отказаться от использования цикла.
Цикл содержит вызовы функций и процедур из сторонних библиотек.
Цикл интенсивно использует какое-то одно исполняющее устройство процессора.
В цикле имеются условные переходы.

Развертка циклов

Такая оптимизация выполняется, когда тело цикла мало. Необходимо более эффективно использовать исполняющие устройства на каждой итерации. Поэтому многократно дублируют тело цикла в зависимости от количества исполняющих устройств. Но такая оптимизация может вызвать зависимость по данным, чтобы от нее избавиться вводятся дополнительные переменные.

До

После

После №2

for (int i = 0; i < iN; i++){

res *= a[i];

}

for (int i = 0; i < iN; i+=3){

res *= a[i];

res *= a[i+1];

res *= a[i+2];

}

for (int i = 0; i < iN; i+=3){

res1 *= a[i];

res2 *= a[i+1];

res3 *= a[i+2];

}

res = res1 * res2 * res3;

В gcc можно применить следующие ключи: -funroll-all-loops -funroll-loops.

Объединение циклов

В цикле может быть долго выполняющиеся инструкции, например, извлечение квадратных корней. Или есть несколько циклов, которые выполняются по одинаковому интервалу индексов. Поэтому целесообразно объединить циклы для более сбалансированной нагрузки исполняющих устройств.

До

После

for(int i = 0; i < iN; i++){

a[i] = b[i] – 5;

}

for(int i = 0; i < iN-1; i++){

d[i] = e[i] * 3;

}

for(int i = 0; i < iN-1; i++){

a[i] = b[i] – 5;

d[i] = e[i] * 3;

}

a[iN-1] = b[iN-1] – 5;

Разрезание циклов

Данная оптимизация применяется, когда тело цикла большое и переменным не хватает регистров. Поэтому данные сначала вытесняются в кэш, а если совсем все плохо, то и в оперативную память. А доступ к оперативной памяти занимает ~300 тактов процессора, а доступ к L2 всего ~10. Доступ к памяти с большим шагом еще больше замедляет программу. Оптимально «ходить» по памяти с шагом 2n, где n – достаточно маленькое число (<7).

До

После

for (int j = 0; j < jN; j++){

for (int k = 0; k < kN; k++){

for (int m = 0; m < mN; m++){

i = j * k + m;

a[i] = b[i] * c[i] + f[i]/e[i]+ x[i] – y[i] +

z[i]/r[i] + d[i] * x[i];

}

for (int j = 0; j < jN; j++){

for (int k = 0; k < kN; k++){

double tmp;

for (int m = 0; m < mN; m++){

i = j * k + m;

tmp = b[i] * c[i] + f[i]/e[i];

a[i] = tmp – y[i] + z[i]/r[i] +

(d[i] + 1) * x[i];

}

Перестановка циклов

Во вложенных циклах важен порядок вложения. Поэтому необходимо помнить как хранятся массивы в памяти. Классический пример: c/c++ хранят матрицы построчно, а fortran – по столбцам.

До

После

for(int i = 0; i < iN; i++){

for(int j = 0; j < jN; j++){

for(int k = 0; k < kN; k++){

c[i][j] = c[i][j] + a[i][k] * b[k][j];

}

for(int i = 0; i < iN; i++){

for(int k = 0; k < kN; k++){

for(int j = 0; j < jN; j++){

c[i][j] = c[i][j] + a[i][k] * b[k][j];

}

Теперь обращения к массиву a идут последовательно.

Разделение циклов на блоки

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

До

После

for(int i = 0; i < iN; i++){

for(int j = 0; j < jN; j++){

a[i][j] = a[i][j] + b[i][j];

}

// размер блоков зависит от размера исходных массивов

int iBlk, jBlk;

for(int k = 0; k < iN/iBlk; k++){

for(int m = 0; m < jN/jBlk; m++){

for(int i = k * iBlk; i < ((k + 1) * iBlk); i++){

for(int j = m * jBlk; j < ((m + 1) * jBlk); j++){

a[i][j] = a[i][j] + b[i][j];

}

Примерно по такому принципу работает технология MPI: делит большие массивы на блоки и рассылает отдельным процессорам.

Разрешение зависимостей

Лучшее решение – избавиться. Но не со всеми зависимостями это получится.

for (int i = 1; i < N; i++){
a[i] = a[i-1] + 1;
}

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

Чтобы проверить цикл на независимость, измените направление движения в цикле на обратное. Если результат вычислений не изменился, то итерации цикла – независимы.

Относительно условных переходов

Потери времени возникают из-за ошибок в предсказании переходов, т. к. приходиться откатывать конвейер. Поэтому лучше всего отказаться от условных конструкций. Но, если это невозможно нужно постараться облегчить работу модулю предсказания переходов. Для этого разместите наиболее вероятные ветви в начале ветвления и, если возможно, вынесите условные конструкции за пределы цикла.

Вместо заключения

Если Вы создаете сложную программу, которая будет занимать много процессорного времени, то

Ознакомтесь с архитектурой процессора (узнайте сколько и каких исполняющих устройств у него есть, сколько конвейеров, размеры кэшей L1 и L2).
Попробуйте компилировать программу разными компиляторами и с различными ключами.
Учитывайте влияние операционной системы.

Также советую ознакомиться с этой статьей.

По своему опыту могу сказать, что грамотное применение оптимизаций может улучшить быстродействие программы в разы.

Если хотите сами потренироваться в оптимизации, то попробуйте вычислить число Пи:

Ниже приведен «плохой» код.

long N = 10000000;
double dx, sum, x;
sum = 0.0;
x = 0.0;
dx = 1.0 / (double) N;
for (long i = 0; i < N; i++){
sum += 4.0 / (1.0 + x * x);
x += dx;
}
double pi = dx * sum;

О чем я не рассказал: о векторизации вычислений (инструкции SSE); о prefetch’ах, облегчающих работу с памятью. Если будут люди «которым интересно», то напишу отдельную статью про векторизацию циклов.

Подсветка исходных кодов Source Code Highlighter.

Источник

Раскрутка петли , также известная как раскрутка петли , представляет собой преобразование петли метод, который пытается оптимизировать скорость выполнения программы за счет ее двоичного размера , который представляет собой подход, известный как компромисс между пространством и временем . Преобразование может быть выполнено вручную программистом или оптимизирующим компилятором . На современных процессорах развертывание цикла часто является контрпродуктивным, поскольку увеличенный размер кода может вызвать большее количество промахов в кэше; ср. Устройство Даффа .

Целью раскрутки цикла является увеличение скорости программы за счет уменьшения или исключения инструкций, управляющих циклом, таких как арифметика указателя и тесты «конца цикла» на каждой итерации; снижение отраслевых штрафов; а также сокрытие задержек, включая задержку чтения данных из памяти. Чтобы исключить эти вычислительные накладные расходы , циклы можно переписать как повторяющуюся последовательность аналогичных независимых операторов.

Развертывание цикла также является частью некоторых методов формальной проверки , в частности, ограниченная проверка модели .

Преимущества

Накладные расходы в «Плотные» циклы часто состоят из инструкций по увеличению указателя или индекса до следующего элемента в массиве (арифметика указателя ), а также тестов «конца цикла». Если оптимизирующий компилятор или ассемблер может предварительно вычислить смещения для каждой индивидуально указанной переменной массива, они могут быть встроены в инструкции машинного кода напрямую, что не требует дополнительных арифметических операций во время выполнения.

Значительный выигрыш может быть получен, если сокращение количества выполняемых инструкций компенсирует любое снижение производительности, вызванное увеличением размера программы.
Штраф за переход сведен к минимуму.
Если операторы в цикле независимы друг от друга (т.е. там, где операторы, которые появляются ранее в цикле, не влияют на операторы, следующие за ними), операторы потенциально могут выполняться в parallel .
Может быть реализовано динамически, если количество массивов элементы неизвестны во время компиляции (как в устройстве Даффа ).

Оптимизирующие компиляторы иногда выполняют развертывание автоматически или по запросу.

Недостатки

Увеличенный размер программного кода, что может быть нежелательно, особенно для встроенных приложений. Может также вызвать увеличение числа промахов в кэше инструкций, что может отрицательно сказаться на производительности.
Если не выполняется прозрачно оптимизирующим компилятором, код может стать менее читаемым .
Если код в теле Цикл e включает в себя вызовы функций, возможно, будет невозможно совместить развертывание с встраиванием , поскольку увеличение размера кода может быть чрезмерным. Таким образом, между двумя оптимизациями может быть компромисс.
Возможное увеличение использования регистров за одну итерацию для хранения временных переменных, что может снизить производительность, хотя многое будет зависеть от возможных оптимизаций.
Помимо очень маленького и простого кода, развернутые циклы, содержащие ветки, работают даже медленнее, чем рекурсии.

Статическое / ручное развертывание цикла

Ручное (или статическое) развертывание цикла требует, чтобы программист анализировал цикл и интерпретировал итераций в последовательность инструкций, что уменьшит накладные расходы цикла. Это контрастирует с динамическим развертыванием, которое выполняется компилятором.

Простой ручной пример на C

Процедура в компьютерной программе – удалить 100 элементов из коллекции. Обычно это выполняется с помощью цикла for , который вызывает функцию delete (item_number). Если эта часть программы должна быть оптимизирована, а накладные расходы на цикл требуют значительных ресурсов по сравнению с таковыми для функции delete (x), для его ускорения можно использовать раскручивание.

Обычный цикл	После разворачивания цикла
int x; for (x = 0; x	int x; for (x = 0; x

) В результате этой модификации новая программа должна сделать только 20 итераций вместо 100. После этого только 20% от необходимо выполнять переходы и условные переходы, и они представляют, в течение многих итераций, потенциально значительное снижение накладных расходов на администрирование цикла. Для получения оптимального преимущества в развернутом коде не следует указывать переменные, требующие арифметики указателя . Обычно для этого требуется адресация «база плюс смещение», а не индексированная ссылка.

С другой стороны, это ручное развертывание цикла увеличивает размер исходного кода с 3 строк до 7, которые должны быть созданы, проверены и отлажены, и компилятору, возможно, придется выделить больше регистров для хранения переменных в расширенной итерации цикла. Кроме того, переменные управления циклом и количество операций внутри структуры развернутого цикла должны быть тщательно выбраны так что результат действительно такой же, как в исходном коде (предположим Это более поздняя оптимизация уже работающего кода). Например, рассмотрим последствия, если количество итераций не делится на 5. Требуемые ручные поправки также становятся несколько более сложными, если условия теста являются переменными. См. Также Устройство Даффа .

Ранняя сложность

В простом случае управление циклом – это просто административные накладные расходы, которые организуют продуктивные операторы. Сам цикл не вносит никакого вклада в желаемые результаты, просто избавляя программиста от утомительного повторения кода сотни раз, что можно было бы сделать с помощью препроцессора, генерирующего репликации, или текстового редактора. Точно так же if -выражения и другие операторы управления потоком могут быть заменены репликацией кода, за исключением того, что результатом может быть раздувание кода . Компьютерные программы легко отслеживают комбинации, но программисты считают это повторение скучным и допускают ошибки. Рассмотрим:

Нормальный цикл	После разворачивания цикла
для i: = 1: 8 do if i mod 2 = 0 then do_even_stuff (i) else do_odd_stuff (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; Для i: = 2: 9 выполните x (i): = x (i – 1) * i; напечатайте i, x (i); следующий я;	х (1): = 1; х (2): = х (1) * 2; выведите 2, x (2); х (3): = х (2) * 3; выведите 3, x (3); х (4): = х (3) * 4; выведите 4, x (4); … и т. д.

, которые в случае компиляции могут привести к появлению большого количества кода (печально известные операторы печати), но возможна дальнейшая оптимизация. В этом примере делается ссылка только на x (i) и x (i – 1) в цикле (последний только для разработки нового значения x (i)), поэтому, учитывая, что нет более поздней ссылки на массив x, разработанный здесь, его использование может быть заменено простой переменной. Однако такое изменение будет означать простую переменную, значение которой изменяется, тогда как, оставаясь с массивом, анализ компилятора может отметить, что значения массива являются постоянными, каждое из которых получено из предыдущей константы, и поэтому переносит постоянные значения так, чтобы код становится

2, 2; печать 3, 6; печать 4, 24; …так далее.

В общем, содержимое цикла может быть большим, что связано со сложной индексацией массивов. Эти случаи, вероятно, лучше всего оставить для развертывания оптимизирующим компиляторам. Репликация самых внутренних циклов может позволить множество возможных оптимизаций, но даст лишь небольшой выигрыш, если n не велико.

Развертывание циклов WHILE

Рассмотрим цикл WHILE с псевдокодом, подобный следующему:

Обычный цикл	После развертывания цикла	Развернутый и “настроенный” цикл
WHILE (условие) DO действие ENDWHILE. . . . . .	WHILE (условие) DO action IF NOT (условие) THEN GOTO break action IF NOT (условие) THEN GOTO break action ENDWHILE LABEL break:.	IF (условие) THEN REPEAT action IF NOT (условие) THEN GOTO break action IF NOT (condition) THEN GOTO break action WHILE (условие) LABEL break:

В этом случае разворачивание выполняется быстрее, поскольку ENDWHILE (a переход к началу цикла) будет выполняться на 66% реже.

Еще лучше, пример “настроенного” псевдокода, который может выполняться автоматически некоторыми оптимизирующими компиляторами, полностью устраняя безусловные переходы.

Динамическое развертывание

Поскольку преимущества развертывания цикла часто зависят от размера массива – который часто может быть неизвестен до времени выполнения – JIT компиляторы (для example) может определить, вызывать ли «стандартную» последовательность цикла или вместо этого генерировать (относительно короткую) последовательность отдельных инструкций для каждого элемента. Такая гибкость является одним из преимуществ своевременных методов по сравнению со статической или ручной оптимизацией в контексте развертывания цикла. В этой ситуации часто бывает при относительно небольших значениях n, когда экономия по-прежнему полезна – требуется совсем небольшое (если вообще есть) общее увеличение размера программы (которое может быть включено только один раз как часть стандартной библиотеки).

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

Пример ассемблера (IBM / 360 или Z / Architecture)

Этот пример предназначен для ассемблеров IBM / 360 или Z / Architecture и предполагает поле размером 100 байт (при нулевом смещении) должно быть скопировано из массива FROM в массив TO – оба имеют 50 записей с длиной элемента 256 байт каждая.

1 * Адрес возврата находится в R14. 2 * Инициализировать регистры R15, R0, R1 и R2 из данных, определенных в конце 3 * программы, начинающейся с метки INIT / MAXM1. 4 LM R15, R2, INIT Set R15 = максимальное количество инструкций MVC 5 * (MAXM1 = 16), 6 * R0 = количество записей в массиве, 7 * R1 = адрес массива FROM и 8 * R2 = адрес массива TO. 9 * 10 * Здесь начинается цикл. 11 LOOP EQU * Определите метку LOOP. 12 * На этом этапе R15 всегда будет содержать число 16 (MAXM1). 13 SR R15, R0 Вычтите оставшееся число 14 * записей в массиве (R0) из R15. 15 BNP ALL Если R15 не является положительным, то есть у нас 16 * осталось более 16 записей 17 * в массиве, перейдите, чтобы выполнить всю последовательность 18 * MVC, а затем повторите. 19 * 20 * Рассчитайте смещение (от начала последовательности MVC) для безусловного перехода до 21 * «размотанного» цикла MVC ниже. 22 * Если количество оставшихся записей в массивах равно нулю, R15 будет 16, поэтому 23 * все инструкции MVC будут пропущены. 24 MH R15, = AL2 (ILEN) Умножьте R15 на длину одной инструкции 25 * MVC. 26 B ALL (R15) Переход к ALL + R15, адресу 27 * вычисленной конкретной инструкции MVC 28 * с переходом к остальным из них. 29 * 30 * Таблица инструкций MVC. 31 * Первая запись имеет максимально допустимое смещение с одним регистром = шестнадцатеричное F00 32 * (15 * 256) в этом примере. 33 * Все 16 из следующих инструкций MVC («перемещение символа») используют адресацию по основанию плюс смещение 34 *, и каждое смещение до / от уменьшается на длину одного элемента массива 35 * (256). Это позволяет избежать арифметики указателей для каждого элемента до 36 * максимально допустимого смещения в команде шестнадцатеричного FFF 37 * (15 * 256 + 255). Инструкции расположены в порядке уменьшения смещения, поэтому последний элемент 38 * в наборе перемещается первым. 39 ALL MVC 15 * 256 (100, R2), 15 * 256 (R1) Перемещение 100 байтов 16-й записи из 40 * массива 1 в массив 2 (с 41 * пропуском). 42 ILEN EQU * -ALL Устанавливает ILEN равным длине предыдущей инструкции 43 * MVC. 44 MVC 14 * 256 (100, R2), 14 * 256 (R1) Переместить 100 байтов 15-й записи. 45 MVC 13 * 256 (100, R2), 13 * 256 (R1) Перемещение 100 байтов 14-й записи. 46 MVC 12 * 256 (100, R2), 12 * 256 (R1) Перемещение 100 байтов 13-й записи. 47 MVC 11 * 256 (100, R2), 11 * 256 (R1) Переместить 100 байт 12-й записи. 48 MVC 10 * 256 (100, R2), 10 * 256 (R1) Перемещение 100 байт 11-й записи. 49 MVC 09 * 256 (100, R2), 09 * 256 (R1) Переместить 100 байтов 10-й записи. 50 MVC 08 * 256 (100, R2), 08 * 256 (R1) Перемещение 100 байтов 9-й записи. 51 MVC 07 * 256 (100, R2), 07 * 256 (R1) Перемещение 100 байтов 8-й записи. 52 MVC 06 * 256 (100, R2), 06 * 256 (R1) Переместить 100 байтов 7-й записи. 53 MVC 05 * 256 (100, R2), 05 * 256 (R1) Переместить 100 байт 6-й записи. 54 MVC 04 * 256 (100, R2), 04 * 256 (R1) Переместить 100 байт 5-й записи. 55 MVC 03 * 256 (100, R2), 03 * 256 (R1) Переместить 100 байт 4-й записи. 56 MVC 02 * 256 (100, R2), 02 * 256 (R1) Переместить 100 байт 3-й записи. 57 MVC 01 * 256 (100, R2), 01 * 256 (R1) Переместить 100 байт 2-й записи. 58 MVC 00 * 256 (100, R2), 00 * 256 (R1) Перемещение 100 байтов 1-й записи. 59 * 60 S R0, MAXM1 Уменьшите количество оставшихся записей 61 * для обработки. 62 BNPR R14 Если больше нет записей для обработки, верните 63 * по адресу в R14. 64 AH R1, = AL2 (16 * 256) Увеличивает указатель массива «FROM» за пределы 65 * первого набора. 66 AH R2, = AL2 (16 * 256) Увеличивает указатель массива «TO» за пределы 67 * первого набора. 68 L R15, MAXM1 Перезагрузите максимальное количество инструкций MVC 69 * на пакет в R15 70 * (уничтожено вычислением в 71 * первой инструкции цикла). 72 B LOOP Повторное выполнение цикла. 73 * 74 * Статические константы и переменные (их можно передавать как параметры, кроме 75 * MAXM1). 76 INIT DS 0A 4 адреса (указатели) 77 * должны быть предварительно загружены с помощью инструкции 78 * LM в начале программы. 79 MAXM1 DC A (16) Максимальное количество инструкций MVC 80 *, выполняемых за пакет. 81 N DC A (50) Количество фактических записей в массиве (переменная 82 *, устанавливается в другом месте). 83 DC A (FROM) Адрес начала массива 1 84 * («указатель»). 85 DC A (TO) Адрес начала массива 2 86 * («указатель»). 87 * 88 * Статические массивы (могут быть получены динамически). 89 FROM DS 50CL256 Массив из 50 записей по 256 байтов каждая. 90 TO DS 50CL256 Массив из 50 записей по 256 байт каждая.

В этом примере для «обычного» цикла (50 итераций) потребуется приблизительно 202 инструкции, тогда как для приведенного выше динамического кода потребуется всего около 89 инструкций (или примерно 56% экономии). Если бы массив состоял только из двух записей, он все равно выполнялся бы примерно за то же время, что и исходный развернутый цикл. Увеличение размера кода составляет всего около 108 байт – даже если в массиве тысячи записей.

Подобные методы, конечно, можно использовать, когда задействовано несколько инструкций, при условии, что длина комбинированной инструкции регулируется соответствующим образом. Например, в этом же примере, если требуется очистить оставшуюся часть каждой записи массива до нуля сразу после копирования 100-байтового поля, дополнительная инструкция очистки, XC xx * 256 + 100 (156, R1), xx * 256 + 100 (R2) , может быть добавлен сразу после каждого MVC в последовательности (где xx соответствует значению в MVC над ним).

Конечно, вполне возможно сгенерировать приведенный выше код «inline» с помощью одного оператора ассемблера macro , указав всего четыре или пять операндов (или, альтернативно, превратить его в библиотеку подпрограммы, доступ к которой осуществляется простым вызовом с передачей списка параметров), что делает оптимизацию легко доступной.

Пример C

В следующем примере демонстрируется динамическое развертывание цикла для простой программы, написанной на C . В отличие от приведенного выше примера ассемблера, арифметика указателя / индекса все еще генерируется компилятором в этом примере, потому что переменная (i) все еще используется для адресации элемента массива. Полная оптимизация возможна только в том случае, если в операторах замены используются абсолютные индексы.

#include / * Количество записей, обработанных за итерацию цикла. * / / * Обратите внимание, что это число является «постоянной константой», отражающей приведенный ниже код. * / #define BUNCHSIZE (8) int main (void) {int i = 0; / * счетчик * / int entry = 50; / * общее количество для обработки * / int repeat; / * количество повторов while * / int left = 0; / * остаток (обработать позже) * / / * Если количество элементов не делится на BUNCHSIZE, * / / * получить время повторения, необходимое для выполнения большей части обработки в цикле while * / repeat = (entries / BUNCHSIZE); / * количество повторений * / left = (entry% BUNCHSIZE); / * вычислить остаток * / / * Развернуть цикл “связками” по 8 * / while (repeat–) {f (“process (% d) n”, i); f (“процесс (% d) n”, i + 1); f (“процесс (% d) n”, i + 2); f (“процесс (% d) n”, i + 3); f (“процесс (% d) n”, i + 4); f (“процесс (% d) n”, i + 5); f (“процесс (% d) n”, i + 6); f (“процесс (% d) n”, i + 7); / * обновляем индекс по количеству обработанных за раз * / i + = BUNCHSIZE; } / * Используйте оператор switch для обработки оставшегося, перейдя к метке case * / / * на метке, которая затем перейдет к завершению набора * / switch (слева) {case 7: f (“process (% d) n “, i + 6); / * обрабатываем и полагаемся на пропуск * / case 6: f (“process (% d) n”, i + 5); случай 5: f (“процесс (% d) n”, i + 4); случай 4: f (“процесс (% d) n”, i + 3); случай 3: f (“процесс (% d) n”, i + 2); случай 2: f (“процесс (% d) n”, i + 1); / * два слева * / case 1: f (“process (% d) n”, i); / * остался только один для обработки * / case 0:; / * none left * /}}

Дублирования кода можно избежать, записав две части вместе, как в устройстве Даффа .

C в примере развертывания цикла языка ассемблера MIPS

В следующем примере будет вычислить скалярное произведение двух векторов A и B с 100 элементами типа double . Вот код на C:

1 double dotProduct = 0; 2 for (int i = 0; i

Преобразование в язык ассемблера MIPS

Ниже приведен ассемблерный код MIPS, который вычисляет скалярное произведение двух векторов из 100 элементов, A и B, перед реализацией развертывания цикла В приведенном ниже коде отсутствуют инициализации цикла:

Инициализировать счетчик цикла ($ 7) равным 100.
Инициализировать скалярное произведение ($ f10) равным 0.
Инициализировать A [i ] указатель ($ 5) на базовый адрес A.
Инициализировать B [i] указатель ($ 6) на базовый адрес B.

Обратите внимание, что размер одного элемента массивов ( a double ) составляет 8 байтов.

1 loop3: 2 ld $ f10, 0 ($ 5); $ f10 ← A [i] 3 ld $ f12, 0 ($ 6); $ f12 ← B [i] 4 mul.d $ f10, $ f10, $ f12; $ f10 ← A [i] * B [i] 5 add.d $ f8, $ f8, $ f10; $ f8 ← $ f8 + A [i ] * B [i] 6 addi $ 5, $ 5, 8; увеличить указатель для A [i] на размер 7. 8 addi $ 6, $ 6, 8; увеличить указатель для B [i] на размер 9; двойного. 10 addi $ 7, $ 7, -1; уменьшить количество циклов 11 test: 12 bgtz $ 7, loop3; продолжить, если количество циклов>0

Развертывание цикла в MIPS

Следующее то же, что и выше, но с развертыванием цикла, реализованным с коэффициентом 4. Еще раз обратите внимание, что размер одного элемента массивов (double ) составляет 8 байтов. ; таким образом, смещения 0, 8, 16, 24 и смещения 32 в каждой петле.

1 loop3: 2 l.d $ f10, 0 ($ 5); итерация со смещением 0 3 l.d $ f12, 0 ($ 6) 4 mul.d $ f10, $ f10, $ f12 5 add.d $ f8, $ f8, $ f10 6 7 l.d $ f10, 8 (5 долларов США); итерация со смещением 8 8 l.d $ f12, 8 ($ 6) 9 mul.d $ f10, $ f10, $ f12 10 add.d $ f8, $ f8, $ f10 11 12 l.d $ f10, 16 (5 $); итерация со смещением 16 13 l.d $ f12, 16 (6 $) 14 mul.d $ f10, $ f10, $ f12 15 add.d $ f8, $ f8, $ f10 16 17 l.d $ f10, 24 (5 $); итерация со смещением 24 18 ld $ f12, 24 (6 $) 19 mul.d $ f10, $ f10, $ f12 20 add.d $ f8, $ f8, $ f10 21 22 addi $ 5, $ 5, 32 23 addi $ 6, $ 6 , 32 24 addi $ 7, $ 7, -4 25 test: 26 bgtz $ 7, loop3; Продолжить цикл, если $ 7>0

См. Также

Ссылки

Дополнительная литература

Кеннеди, Кен; Аллен, Рэнди (2001). Оптимизация компиляторов для современных архитектур: подход, основанный на зависимости . Морган Кауфманн. ISBN1-55860-286-0 .

Внешние ссылки

Глава 7, страницы с 8 по 10 графического программирования Майкла Абраша , черный Книга посвящена развертыванию цикла с примером на ассемблере x86.
Обобщенное развертывание цикла дает краткое введение.
Оптимизация подпрограмм на языке ассемблера Руководство по оптимизации Agner Fog с техникой развертывания цикла (2012 г. ).

Источник