5

可変長の多次元データ配列のセットを効率的に格納 (およびその後アクセス) するためのベスト プラクティスを知りたいです。焦点はパフォーマンスにありますが、実行時に個々のデータ セットの長さをあまりオーバーヘッドなく変更できるようにする必要もあります。

注：これはやや長い質問であることは承知していますが、かなり調べてみましたが、目前の問題を十分に正確に説明する解決策や例を見つけることができませんでした。

バックグラウンド

コンテキストは、不連続ガラーキン スペクトル要素法 (DGSEM) に基づく数値流体力学 (CFD) コードです (参照: Kopriva (2009), Implementing Spectral Methods for Partial Differential Equations )。簡単にするために、2D データ レイアウトを想定してみましょう (実際には 3 次元ですが、2D から 3D への拡張は簡単です)。

異なる (物理) サイズのK正方形要素k( )で構成されるグリッドがあります。k = 0,...,K-1各グリッド要素 (または「セル」)k内に、N_k^2データ ポイントがあります。N_kは各次元のデータ ポイントの数であり、異なるグリッド セル間で異なる場合があります。

各データ ポイントn_k,i(ここでi = 0,...,N_k^2-1) で、解の値の配列を格納する必要があります。これは、nVarsドメイン全体 (つまり、どこでも) で同じ長さを持ち、実行時に変化しません。

寸法と変更

グリッド セルの数は最大Kであり、実行時に変更さO(10^5)れる可能性O(10^6)があります。各グリッド セル のデータ ポイントの数は、 と の間であり、実行時に変更される可能性があります (セルごとに異なる場合があります)。各グリッド ポイントに格納されている 変数の数は約 1 つであり、実行時に変更することはできません(すべてのグリッド セルでも同じです)。
N_k28
nVars510

要件

ここではパフォーマンスが重要な問題です。すべてのセルのすべてのグリッド ポイントを効率的に (つまり、あまり多くのキャッシュ ミスを発生させずに) 順序付けられた方法で定期的に反復できる必要があります。一般に、KおよびN_kはシミュレーション中にあまり頻繁に変更されないため、たとえば、すべてのセルとデータ ポイントに対して大規模な連続したメモリ ブロックを使用することもできます。

ただし、実行時にグリッドを調整または粗くする必要があります (つまり、セルを削除して新しいセルを作成します。新しいセルは最後に追加される場合があります)。また、近似順序を変更できるようにする必要があるためN_k、各セルに保存するデータ ポイントの数も実行時に変更できます。

結論

どんな入力でも大歓迎です。ご自身での経験がある場合、または私が参照できるいくつかの優れたリソースを知っている場合は、お知らせください。ただし、解決策は最終的なプログラムのパフォーマンスにとって重要ですが、それは多くの問題の 1 つにすぎないため、解決策は純粋に学術的なものではなく、応用的な性質のものである必要があります。

この質問をする場所が間違っている場合は、より適切な場所を教えてください。

4

2 に答える 2

3

多くの場合、この種の動的メッシュ構造は効率的に処理するのが非常に難しい場合がありますが、ブロック構造の適応メッシュ リファインメント コード (複雑な形状が重要でない天体物理学では一般的) または大きなブロック サイズを持つスペクトル要素コードでは、 、それは多くの場合、それほど問題ではありません。ブロック/要素ごとに行う作業が非常に多いため (この場合、少なくとも 10^5 セル x 2 ポイント/セル)、ブロック間の切り替えのコストは比較的わずかです。

また、ブロックのかなりの量のデータが既にキャッシュに存在するまで、通常は各要素またはブロックに対して多くのハードワークを行うことはできないことにも注意してください。とにかく、ブロック N+1 で多くの作業を行う前に、ブロック N のデータのほとんどをキャッシュからフラッシュする必要があります。(これに対する例外である操作がコード内にいくつかあるかもしれませんが、データの再利用があまりないため、それらはおそらくとにかく多くの時間を費やしているものではありません。キャッシュまたはキャッシュなしです。セル値)。そのため、各ブロック/要素を隣り合わせに保つことは、必ずしも大したことではありません。一方、ブロック/要素自体が連続していることは間違いありません。

また、サイズが変更されたときにブロックを移動して連続性を保つことができますが、これらすべてのメモリ コピーがキャッシュを消去するだけでなく、メモリ コピー自体が非常に高価になることにも注意してください。問題がメモリのかなりの部分を占有している場合 (常にそうではありませんか?)、たとえば 1GB とすると、再調整後にその 20% を移動して、物事を再び連続させる必要がある場合、それは 0.2 GB (読み取り + 書き込み) / ~20 GB/s ~ 20 ms (たとえば) 16k キャッシュ ラインをそれぞれ ~100ns で ~1.5 ms 再ロードするのに比べて。とにかく、シャッフル後にキャッシュは破棄されます。これは、洗練/非定義をめったに行わないことがわかっている場合でも、実行する価値があるかもしれません。

しかし実際問題として、天体物理流体力学におけるほとんどのアダプティブ メッシュ コード (私はそのコードについて十分に理解しています) は、単にブロックとそのメタデータのリストを維持し、それらの連続性について心配する必要はありません。もちろんYMMV。私の提案は、完全なデータ構造の作成に多くの時間を費やす前に、まず 2 つの要素で操作を 2 回テストすることです。1 つ目は要素を順番に並べて計算する 1-2 で、2 つ目は「間違った」順序で操作を行い 2-1 、2 つの計算のタイミングを数回とります。

于 2012-07-10T14:57:55.350 に答える
1

セルごとに、セル データを検索するためのオフセットを連続した配列に格納します。このオフセット マッピングは非常に効率的で、広く使用されています。トラバーサルでキャッシュを再利用するためにセルを並べ替えることができます。セルの順序または数が変更された場合は、新しい配列を作成して補間し、古い配列を破棄します。このストレージは、クリロフ法の内積やルンゲ クッタ法のステージなどの操作をメッシュを参照せずに管理できるため、外部分析にははるかに適しています。また、ベクトルごとに最小限のメモリしか必要としません (たとえば、Krylov ベースで、時間積分を使用する場合)。

于 2012-08-26T04:18:10.833 に答える