32 ビット・インテル® アーキテクチャー上でデータ構造を調整してメモリー使用量を最適化する方法

同カテゴリーの次の記事

インテル® Optane™ DC パーシステント・メモリー導入への道: その 1 - 計画から装着まで

この記事は、インテル® デベロッパー・ゾーンに公開されている「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、x3xF、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」 (英語) ページを参照してください。

コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。

関連記事

  • インテル Parallel Universe 28 号日本語版の公開インテル Parallel Universe 28 号日本語版の公開 インテル Parallel Universe マガジンの最新号が公開されました。この号では、次の C++ 標準 (C++17) で実装される Parallel Standard Template Library (PSTL) の概要とその使用法を示すサンプルコードを紹介します。また、誕生から 20 周年を迎えた […]
  • インテル Parallel Universe 26 号日本語版の公開インテル Parallel Universe 26 号日本語版の公開 インテル Parallel Universe マガジンの最新号が公開されました。この号では、インテル® Xeon Phi™ プロセッサー向けのコードの現代化について説明します。また、インテル® Parallel Studio XE 2017 […]
  • Parallel STL: C++ STL コードのパフォーマンスの向上Parallel STL: C++ STL コードのパフォーマンスの向上 この記事は、インテルの The Parallel Universe Magazine 28 号に収録されている、新機能の Parallel STL を利用してパフォーマンスを向上する方法を紹介した章を抜粋翻訳したものです。 コンピューティング・システムは、シングルスレッドと SISD […]
  • コードの現代化を成功に導く 3 つのアドバイスコードの現代化を成功に導く 3 つのアドバイス この記事は、インテル® デベロッパー・ゾーンに公開されている「Three Pieces of Advice for Code Modernization Success」の日本語参考訳です。 プログラムを高速化するための開発者への 3 つのアドバイスについてブログの執筆依頼を受けたとき、最初に思い浮かんだのは […]
  • マルチスレッド開発ガイド: 4.6 インテル® Parallel Composer を利用して並列コードを開発するマルチスレッド開発ガイド: 4.6 インテル® Parallel Composer を利用して並列コードを開発する コードの並列化にはさまざまな手法があります。この記事では、インテル® Parallel Composer で利用可能な手法の概要を説明し、各手法の主な長所を比較します。インテル® Parallel Composer は Windows* 上の C/C++ を使用した開発のみを対象としていますが、これらの手法の多くは Fortran や […]