AVX2 sammeln laden eine Struktur von zwei Ints

Question

Ich versuche derzeit, eine AVX2-Version (Haswell CPU) von einigen vorhandenen Skalar-Code von mir zu implementieren. Welche implementiert einen Schritt wie folgt aus:

struct entry { 
    uint32_t low, high; 
}; 

// both filled with "random" data in previous loops 
std::vector<entry> table; 
std::vector<int> queue; // this is strictly increasing but 
          // without a constant delta 

for (auto index : queue) { 
    auto v = table[index]; 
    uint32_t rank = v.high + __builtin_popcount(_bzhi_u32(v.low, index % 32)); 
    use_rank(rank); // contains a lot of integer operations which nicely map to avx2 
} 

ich diese Anweisungen sammeln mit 2 implementiert haben, dass jede Last ein int32 wie folgt aus:

__m256iv_low = _mm256_i32gather_epi32 (reinterpret_cast<int *>(table.data()) + 0, index, 8); 
__m256i v_high = _mm256_i32gather_epi32 (reinterpret_cast<int *>(table.data()) + 1, index, 8); 

Gibt es einen schnelleren Weg, zwei Last diese Werte? Ich habe darüber nachgedacht, 2 64-Bit-Ladevorgänge (die nur die Hälfte der Lesevorgänge ausgeben => weniger Verkehr für die Ausführungsports) und dann die resultierenden Vektoren mischen, um zum Beispiel v_low und v_high zu bekommen, aber leider, soweit ich die meisten Shuffle unterscheiden kann Funktionen erlauben nur 128 Bit getrennt zu mischen.

Edit für Paul R: Dieser Code ist Teil einer Routine Teilzeichenfolge Aufzählung mit der Burrows-Wheeler-Transformation, dass ich in meinem Kompressionsalgorithmus verwenden. table enthält Rangdaten für einen Bitvektor. Der obere Teil enthält die Anzahl der Einsen in den vorherigen Einträgen und der untere Teil wird ausgeblendet und popcounted dann hinzugefügt, um die endgültige Anzahl der gesetzten Bits vor dem gegebenen Index zu erhalten. Danach passiert viel mehr Berechnung, die glücklicherweise gut parallelisierbar ist.

Die Deltas in der Warteschlange sind am Anfang und am Ende (aufgrund der Art des Algorithmus) sehr hoch. Dies verursachte eine Menge Cache-Misses und ist der Grund, warum ich von SoA auf AoS umschaltete, um den Druck auf die Ladeports im Skalarkode zu reduzieren.

Die Verwendung von SoA würde auch zu den gleichen unabhängigen Sammelanweisungen führen, würde aber die Menge der Cache-Zeilen, auf die zugegriffen wird, verdoppeln.

Edit (Teilantwort): habe ich versucht, zwei _mm_i32gather_epi64 auf die Hälfte der Anzahl der Speicherzugriffe unter Verwendung (und damit die Zyklen, siehe here).

__m256i index; // contains the indices 
__m128i low = _mm256_extractf128_si256(index, 0); 
__m128i high = _mm256_extractf128_si256(index, 1); 
__m256i v_part1 = _mm256_i32gather_epi64(reinterpret_cast<long long int*>(table.data()), low , 8); 
__m256i v_part2 = _mm256_i32gather_epi64(reinterpret_cast<long long int*>(table.data()), high, 8); 

, die meine Daten in zwei ymm laden Register dieses Formats (keine C++):

register v_part1: 
[v[0].low][v[0].high][v[1].low][v[1].high][v[2].low][v[2].high][v[3].low][v[3].high] 
register v_part2: 
[v[4].low][v[4].high][v[5].low][v[5].high][v[6].low][v[6].high][v[7].low][v[7].high] 

Gibt es einen effizienten Weg, um sie in Ordnung verschachteln, das ursprüngliche Format zu erhalten:

register v_low: 
[v[0].low][v[1].low][v[2].low][v[3].low][v[4].low][v[5].low][v[6].low][v[7].low] 
register v_high: 
[v[0].high][v[1].high][v[2].high][v[3].high][v[4].high][v[5].high][v[6].high][v[7].high] 

Answer 1

Ich habe einen Weg gefunden, um die Werte mit 5 Anweisungen selbst neu zu ordnen:

// this results in [01][45][23][67] when gathering 
index = _mm256_permute4x64_epi64(index, _MM_SHUFFLE(3,1,2,0)); 

// gather the values 
__m256i v_part1 = _mm256_i32gather_epi64(i, _mm256_extractf128_si256(index, 0), 8); 
__m256i v_part2 = _mm256_i32gather_epi64(i, _mm256_extractf128_si256(index, 1), 8); 

// seperates low and high values 
v_part1 = _mm256_shuffle_epi32(v_part1, _MM_SHUFFLE(3,1,2,0)); 
v_part2 = _mm256_shuffle_epi32(v_part2, _MM_SHUFFLE(3,1,2,0)); 

// unpack merges lows and highs: [01][23][45][56] 
o1 = _mm256_unpackhi_epi64(v_part1, v_part2); 
o2 = _mm256_unpacklo_epi64(v_part1, v_part2);