Разбиение цикла на блоки
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];Выбор размера блока
Не всегда легко определить, какой размер блока оптимален для конкретного цикла, так как это зависит от аккуратности вычисления областей массивов, к которым производится доступ. Порядок вложения циклов также играет важную роль в достижении лучшей производительности.