我目前正在研究是否有可能加速面包车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美分是多少,因为人们可能会对大型树的最高性能感兴趣.提前感谢你花时间在这上面:-)