Средства разработки приложений


Обзор методов оптимизации кода - часть 15


На рис. 9 показан пример конвейеризации цикла. Команды, относящиеся к одной итерации исходного цикла, не могут выполняться параллельно в силу зависимостей по данным. Тело результирующего цикла составлено из команд, относящихся к трем смежным итерациям (i, i+1, i+2) и не зависящих друг от друга, так что их выполнение может быть спланировано параллельно. Число итераций, участвующих в конвейерном выполнении цикла, называется глубиной конвейеризацией (по аналогии с аппаратной конвейеризацией). Число итераций конвейеризованного цикла сокращается на n-1, где n - глубина конвейеризации, а в пролог и эпилог выносятся команды, относящиеся к начальным и завершающим итерациям исходного цикла.

a[0]=b[0]+2;

a[1]=b[1]+2;

d[0]=a[0]/n;

for (i=0;i<100;i++){ for (i=0;i<98;i++){

a[i]=b[i]+2; f[i]=d[i]+a[i];

d[i]=a[i]/n; ==> d[i+1]=a[i+1]/n;

f[i]=d[i]+a[i];} a[a+2]=b[i+2]+2;}

d[99]=a[99]/n;

f[98]=d[98]+a[98];

f[99]=d[99]+a[99]];

Рис. 9. Конвейеризация цикла

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

Обзор методов конвейеризации циклов можно найти в работах [7], [12].

Разбивка циклов (loop distribution). В некоторых случаях может иметь смысл преобразование, обратное слиянию и называемое разбивкой циклов. Это целесообразно, например, если тело цикла слишком длинное, и имеющееся число регистров недостаточно для размещения всех используемых в теле цикла переменных. В этом случае часть промежуточных значений приходится временно выгружать в память, а перед использованием в вычислениях загружать на регистры (в англоязычной литературе этот процесс обозначают термином register spilling). Благодаря разбивке цикла можно избежать дефицита регистров и выталкивания значений в память.

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




- Начало -  - Назад -  - Вперед -