3

スパース ジオメトリの非立方バウンディング ボックスを含む 3D 配列があります。

配列 geometry[x][y][z] には、(x,y,z) が計算領域の一部である場合は値 0 が含まれ、そうでない場合は 1 が含まれます。

計算を並べ替えるために、ヒルベルト曲線を使用してこの空間をトラバースしたいと考えています。

コンテキストは、メモリにバインドされた GPU プログラムでグローバル メモリ アクセスを最適化しています。

どうすればこれを実装できますか?

更新:要素の19個の隣接ノードを追跡する隣接リストと一緒に(配列に)格納するだけなので、空でないセルをトラバースしたいだけです。

計算は、2 つの配列間でコピーするだけです。

dst[i] = src[adjacency_map[i]]

これは疎格子ボルツマン法の伝播段階であり、物理的な解釈は隣接するサイトから「流体粒子」をストリーミングしています。

adjacency_map の値が連続的であるほど、次のようになります。より合体したメモリアクセスが得られることを願っています。

OpenCL カーネル:

__kernel void propagation(__global double *dst, __global double *source,
                          __global const int *adjacency_map, const uint max_size)
{
    size_t l = get_global_id(0);

    if( l > max_size ) 
        return;

    dst[l] = src[adjacency_map[l]];
}
4

2 に答える 2

3

ヒルベルト曲線は難しい注文です。曲線上の点のインデックスへのランダム アクセスを可能にする定式化を見つけるのは難しいようです。

ただし、モートン順序付けは合理的であり、空間充填曲線でもあるため、同様の優れた特性がいくつかあります。N 次元の点のモートン数を見つけるためのランダム アクセス手順もあります。

考えられるのは、次の 2 段階のプロセスです。

  1. データにストリーム圧縮のステップを適用して、処理するボリューム要素を選択します

  2. Morton インデックスをソート キーとして使用して、この圧縮されたデータをソートします。

ストリームの圧縮とキー値の並べ替えの両方に推力を使用できます。

これにより、連続性を促進する順序でボリューム要素のリストが生成されます。とはいえ、データを再編成するオーバーヘッドが、元の不規則なアクセス パターンのコストを支配する可能性があります。

于 2011-08-02T18:33:52.640 に答える
1

それはまったく不可能に聞こえます。

kdtreeまたはoctreeをすでに除外しましたか？

数値レシピでのkdtree（21.2章）とoctree（21.8章）の説明は非常に理解しやすいです：http： //apps.nrbook.com/rollover/index.html

于 2011-07-31T00:10:29.193 に答える