c++ - オクトリーのスレッド化

Question

oct 内の各 octcell に含まれるポインターが、同じレベルでツリー内を簡単にトラバーサルできるように、octree をスレッド化する効率的な方法。

ここでは完全にスレッド化されたツリーを使用して、openmp を使用して同じレベルでコードを並列化できるようにする必要があります。

Answer 1

私はオクトツリーの経験があり、自分でいくつかコーディングしました。基本的な問題は、ツリーに (少なくとも) 2 つのトラバーサル方向があることです: 水平方向 (娘セル間) と垂直方向 (母細胞と娘細胞の間) であり、線形メモリにマップすることはできません。したがって、ツリーをトラバースすると (たとえば、近隣検索の場合)、必然的にキャッシュ ミスが発生します。

最も効率的な実装では、非最終セルのすべて (最大 8 つ) のドーター セルをメモリの 1 つの連続したブロックに配置し、それらをトラバースする際のキャッシュ ミスとそれらをポインターでリンクする必要の両方を回避する必要があります。各セルは、最初の娘セルに対して 1 つのポインター/インデックスのみを必要とし、場合によっては (アプリケーションのニーズに応じて) 母セルへのポインターを必要とします。

同様に、ツリーによってソートされたパーティクル/位置は、すべてのツリー レベルで、セル内に含まれるすべてがメモリ内で連続するように並べ替える必要があります。次に、各セルは最初の粒子とその数だけを格納する必要があり、ツリーのすべてのレベル (最終セルだけでなく) ですべての粒子にアクセスできます。

実際には、このような順序付けは、最初に完全にリンクされたツリーを構築し、次にそれを上記の形式にマッピングすることによって実現できます。このマッピングのオーバーヘッドはわずかですが、アプリケーションでのメリットは相当なものです。

最後に、パーティクルの位置をわずかに変更してツリーを再構築すると、(アルゴリズムによっては) パーティクルを以前のツリー順序でツリー構築アルゴリズムに供給するための速度が大幅に向上します。