向量化（SIMD）树操作

Question

9

在向量化树操作方面，有哪些一般的提示/指导？包括内存布局、算法等。

某些领域的特定内容：

- jameszhao00

3个回答

2

由于树的随机性质，向量化遍历对您来说不是立即显而易见的好处。

我建议将树布局为一个平坦数组，其中包含（parentid，node data）“节点”项，按parentid排序，这样您至少可以一起访问节点的子节点。当然，如果您的树不是“胖”的（即节点平均具有较少的子节点），则这并没有给您带来太多好处。

不过，您最好还是强调SIMD的暴力优势，因为您不能使用此API通过列表进行花式随机跳转。

编辑：我不会放弃您可能拥有的常规树类，实现SIMD方式并查看是否真正获得了任何东西，我并不确定...

- Blindy

0

使用谱图理论算法怎么样？它们应该更容易向量化，因为它们处理矩阵。

- trebuchet

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- alecco · Accepted Answer

注意，这非常难以实现。去年，英特尔、甲骨文和加州大学圣克鲁兹分校的团队提出了一个惊人的解决方案“FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs”。他们赢得了ACM SIGMOD颁发的“2010最佳论文奖”。