3d疎なジオメトリのヒルベルト曲線

Question

私は疎なジオメトリの非立方体のバウンディングボックスを含む3次元配列を持っています。

アレイジオメトリ[X] [Y]（x、y、z）が計算領域の部分とそうでない場合は1

私はだろう演算の順序を変更しようとする試みである場合、[z]は値0を含んでいヒルベルト曲線を使ってこの空間を横断するのが好きです。

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

どうすれば実装できますか？

更新： 私は私は一緒に要素の19個の隣接ノードを追跡する隣接リストと（配列で）それらを保存するように、非空のセルを通過します。

計算は、単に二つの配列の間にコピーされる：

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]]; 
} 

Answer 1

ヒルベルト曲線は、背の高い順番であろう。カーブ上の点のインデックスにランダムにアクセスできるような定式化を見つけるのは難しいようです。

Morton orderingしかし、これは妥当であり、スペース充填曲線であるのと同じ素敵な特性を持っています。また、N次元点のモートン数を求めるためのランダムアクセス手順もある。あなたが考えるかもしれません何

は、2段階のプロセスである：

1. あなたは

2. ソートにこの圧縮されたデータを処理したいボリューム要素を選択するためにあなたのデータへのストリーム圧縮のステップを適用し、 Morton indices as the sorting keyを使用して

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

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

Answer 2

かなり不可能に聞こえます。

あなたは既にkdtreeまたはoctreeを除外しましたか？数値的レシピでkdtreeの

記述（章21.2）および八分木（章21.8）は、非常に理解している：

http://apps.nrbook.com/rollover/index.html