Оптимальный алгоритм SIMD для поворота или транспонирования массива

Question

Я работаю над структурой данных, где у меня есть массив из 16 uint64. Они раскладывают, как это в памяти (каждый ниже, представляющий одну int64):

A0 A1 A2 A3 B0 B1 B2 B3 C0 C1 C2 C3 D0 D1 D2 D3 

Желаемый результат состоит в переносе массива в этом:

A0 B0 C0 D0 A1 B1 C1 D1 A2 B2 C2 D2 A3 B3 C3 D3 

Вращение массива 90 градусов также является приемлемым решением для будущего цикла:

D0 C0 B0 A0 D1 C1 B1 A1 D2 C2 B2 A2 D3 C3 B3 A3 

мне это нужно для того, чтобы работать на стрелке быстро на более позднем этапе (Траверса его последовательно с другой поездкой SIMD, 4 за один раз).

До сих пор я пытался «скомпоновать» данные, загружая 4-х битный вектор A, битмаскизируя и перетасовывая элементы и OR'ing его с помощью B и т. Д., А затем повторяя это для C ... К сожалению, это 5 x 4 SIMD инструкций на сегмент из 4 элементов в массиве (одна загрузка, одна маска, одна тасовка, одна или со следующим элементом и, наконец, хранилище). Кажется, я смогу сделать лучше.

У меня есть AVX2, и я компилирую с clang.

Answer 1

uint64_t A[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; 
__m256i row0 = _mm256_loadu_si256((__m256i*)&A[ 0]); //0 1 2 3 
__m256i row1 = _mm256_loadu_si256((__m256i*)&A[ 4]); //4 5 6 7 
__m256i row2 = _mm256_loadu_si256((__m256i*)&A[ 8]); //8 9 a b 
__m256i row3 = _mm256_loadu_si256((__m256i*)&A[12]); //c d e f 

У меня нет оборудования, чтобы проверить это прямо сейчас, но что-то вроде следующего должен делать то, что вы хотите

__m256i tmp3, tmp2, tmp1, tmp0; 
tmp0 = _mm256_unpacklo_epi64(row0, row1);   //0 4 2 6 
tmp1 = _mm256_unpackhi_epi64(row0, row1);   //1 5 3 7 
tmp2 = _mm256_unpacklo_epi64(row2, row3);   //8 c a e 
tmp3 = _mm256_unpackhi_epi64(row2, row3);   //9 d b f 
//now select the appropriate 128-bit lanes 
row0 = _mm256_permute2x128_si256(tmp0, tmp2, 0x20); //0 4 8 c 
row1 = _mm256_permute2x128_si256(tmp1, tmp3, 0x20); //1 5 9 d 
row2 = _mm256_permute2x128_si256(tmp0, tmp2, 0x31); //2 6 a e 
row3 = _mm256_permute2x128_si256(tmp1, tmp3, 0x31); //3 7 b f 

The

__m256i _mm256_permute2x128_si256 (__m256i a, __m256i b, const int imm) 

присущий выбирает 128-битные полосы из двух источников. Вы можете прочитать об этом в the Intel Intrinsic Guide. Существует версия _mm256_permute2f128_si256, которая требует только AVX и действует в домене с плавающей запятой. Я использовал это, чтобы проверить, что я использовал правильные контрольные слова.

Answer 2

Альтернативой является использование команды , вы можете загрузить непосредственно транспонированную матрицу. Пять строк кода ниже в порядке с gcc на i7-Haswell.

int32_t stride = 4 * sizeof(A[0]); 
    __m128i r128_gather_idx = _mm_set_epi32(3 * stride, 2 * stride, 1 * stride, 0 * stride); 
    __m256i row0 = _mm256_i32gather_epi64(reinterpret_cast<long long const *>(&A[ 0]), r128_gather_idx, 1); 
    __m256i row1 = _mm256_i32gather_epi64(reinterpret_cast<long long const *>(&A[ 1]), r128_gather_idx, 1); 
    __m256i row2 = _mm256_i32gather_epi64(reinterpret_cast<long long const *>(&A[ 2]), r128_gather_idx, 1);