0

7 ポイントの計算ステンシルを含む問題に取り組みたいと考えています。知らない人のために説明すると、これは 3D グリッドであり、7 つのポイントは n 番目のポイントであり、隣接するポイントは x、y、z 方向に正と負の両方で 1 つ離れたポイントです (または東に隣接するポイント)。 /west/north/south および up/down)。

したがって、これらの 6 つのポイントに加えて、私が取り組んでいる 1 つの追加ポイントが計算に使用され、すべて 1 次元配列に格納されます。

nx を立方体の幅、ny を高さとします。メモリ内では、All_points[n] などの配列 All_Points 内のポイントにアクセスしているときに、各方向の隣接ポイントを取得するために、All_points[n-1]、All_points[n+1] にもアクセスしたいと考えています。 、All_points[n-nx]、All_points[n+nx]、All_points[n-nx ny]、および All_points[n+nx ny]。

したがって、これに関する私の問題は、大量のキャッシュミスが発生していることです。この問題を回避する方法を示すコード例が見つからないようです。理想的には、この配列を All_x_points[] などの x、y、z 座標に分割して戻したいのですが、All_points[n] が変更されるため、それを更新し続けようとすると問題が発生します。つまり、他の All_points[n'] の場合、x、y、または z の値を更新する必要があります。

この種のことが以前に行われたのを見た人はいますか？

4

2 に答える 2

1

7点ステンシルを使ったアクセスパターンは？キャッシュの一貫性に問題がある場合、これが最初の質問です。中央の (x、y、z) 座標のアクセス パターンが完全にランダムである場合は、うまくいかない可能性があります。

アクセス パターンをある程度制御できる場合は、よりキャッシュしやすいように調整を試みることができます。そうでない場合は、予想されるアクセス パターンの種類を検討する必要があります。このアクセス パターンがより無害になるようにデータを配置できる場合があります。これら 2 つの組み合わせは、非常に効果的な場合があります。

この種の場合に頻繁に役立つ特定のデータ配置があります: ビットインターリーブ配列レイアウトです。簡単にするために、各座標のサイズは 2 の累乗であると仮定します。次に、「通常の」レイアウトは、各座標のビットを連結してインデックスを構築します。ただし、ビット インターリーブ レイアウトでは、ラウンドロビン方式で各次元にビットが割り当てられます。

3D index coords: (xxxx, yyyy, zzzz)

normal index:    data[zzzzyyyyxxxx]  (x-coord has least-significant bits, then y)
bit-interleaved: data[zyxzyxzyxzyx]  (lsb are now relatively local)

実際には、わずかなコストがかかります。座標にステップ値を掛ける代わりに、ルックアップ テーブルを使用してオフセットを見つける必要があります。しかし、おそらく非常に短いルックアップ テーブルしか必要ないため (特に 3D 配列の場合)、それらはすべてキャッシュにうまく収まるはずです。

3D coords:  (x,y,z)

normal index:      data[x + y*ystep + z*zstep]  where:
  ystep= xsize (possibly aligned-up, if not a power of 2?)
  zsetp= ysize * ystep

bit-interleaved:   data[xtab[x] + ytab[y] + ztab[z]]  where:
  xtab={  0,  1,  8,  9, 64, 65, 72, 73,512...}   (x has bits 0,3,6,9...)
  ytab={  0,  2, 16, 18,128,130,144,146,1024...}  (y has bits 1,4,7,10...)
  ztab={  0,  4, 32, 36,256,260,288,292,2048...}  (y has bits 2,5,8,11...)

最終的に、これが役に立つかどうかは、アルゴリズムの要件に完全に依存します。ただし、繰り返しになりますが、アルゴリズムがキャッシュに対して要求が高すぎる場合は、レイアウトだけでなく、アルゴリズムの調整を検討することをお勧めします。

于 2009-12-12T13:05:49.120 に答える
0

7点？空間座標を定義する 6 つ、長さを定義する 1 つ？これらは... スターゲイト座標ですか？

構造体配列 (AOS) を構造体配列 (SOA) に変えてみませんか?

int point = points_all[i]; // the point you want
Vec2 points_x[point]; // x and y are the neighbours left and right
Vec2 points_y[point]; // x and y are the neighbours up and down
Vec2 points_z[point]; // x and y are the neighbours front and back
于 2009-12-10T19:28:41.727 に答える