Morton-Orderによる最近隣の検索の利点？

Question

粒子の相互作用のシミュレーションに取り組んでいる間、私はモートンオーダー（z-order）のグリッドインデックスを越えてつまずきました（z-order）（ウィキペディアリンク）これは、効率的な最近隣接セル検索を提供すると見なされています。私が読んだ主な理由は、メモリ内の空間的に近いセルのほぼ連続した順序です。

最初の実装の途中であるため、特に基本的な均一なグリッドと比較して、最近の隣人のアルゴリズムを効率的に実装する方法を頭に巻き付けることはできません。

1. セル（x、y）が与えられた場合、8つの隣接細胞インデックスを取得し、それぞれのz-indexを計算することは些細なことです。これにより、要素への一定のアクセス時間が提供されますが、z-indexを計算するか、事前定義されたテーブルで検索する必要があります（各軸とORの分離）。これはどのようにしてより効率的になる可能性がありますか？確かに、配列a内の要素にアクセスすると、[0] - > a1 - > a [3] - > a [4] - > ...順序A [1023] - > a [12] - > a [456] - > a [56] - > .. 。？

2. Zオーダーの最も近い隣人を見つけるために、より単純なアルゴリズムが存在することを期待していました。線に沿って何か：隣人の最初のセルを見つけ、反復します。しかし、これは2^4サイズのブロック内でのみうまく機能するため、これは真実ではありません。ただし、2つの問題があります。セルが境界上にない場合、ブロックの最初のセルを簡単に決定し、ブロック内のセルを繰り返すことができますが、セルが最も近い隣接であるかどうかを確認する必要があります。細胞が境界にある場合、さらに悪いことに、2^5のセルを考慮する必要があります。ここに何が欠けていますか？私が必要なことを行う比較的単純で効率的なアルゴリズムはありますか？

ポイント1の質問は簡単にテストできますが、説明されているアクセスパターンが生成し、舞台裏で何が起こっているのかを本当に理解したいという根本的な指示にはあまり精通していません。

支援、参照などを前もってありがとう...

---

編集：
ポイント1を明確にしてくれてありがとう！したがって、Z順序では、隣接セルのキャッシュヒット率が平均して増加しますが、興味深いものになります。キャッシュヒット/ミスレートをプロファイルする方法はありますか？

ポイント2については、インデックスi = f（x1、x2、...、xd）がビットワイズインターレースなどから取得されるr^dのポイントクラウドのモートン順序アレイを構築する方法を理解する必要があります。私が理解しようとしているのは、最近の隣人を得るために次の素朴なアンサッツよりも良い方法があるかどうかです（ここではd = 2、「pseudo code "）：

// Get the z-indices of cells adjacent to the cell containing (x, y) 
// Accessing the contents of the cells is irrelevant here
(x, y) \elem R^2    
point = (x, y)
zindex = f(x, y)     
(zx, zy) = f^(-1)(zindex)          // grid coordinates 
nc = [(zx - 1, zy - 1), (zx - 1, zy), (zx - 1, zy + 1),  // neighbor grid 
      (zx    , zy - 1),               (zx,     zy + 1),  // coordinates
      (zx + 1, zy - 1), (zx + 1, zy), (zx + 1, zy + 1)]

ni= [f(x[0], x[1]) for x in nc]    // neighbor indices

Answer 1

最新のマルチレベルのキャッシュベースのコンピューターシステムでは、空間局所性は、データ要素へのアクセス時間を最適化する重要な要素です。

簡単に言えば、これはメモリ内のデータ要素にアクセスすると、近くにあるメモリ内の別のデータ要素にアクセスすると（最初に近いアドレスがあります）、数桁安くなる可能性があります。遠く。

単純な画像処理またはサウンド処理のように、または各要素の処理を繰り返して同じ方法でデータ構造を繰り返すように、1 -Dデータにシーケンシャルにアクセスすると、メモリのデータ要素を順に配置すると、空間の局所性が得られる傾向があります。つまり、要素にアクセスするため、 n+1要素nにアクセスした直後に、2つの要素をメモリに隣り合わせて配置する必要があります。

標準のCアレイ（および他の多くのデータ構造）には、このプロパティがあります。

モートンの注文のポイントは、データにアクセスされるスキームをサポートすることです 2 ではなく寸法 1 寸法。言い換えれば、要素（x、y）にアクセスした後、アクセス（x+1、y）または（x、y+1）などにアクセスすることができます。

モートンの順序は、（x、y）、（x+1、y）、および（x、y+1）がメモリに互いに近くにあることを意味します。標準のC多次元配列では、これは必ずしもそうではありません。たとえば、配列では、myarray [10000] [10000]、（x、y）、および（x、y+1）は10000要素です。

---

モートンの注文では、標準のCアレイをデータのストアとして使用できますが、（x、y）がストア[x+y*rowsize]ほど単純ではなくなった場合に計算する計算はありません。

モートンの注文を使用してアプリケーションを実装するには、座標（x、y）をストア内のアドレスに変換する方法を解決する必要があります。つまり、関数が必要です f(x,y) それは、ようにストアにアクセスするために使用できます store[f(x,y)].

さらに調査する必要があるようです - ウィキペディアページ、特にのリンクに従ってください。 BIGMIN 働き。

Answer 2

はい、配列要素に順番にアクセスするのが実際に高速です。 CPUは、RAMからチャンクのキャッシュにメモリをロードします。順次アクセスすると、CPUは次のチャンクを簡単にプリロードでき、負荷時間に気付くことができません。ランダムにアクセスすると、できません。これはキャッシュコヒーレンシーと呼ばれ、それが意味することは、すでにアクセスしたメモリに近いメモリにアクセスすることがより速いということです。

例では、[1]、[2]、[3]、および[4]をロードすると、プロセッサはおそらくこれらのインデックスのいくつかを一度にロードし、非常に些細なことです。さらに、[5]にアクセスしようとすると、[1]などで操作中にそのチャンクを事前ロードでき、負荷時間を効果的に何もしません。

ただし、[1023]をロードする場合、プロセッサはそのチャンクをロードする必要があります。次に、[12]をロードする必要があります。これはまだロードされていないため、新しいチャンクをロードする必要があります。 et cetera、et cetera。ただし、残りの質問については知りません。