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


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


Число n называется коэффициентом развертки цикла.

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

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

==> a[i+1]=a[i+1]+c;

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). Идея конвейеризации цикла заключается в том, что выполнение команд, относящихся к последующим итерациям, начинается раньше, чем завершается выполнение предшествующих итераций. Конвейеризация применима в тех случаях, когда тело цикла можно разбить на группы команд, не зависящих друг от друга на разных итерациях.




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