Оптимизации циклических конструкций

10/17/10 FE (C++/C или Fortran) Внутреннее представление Профилировщик Скалярные оптимизации HPO Генератор кода Исходные файлы Обьектные файлы Временный файл или Obj с ВП IP/IPO оптимизации Скалярные оптимизации HPOГенератор кода Исполняемый файл Библиотека Архитектура компилятора

Циклы В большинстве случаев именно циклы являются «горячими местами» программы. Именно поэтому циклам уделяется много внимания как в архитектуре микропроцессора, так и в компиляторе. Loop Stream Detector – позволяет отказаться от выборки и декодирования инструкций для маленьких циклов. В компиляторе существует множество оптимизаций, ориентированных именно на обработку циклов.

Распознание и классификация циклов Такие оптимизации, как правило, могут быть выполнены только для циклов с определенным количеством итераций; имеющих последовательно изменяющиеся итерационные переменные; не имеющих переходов за пределы цикла; не имеющих вызовов неизвестных функций; Примеры «хороших» циклов: 1.) for(i=0;i

Примеры «плохих» циклов: 1.) for(i=0;i

Обзор оптимизаций циклических конструкций Значительная часть оптимизаций компилятора связаны с циклами. Вынос инвариантов цикла (Loop invariant code motion) – оптимизация, которая находит и выносит за пределы цикла выражения, независящие от индексных переменных цикла. То есть это выражение неизменно на каждой итерации. while (j < maximum - 1) { j = j + (4+array[k])*pi+5; } => loop invariant code motion => int maxval = maximum - 1; int calcval = (4+array[k])*pi+5; while (j < maxval) { j = j + calcval; }

Вынос условных переходов (Loop unswitching) – оптимизация, которая выносит условные переходы, инвариантные для цикла, из цикла путем дублирования тела цикла. do i=1,1000 x[i] = x[i] + y[i]; if (w) then y[i] = 0; end do; => loop unswitching => if (w) then do i=1,1000 x[i] = x[i] + y[i]; y[i] = 0; end do; else do i=1,1000 do x[i] = x[i] + y[i]; end do end if;

Тест для оценки эффекта оптимизации loop unswitching: #include int main() { float x[1000],y[1000]; int i,repeat,p; for(i=0;i

Сравнение событий BR_MISSP_EXEC для оригинального и модифицированного теста:

Привязка событий процессора к строкам кода:

Разбиение, объединение циклов (Loop distribution, loop fusion) – это обратные друг другу оптимизации. Компилятор должен иметь инструмент оценки выгодности таких оптимизаций. Разбиение циклов способно улучшить производительность за счет улучшения работы с памятью. Т.е. если цикл работает с большим количеством различных массивов, то может происходить вытеснение из кеша необходимых для последующих операций адресов. Из-за большого количества инвариантов цикла будет происходить вытеснение регистров (register spilling). Есть еще факторы, которые способны улучшить производительность при разбиении циклов. int i, a[100], b[100]; for (i = 0; i < 100; i++) { a[i] = 1; b[i] = 2; } => Loop distribution => for (i = 0; i < 100; i++) { a[i] = 1; } for (i = 0; i < 100; i++) { b[i] = 2; }

Объединение циклов может быть выгодным для небольших циклов за счет улучшения уровня инструкционного параллелизма и повторного использования данных. int i, a[100], b[100]; for (i = 0; i < 100; i++) { a[i] = 1; } for (i = 0; i < 100; i++) { b[i] = 2; } => Loop fusion for (i = 0; i < 100; i++) { a[i] = 1; b[i] = 2; } Различные микропроцессоры имеют различные критерии выгодности применения этой оптимизации.

Расщепление цикла (Loop peeling,splitting) – оптимизация, которая пытается упростить цикл «отщеплением» крайних итераций. p = 10; for (i=0; iLoop peeling => y[0] = x[0] + x[10]; for (i=1; i

Развертка цикла (Loop unrolling) – эта техника призвана уменьшить количество условных переходов в цикле. Может улучшить инструкционный параллелизм. Несколько итераций цикла объединяются в одну. Есть свои минусы. Может повыситься нагрузка на регистры, увеличивается размер кода, что также может привести к ухудшению производительности. for (int x = 0; x < 100; x++) { delete(x); } => Loop unrolling => for (int x = 0; x < 100; x += 5) { delete(x); delete(x+1); delete(x+2); delete(x+3); delete(x+4); } Полная развертка (complete unrolling) применяется к небольшим циклам и бывает очень эффективна. Как правило, в случае вложенных циклов развертываются внутренние циклы.

Перестановка циклов (Loop interchange) – оптимизация, при которой меняется порядок итерационных переменных. do i=0,10 do j=0,20 a[i,j] = i + j => Loop interchange do j=0,20 do i=0,10 a[i,j] = i + j ? Для чего выполняется эта оптимизация ?

ifort -O3 test.f90 -o a.out ifort -O2 test.f90 -o b.out Сообщение, выдаваемое компилятором ( с внутренними ключом), сообщает, что в первом случае компилятор совершил перестановку циклов. … LOOP INTERCHANGE in loops at line: Loopnest permutation ( ) --> ( ) … time./a.out real 0m0.960s time./b.out real 0m6.862s INTEGER,PARAMETER :: N=100 INTEGER,PARAMETER :: REPEAT=1000 INTEGER :: A(N,N,N), B(N,N,N) INTEGER :: REP,I,J,K A=1 B=1 DO REP=1,REPEAT DO I=1,N DO J=1,N DO K=1,N A(J,K,I) = A(J,K,I)+B(J,K,I) END DO END DO PRINT *,A(1,1,1) END Пример эффективности оптимизации перестановки циклов :

Вытеснение данных из кэш:

Разбиение цикла на блоки (Loop blocking) INTEGER, PARAMETER :: N=2000 INTEGER :: BF,BN,I,J,K,I1,J1,K1 DOUBLE PRECISION, ALLOCATABLE :: A(:,:),B(:,:),C(:,:) ALLOCATE(A(N,N),B(N,N),C(N,N)) A=1 B=-1 #ifdef PERF BF=8 BN=N/BF DO I1=1,BF DO J1=1,BF DO K1=1,BF DO I=1+BN*(I1-1),MIN(BN*I1,N) DO J=1+BN*(J1-1),MIN(BN*J1,N) DO K=1+BN*(K1-1),MIN(BN*K1,N) C(J,I) = C(J,I) + A(I,K)*B(K,J) END DO #else DO I=1,N DO J=1,N DO K=1,N C(J,I) = C(J,I) + A(I,K)*B(K,J) END DO #endif PRINT *,C(1:100,700:800) END ifort loop_blocking.F90 /fpp –Od -Feoriginal ifort loop_blocking.F90 /fpp –DPERF –Od –Feblocking Nehalem: Time original.exe ~150s Time blocking.exe ~105s

10/17/10

Определение индукционных переменных Выражения, которые являются линейной функцией от счетчиков цикла могут вычисляться прибавлением константы к значению на предыдущей итерации. for(i=0;i temp=4; for(i=0;i

Другие оптимизации Помимо этих оптимизаций существуют и другие, порой очень нетривиальные: Strength reduction Scalar expansion Loop skewing Loop coalescing Loop collapsing и многие другие. Компилятору в каждом случае необходимо доказать корректность производимой цикловой оптимизации и определить ее выгодность.

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

Зависимость – это связь между утверждениями программы. Пара утверждений находится в зависимости, если S2 должно выполняться после S1 для того, чтобы сохранить неизменным результат в памяти. S1 PI = 3.14 S2 R = 5 S3 AREA = PI*R **2 эквивалентно Таким образом здесь существуют две зависимости.,. Концепция зависимости в линейном коде проста, но для получения реальной выгоды от преобразований мы должны расширить эту концепцию для циклов и массивов. DO I=1,N S1 A(I) = B(I) + 1 S2 B(I+1) = A(I) – 5 END DO В этом цикле есть зависимость и зависимость для всех итераций, кроме первой. Эти зависимости - пример зависимостей по данным (Data dependence). S1 IF (T.NE.0) THEN S2 A=A/T S3 ENDIF Это пример зависимости по управлению (control dependence). S2 не может вычисляться перед S1.

Определение: Существует зависимость по данным между утверждением S1 и S2 тогда и только тогда, когда 1.оба утверждения обращаются к одной и той же области памяти, и по крайней мере одно из них пишет в память; 2.существует возможный путь при исполнении программы от выражения S1 к выражению S2. Зависимости по данным классифицируются следующим образом: 1.Истинная зависимость (True dependence) S1 X=… S2 …=X Обозначается S1δS2 (δ – дельта) или еще flow dependence 2.Антизависимость (antidependence) S1 …=X S2 X=… S1δ - S2 3.Выходная зависимость (output dependence) S1 X=… S2 X=… S1δ 0 S2

Для зависимостей в циклах вводятся дополнительные определения. DO I=1,N S1 A(I+1) =A(I) + B(I) END DO S1 зависит от себя на предыдущей итерации DO I=1,N S1 A(I+2) = A(I) +B(I) END DO Для определения зависимостей используется нормализованный цикл. Т.е. цикл от 1 до некоторого N c шагом 1. Пусть дано множество вложенных циклов из n циклов. Тогда итерационным вектором I некоторой итерации является вектор целых чисел, каждое из которых представляет значение итерационной переменной для каждого цикла в порядке вложенности. I={i1,i2,…,in} Существует циклическая зависимость между утверждениями S1 и S2 во множестве вложенных циклов тогда и только тогда, когда 1.существует два итерационных вектора i и j для этого множества, такие что i

Нормализованный цикл Предположим, у нас есть цикл: DO I=L,U,S A(I)=… END DO Для упрощения рассуждений его можно преобразовать к нормализованному циклу: DO J=1,(U-L+S)/S,1 A(J*S-S+L) = … END DO Так как любой цикл может быть нормализован, будем без ограничения общности рассматривать в примерах нормализованные циклы.

Теперь наша задача связать эквивалентность двух вычислительных процессов (в нашем случае до и после компиляторной оптимизации) с понятием зависимости. Все обсуждаемые ранее оптимизации циклических конструкций - это так называемые перестановочные (reordering) трансформации. Они изменяют порядок выполнения кода без добавления или удаления каких- либо утверждений. Фундаментальная теорема зависимостей: Всякая оптимизация, сохраняющая зависимости в программе (т.е. не изменяющая порядка зависимых утверждений), не влияет на результат вычислений. Соответственно, некая трансформация правомерна в данной программе, если она сохраняет все зависимости в программе.

Каким образом находятся зависимости? Предположим, что мы имеем набор вложенных циклов DO i 1 =1,N 1 DO i 2 =1,N 2 … DO i n =1,N n S1 A(f 1 (i 1,…,i n ),…,f m (i 1,…,i n )) = A(g 1 (i 1,…,i n ),…,g m (i 1,…,i n )) END DO … END DO Зависимость существует тогда и только тогда, когда существуют итерационные вектора I и J, такие что I

Предположим, что существует некоторая зависимость между утверждением S1 на итерации i набора вложенных циклов и утверждением S2 на итерации j, тогда дистанционный вектор зависимости (dependence distance vector) d(i,j) определяется как вектор длины n такой, что d(i,j) k =jk -ik. Вектор направления зависимости будет D(i,j) k = 0 > if(d(i,j) k

Зависимость в цикле не существует, если она имеет вектор направления такой, что крайнее слева не = направление не является для крайнего слева не = направления. Это означает, что в процессе трансформации мы сохранили все зависимости, и ни одна зависимость не изменила своего смысла.

Мы рассмотрели принципы доказательства правомерности трансформации в случае неизменности порядка утверждений внутри цикла. Существует методы доказательства правомерности перестановок с изменением порядка утверждений в теле цикла. Зависимости в цикле могут быть привносимыми циклом (loop-carried) и независимыми от цикла (loop-independent). DO I=1,N S1 A(I+1) =F(I) S2 F(I+1) = A(I) END DO Это пример зависимости, привносимой циклом. DO I=1,N S1 A(I)=… S2 …=A(I) END DO Это пример зависимости, независимой от цикла.

Разрешение противоречий при работе с памятью Для того чтобы правильно найти зависимости в программе, важно также произвести устранение неоднозначности при работе с памятью (memory disambiguation). То есть выделить объекты, которые могут пересекаться по памяти. При принятии решения используется вся возможная информация Особенности языка Результаты межпроцедурного анализа Local Point To анализ и т.д. Если есть объекты, для которых мы не можем гарантированно утверждать, что они не пересекаются по памяти, то нужно действовать консервативно - перестановочные оптимизации невозможны.

10/17/10 File sub.c int sub(int *a, float *b, int n) { int i; for(i=0;i

icc main.c 2.c –O3 2.c(3): (col. 1) remark: LOOP WAS VECTORIZED. 2.c(6): (col. 1) remark: LOOP WAS VECTORIZED. icc main.c 2.c –O3 –ansi-alias 2.c(3): (col. 1) remark: FUSED LOOP WAS VECTORIZED. В чем здесь разница? -[no-]ansi-alias enable/disable(DEFAULT) use of ANSI aliasing rules in optimizations; user asserts that the program adheres to these rules. Правила anti aliasing требуют, указатель может быть разыменован только к объекту такого же или совместимого типа. На практике это означает, что указатели несовместимых типов не могут адресовать одну память. Указав при компиляции опцию – anti-alias, вы позволяете компилятору выполнять оптимизации более агрессивно.

Для облегчения работы компилятора при различении объектов, адресующих различную память в C/C++, можно использовать атрибут restrict при объявлении указателей. Этот атрибут объявляет, что только указатель или выражение базирующееся на этом указателе может ссылаться на память, на которую он указывает. int sub(int *a, float *b, int n) => int sub(int* restrict a, float *restrict b, int n) Язык Фортран имеет специальные атрибуты для упрощения работы по различению объектов. Хотя в языке существуют указатели на массивы, но каждый массив, на который может ссылаться указатель, должен быть явно объявлен как TARGET. По умолчанию аргументы функции не должны указывать на объекты, которые пересекаются по памяти.

/Qopt-report[:n] generate an optimization report to stderr 0 disable optimization report output 1 minimum report output 2 medium output (DEFAULT when enabled) 3 maximum report output Пример диагностики: LOOP INTERCHANGE in loops at line: 8 9 Loopnest permutation ( 1 2 ) --> ( 2 1 ) Fusion loop partitions: (loop line numbers) Fused Loops: ( 9 14 ) 10/17/10

Спасибо за внимание!