Форум Статьи Контакты
Строительство — возведение зданий и сооружений, а также их капитальный и текущий ремонт, реконструкция, реставрация и реновация.

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

Дата: 29-09-2021, 07:02 » Раздел: Статьи  » 

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

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

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


(голосов:0)

Пожожие новости
Комментарии

Ваше Имя:   

Ваш E-Mail: