穿越八叉樹

Question

穿越八叉樹的有效方法是這樣的，即每個八進制單元包含的指針在一個十進制中可以使遍歷同一級別的樹時更容易。

我們必須在這裏使用完全線程化的樹，以便我可以使用openmp在同一級別並行化代碼。

Answer 1

我有一些八叉樹的經驗和編碼幾個我自己。基本問題是樹至少有兩個遍歷方向：水平（在子單元之間）和垂直（在母單元和子單元之間），它們不能映射到線性內存。因此，遍歷樹（例如用於鄰居搜索）將不可避免地導致緩存未命中。

對於最有效的實現，您應該將非最終單元格的所有（最多8個）子單元放在一個連續的內存塊中，避免在遍歷它們時緩存未命中以及需要鏈接它們與指針。然後每個單元只需要一個指針/索引用於它們的第一個子單元，並且可能（取決於應用程序的需要）指向它們的母單元。

類似地，任何由樹排序的粒子/位置都應該排序，使得所有包含在單元格內的粒子在內存中都是連續的，在所有樹級別。然後每個單元格只需要存儲第一個和多個粒子，從而允許在樹的每一層訪問所有它們（而不僅僅是最終單元格）。

實際上，這樣的排序可以通過首先構建一個完全鏈接的樹，然後將其映射到上面描述的形式來實現。這種映射的開銷很小，但是應用程序的收益很大。

最後，當只用稍微改變的粒子位置重新構建樹時，它會顯着加速（取決於您的算法），將前一樹順序中的粒子送入樹構建算法。