оптимизация вложенного цикла компилятора для последовательного доступа к памяти.

Question

Я столкнулся со странной проблемой производительности в тесте умножения матриц (matrix_mult в Metis из набора MOSBENCH ). Тест был оптимизирован для разбиения данных таким образом, чтобы активный рабочий набор составлял 12 КБ (3 элемента размером 32x32 дюйма) и помещался в кэш L1. Короче говоря, при замене двух внутренних контуров разница в производительности при определенных размерах входных массивов (4096, 8192) почти в 4 раза, а в остальных - около 30%. Проблема, по сути, сводилась к последовательному доступу к элементам, а не к шагу. Я думаю, что определенные размеры массивов создавали неверный доступ, что приводило к коллизиям строк кэша. Разница в производительности заметно меньше при переходе от 2-сторонней ассоциативной L1 к 8-позиционной ассоциативной L1.

Мой вопрос: почему gcc не оптимизирует упорядочение циклов, чтобы максимизировать последовательный доступ к памяти?

Ниже приведена упрощенная версия проблемы (обратите внимание, что время производительности сильно зависит от конфигурации L1. Указанные ниже цифры приведены для системы AMD с частотой 2,3 ГГц и двухканальной ассоциативной ассоциацией 64K L1, скомпилированной с -O3).

N = ARRAY_SIZE // 1024
int* mat_A = (int*)malloc(N*N*sizeof(int));
int* mat_B = (int*)malloc(N*N*sizeof(int));
int* mat_C = (int*)malloc(N*N*sizeof(int));

// Elements of mat_B are accessed in a stride pattern of length N
// This takes 800 msec  
for (int t = 0; t < 1000; t++) 
   for (int a = 0; a < 32; a++) 
      for (int b = 0; b < 32; b++)
         for (int c = 0; c < 32; c++) 
            mat_C[N*a+b] += mat_A[N*a+c] * mat_B[N*c+b];

// Inner two loops are swapped
// Elements are now accessed sequentially in inner loop
// This takes 172 msec  
for (int t = 0; t < 1000; t++) 
   for (int a = 0; a < 32; a++) 
      for (int c = 0; c < 32; c++) 
         for (int b = 0; b < 32; b++)
            mat_C[N*a+b] += mat_A[N*a+c] * mat_B[N*c+b];

Answer 1

1. gcc не сможет доказать, что указатели не перекрываются. Если вы хорошо используете нестандартные расширения, вы можете попробовать __ restrict .
2. gcc не в полной мере использует вашу архитектуру, чтобы избежать необходимости перекомпиляции для каждого процессора. Использование опции -march с соответствующим значением для вашей системы может помочь.

Answer 2

gcc имеет кучу оптимизаций, которые просто делают то, что вы хотите.

Найдите параметры компилятора -floop-strip-mine и -floop-block.

Цитата из руководства:

Выполнить преобразования блокировки цикла в циклах.Блокирующая полоса копирует каждую петлю в гнезде петель так, чтобы обращения к памяти петель элементов помещались внутри кэшей.Длина полосы может быть изменена с помощью параметра loop-block-tile-size.