Loop tiling

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];

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

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

См. также

1.  (англ.) Wolfe, M. More Iteration Space Tiling. Supercomputing'89, страницы 655—664, 1989.
2.  (англ.) Wolf, M. E. and Lam, M. A Data Locality Optimizing Algorithm. PLDI'91, страницы 30—44, 1991.
3.  (англ.) Irigoin, F. and Triolet, R. Supernode Partitioning. POPL'88, страницы 319—329, 1988.
4.  (англ.) Xue, J. Loop Tiling for Parallelism. Kluwer Academic Publishers. 2000.