Оптимизация циклов Юрий Долгов, Дмитрий Шкурко

Optimization of applications for Intel* platforms Оптимизация Уменьшение требований к ресурсам Времени исполнения Используемой памяти Потребления энергии Очень сложная проблема Сложность от неразрешимой до NP-трудной Используются эвристики Эвристики и методы зависят от архитектуры

Optimization of applications for Intel* platforms Оптимизация циклов Наиболее важной областью для оптимизации являются циклы, т. к. в них выполняется большая часть команд. Одни и те же действия можно выполнить разными путями. Цель – выбрать наиболее подходящий, исходя из наличия портов, исполнительных устройств, задержки готовности данных. Вращающиеся регистры, механизм предикатов и специальные команды перехода позволяют организовать программный конвейер, который заметно уменьшает влияние задержек готовности данных

Optimization of applications for Intel* platforms Вращение регистров Вращающиеся регистры f (вращаются все регистры) p16-63 (вращаются все регистры) r (число вращающихся регистров должно быть кратно 8 и определяется командой alloc) –alloc r14=ar.pfs,4,28,0,16 Вращение регистров запускается следующими командами перехода –br.ctopbr.cexitbr.wtopbr.wexit Вращение осуществляется от меньшего к большему номеру регистра –f32 f33p16 p17r35 r36 Круговое вращение –f127 f32p63 p16r47 r32 (если задано 16 вращающихся регистров)

Optimization of applications for Intel* platforms Программный конвейер (Software Pipeline) Stage 1 Stage 2 Stage 3 Prolog 1 Prolog 2 Loop Body Epilog 1 Epilog 2

Optimization of applications for Intel* platforms Прохождение программного конвейера

Optimization of applications for Intel* platforms Data-Flow-Based Loop Transformations Loop-Based Strength Reduction (Уменьшение сложности цикла): Исходный цикл:После уменьшения сложности: do i = 1, nT = c; a[i] = a[i] + c * i;do i = 1, n end do a[i] = a[i] + T; T = T + c; end do

Optimization of applications for Intel* platforms Data-Flow-Based Loop Transformations Loop Invariant Code motion (Вынос инвариантного кода из цикла): Исходный цикл:После выноса кода: do i = 1, nif (n > 0) C = sqrt(r); a[i] = a[i] + sqrt(r);do i = 1, n end do a[i] = a[i] + C; end do

Optimization of applications for Intel* platforms Data-Flow-Based Loop Transformations Loop Unswitching (Вынос условия из цикла): Исходный цикл:После выноса условия: do i = 2, nif (n > 1) then a[i] = a[i] + с; if (x < 7) then if (x < 7) then do i = 2, n b[i] = a[i] * c[i]; a[i] = a[i] + c; else b[i] = a[i] * c[i]; b[i] = a[i-1] * b[i-1]; end do end if else end do do i = 2, n a[i] = a[i] + c; b[i] = a[i-1] * b[i-1]; end do end if

Optimization of applications for Intel* platforms Loop Reordering (переупорядочивание цикла) Loop interchange (Смена порядка циклов): Исходный цикл:После смены порядка: do i = 1, ndo j = 1, n do j = 1, n do i = 1, n total[i] = total[i] + a[i,j]; end doend do

Optimization of applications for Intel* platforms Loop Reordering (переупорядочивание цикла) Loop skewing (Скос цикла): Исходный цикл:После скоса: do i = 2, n-1do i = 2, n-1 do j = 2, m-1 do j = i+2, i+m-1 a[i, j] = (a[i-1, j] + a[i, j-1] + a[i, j] = (a[i-1, j-i] + a[i, j-1-i] + a[i+1, j] + a[i, j+1]) / 4; a[i+1, j-i] + a[i, j+1-i]) / 4; end do end doend do После скоса и смены порядка do j = 4, m+n-2 do i = max(2, j-i+1), min(n-1, j-2) a[i, j] = (a[i-1, j-i] + a[i, j-1-i] + a[i+1, j-i] + a[i, j+1-i]) / 4; end do

Optimization of applications for Intel* platforms Loop Reordering (переупорядочивание цикла) Loop reversal (Реверсия цикла): Исходный цикл:После реверсии: do i = 1, ndo i = 1, n do j = 1, n do j = n, 1, -1 a[i, j] = a[i-1, j+1] + 1; a[i, j] = a[i-1, j+1] + 1; end do end doend do П орядок циклов менятьПорядок циклов менять нельзя! можно!

