Статья: Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд

a[i+2]=a[i+2]+c;

a[i+3]=a[i+3]+c;}

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

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

Слияние циклов (loop fusion). Два расположенных последовательно цикла можно слить, если они имеют одинаковое число итераций и отсутствуют зависимости по данным, препятствующие объединению. Если тела сливаемых циклов не зависят друг от друга (рис. 7), появляется возможность спланировать параллельное выполнение команд, относящихся к разным циклам.

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

b[i]=b[i]+c; ==> b[i]=b[i]+c;

for (j=0;j<100;j++) a[i]=a[i]*2;

a[j]=a[j]*2; }

Рис. 7. Слияние циклов

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

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

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

b[i]=b[i+2]+c; ==> b[i]=b[i+2]+c;

for (j=0;j<102;j++) a[i]=a[i]*2;}

a[j]=a[j]*2; a[100]=a[100]*2;

a[101]=a[101]*2;

Рис. 8. Слияние циклов с подгонкой одного из них

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

На рис. 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];