使用SIMD/AVX/SSE进行树遍历

Question

我目前正在研究是否有可能加速面包车Emde Boas(或任何树)遍历.给定单个搜索查询作为输入,已经在缓存行中具有多个树节点(van emde Boas布局),树遍历似乎是指令瓶颈.

作为SIMD/AVX/SSE指令的新手,我想知道该主题的专家是否可以将多个节点一次比较到一个值,然后找出要进一步遵循的树路径.我的研究得出以下问题:

在构建SIMD/AVX/SSE寄存器等时浪费了多少cpu周期/指令.如果构建比手动遍历整个子树需要更多的时间(2 + 4 + 8个节点),这将使其用于wayne. 1个大小为64字节的高速缓存行).

在寻找合适的SIMD/AVX/SSE寄存器时,浪费了多少cpu周期/指令,并确定了要遵循的路径？任何人都可以想出一个聪明的方法,以便那些"findMinimumInteger"AVX指令可用于决定1(??)cpu周期？

你猜怎么着？

加速树遍历的另一种更棘手的方法是在最后一个树级别中很可能在节点中紧密地着陆时,同时运行多个搜索查询.对此有何猜测？但是,它必须将那些不再属于同一子树的查询放在一边,然后在完成树的第一次"并行遍历"之后递归地找到它们.树查询具有顺序但不是恒定的访问模式(query [i]总是<而不是查询[i + 1]).

重要的是:这个东西是关于整数树的,这就是使用van Emde Boas Tree的原因(也许x-fast/y-fast稍后尝试)

我很好奇你在这个问题上的50美分是多少,因为人们可能会对大型树的最高性能感兴趣.提前感谢你花时间在这上面:-)

Answer 1

我使用SSE2/AVX2来帮助执行B +树搜索.这是在AVX2中对16个DWORD的完整缓存行执行二进制搜索的代码:

// 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布局); 每个缓存行展开循环; //所有优化都已开启.每个元素为4个字节.Intel 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的话).值得对此进行基准测试之夜.感谢所有参与者:-)