Эффективная перестановка времени прямоугольной матрицы произвольного размера

Question

Я нажимаю на время, чтобы оптимизировать большую часть кода C для скорости, и я ищу алгоритм --- в лучшем случае фрагмент C "- -Вот переставляет прямоугольные Source матрицуu[r][c]произвольного размера (r количества строк, c числа столбцов) в целевой матрицу v[s][d] (s = c количество строк, d = r число столбцов) в «cache- friendly " i. е. подход к данным. Типичный размер u составляет около 5000 ... 15000 строк на 50-500 столбцов, и ясно, что доступ к элементам по ряду причин очень неэффективен в кэше.

Существует много дискуссий по этой теме в Интернете (рядом с этим thread), но, насколько я вижу, все они обсуждают пространственные случаи, такие как квадратные матрицы, u[r][r] или определение on-мерного массива, e. г. u[r * c], а не вышеупомянутый «массив массивов» (равной длины), используемый в моем контексте Численные рецепты (фон см. here).

Я бы очень благодарен за любой намек, который помогает избавить меня от «переосмысления колеса».

Martin

Answer 1

Я не думаю, что массив массивов гораздо сложнее транспонировать, чем линейный массив в целом. Но если у вас будет 50 столбцов в каждом массиве, это звучит плохо: этого может быть недостаточно, чтобы скрыть накладные расходы на разыменование указателя.

Я думаю, что общая стратегия реализации с кэшем одинакова: обработайте свою матрицу в плитки, выберите размер плиток, который лучше всего работает в соответствии с экспериментами.

template<int BLOCK> 
void TransposeBlocked(Matrix &dst, const Matrix &src) { 
    int r = dst.r, c = dst.c; 
    assert(r == src.c && c == src.r); 
    for (int i = 0; i < r; i += BLOCK) 
     for (int j = 0; j < c; j += BLOCK) { 
      if (i + BLOCK <= r && j + BLOCK <= c) 
       ProcessFullBlock<BLOCK>(dst.data, src.data, i, j); 
      else 
       ProcessPartialBlock(dst.data, src.data, r, c, i, j, BLOCK); 
     } 
} 

Я пытался оптимизировать лучший случай, когда г = 10000, с = 500 (с float типа). На моей локальной машине 128 x 128 плиток дают ускорение в 2,5 раза. Кроме того, я попытался использовать SSE для ускорения транспозиции, но не значительно изменил тайминги.Я думаю, это потому, что проблема связана с памятью.

Вот полные тайминги (для 100 запусков каждый) различных реализаций на Core2 E4700 2.6GHz:

Trivial: 6.111 sec 
Blocked(4): 8.370 sec 
Blocked(16): 3.934 sec 
Blocked(64): 2.604 sec 
Blocked(128): 2.441 sec 
Blocked(256): 2.266 sec 
BlockedSSE(16): 4.158 sec 
BlockedSSE(64): 2.604 sec 
BlockedSSE(128): 2.245 sec 
BlockedSSE(256): 2.036 sec 

Здесь full code используется.

Answer 2

Итак, я предполагаю, что у вас есть массив из массива поплавков/двойников. Эта настройка уже очень плоха для производительности кеша. Причина в том, что с 1-мерным массивом компилятор может выводить код, который приводит к операции предварительной выборки и (в случае очень нового компилятора) создает код SIMD/vectorized. С помощью массива указателей на каждом шаге выполняется операция отсрочки, что усложняет предварительную выборку. Не говоря уже о каких-либо гарантиях выравнивания памяти.

Если это для задания, и у вас нет выбора, кроме как написать код с нуля, я бы рекомендовал посмотреть, как это делается CBLAS (обратите внимание, что вам все равно понадобится «сплющенный» массив). В противном случае вам будет лучше использовать высоко оптимизированную реализацию BLAS, например OpenBLAS. Он оптимизирован почти на десять лет и будет производить самый быстрый код для вашего целевого процессора (настройка для таких вещей, как размеры кеша и набор векторных инструкций).

tl; dr состоит в том, что использование массива массивов приведет к ужасной производительности независимо от того, что. Сгладьте свои массивы и сделайте свой код приятным для чтения, используя #define для доступа к элементам массива.