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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Loop tiling»)
Перейти к: навигация, поиск

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

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

Пример: умножение матрицы на вектор[править | править вики-текст]

 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.