使用SIMD/AVX/SSE進行樹遍歷

Question

我目前正在研究是否有可能加速van Emde Boas（或任何樹）遍歷樹。給定一個搜索查詢作爲輸入，已經在緩存行中有多個樹節點（van emde Boas佈局），樹遍歷似乎是指令瓶頸。

對於SIMD/AVX/SSE指令而言，我想知道是否有可能將多個節點一次比較爲一個值，然後找出哪條樹路徑需要進一步跟蹤。我的研究導致以下問題：

構建SIMD/AVX/SSE寄存器等時會浪費多少CPU週期/指令。如果構建比遍歷整個過程需要更多時間，這將用於wayne。手動子樹（1個大小爲64字節的緩存行中的2 + 4 + 8個節點）。

找到正確的SIMD/AVX/SSE寄存器來保存哪個路徑的答案會浪費多少CPU週期/指令？任何人都可以想出一個聰明的方法，以便那些「findMinimumInteger」AVX指令可以用來決定在1（??）cpu週期中？

你的猜測是什麼？

加速樹遍歷的另一個更棘手的方法是在多個搜索查詢同時運行時，如果在最後一個樹級別中緊靠在一起的節點的可能性很高。對此有何猜測？ Ofc將不得不將那些不屬於同一子樹的查詢放在一邊，然後在完成樹的第一個「並行遍歷」後遞歸地找到它們。樹查詢具有連續的，但不是常量的訪問模式（查詢[i]總是<比查詢[i + 1]）。

重要：這東西是關於整樹的，這就是爲什麼麪包車昂德博阿斯樹被使用（也許X-FAST/Y型快速嘗試以後）

我很好奇，什麼是您對此的50美分問題，因爲人們可能對大型樹上的最高可實現性能感興趣。預先感謝您在這方面花費的時間:-)

Answer 1

我已經使用SSE2/AVX2來幫助執行B +樹搜索。下面的代碼將在AVX2的16個DWORDs整個緩存線執行二進制搜索：

// perf-critical: ensure this is 64-byte aligned. (a full cache line) 
union bnode 
{ 
    int32_t i32[16]; 
    __m256i m256[2]; 
}; 

// returns from 0 (if value < i32[0]) to 16 (if value >= i32[15]) 
unsigned bsearch_avx2(bnode const* const node, __m256i const value) 
{ 
    __m256i const perm_mask = _mm256_set_epi32(7, 6, 3, 2, 5, 4, 1, 0); 

    // compare the two halves of the cache line. 

    __m256i cmp1 = _mm256_load_si256(&node->m256[0]); 
    __m256i cmp2 = _mm256_load_si256(&node->m256[1]); 

    cmp1 = _mm256_cmpgt_epi32(cmp1, value); // PCMPGTD 
    cmp2 = _mm256_cmpgt_epi32(cmp2, value); // PCMPGTD 

    // merge the comparisons back together. 
    // 
    // a permute is required to get the pack results back into order 
    // because AVX-256 introduced that unfortunate two-lane interleave. 
    // 
    // alternately, you could pre-process your data to remove the need 
    // for the permute. 

    __m256i cmp = _mm256_packs_epi32(cmp1, cmp2); // PACKSSDW 
    cmp = _mm256_permutevar8x32_epi32(cmp, perm_mask); // PERMD 

    // finally create a move mask and count trailing 
    // zeroes to get an index to the next node. 

    unsigned mask = _mm256_movemask_epi8(cmp); // PMOVMSKB 
    return _tzcnt_u32(mask)/2; // TZCNT 
} 

最終你會與每bnode一個高度可預測的分支，以測試樹已到頭。

這應該可以簡單地擴展到AVX-512。

預處理和擺脫慢PERMD指令，這將用於：

void preprocess_avx2(bnode* const node) 
{ 
    __m256i const perm_mask = _mm256_set_epi32(3, 2, 1, 0, 7, 6, 5, 4); 
    __m256i *const middle = (__m256i*)&node->i32[4]; 

    __m256i x = _mm256_loadu_si256(middle); 
    x = _mm256_permutevar8x32_epi32(x, perm_mask); 
    _mm256_storeu_si256(middle, x); 
} 

Answer 2

基於您的代碼，我已經說幹就幹，基準3個選項：AVX2供電，嵌套分支（4跳躍）和無分支變體。這些是結果：

//性能表... //全部使用緩存行大小64byteAligned塊（van Emde-Boas Layout）;循環展開每個緩存線; //開啓所有優化。每個元素都是4個字節。英特爾i7 4770k Haswell @ 3。50GHz

Type  ElementAmount  LoopCount  Avg. Cycles/Query 
=================================================================== 
AVX2  210485750   100000000  610 cycles  
AVX2  21048575   100000000  427 cycles   
AVX2  2104857    100000000  288 cycles 
AVX2  210485    100000000  157 cycles 
AVX2  21048    100000000  95 cycles 
AVX2  2104    100000000  49 cycles  
AVX2  210     100000000  17 cycles 
AVX2  100     100000000  16 cycles 


Type  ElementAmount  LoopCount  Avg. Cycles/Query 
=================================================================== 
Branching 210485750   100000000  819 cycles 
Branching 21048575   100000000  594 cycles 
Branching 2104857    100000000  358 cycles 
Branching 210485    100000000  165 cycles 
Branching 21048    100000000  82 cycles 
Branching 2104    100000000  49 cycles 
Branching 210     100000000  21 cycles 
Branching 100     100000000  16 cycles 


Type  ElementAmount  LoopCount  Avg. Cycles/Query 
=================================================================== 
BranchLESS 210485750   100000000  675 cycles 
BranchLESS 21048575   100000000  602 cycles 
BranchLESS 2104857    100000000  417 cycles 
BranchLESS 210485    100000000  273 cycles 
BranchLESS 21048    100000000  130 cycles 
BranchLESS 2104    100000000  72 cycles 
BranchLESS 210     100000000  27 cycles 
BranchLESS 100     100000000  18 cycles 

所以我的結論是這樣的：當內存訪問是最理想的時候，AVX可以幫助Tree的大於200k元素。在這之下，幾乎沒有任何懲罰可以支付（如果你不使用AVX做其他事情）。這是值得的標準這個晚上。感謝所有參與者:-)