2023-01-22
Перестановка циклов (loop interchange) – это одна из простейших техник оптимизации доступа к данным в кеш-памяти процессорного ядра, направленная на улучшение временной локальности кода (temporal locality).
Основная идея заключается в перестановке вложенных циклов (циклов одного гнезда, loop nest) или их индуктивных переменных так, чтобы шаг обращения к элементам массива (stride) был минимальным. Это обеспечивает попадание большего числа элементов массива в одну строку кеш-памяти и приводит к меньшему числу промахов при обращении к кешу ядра процессора. Перестановка циклов может способствовать их эффективной векторизации, за счет сокращения шага доступа к элементам массива.
Рассмотрим пример суммирования элементов массива a[N][N]
в переменную sum
. В исходной версии имеется гнездо из двух
циклов. Внешний цикл j
выполняет перебор N
столбцов, а внутренний цикл i
проходит по N
строкам. Получаем следующий порядок чтения элементов массива:
a[0][0], a[1][0], a[2][0], ..., a[N][0], a[0][1], ..., a[N-1][N-1]
.
double matrix_sum(double a[N][N])
{
double sum = 0;
for (int j = 0; j < N; j++) {
for (int i = 0; i < N; i++) {
sum += a[i][j];
}
}
return sum;
}
В языке С многомерные массивы хранятся в памяти строка за строкой
(row-major order). Поэтому элементы a[0][0]
и
a[1][0]
находятся в памяти на расстоянии
N * sizeof(double)
байт. На каждой итерации внутреннего
цикла мы обращаемся к элементам массива a
с шагом
N
. Для простоты изложения предположим, что массив
a
отсутствует в кеш-памяти (вытеснен другими данными),
адрес массива выравнен на границу кратную размеру строки
кеш-памяти (64 байта для архитектуры x86-64), а размерность матрицы
N >= 8
. Рассмотрим ход выполнения функции начиная с
первой итерации j=0,i=0
:
j=0,i=0
происходит
чтение элемента a[0][0]
, выполняется поиск в кеше
процессора, данные в кеш-памяти отсутствуют (cache miss), из
системной памяти загружается блок 64 байта (cache line), содержащий 8
элементов типа double
(a[0][0], a[0][1], ..., a[0][7]
);j=0,i=1
происходит обращение к
a[1][0]
, данные в кеше отсутствуют (мы перешагнули через
закешированные на предыдущей итерации элементы), из системной памяти
загружается строка с элементами:
a[1][0], a[1][1], ..., a[1][7]
(64 байта);j=0,i=3
происходит обращение
к a[2][0]
, данные в кеш-памяти отсутствуют, …Таким образом, при j=0
на каждой итерации внутреннего
цикла происходит промах при обращении к кеш-памяти. А за время
выполнения цикла i
в кеш ядра процессора загружается
N
новых строк.
В лучшем случае N * 64 <= L1_SIZE
– кеш L1 ядра
процессора располагает достаточным количеством строк по 64 байта для
хранения части матрицы a
. Точнее в кеш L1 помещается
подматрица a[0:N-1][0:7]
из N
строк и первых 8
столбцов. Следовательно на второй итерации цикла (j=1
)
элементы a[j][i]
будут загружаться из кеш-памяти. Промахи
доступа к кешу начнутся начиная с элемента a[0][8]
.
В худшем случае N * 64 > L1_SIZE
– в кеш-памяти L1
недостаточно места для хранения подматрицы. Начиная с итерации
j=0, i=L1_SIZE / (N * 64)
в L1 не останется свободных строк
и начнется вытеснение (replacement) ранее загруженных строк матрицы
a
. Следовательно на второй итерации цикла промахи начнутся
значительно раньше.
Переставим местами внутренний и внешний циклы. Это не сказывается на корректности программы.
double matrix_sum_interchanged(double a[N][N])
{
double sum = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sum += a[i][j];
}
}
return sum;
}
В новой версии на каждой итерации внутреннего цикла мы обращаемся к
элементам массива с шагом 1:
a[0][0], a[0][1], a[0][2], ..., a[0][N], a[1][0], ..., a[N-1][N-1]
.
Теперь промах при обращении к кеш-памяти возникает не на каждой
итерации, а через 8.
Ниже приведены результаты запуска исходной и оптимизированной версий на процессоре Intel i7-1160G7 (Tiger Lake):
Компилятор gcc 12.2.0, ядро linux 5.19.0-29-generic x86_64.
Результаты для исходной версии. Взята матрица, не помещающаяся в кеш
L1 (N=4000
):
$ gcc -DN=4000 -Wall -o loop ./loop.c
$ perf stat -e cache-misses taskset --cpu-list 0 ./loop
Matrix sum: N=4000, elapsed time (sec) 0.066034, Melems/sec 242.3
Performance counter stats for 'taskset --cpu-list 0 ./loop':
5 031 988 cache-misses
0,318452173 seconds time elapsed
0,302263000 seconds user
0,016120000 seconds sys
Программа выводит время выполнения функции и количество миллионов элементов матрицы, просуммированных в секунду (Melems/sec).
Результаты версии с переставленными циклами:
$ gcc -DN=4000 -Wall -o loop ./loop.c
$ perf stat -e cache-misses taskset --cpu-list 0 ./loop
Matrix sum: N=4000, elapsed time (sec) 0.035631, Melems/sec 449.1
Performance counter stats for 'taskset --cpu-list 0 ./loop':
2 860 550 cache-misses
0,297849142 seconds time elapsed
0,269678000 seconds user
0,028175000 seconds sys
В оптимизированной версии на 75% меньше промахов при обращении к
кеш-памяти: 2 860 550 cache-misses
против
5 031 988 cache-misses
.
Ниже для исходной и оптимизированной версий приведены графики
зависимости количества элементов суммируемых в секунду от размерности
N
матрицы. Синие вертикальные линии показывают границы
размеров кеш-памяти L1 и L2 ядра Intel i7-1160G7. Видно, что
производительность исходной версии падает с увеличением размера массива,
оптимизированная версия характеризуется более устойчивой
производительностью.
За кадром остались: влияние кеш-памяти L2, LLC (инклюзивность), автоматическая трансформация гнезда циклов при включении оптимизации (gcc/clang: -O2, -O3).