矢量化 (SIMD) 树运算
关于向量化树操作的一般提示/指针有哪些？内存布局明智、算法明智等。
一些特定于领域的内容：
- 每个父节点将有相当多（20 - 200）个子节点。
- 每个节点拥有子节点的概率都很低。
- 对树的操作主要是条件行走。
- 遍历树的性能比插入/删除/搜索速度更重要。
What are some general tips/pointers on vectorizing tree operations? Memory layout wise, algorithm wise, etc.
Some domain specific stuff:
- Each parent node will have quite a few (20 - 200) child nodes.
- Each node has a low probability of having child nodes.
- Operations on the tree is mostly conditional walks.
- The performance of walking over the tree is more important than insertion/deletion/search speeds.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
请注意，这很难实现。去年，由英特尔、甲骨文和 UCSC 组成的团队提出了一个令人惊叹的解决方案“快速：快速架构敏感树搜索
on Modern CPUs and GPUs”。他们获得了“2010年最佳论文奖” ”，作者：ACM SIGMOD。
Beware, this is very hard to implement. Last year a team of Intel, Oracle and UCSC presented an amazing solution "FAST: Fast Architecture Sensitive Tree Search
on Modern CPUs and GPUs". They won the "Best Paper Award 2010" by ACM SIGMOD.
由于树木的随机性，矢量化行走对您来说有何好处并不是立即显而易见的。
我会将树布置为（parentid，节点数据）“节点”项的平面数组，按parentid排序，这样您至少可以一起访问节点的子节点。当然，如果您的树不是“胖”（即节点的平均子节点数量较少），那么这不会给您带来太多好处。
不过，您最好的选择实际上只是强调 SIMD 的强力，因为您确实无法使用此 API 在列表中进行奇特的随机跳转。
编辑：我不会扔掉你最有可能拥有的普通树类，实现 SIMD 方式并看看你是否真的获得任何东西，我不相信你会......
Because of the random nature of trees it's not immediately obvious how vectorizing walks would be a big plus to you.
I would lay the tree out as a flat array of (parentid, node data) "node" items, sorted by parentid, so you can at least visit the children of a node together. Of course this doesn't give you much if your tree isn't "fat" (ie low number of children on average for a node).
Your best bet though is really just to emphasize on the brute force of SIMD, because you really can't do fancy random jumps through your list with this API.
Edit: I wouldn't throw out the normal tree class you most likely have though, implement the SIMD way and see if you really gain anything, I'm not convinced you will...
使用谱图论算法怎么样？它们应该很容易矢量化，因为它们处理矩阵。
What about using spectral graph theory algorithms? They should be much easy to vectorize, as they deal with matrices.