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

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

Есть много дискуссий на эту тему в Интернете (рядом с этой веткой), но, насколько я вижу, все они обсуждают пространственные случаи, такие как квадратные матрицы, u[r][r]или определение одномерного массива, например u[r * c], а не вышеупомянутый "массив массивов" (равной длины), используемый в моем контексте " Числовые рецепты" (фон см. здесь).

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

Мартин

Источник

2 ответа

Решение

Я не думаю, что массив массивов гораздо сложнее транспонировать, чем линейный массив в целом. Но если у вас будет 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 х 128 плиток дают ускорение в 2,5 раза. Кроме того, я попытался использовать SSE для ускорения транспонирования, но это существенно не меняет время. Я думаю, что это потому, что проблема связана с памятью.

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

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

Вот полный использованный код.

Источник

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

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

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

Источник
Другие вопросы по тегам