2023-04-04
Разбиение цикла на блоки (loop tiling, loop blocking) – это разбиение пространства итераций вложенных циклов на блоки меньших размеров с целью повышение эффективности использования кеш-памяти процессора. Ключевая идея – загрузка и хранение блоков в кеш-памяти для их повторного использования. Сокращение времени выполнения достигается за счет уменьшения числа кеш-промахов и нежелательного вытеснения строк из кеш-памяти.
Рассмотрим пример суммирования элементов двух массивов
a[m][n] и b[m][n].
void sum(double *a, double *b, int m, int n)
{
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
a[i * n + j] += b[j * n + i];
}
}Будем считать, что адреса массивов выравнены на границу размера
строки кеш-памяти (64 байта для x86-64). Следовательно элемент
b[0][0] попадет в начало строки кеш-памяти. Обращение к
элементам массива b характеризуется плохой пространственной
локальностью, осуществляется с шагом n. На первой итерации
внутреннего цикла (i=0, j=0) выполняется чтение
b[0][0]. Он отсутствует в кеш-памяти, происходит кеш-промах
(cache miss). Из памяти в кеш загружается строка, содержащая 64 байта –
8 элементов типа double
b[0][0], b[0][1], ..., b[0][7].
На второй итерации внутреннего цикла (i=0, j=1)
выполняется чтение b[1][0] и происходит кеш-промах, так как
мы “перешагнули” элементы загруженные в кеш на предыдущей итерации.
Таким образом, при каждом обращении к массиву b[j][0]
происходит кеш-промах.
Если количество строк m в массиве больше чем строк в
кеш-памяти, то промахи обращения к массиву b приведут к
тому, что из кеш-памяти начнут вытесняться ранее загруженные строки.
Если разбить пространство итераций двух циклов на блоки, то можно сохранить подмассивы в кеш-памяти и сократить число кеш-промахов. В примере ниже два внутренних цикла обрабатывают подматрицы 8x8 элементов.
void sum_block(double *a, double *b, int m, int n)
{
int bs = 8;
for (int i = 0; i < m; i += bs) {
for (int j = 0; j < n; j += bs) {
for (int ii = i; ii < IMIN(i + bs, m); ii++) {
for (int jj = j; jj < IMIN(j + bs, n); jj++) {
a[ii * n + jj] += b[jj * n + ii];
}
}
}
}
}При проходе по циклу jj происходит bs
промахов и в кеш загружаются строки: b[0][0-7],
b[1][0-7], …, b[bs-1][0-7]. Но в отличии от
предыдущей версии на следующей итерации ii элементы
b[0][1], b[1][1], ..., b[bs-1][1] читаются из
кеш-памяти!
Ниже приведены результаты запуска исходной и оптимизированной версий на процессоре Intel i7-1160G7 (Tiger Lake). Компилятор gcc 12.2.0, ядро linux 5.19.0-29-generic x86_64.
Результаты для исходной версии (m=10000, n=1000):
$ gcc -O2 -Wall -o sum ./sum.c
$ perf stat -e cache-misses -- taskset --cpu-list 3 ./sum
# [m] [time, sec] [MFLOPS]
10000 0.011390 877.99
Performance counter stats for 'taskset --cpu-list 3 ./sum':
366 323 214 cache-misses Результаты версии с разбиением пространства итераций на блоки 8x8:
$ perf stat -e cache-misses -- taskset --cpu-list 3 ./sum
# [m] [time, sec] [MFLOPS]
10000 0.009266 1079.20
Performance counter stats for 'taskset --cpu-list 3 ./sum':
305 873 384 cache-misses Время оптимизированной версии сократилось на 23%.
Разбиение циклов на блоки позволяет оптимизировать работу с
кеш-памятью и в программах с хорошей пространственной локализацией.
Типичный пример – умножение матрицы на вектор. Доступ к массивам
a[m][n], b[n], c[m] выполняется с
шагом 1, но при больших значениях m на итерациях
внутреннего цикла j из кеш-памяти начнут вытесняться ранее
загруженные строки.
void dgemv(double *a, double *b, double *c, int m, int n)
{
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
c[i] += a[i * n + j] * b[j];
}
}Разбиение цикла на блоки позволяет сохранить в кеш-памяти подмассивы для их обработки:
void dgemv_block(double *a, double *b, double *c, int m, int n)
{
int bs = 8;
for (int i = 0; i < m; i += bs) {
for (int j = 0; j < n; j += bs) {
for (int ii = i; ii < IMIN(i + bs, m); ii++) {
for (int jj = j; jj < IMIN(j + bs, n); jj++) {
c[ii] += a[ii * n + jj] * b[jj];
}
}
}
}
}