Введение

Слияние циклов (loop fusion, loop jamming) – это объединение двух смежных циклов в один с целью повышения временной локальности обращений к общим массивам и устранения накладных расходов на поддержание второго цикла (вычисление условного выражения, выполнение перехода/предсказания). Объединяемые циклы должны иметь одинаковое пространство итераций.

Рассмотрим пример. В функции vec_sum первый цикл читает элементы массива a[i] и записывает их в b[i]. Во втором смежном цикле выполняется заполнение массива c[i] на основе ранее вычисленных значений b[i].

В первом цикле при больших значениях N начальные элементы a[i] и b[i] могут быть вытеснены из кеш-памяти. Поэтому во втором цикле чтение b[i] будет происходит из системной памяти.

void vec_sum(double a[N], double b[N], double c[N])
{
    for (int i = 0; i < N; i++) {
        b[i] = a[i] + 1.0;
    }
    /* For large N, the initial elems of the a[i], b[i] will be evicted */

    for (int i = 0; i < N; i++) {
        c[i] = b[i] * 4.0;
    }
}

Если объеденить циклы, то чтение элементов b[i] для заполнения c[i] будет осуществляться из кеш-памяти.

void vec_sum_fusion(double a[N], double b[N], double c[N])
{
    for (int i = 0; i < N; i++) {
        b[i] = a[i] + 1.0;
        c[i] = b[i] * 4.0;  /* b[i] is loaded from cache */
    }
}

Эксперименты

Ниже приведены результаты запуска исходной и оптимизированной версий на процессоре Intel i7-1160G7 (Tiger Lake):

• кеш L1d: 48 KiB, 12-way 64 sets, 768 cache lines
• кеш L2: 1280 KiB, 20-way 1024 sets, 20480 cache lines
• кеш LLC: 12288 KiB, 12-way 16384 sets, 196608 cache lines

Компилятор gcc 12.2.0, ядро linux 5.19.0-29-generic x86_64.

Результаты для исходной версии (N=700000):

$ gcc -g -Wall -o loop ./loop.c  

$ perf stat -e cache-misses,branches taskset --cpu-list 0 ./loop

# Vec sum def: N=700000, elapsed time (sec) 0.002705, Melems/sec 258.7

 Performance counter stats for 'taskset --cpu-list 0 ./loop':

        86 582 547      cache-misses                                                
     1 438 735 511      branches

       2,754338205 seconds time elapsed

       2,754151000 seconds user
       0,000000000 seconds sys

Программа выводит время выполнения функции и количество миллионов обработанных элементов в секунду (Melems/sec).

Результаты версии с объединенными циклами:

$ perf stat -e cache-misses,branches taskset --cpu-list 0 ./loop

# Vec sum fusion: N=700000, elapsed time (sec) 0.001667, Melems/sec 420.0

 Performance counter stats for 'taskset --cpu-list 0 ./loop':

        70 721 194      cache-misses                                                
       738 344 857      branches

       1,705521495 seconds time elapsed

       1,701314000 seconds user
       0,004003000 seconds sys

Время оптимизированной версии сократилось на 59% и на 22% меньше промахов при обращении к кеш-памяти, на 95% меньше условных переходов.

• Исходный код: loop-fusion.tar.gz