2023-02-06
Слияние циклов (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):
Компилятор 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% меньше условных переходов.