SIMD транспонировать, когда размер строки больше, чем ширина вектора - PullRequest
Новая
       94

SIMD транспонировать, когда размер строки больше, чем ширина вектора

2 голосов
/ 18 октября 2019

Вы можете найти много хороших ответов для транспонирования матрицы, которая соответствует размеру натурального набора инструкций SIMD, в частности, гдеразмер одной строки не больше ширины вектора. В качестве примера можно привести транспонирование 4x4 float в SSE или транспонирование 4x4 double или 8x8 float в AVX / AVX2 (снова удвоить все для AVX-512).

Однако, каковы вариантыкогда матрица больше, чем это? Например, матрица 16x16 float с использованием AVX2? Можно ли вообще использовать SIMD-тасовки, чтобы ускорить процесс, или единственная запись с последовательной записью + последовательная запись?

Ответы [ 2 ]

2 голосов
/ 18 октября 2019

Если все ваши размеры матрицы кратны размеру вашего пакета, вы можете выполнять операции по блокам и менять блоки по мере необходимости. Пример для двойной матрицы 4x4 с использованием SSE2: 

// transpose vectors i0 and i1 and store the result to addresses r0 and r1
void transpose2x2(double *r0, double* r1, __m128d i0, __m128d i1)
{
    __m128d t0 = _mm_unpacklo_pd(i0,i1);
    __m128d t1 = _mm_unpackhi_pd(i0,i1);
    _mm_storeu_pd(r0, t0);
    _mm_storeu_pd(r1, t1);
}


void transpose(double mat[4][4])
{
    // transpose [00]-block in-place
    transpose2x2(mat[0]+0, mat[1]+0,_mm_loadu_pd(mat[0]+0),_mm_loadu_pd(mat[1]+0));

    // load [20]-block
    __m128d t20 = _mm_loadu_pd(mat[2]+0), t30 = _mm_loadu_pd(mat[3]+0);
    // transpose [02]-block and store it to [20] position
    transpose2x2(mat[2]+0,mat[3]+0, _mm_loadu_pd(mat[0]+2),_mm_loadu_pd(mat[1]+2));
    // transpose temp-block and store it to [02] position
    transpose2x2(mat[0]+2,mat[1]+2, t20, t30);

    // transpose [22]-block in-place
    transpose2x2(mat[2]+2, mat[3]+2,_mm_loadu_pd(mat[2]+2),_mm_loadu_pd(mat[3]+2));
}

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

Для некоторых размеров, например, матриц 3x4 или 3x8, существуют специальные алгоритмы [1] - если у вас есть матрица 1003x1003, вы можете использовать это для последних строк / столбцов (и, вероятно, также существуют алгоритмы для других нечетных размеров).

С некоторыми усилиями вы могли бы также написать это для прямоугольных матриц (нужно подумать, как избежать кеширования более одного блока за раз, но это возможно).

Godboltдемо: https://godbolt.org/z/tVk_Bc

[1] https://software.intel.com/en-us/articles/3d-vector-normalization-using-256-bit-intel-advanced-vector-extensions-intel-avx

0 голосов
/ 19 октября 2019

Возможно, можно использовать intranic для TRANSPOSE на Fortran с ISO_C_BINDING и связать его с C в качестве вызова подпрограммы или функции.

TRANSPOSE довольно хорошо оптимизирован в Fortran.

И иногда смешанные языковые навыкиполезно знать в общем. Я даже связал F90 с GO.

...