c++ - 线程化八叉树

Question

线程化八叉树的有效方法，使得八进制中每个八进制单元所包含的指针可以轻松地遍历同一级别的树。

我们必须在这里使用全线程树，以便我可以使用 openmp 在同一级别并行化代码。

Answer 1

我对八叉树有一些经验，并自己编写了几个代码。基本问题是树有（至少）两个遍历方向：水平（在子细胞之间）和垂直（在母细胞和子细胞之间），不能映射到线性内存。因此，遍历树（例如邻居搜索）将不可避免地导致缓存未命中。

对于最有效的实现，您应该将非最终单元的所有（最多 8 个）子单元都放在一个连续的内存块中，避免在遍历它们时缓存未命中以及使用指针链接它们的需要。然后每个单元只需要一个指针/索引用于它们的第一个子单元，并且可能（取决于您的应用程序的需要）一个指向其母单元的指针。

类似地，任何由树排序的粒子/位置都应该被排序，使得一个单元中包含的所有粒子/位置在所有树级别的内存中都是连续的。然后每个单元只需要存储第一个和数量的粒子，允许在树的每个级别访问所有粒子（不仅仅是最终单元）。

在实践中，可以通过首先构建一个完全链接的树，然后将其映射到上述形式来实现这种排序。这种映射的开销很小，但应用程序的增益很大。

最后，当仅略微改变粒子位置重新构建树时，将先前树顺序中的粒子提供给树构建算法会显着加快速度（取决于您的算法）。