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

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.
5.  (англ.)M. S. Lam, E. E. Rothberg, and M. E. Wolf. The cache performance and optimizations of blocked algorithms. In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 63–74, April 1991.