ТЕХНИКА ОПТИМИЗАЦИИ ПРОГРАММ

       

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


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

Техника разворачивания циклов в общем случае сводится к уменьшению количества итераций за счет дублирования тела цикла соответствующее число раз. Рассмотрим следующий цикл:

for(a = 0; a < 666; a++)

      x+=p[a];

Листинг 2 Не оптимизированный исходный цикл

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

for(a = 0; a < 666; a+=2)

{// обратите внимание ^^^ с разверткой цикла

 // мы соответственно увеличиваем и шаг

     

      x+=p[a];

      x+=p[a + 1];      // продублированное тело цикла

      /*     ^^^ корректируем значение счетчика цикла */



}

Листинг 3 Пример реализации двукратного разворота цикла

Разворот цикла в четыре раза будет еще эффективнее, но непосредственно этого не сделать, ведь количество итераций цикла не кратно четырем: 666 на 4 нацело не делится! Один из возможных путей решения: округлить количество итераций до величины кратной четырем (или, в более общем случае, – кратности разворота цикла), а оставшиеся итерации поместить за концом цикла.

Оптимизированный код может выглядеть, например, так:

for(a = 0; a < 664; a+=4)

{ // округляем ^^^ количество итераций до величины

  // кратной четырем

 

      x+=p[a];          // четырежды

      x+=p[a + 1];      //    дублируем


      x+=p[a + 2];      //          тело

      x+=p[a + 3];      //                цикла

}

x+=p[a];          // оставшиеся две итерации добавляем в конец

x+=p[a + 1];      // цикла

Листинг 4 Пример реализации четырехкратного разворота цикла в случае, когда количество итераций цикла не кратно четырем

Хорошо, а как быть, если количество итераций на стадии компиляции еще неизвестно? (То есть, количество итераций – переменная, а не константа). В этой ситуации разумнее всего прибегнуть к битовым операциям:

for(a = 0; a < (N & ~3); a += k)

{ // округляем ^^^ количество итераций до величины

  // кратной степени разворота

     

            x+=p[a];

            x+=p[a + 1];

            x+=p[a + 2];

            x+=p[a + 3];

}

// оставшиеся итерации добавляем в конец цикла

for(a = (N & ~3)); a < N; a++)

      x+=p[a];

Листинг 5 Пример реализации четырехкратного разворота цикла в случае заранее неизвестного количества итераций

Как нетрудно догадаться, выражение (N & ~3)) и осуществляет округление количества итераций до величины кратной четырем. А почему, собственно, четырем? Как вообще зависит скорость выполнения цикла от глубины его развертки? Что ж, давайте поставим эксперимент! Несколько забегая вперед отметим, что эффективность оптимизации зависит не только от глубины развертки цикла, но и рода обработки данных. Поэтому, циклы, читающие память, и циклы, записывающие память, должны тестироваться отдельно. Вот с чтения памяти мы, пожалуй, и начнем…

/* -----------------------------------------------------------------------

 

                     не оптимизированный вариант

                           (чтение)

----------------------------------------------------------------------- */

for (a = 0; a < BLOCK_SIZE; a += sizeof(int))

       x += *(int *)((int)p + a);

/* -----------------------------------------------------------------------

 

                     разворот на четыре итерации



                           (чтение)

----------------------------------------------------------------------- */

for (a = 0; a < BLOCK_SIZE; a += 4*sizeof(int))

{

       x += *(int *)((int)p + a );

       x += *(int *)((int)p + a + 1*sizeof(int));

       x += *(int *)((int)p + a + 2*sizeof(int));

       x += *(int *)((int)p + a + 3*sizeof(int));

}

Листинг 6 [Memory/unroll.read.c] Фрагмент программы, исследующий влияние глубины развертки цикла, читающего память, на время его выполнения

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

Целесообразнее всего, как следует из диаграммы graph 28, разворачивать цикл в восемь или шестнадцать раз. Дальнейшее увеличение степени развертки практически не добавляет производительности.



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

С записью же картина совсем другая (см. рис. graph 29). /* Поскольку, тестовая программа мало чем отличается от предыдущей ради экономии места она опускается. */ На P?III/I815EP время выполнения цикла, записывающего память, вообще не зависит от глубины развертки. Ну, практически не зависит. Развернутый цикл выполняется на ~2% медленнее за счет потери компактности кода. Впрочем, этой величиной можно и пренебречь. Для увеличения эффективности выполнения программы под процессором Athlon следует развернуть записывающий цикл в шестнадцать раз. Это практически на четверть повысит его быстродействие!





Рисунок 17 graph 29 Эффективность разворачивания циклов, записывающих память. Время выполнения цикла практически не зависит от глубины развертки и лишь на AMD Athlon шестнадцати кратная развертка несколько увеличивает его производительность

Что же касается смешанных циклов, обращающихся к памяти и на запись, и на чтение одновременно, – их так же рекомендуется разворачивать в восемь–шестнадцать раз. (см. так же "Группировка операций чтения с операциями записи").

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

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

Одна из таких программ и приведена ниже в качестве наглядной иллюстрации. Согласитесь, элегантно решить эту (отнюдь не надуманную!) задачу средствами ANSI Cи/Си++ физически невозможно!

; /* -------------------------------------

;  *

;  * макрос, дублирующий свое тело N раз

;  *

;

-------------------------------------- */


READ_BUFF MACRO N

       MYN = N

       MYA = 0

       ; // цикл дублирования своего тела

       WHILE MYA NE MYN

              ; // тело цикла

              ; // макропроцессор продублирует его заданное число раз

              MOV EDX, [EBX + 32 * MYA]

              MYA = MYA + 1

       ENDM

ENDM

UNROLL_POWER  EQU 8  ; //   глубина разворота цикла

Loop:

       READ_BUFF UNROLL_POWER



       ; //      ^^^^^^^^^^^^     обратите внимание, глубина разворота

       ; //                       задается препроцессорной константой!

       ; //                       никакой ручной работы!

      

       ADD EAX, EDX

       ADD EBX, 4 * UNROLL_POWER

       ; // коррекция ^^^^^^^^^^^^^^ количества итераций

      

       DEC ECX

       JNZ Loop

Листинг 7 Пример разворачивания цикла средствами макроассемблера. Макрос READ_BUFF позволяет разворачивать цикл произвольное количество раз

Разворот цикла средствами препроцессора Си. Хотя автоматически развернуть цикл директивами препроцессора ANSI Cи/Си++ невозможно, пути изгнания рутины из жизни программиста все-таки существуют! Стоит только подумать…

Одна из идей состоит в отказе от модификации счетчика цикла внутри заголовка цикла и выполнении этой операции внутри макроса "продразверстки". В результате, необходимость ручной коррекции счетчика отпадает и все копии тела цикла становятся идентичны друг другу. А раз так, – почему бы их не засунуть в препроцессорный макрос?

Это можно сделать, например, так:

#define BODY x+=p[a++];           // тело цикла

for(a=0; a < BLOCK_SIZE;)

{

       // разворот цикла в 8 раз

       BODY;  BODY; BODY; BODY;

       BODY;  BODY; BODY; BODY;

}

Листинг 8 Пример разворачивания цикла средствами препроцессора языка Си. Это лучшее, что язык Си в состоянии нам предложить


Содержание раздела