Mikhail Kurnosov

Loop Interchange (перестановка циклов)

Mikhail Kurnosov

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 в кеш ядра процессора загружается 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).