カードで利用可能なすべてのRAMを利用するCUDAアプリに取り組んでおり、キャッシュミスを減らすさまざまな方法を見つけようとしています。

問題領域は、解決する問題のタイプに応じて、大きな 2 次元または 3 次元のグリッドで構成されます。(興味のある方は、FDTD シミュレータです)。各要素は、「並列」配列 (つまり、ほぼ同じ次元の別の配列) の 2 つまたは 4 つの要素に依存するため、カーネルは 3 つまたは 6 つの異なる配列にアクセスする必要があります。

問題

*これが「ローカライズされすぎていない」ことを願っています。質問は自由に編集してください

3 つの配列間の関係は、次のように視覚化できます (平凡な ASCII アートで申し訳ありません)。

線でつながれたアイテムが結合されます。上に見られるように、A[]は と の両方に依存しますが、B[]とC[]同様B[]に のみに依存A[]しC[]ます。のすべてがA[]最初のカーネルで更新され、すべてのB[]とC[]が 2 番目のパスで更新されます。

これらの配列を単純な 2D 配列として宣言すると、ストライド メモリ アクセスが発生します。ドメイン サイズが非常に大きい場合 (上記のグリッドでは 3x3 +- 1)、占有率とパフォーマンスの低下が発生します。

そこで、Z オーダー曲線で配列レイアウトを再配置することを考えました。

また、これらを 1 つの配列にインターリーブするのはかなり簡単です。(インターリーブの順序によっては) 特定のセルの更新に必要な要素の少なくとも半分が互いに近くにあるため、フェッチのパフォーマンスが向上するはずです。ただし、GPU が複数の配列にアクセスするときに複数のデータ ポインターを使用するかどうかは明確ではありません。もしそうなら、この想像上の利益は実際には障害になる可能性があります.

質問

テクスチャ メモリまたはcudaArray. これが当てはまらない場合、小さなグリッドでの局所性の利点を排除するために、大きなスパンを横切るとき (高いサブディビジョン レベルで Z 曲線が右上から左下に移動するとき) にレイテンシが増加することを予期する必要がありますか?

3. グリッドを共有メモリに収まる小さなブロックに分割することは確かに役立つはずであり、Z オーダーによりこれはかなり簡単になります。ブロック間の境界を更新する別のカーネル パスが必要ですか? 別のカーネルを起動するオーバーヘッドは、私が期待する節約と比較して重要ですか?

4. 2D と 1D の配列を使用することには、実際の利点はありますか? メモリは線形であると予想していますが、CUDA 文献でよく使用される 2D メモリ レイアウトの比喩に実際の意味があるかどうかはわかりません。

うわー - 長い質問です。これを読んで答えてくれてありがとう。

3D のポイントである現在の入力データについては、モートン コードを使用して、ポイント リストにアクセスする際のキャッシュの一貫性を改善しています。

他に 6D と 7D のデータがあります。モートン コードは、このような次元に対しても優れた手法ですか? それとも他のテクニックはありますか？他の空間充填曲線の手法は、3D 自体の Morton よりも計算が複雑でした。人々が 6D/7D またはそれ以上の代替手法を使用するかどうか疑問に思っています。

Hacker's Delight 2nd Edition のアルゴリズム

pythonに移植

シンプルなヒルベルト曲線クラス。

だから私が欲しいのは、 next() が呼び出されるたびに (x,y) を与えるものです。私はこれを自分でやろうとしましたが、うまくいかないので、助けていただければ幸いです。ジェネレーターで動作するようにこれを書き直す必要がありますか? ソース

Peano 曲線などの空間充填曲線は、物理的な空間的局所性を維持するため、線形アドレス空間でキャッシュに適したデータ構造を維持するのに役立つと読みました。

ただし、実際にそれらを使用する方法はわかりません。これらの曲線のいずれかに、線形アドレスを (x,y) 座標に、またはその逆にすばやく変換するための式がありますか? それ以外の場合、特定の座標のペアを検索するときにメモリ内のどこを参照するかをどのように判断すればよいでしょうか? 例は非常に役に立ちます。

空間充填曲線は、局所性を維持する線でグリッドを埋める方法です。つまり、線の 2 つの近接点は、空間上の 2 つの近接点でもあります。

O(1)N 次元の座標と、対応する N 次元の空間充填曲線上のインデックスとの間をマッピングする高速な ( ) アルゴリズムはありますか?

Z インデックスを計算するためにいくつかのアルゴリズムをテストしたので、少し混乱しています。(8, 8, 8) の場合は 3584 が得られ、(7, 7, 7) の場合は 511 が得られます。これは正しいです。問題は 8*8*8 = 512 ですが、z インデックスは 3584 です。つまり、1 次元配列を使用して z インデックスで格納すると、より多くのスペースを使用することになり、空になります。配列のスロット？同様に、7*7*7 = 343 で、これは 511 よりも小さいです。ウィキペディアの z-indexing/Morton エンコーディングのページを見ると、x と y のインデックスが 0 から始まる 8*8 の 2 次元の例が見つかります。ただし、最大の z-index は 111111 であり、これは 63 であり、0 から数えると正確に 64 番目の要素であるため、64 要素を格納するために必要以上のスペースを使用しません。ここで何か問題がありますか？

ありがとう

2D 画像を平坦化するために、Python で (Matlab のものから) Hilbert-Peano 空間充填曲線の実装を作成しました。

ただし、従来の Hilbert-Peano 曲線は、形状が 2 のべき乗である多次元配列に対してのみ機能します (例: 2D 配列の場合は 256*256 または 512*512 (画像))。

これを任意のサイズの配列に拡張する方法を知っている人はいますか?