Algoritmo SIMD ottimale per ruotare o trasporre una matrice

Question

Sto lavorando su una struttura dati in cui ho una matrice di 16 uint64. Essi sono disposti come questo in memoria (ciascuno di seguito rappresenta una singola int64):

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

Il risultato desiderato è quello di trasporre la matrice in questo:

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

La rotazione della matrice 90 gradi è anche una soluzione accettabile per il ciclo futuro:

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

ho bisogno di questo per operare sulla freccia veloce a un punto successivo (lo attraversano in successione con un altro viaggio SIMD, 4 alla volta).

Finora, ho provato a "fondere" i dati caricando un vettore di 4 x 64 bit di A, mascherando e mischiando gli elementi OR e facendolo con B's etc e quindi ripetendolo per C's ... Sfortunatamente, questo è 5 x 4 istruzioni SIMD per segmento di 4 elementi nell'array (un carico, una maschera, uno shuffle, uno o con l'elemento successivo e infine un negozio). Sembra che dovrei essere in grado di fare meglio.

Ho AVX2 disponibile e io una compilazione con 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 

non devo hardware per testare questo in questo momento, ma qualcosa come il seguente dovrebbe fare quello che vuoi

__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 

I

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

intrinseca seleziona i 128 bit corsie da due fonti. Puoi leggere su di esso in the Intel Intrinsic Guide. Esiste una versione _mm256_permute2f128_si256 che richiede solo AVX e agisce nel dominio in virgola mobile. L'ho usato per verificare che ho usato le parole di controllo corrette.

Answer 2

Un'alternativa è utilizzare per raccogliere le istruzioni, è possibile caricare direttamente la matrice trasposta. Le cinque righe di codice qui sotto sono ok con gcc su 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);