Основные способы оптимизации циклов

Методы оптимизации циклов

Разбиение цикла на блоки

Loop tiling (разбиение цикла на блоки) — оптимизирующее преобразование, призванное сделать исполнение некоторых типов циклов более эффективным.

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

Пример: умножение матрицы на вектор

for (i = 0; i < N; i++)

for (j = 0; j < N; j++)

c[i] = c[i] + a[i, j] * b[j];

После разбиение цикла на блоки 2 × 2

for (i = 0; i < N; i += 2)

for (j = 0; j < N; j += 2)

for (ii = i; ii < min(i + 2, N); ii++)

for (jj = j; jj < min(j + 2,N); jj++)

c[ii] = c[ii] + a[ii, jj] * b[ii];

Изначально, пространство итерирования имеет размеры N × N. Блок массива, a[i, j] к которому требуется доступ, также имеет размер N × N. Если N принимает слишком большие значения, и размер кэша процессора недостаточен для того, чтобы полностью вместить данные, то элементы, которые используются в пределах одной итерации (например, при i = 1, j меняется от 1 до N), то возникают промахи по кэшу, приходится выгружать различные части массива, что сильно снижает производительность.

Пример: умножение матриц

Другим примером использования данного оптимизирующего преобразования является умножение матриц.

Исходный код:

for (i = 0; i < N; i++)

for (k = 0; k < N; k++)

for (j = 0; j < N; j++)

z[i, j] = z[i, j] + x[i, k] * y[k, j]

После разбиения на блоки B × B:

for (k2 = 0; k2 < N; i += B)

for (j2 = 0; j2 < N; j += B)

for (i = 0; i < N; i++)

for (k1 = k2; k1 < min(k2 + B, N); k1++)

for (j1 = j2; k2 < min(j2 + B, N); j1++)

z[i, j1] = z[i, j1] + x[i, k1] * y[k1, j1];

Выбор размера блока

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

Размотка цикла

В программировании, размотка цикла (англ. loop unwinding) или раскрутка цикла (англ. loop unrolling) — техника оптимизации компьютерных программ, состоящая в искусственном увеличении количества инструкций, исполняемых в течение одной итерации цикла. В результате применения этой оптимизации увеличивается количество инструкций, которые потенциально могут выполняться параллельно, и становится возможным более интенсивное использование регистров, кэша данных и исполнительных устройств.

Пример

for (i = 1; i < n; i++)

{a[i] = (i % b[i]);}

преобразуется в такой код:

for (i = 1; i < n - 3; i += 4)

{

a[i] = (i % b[i]);

a[i + 1] = ((i + 1) % b[i + 1]);

a[i + 2] = ((i + 2) % b[i + 2]);

a[i + 3] = ((i + 3) % b[i + 3]);

}

for (i = 4*(n/4); i < n; i++)

a[i] = (i % b[i]);

}

Подробно данный вид оптимизации рассмотрен, например, в Generalized Loop-Unrolling. Он (совместно с loop fission) при определённых условиях (отсутствии зависимостей по данным между инструкциями в новом цикле) позволяет выполнять цикл на нескольких процессорах.

Известен также и необычный способ реализации размотки цикла, называемый «устройством Даффа», — в этой реализации используются малоизвестные и неочевидные возможности синтаксиса языка Си.