Optimaler SIMD-Algorithmus zum Drehen oder Transponieren eines Arrays

Question

Ich arbeite an einer Datenstruktur, wo ich ein Array von 16 Uint64 habe. Sie sind wie diese in dem Speicher angelegt (die jeweils unter einer einzigen int64 darstellt):

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

Das gewünschte Ergebnis ist die Matrix in dieser transponieren:

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

Die Drehung der Anordnung 90 Grad ist auch eine akzeptable Lösung für die Zukunft Schleife:

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

ich brauche dies, um auf dem Pfeil schnell zu einem späteren Zeitpunkt (Traverse es die Reihe nach mit einer anderen SIMD Reise, 4 zu einem Zeitpunkt) zu betreiben.

Bisher habe ich versucht, die Daten zu "mixen", indem ich einen 4 x 64 Bit Vektor von A's hochlade, die Elemente maskierte und mischte und sie mit B's orderte und dann für C's wiederholte ... Leider sind dies 5 x 4 SIMD-Befehle pro Segment von 4 Elementen in dem Array (ein Laden, eine Maske, ein Shuffle, ein oder mit dem nächsten Element und schließlich ein Speicher). Es scheint, ich sollte es besser machen können.

Ich habe AVX2 verfügbar und ich kompiliere mit 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 

Ich habe Hardware nicht, dies jetzt testen auf, aber so etwas wie die folgenden sollten tun, was Sie

__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 

Die

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

intrinsische wählt 128-Bit-Bahnen wollen aus zwei Quellen. Sie können darüber in the Intel Intrinsic Guide lesen. Es gibt eine Version _mm256_permute2f128_si256, die nur AVX benötigt und in der Gleitkommadomäne agiert. Ich habe dies verwendet, um zu überprüfen, ob ich die richtigen Kontrollwörter verwendet habe.

Answer 2

Eine Alternative ist die Verwendung der sammeln Anweisungen, können Sie direkt die transponierte Matrix laden. Die fünf Zeilen Code unten sind ok mit gcc auf einem 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);