この記事は、インテル® デベロッパー・ゾーンに公開されている「How to Manipulate Data Structure to Optimize Memory Use on 32-Bit Intel® Architecture」(https://software.intel.com/en-us/articles/how-to-manipulate-data-structure-to-optimize-memory-use-on-32-bit-intel-architecture) の日本語参考訳です。
課題
データ構造のレイアウトを調整してメモリー使用量を改善します。3D 変換やライティングなどの特定のアルゴリズムでは、バーテックス・データを配置する 2 つの基本的な方法があります。従来の方法は、次に示すように、バーテックスごとに構造体を作成する構造体配列 (AoS) です。
typedef struct{
float x,y,z;
int a,b,c;
. . .
} Vertex;
Vertex Vertices[NumOfVertices];
この方法は、SIMD テクノロジーの能力を最大限に引き出すことができません。
ソリューション
座標ごとの配列にデータを配置して、配列構造体 (SoA) 処理方式の利点が得られるようにします。次に SoA データ構造を示します。
typedef struct{
float x[NumOfVertices];
float y[NumOfVertices];
float z[NumOfVertices];
int a[NumOfVertices];
int b[NumOfVertices];
int c[NumOfVertices];
. . .
} VerticesList;
VerticesList Vertices;
AoS 形式のデータを計算するには、2 つの選択肢があります: AoS 形式のままデータを操作するか、動的に SoA 形式に変換 (スウィズル) します。次のサンプルコードは、ドット積におけるそれぞれの選択肢を示しています。
; The dot product of an array of vectors (Array) and a
; fixed vector (Fixed) is a common operation in 3D
; lighting operations,
; where Array = (x0,y0,z0),(x1,y1,z1),...
; and Fixed = (xF,yF,zF)
; A dot product is defined as the scalar quantity
; d0 = x0*xF + y0*yF + z0*zF.
; AoS code
; All values marked DC are "don't-care."
; In the AOS model, the vertices are stored in the
; xyz format
movaps xmm0, Array ; xmm0 = DC, x0, y0, z0
movaps xmm1, Fixed ; xmm1 = DC, xF, yF, zF
mulps xmm0, xmm1 ; xmm0 = DC, x0*xF, y0*yF, z0*zF
movhlps xmm1, xmm0 ; xmm1 = DC, DC, DC, x0*xF
addps xmm1, xmm0 ; xmm0 = DC, DC, DC,
; x0*xF+z0*zF
movaps xmm2, xmm1
shufps xmm2, xmm2,55h ; xmm2 = DC, DC, DC, y0*yF
addps mm2, xmm1 ; xmm1 = DC, DC, DC,
; x0*xF+y0*yF+z0*zF
; SoA code
;
;
X = x0,x1,x2,x3
; Y = y0,y1,y2,y3
; Z = z0,z1,z2,z3
; A = xF,xF,xF,xF
; B = yF,yF,yF,yF
; C = zF,zF,zF,zF
movaps xmm0, X ; xmm0 = x0,x1,x2,x3
movaps xmm1, Y ; xmm0 = y0,y1,y2,y3
movaps xmm2, Z ; xmm0 = z0,z1,z2,z3
mulps xmm0, A ; xmm0 = x0*xF, x1*xF, x2*xF, x3*xF
mulps xmm1, B ; xmm1 = y0*yF, y1*yF, y2*yF, y3*xF
mulps xmm2, C ; xmm2 = z0*zF, z1*zF, z2*zF, z3*zF
addps xmm0, xmm1
addps xmm0, xmm2 ; xmm0 = (x0*xF+y0*yF+z0*zF), ...
元の AoS 形式で SIMD 操作を実行すると、より多くの計算が必要となる場合があり、一部の操作では利用可能なすべての SIMD 要素を活用できません。そのため、この選択肢は一般に非効率的です。
AoS 形式でデータを計算する際の推奨方法は、SIMD テクノロジーを使用して処理する前に、各要素セットを SoA 形式に変換することです。この変換は、プログラムの実行中に動的に行うか、データ構造の生成時に静的に行います。コードの変換の具体例は、『インテル® 64 アーキテクチャーおよび IA-32 アーキテクチャー最適化リファレンス・マニュアル』の 4 章と 5 章を参照してください。動的に変換するほうが、一般に AoS を使用するよりも優れていますが、計算中に追加命令のオーバーヘッドが生じるため、やや非効率です。データ構造の生成時に静的に変換すると、実行時のオーバーヘッドはありません。
前述のとおり、SoA 形式のほうが、データはより最適な垂直形式で配置されているため、SIMD テクノロジーの並列性を効率良く利用できます: 4 つの SIMD レーンを使用してコンポーネント x0、x1、x2、x3 と xF、xF、xF、xF を乗算して、4 つの結果を生成します。一方、AoS データを直接計算すると、水平に処理が行われ、前述のサンプルコードにある多くの「don’t-care」 (DC) が示すように、SIMD レーンは消費されますが、単一のスカラー結果しか生成されません。
また、SoA 形式のデータ構造を使用すると、キャッシュと帯域幅も効率良く利用できます。構造体要素が同じ頻度でアクセスされない場合 (要素 x、y、z がほかのエントリーよりも 10 倍頻度でアクセスされる場合のように)、SoA はメモリー使用量を軽減するだけでなく、不要なデータ項目 a、b、c のフェッチも防止します。
SoA には、より多くの独立したメモリーストリーム参照が必要になるというデメリットがあります。「ソリューション」セクションの最初のサンプルコードで配列 x、y、z を使用する計算では、3 つの独立したデータストリームを必要とします。これは、プリフェッチやアドレス生成計算が追加されるだけでなく、ページアクセス効率にも大きく影響します。別の方法として、2 つの方法を組み合わせたハイブリッド SoA アプローチがあります。
NumOfGroups = NumOfVertices/SIMDwidth
typedef struct{
float x[SIMDwidth];
float y[SIMDwidth];
float z[SIMDwidth];
} VerticesCoordList;
typedef struct{
int a[SIMDwidth];
int b[SIMDwidth];
int c[SIMDwidth];
. . .
} VerticesColorList;
VerticesCoordList VerticesCoord[NumOfGroups];
VerticesColorList VerticesColor[NumOfGroups];
この方法では、2 つの独立したアドレスストリームのみが生成および参照されます。1 つには xxxx、yyyy、zzzz、zzzz、… が含まれており、もう 1 つには aaaa、bbbb、cccc、aaaa、dddd、… が含まれます。また、この方法は、変数 x、y、z が常に同時に使用されるのに対して、変数 a、b、c も一緒に使用されるが、x、y、z とは一緒に使用されないと仮定して、不要なデータのフェッチを防ぎます。このハイブリッド SoA は、次のことを確実にします。
- 垂直 SIMD 計算を効率良く行えるようにデータを並べ替えます。
- AoS よりもアドレス生成が単純で少なくなります。
- ストリーム数が少ないため、ページミスが軽減されます。
- ストリーム数が少ないため、プリフェッチの回数も減ります。
- 同時に使用されるデータ要素を効率良くキャッシュラインでパックします。
SIMD テクノロジーの登場により、データ構造の選択がより重要になります。データに対して実行する操作に基づいて、データ構造を慎重に選択すべきです。一部のアプリケーションでは、従来のデータレイアウトではパフォーマンスを最大限に引き出すことができません。アプリケーション開発者は、効率良く計算するため、さまざまなデータレイアウトとデータ・セグメンテーション・ポリシーを検討することをお勧めします。場合によっては、1 つのアプリケーションで AoS、SoA、ハイブリッド SoA を組み合わせて使用する必要があるかもしれません。
以下は、ここで紹介したトピックに関連する情報です。
参考文献
『インテル® 64 アーキテクチャーおよび IA-32 アーキテクチャー最適化リファレンス・マニュアル』 (PDF)
お問い合わせ先
サポートオプションについては、「Get Help」 (英語) ページを参照してください。
コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。