Optimization of applications for Intel* platforms Loop Reordering (переупорядочивание цикла) Loop tiling (Разбиение на блоки) Исходный цикл:После разбиения на блоки: do i = 1, ndo TI = 1, n, 64 do j = 1, n do TJ = 1, n, 64 a[i, j] = b[j, i]; do i = TI, min(TI+63, n) end do do j – TJ, min(TJ+63, n) end do a[j, j] = b[j, i]; end do

Optimization of applications for Intel* platforms Loop Reordering (переупорядочивание цикла) Loop distribution (Разбиение цикла) Исходный цикл:После применения разбиения: do i = 1, ndo i = 1, n a[i] = a[i] + c; a[i] = a[i] + c; x[i+1] = x[i] * 7 + x[i+1] + a[i];end do end dodo i = 1, n x[i+1] = x[i] * 7 + x[i+1] + a[i]; end do; Loop fusion (Объединение циклов) – обратная операция.

Optimization of applications for Intel* platforms Loop Restructuring (Изменение структуры цикла) Loop unrolling (Раскрутка цикла) Исходный цикл:После раскрутки: do i = 2, n-1do i = 2, n-1, 2 a[i] = a[i] + a[i-1] * a[i+1]; a[i] = a[i] + a[i-1] * a[i+1]; end do a[i+1] = a[i+1] + a[i] * a[i+2]; end do if (mod(n-2,2) = 1) then a[n-1] = a[n-1] + a[n-2] * a[nl end if

Optimization of applications for Intel* platforms Loop Restructuring (Изменение структуры цикла) Loop collapsing (Свертывание цикла) Исходный цикл:После свёртки: do i = 1, nreal TA[n*m]; do j = 1, m copy(TA, a); a[i, j] = a[i, j] * a[i, j] + c; do i = 1, m*n end do TA[i] = TA[i] * TA[i] + c;end do

Optimization of applications for Intel* platforms Memory Access Transformations Array padding Исходный цикл:После пэддинга: real[n, 16384] real[n, 16385] do i = 1, ndo i = 1, n a[i, 1] = a[i, 1] * a[i, 1] + c; a[i, 1] = a[i, 1] * a[i, 1] + c;end do

Optimization of applications for Intel* platforms Memory Access Transformations Scalar expansion (Расширение скаляров) Исходный цикл:После расширения: do i = 1, nreal T[n]; с = b[i]; do i = 1, n a[i] = a[i] + c; T[i] = b[i]; end do a[i] = a[i] + T[i]; end do

Optimization of applications for Intel* platforms Memory Access Transformations Scalar replacement (Замена скалярами) Исходный цикл:После замены: do i = 1, ndo i = 1, n do j = 1, m T = total[i]; total[i] = total[i] + a[i, j]; do j = 1, m end do T = T + a[i, j]; end do total[i] = T; end do

Optimization of applications for Intel* platforms Векторизация – это изменение циклов таким образом, чтобы задействовать MMX/SSE/SSE2 инструкции и регистры. Типы данных: char/short/int/float/double не могут быть смешанными C/C++ and Fortran Ключи компилятора: -xW, -xK, -axW, -axK -vec_report3 позволяет узнать был ли цикл векторизован. Vectorization (Векторизация)

Optimization of applications for Intel* platforms SIMD data types 16x bytes 8x words 4x dwords 2x qwords 1x dqword 4x floats 2x doubles Pentium 4 Pentium III

Optimization of applications for Intel* platforms Условия для векторизации Итерации должны быть независимыми Векторизуются только внутренние циклы Только циклы типа for Желательно иметь выравненные массивы Разрешаются: Простые выражения с if Некоторые intrinsic функции Присваивание скалярам Не единичный шаг (может быть неэффективно)

Optimization of applications for Intel* platforms Q&A

Optimization of applications for Intel* platforms Thank you.

Optimization of applications for Intel* platforms Список литературы Compiler transformations for high-performance computing David F. Bacon, Susan L. Graham, Oliver J. Sharp IA-32 Intel® Architecture Optimization Reference Manual