3

効率のために、小さな次元 (X、Y、Z としましょう) の N 個のベクトルをどのように保存すればよいのでしょうか。

キャッシュの局所性の理由から、ベクターを次々に [N][3] (行優先) にパックすると、レイアウト [3][N] (次元 X、Y、Z が配置される) よりも良い結果が得られると予想していました。 OpenMP を使用してベクトル操作を行う場合。

しかし、各ベクトルを 3x3 行列で乗算し、インテル® MKL BLAS を使用すると、レイアウト [3][N] の方が 2 倍高速であることがわかりました。

SSE命令が非ストライドデータに対して機能するという事実によって、キャッシュの局所性が相殺されていると思います。これにより、人々が (たとえばコンピューター グラフィックスで) ベクターをどのように保存するのか、また、他の長所と短所があるかどうか疑問に思いました。

4

1 に答える 1

1

使用される一般的なデータ レイアウトには、構造体の配列 (AoS) と配列の構造体 (SoA) の 2 種類があります。

AoS:

struct
{
   float x;
   float y;
   float z;
} points[N];

SoA:

struct
{
   float x[N];
   float y[N];
   float z[N];
} points;

AoS ケースの各ポイントを 3x3 マトリックスで乗算するためにM、ループの本体は次のようになります。

r[i].x = M[0][0]*points[i].x +
         M[0][1]*points[i].y +
         M[0][2]*points[i].z;
// ditto for r[i].y and r[i].z

SSE は一度に 4 つの float を乗算でき (AVX は 8 つの float を乗算できます)、内積演算も提供しますが、ベクトル レジスタに 3 つの float をロードするのは非常に非効率的な操作であるという問題があります。構造体をパディングするフィールドを追加できfloatますが、両方のベクトル オペランドの 4 番目の float が使用されない (または有用な情報が含まれていない) ため、計算能力の 1/4 が失われます。また、ポイントをベクトル化することもできません。たとえば、一度に 4 つのポイントを処理することはできません。一度にロードpoints[i].xするpoints[i+3].xには、x86 では (まだ) サポートされていないギャザー ロードが必要になるためです (ただし、AVX2 対応の CPU が利用可能になると、これは変更されます)。

SoA の場合、内側のループは次のとおりです。

r.x[i] = M[0][0]*points.x[i] +
         M[0][1]*points.y[i] +
         M[0][2]*points.z[i];
// ditto for r.y[i] and r.z[i]

基本的には同じように見えますが、決定的な違いがあります。これで、コンパイラはベクトル命令を使用して、一度に 4 つのポイント (または AVX では 8 つのポイント) を処理できるようになりました。たとえば、ループをアンロールして、次の同等のベクトルに変換できます。

<r.x[i], r.x[i+1], r.x[i+2], r.x[i+3]> =
    M[0][0]*<x[i], x[i+1], x[i+2], x[i+3]> +
    M[0][1]*<y[i], y[i+1], y[i+2], y[i+3]> +
    M[0][2]*<z[i], z[i+1], z[i+2], z[i+3]>

ここには、3 つのベクトル ロード、3 つのスカラー ベクトル乗算、3 つのベクトル加算、および 1 つのベクトル ストアがあります。それらはすべて、SSE のベクター機能を 100% 利用しています。唯一の問題は、ポイントの数が 4 で割り切れない場合ですが、配列を簡単にパディングできるか、コンパイラがスカラー コードを生成して残りの反復をシリアルに実行する可能性がある場合です。いずれにせよ、多くのポイントがある場合、各ポイントで常にハードウェアを十分に活用しないよりも、残りの 1 ～ 3 ポイントのパフォーマンスをいくらか低下させるだけの方がはるかに有益です。

一方、(x,y,z)ランダム ポイントのタプルに頻繁にアクセスする必要がある場合、SoA 実装では (データがキャッシュに収まらない場合) 3 回のキャッシュ ライン読み取りが発生し、AoS 実装では 1 回または 2 回 (パディングあり) が必要になります。 2 つの負荷が必要な場合を回避できます)。答えは、データ構造は、アルゴリズムを支配する操作の種類によって異なります。

于 2012-12-13T11:28:46.850 に答える