並列パフォーマンスを向上する最も一般的な手法 － インテル® Xeon® プロセッサーおよびインテル® Xeon Phi™ コプロセッサー向け

この記事は、インテル® デベロッパー・ゾーンに掲載されている「Common Best Known Methods for Parallel Performance, from Intel® Xeon® to Intel® Xeon Phi™ Processors」 (http://software.intel.com/en-us/articles/common-best-known-methods-for-parallel-performance-from-intel-xeon-to-intel-xeon-phi) の日本語参考訳です。

---

アプリケーションとカーネルのパフォーマンスを向上するため、常に新しい最も一般的な手法 (BKM) の調査が行われています。しかし、調査が複雑になるにつれて、ベース・パフォーマンスからどれだけ向上したかを常に考えることが重要になります。この記事では、並列パフォーマンスを向上する最も一般的な手法とその適用方法について説明します。ここで紹介するアドバイスは、インテル® Xeon Phi™ コプロセッサーまたはインテル® Xeon® プロセッサー (ホスト) で実行するコードの高速化を支援します。

BKM: アムダールの法則の制限に注意し、制限を利点として活用する

アムダールの法則は並列アプリケーションのパフォーマンスにおける基本的な制限であり、すべての並列プログラムは、「複数の計算を同時に実行できる部分とできない部分に分かれる」、という単純な見解に基づくものです。並列に実行できる部分は処理ユニットを追加することで実行にかかる時間を短縮できますが、1 つのユニットしか使用できない部分の時間は短縮できません。ユニットが独立したハードウェア・スレッドやベクトル処理ユニットのレーンの場合も同じです。プログラムの並列およびベクトル処理部分はより多くのユニットを利用することで時間を短縮できますが、シリアルおよびスカラー部分の時間は短縮できず、合計実行時間に大きく影響します。実際、アルゴリズム中のわずかなシリアルおよびスカラーコードによって、高度な並列ベクトルマシンの使用率は大きく制限されます。わずか 1% のシリアル時間でも大きな要因となることがあります。できるだけ多くの計算を並列にそしてベクトル処理を行うようにし、アムダールの法則を活用してください。次に、並列およびベクトルコードができるだけ作業を均等に分散し、できるだけ多くのベクトルレーンを使用するようにします。最後に、並列ワークはより小さな間隔に分割されると、一部の固定システム・オーバーヘッドは縮小されず増えることに注意してください。フォーク/ジョインを 1 回行うと、並列化のためスレッドのディスパッチと同期が必要になり、約 3 万サイクルのコストがかかります。つまり、グスタフソンは正しかったのです。並列部分を増やすだけでは十分ではなく、増加したスレッドやベクトル幅を完全に活用するべくワークロードのサイズも増やす必要があります。

見解: アプリケーション/カーネルが時間を費やしている部分のパフォーマンス・チューニングに集中する

アムダールの法則の別の重要な見識は、スケーリング問題です。シリアルまたはスカラーコードの改良はそれなりに効果がありますが、並列コードの改良はアクティブなスレッドやプロセスの数が多くなるほど効果が大きくなります。同様に、実行時間全体の大部分を占めるコードは最適化に最も適した候補です。hotspot 解析の重要な目的は、このような最適化の可能性を見出すことです。ハードウェア・スレッドが最も多くの時間を費やしているプログラムまたは計算カーネルの領域を特定します。これらのコード領域および関数をより高速に実行することは、実行時間全体に最も大きく影響します。インテル® アーキテクチャーは、プロセッサーの動作状況やキャッシュミスのようなコードのボトルネックを示すパフォーマンス・イベントを収集する強力な機能を提供します。しかし、それらの高イベントのコードが hotspot かどうかを考えることなくイベントが発生しているコードを修正すると、多くの時間を無駄にすることになるでしょう。シリアル実行を行うコード中の hotspot は、並列化およびベクトル化の候補でもあります。hotspot 解析とパフォーマンス・モニタリング・イベントの相関性は、インテル® VTune™ Amplifier XE が提供する重要な機能です。高い負荷のコード領域を調べて、それらの領域で可能性のあるボトルネックと不足しているリソースを特定してください。

BKM: 制限されているシステムリソースの割り当てを統合し、再利用を最大化しつつ使用を最小化することにより、それらのリソースを管理する

一般に、計算処理を完了するには、ワークを実行するスレッド、データを保持するメモリー、プロセッサーとデータをやり取りするメモリー帯域幅、ほかのノードからデータを送受信する通信帯域幅、パフォーマンスやタイムスタンプ・トランザクションを測定する時間など、さまざまなシステムリソースが必要です。これらのリソースの多くは、取得/解放に多少の負荷がかかり、制限を超えるとコストが発生します。メモリーを割り当てたり現在の時間を取得するには、システムコールを利用する必要があります。また、システムカーネルを利用することにより遅延も発生します。通信コードは同時に実行するコードと通信チャネルを共有し、本質的にシリアルカーネルの I/O ドライバーに依存します。これらのリソースを扱う上で節約は当然であり、これを支援するべくさまざまなレイヤーが提供されています。例えば、OpenMP*、インテル® スレッディング・ビルディング・ブロック (インテル® TBB)、インテル® Cilk™ Plus などのスレッディング・モデルはすべて、スレッドが必要になるたびに新しいスレッドを生成しないで済むように、スレッドプールを採用しています。インテル® TBB には、個々のスレッドにメモリープールを分配するメモリー割り当てパッケージが用意されているため、グローバルリソースをロックすることなくローカル割り当てが可能です。コーディングではこれらの節約を心がけ、オーバーヘッドを考慮して特別なシステムコールはなるべく使用しないでください。データをできるだけ再利用するため、動的なデータの使用を計画します。最初にいくつかの大きなメモリー割り当てを行うほうが、コード全体にわたって多くの小さな割り当てを行うよりも効率的です。キャッシュ・ブロッキング (後述) は、現在割り当てられているデータを再利用できる程度に小さくしておくことにより、メモリーからの余分なフェッチを回避し、メモリーのパフォーマンスを向上します。

BKM: ホスト上で特定の機能をテストして、アプリケーション/カーネルをコプロセッサーで実行するメリットがあるかどうかを判断する

インテル® Xeon Phi™ コプロセッサー上で優れたパフォーマンスを得られる可能性のあるアプリケーションには、一定の指標があります。まず、ホストでどの程度スケールするかを測定します。単一の実行スレッドのみでワークロードを実行し、利用可能なホストスレッドのすべてまたは半分、あるいは特定のスレッド数で同じワークロードを実行した場合のパフォーマンスと比較します。パフォーマンスはスケールしていますか? スレッド数が多くなると並列効率の伸びが低下する場合、ハードウェア・スレッドを追加するだけではスピードアップは見込めません。測定の際は、ワークを均等に分割してロード・インバランスが発生しないように注意してください。バランスをとり、スケーリングを適切に評価するには、ループカウントを少なくとも利用可能なスレッド数の 10 倍にしてください。

ホストの帯域幅の制限に達していますか? 同じスレッド数、同じワークロードでメモリー帯域幅を測定し、そのマシン上で最適化された McCalpin Stream* ベンチマーク (Triad) を実行して測定した帯域幅と比較します。アプリケーションがインテル® Xeon® プロセッサーの帯域幅の制限に達していない場合、インテル® Xeon Phi™ コプロセッサーが持つ高い帯域幅の恩恵は得られません。

ベクトル化できる可能性はありますか? ベクトル化は、最適化レベル -O2 コンパイラー・オプション以上ではデフォルトで有効です。ベクトル化を無効にするには、”-no-vec” と “-no-simd” コンパイラー・オプションを指定します。ベクトル化したケースとベクトル化していないケースのワークロードのパフォーマンスを比較してください。ベクトル化によりアプリケーションのパフォーマンスは向上しましたか? (プラットフォームに基づく最大のスピードアップと比較して) 大幅にスピードアップした場合、ベクトル化の利点を得ています。パフォーマンスが向上しなかった場合、「ベクトル化の基本」のヒントに従って hotspot のベクトル化の効率を向上させます。インテル® Xeon Phi™ コプロセッサーの並列機能のメリットを得るには、100 以上のスレッドを使用し、高いメモリー帯域幅を活用するか、効率良くベクトル化できなければいけません。詳細は、「インテル® MIC アーキテクチャーに適したアプリケーション解析」を参照してください。「インテル® Xeon® プロセッサーおよびインテル® Xeon Phi™ コプロセッサーに適したアプリケーション」(http://software.intel.com/node/393883 (英語)) で紹介されている資料も参考になります。

BKM: ベクトル化のスループットを最大限にするため 64 バイト境界でベクトルデータをアライメントし、効率良いベクトル化コードの生成に必要なすべてのデータ・アライメント情報をコンパイラーに知らせる

現在のインテル® アーキテクチャーのプロセッサーは 64 バイトのキャッシュラインを採用しています。インテル® Xeon Phi™ コプロセッサーのベクトルレジスターの幅も 64 バイトです。ベクトルデータの読み込みでデータがアライメントされていない場合、余分な命令と複数のキャッシュラインの読み込みが必要になります。配列を作成する際に __declspec(align(64)) (静的データ) や _mm_malloc (動的データ) のようなコンパイラー宣言子で適切にアライメントすることにより、データのロードとストアに必要なキャッシュライン・アクセスの数を最小限に抑えることができます。ただし、これだけでは十分ではありません。データのアライメントを活用するには、データがアライメントされていることをコンパイラーに知らせる必要があります。コンパイラーは、個々のメモリー参照のアライメントを必ず判断できるとは限りません (特に、配列パラメーターおよびポインターが関数に渡された場合)。データアクセスがポインターで行われる場合、ポインターがアライメントされていることをコンパイラーに知らせる必要があります。配列インデックスを使用する場合、配列とインデックスの両方がアライメントされた場所を指していなければいけません。C/C++ の場合は影響するデータ参照の前に適切な __assume_aligned および __assume 節を指定し、Fortran の場合は基本配列およびインデックスのアライメントに –align array64byte コマンドライン・オプションおよび ASSUME_ALIGNED 宣言子を使用します。詳細は、「ベクトル化の可能性を高めるデータ・アライメント」を参照してください。

BKM: コンパイラーがループを効率良くベクトル化できる可能性を最大限にするため、ベクトル演算を行う構文を使用し、高いトリップカウントおよび複数の入れ子のループを探す

多くの場合、データ配列をアクセスするループは、並列化およびベクトル化に最も適した構造です。一般的に並列化は外部ループ、ベクトル化は内部ループに適用されます。ベクトル化では連続していないメモリーから必要なデータを収集することもできますが、連続するメモリーから読み込んだほうがより優れた最適化を行えます。配列の隣接するメモリー位置を処理する最内ループでインデックスがインクリメントされる場合、メモリーからベクトルレジスターにベクトルを直接読み込めるため、さらに効率良い最適化が可能です。この場合、最内スカラーループがベクトルループになります。ベクトル要素を最大限に利用する方法については、「ベクトルのフル活用と -opt-assume-safe-padding オプションの使用」を参照してください。

ベクトル化に適したソースコードには、いくつかの要件があります。まず、後方へのループ伝搬依存性があってはいけません。例えば、反復 2 のステートメント 1 よりも前に、反復 1 のステートメント 2 を実行する必要があってはいけません。ループ内に関数呼び出しが含まれる場合、それらの関数はループ内でインライン展開できるか、コンパイラーがベクトル・コンポーネントとして直接使用できる SIMD 対応関数でなければいけません。ループの反復回数はあらかじめ定義しなければいけません。各反復で条件をチェックしないようにすると、ベクトル化が容易になります。詳細は、「ループをベクトル化するための条件」を参照してください。

見解: ループ交換は隣接するデータ間の反復を最内ループで行う強力な手法であり、ベクトル化に利用できる。実際、インテル® コンパイラーは可能性があればループ交換を試みる

次に典型的な例を示します。

     matmul3(float *c[], float *a[], float *b[], int msize) {
        int i, j, k;
        for (i=0; i<msize; ++i) {
           for (j=0; j<msize; ++j) {
              for (k=0; k<msize; ++k) {
                  c[i][j] += a[i][k] * b[k][j];
              }
           }
        }
     }

これは行列乗算の基本的なアルゴリズムです。結果を書き込む配列 c は、配列 a と b の積を受け取り、典型的な実装ではイテレーター i、j、k で演算が行われます。ここで、最内ループが k をインクリメントしていることに注意してください。これは、後続の反復で新しい a_ik および新しい b_kj が必要になることを意味します。さらに、b_kj で、後続の値は次の行に含まれます。つまり、C/C++ のような行優先言語では、次の値が別のキャッシュラインに含まれることになります。では、最内の 2 つのループのインデックスを入れ換えてみましょう。

     matmul3(float *c[], float *a[], float *b[], int msize) {
        int i, j, k;
        for (i=0; i<msize; ++i) {
           for (k=0; k<msize; ++k) {
              for (j=0; j<msize; ++j) {
                  c[i][j] += a[i][k] * b[k][j];
              }
           }
        }
     }

同じ組み合わせのループ・インデックスがすべて処理されるため、集計される項ではなく、評価の順序のみ変更されます。合計に対して何が行われるか見ておきましょう。a 項は内部ループの定数であり、最内インデックスは変更されません。b 項では、最内反復が 2 つ目の “列” インデックスで生じます。後続のインデックスは配列の隣接する値を指します。すべての値を同じキャッシュラインから得られるようになっただけでなく、値が共通ベクトルにともにロードされ、すべてのベクトルレーンに a 項の値のブロードキャストを含む項が乗算されます。ほとんどの場合、このバージョンははるかに高速に動作します。

前述したように、–O3 オプションを指定すると、インテル® コンパイラーはベクトル化の効率を高める高度なループ最適化を行います。コンパイラーの最適化レポート (-opt-report 3) を利用して、特定の入れ子のループで行われた最適化の詳細を確認してください。レポートは、手動で書き換えることで変換を行うと効果的な入れ子のループに関するヒントも示します (コンパイラーが変換を自動的に実行できなかった場合)。

BKM: キャッシュ・ブロッキング はメモリーアクセス回数を最小化し、メモリーの負荷を減らして、タイムリーなデータの再利用を高められる

インテル® Xeon Phi™ コプロセッサーは、メモリー・レイテンシーの大きい、特別なメモリーデバイスを使用して帯域幅を最大化しています。レイテンシーを隠蔽する一般的な方法は、プリフェッチを用いて、特にストリーミング形式のアルゴリズムで使われるデータ (1 度しか必要でないデータ) はリニアに処理されるようにメモリーアクセスを調整し、ハードウェア・プリフェッチおよびコンパイラーが挿入するソフトウェア・プリフェッチを活用することです (詳細は、https://software.intel.com/sites/default/files/article/326703/5.3-prefetching-on-mic-4.pdf (英語) を参照)。ただし、複数の計算で必要になるデータは再利用できる可能性があります。最適なプログラムは、メモリーからのフェッチを最小限に抑えます。キャッシュ・ブロッキングは、再利用の可能性を増やす方法です。例えば、各時間ステップの各要素で、隣接する古い値を組み合わせて新しい値を計算する 3D 配列について考えてみます。最も単純なループの範囲は配列の各次元ですが、範囲が非常に大きくなる可能性があるため、1 つの行ごと (1 次元) または 1 つの平面ごと (2 次元) に配列全体を処理する計算が考えられるでしょう。隣接する平面のデータを使用する配列演算では、次の平面を処理するとき、隣接する平面のデータがキャッシュにまだ残っていればそのデータを再利用できます。キャッシュ・ブロッキングは、次の平面の隣接する領域に移動する前に各スレッドで処理する平面のサイズを減らすことにより、再利用の可能性を高めます。このような隣接配列演算では、次の平面でフェッチされるデータが現在の平面になるときに再利用され、前の平面になるときに再び再利用されます。キャッシュ・ブロッキング手法の詳細は、「キャッシュ・ブロッキング手法」を参照してください。

BKM: 最良のパフォーマンスは、各キャッシュラインのデータの使用を最大化するように、ベクトル演算で処理する配列コンポーネントをまとめたデータ構造にすることで得られる。新しいアーキテクチャーのさらに長いベクトル長は、構造体配列 (AoS) を対応する配列構造体 (SoA) に再構成することで効率良く使用できる。

C/C++ では、構造体およびオブジェクトにデータを構成した後、そのオブジェクトをインデックス・アクセス可能な配列にして、複雑な処理を表現することがよくあります。これらの構造体は、必要なものだけを含む小さな場合もあれば、ほかの計算やテストに必要なデータを含む大きな場合もあります。この多用途データ構造体は、最も効率良くキャッシュを使用するようにデータを再構成する際にトレードオフが生じます。ここで、構造体配列を (並列にインデックスされた) 分割された構造体の複数の配列に変更して、ベクトルデータを処理するために必要なキャッシュライン読み込みの数を減らすほうが良いでしょうか? あるいはベクトルデータをフェッチするときにすべての要素を処理すると全体的な計算のメリットが得られるでしょうか?

データ構造体のすべての要素がベクトル演算に関連する場合、ほかの変更も考慮すべきです。インテル® Xeon Phi™ コプロセッサーのような新しいアーキテクチャーでは、ベクトル幅が増加しています (現在はユニットあたり 16 float)。例えば、X、Y、Z の位置データを処理するとします。各ベクトルで約 5 つのオブジェクトの値と 1 つの未使用レーンを格納できます。または、X、Y、Z をすべて組み合わせるようにデータを再構成し、最初の 16 個のオブジェクト X をあるベクトルで、次の 16 個のオブジェクトを次のベクトルで処理します。この形式のベクトル・コンポーネントを計算で使用できる場合、再構成が計算全体に役立つかどうかをテストする価値があるでしょう。データ構成についての詳細は、「メモリーレイアウト変換」を参照してください。

ここでのアドバイスは、データレイアウトを計算固有のデータ・アクセス・パターンに合わせることです。アルゴリズムがすべての X、すべての Y、すべての Z をともにベクトルで計算できる場合、データをそのように構成するのが最適です。「インテル® Xeon® プロセッサーおよびインテル® Xeon Phi™ 製品ファミリー・プロセッサー上で計算集約型ループを実行する場合の AoS (構造体配列) と SoA (配列構造体) データレイアウト比較のケーススタディー」 (英語) の例を参照してください。

オブジェクト全体を制御することによってアルゴリズム全体のメリットが得られる場合、ギャザー/スキャッターを使用する可能性を探すのが賢明です。ベクトル-ギャザー-スキャッター命令およびベクトル-ギャザー-プリフェッチ命令の両方を備えたインテル® Xeon Phi™ コプロセッサーは、これらの複雑な処理に適していますが、コンパイラーがこれらの命令を利用できることを判断できるように支援する必要があります。「ギャザーによる構造化されたデータのベクトル化」では、SoA 構造が実用的でないときに、コンパイラーがそれらの命令を利用できるように支援する方法を示しています。

BKM: 最適なベクトル化を行う。そして、–vec-report を活用する

インテル® Xeon Phi™ コプロセッサーは、ベクトル化をサポートする多くの強力なベクトル命令と広いメモリー帯域幅による優れた演算パフォーマンスを備えていますが、これらはベクトル化された場合にのみ効果があります。ある意味、これはアムダールの法則の別の見解でもあります。インテル® コンパイラーはベクトル化の可能性を認識した場合、特定のカーネルのパフォーマンスを向上するためにさまざまなことを行います。最適なベクトル化には、データのアライメントやループの独立性のような特定の条件が求められます。インテル® コンパイラーは、ループのベクトル化 (およびベクトル化されない理由) に関する多くの情報を提供します。「ベクトル化レポートと新しい vec-report6 の概要」の説明のように、–vec-report3 または新しい –vec-report6 オプションを使用してレポートを活用してください。

見解: (vec-report に注意して) pragma simd (または !DEC$ SIMD) を用いてループをベクトル化する

ベクトル化の可能性を解析するとき、コンパイラーは保守的で、速度よりも正当性を常に優先します。起源が不明なデータ (例えば、ポインターで関数に渡されたデータ) に直面したとき、コンパイラーはベクトル化を行わない傾向にあります。これは、vec-report によるレポートで確認できます。コンパイラーがベクトル化しない特定のループでも安全にベクトル化できることが明白な場合、#pragma simd を指定すると、多くの場合、最適かつ予測可能な効果が得られることが分かっています。外部ループのベクトル化に #pragma simd を使用する例は、「外部ループのベクトル化」を参照してください。

BKM: ループのサイズが重要

パイプラインや特殊なタスク構造を持つ並列処理の例もありますが、並列実行 (マルチスレッドとベクトルの両方) の主力は現在でもループです。各アーキテクチャーおよびアルゴリズムの最適なループサイズは利用可能なリソースによって決まります。キャッシュに格納されているデータを最大限に再利用するには、同じインデックス範囲を使用する隣接するループを融合します。データ移動が多いループでは、ワーキングセットのサイズがキャッシュのサイズを超えたり、利用可能なメモリー帯域幅を超えたり (インテル® メニー・インテグレーテッド・コア・アーキテクチャーではほとんど起こりませんが可能性はあります)、ストアバッファーをすべて使い切ってしまうこともあります。このような場合、マシンリソース不足によりワークが複数のループに分割されると、再計算が追加で必要になったとしても、全体的には高速になる可能性があります。パフォーマンス解析は、各ループの演算に関する多くの情報を提供します。hotspot 解析は最も重要なループを特定できます。キャッシュミスや高いメモリー帯域幅のような特定のイベントとの相関性は融合や分解の候補の識別に役立ちますが、最終的にはアルゴリズムとリソース要件によって妥当性が決定されます。基本的なガイドラインとして、ハードウェア・プリフェッチャーを効率良く使用するために 16 (要確認) を超えるアドレスストリームを回避します。また、各コアの全スレッドのワーキングサイズが L1 キャッシュに収まるようにし、全コアのワーキングサイズが L2 キャッシュに収まるようにします。コンパイラーは、-O3 最適化レベルで高度なループ変換 (ループ融合、分解、その他) を行います。コンパイラーによる入れ子ループの最適化を理解するため、–opt-report の出力結果を確認した後、手動でさらに最適化を行うことで、パフォーマンス向上につながるかどうかを確認します。コンパイラーは、最適化の動作を微調整するオプションやプラグマをサポートしています。詳細は、「インテル® Composer XE 2013 入門: コンパイラーのプラグマ/ディレクティブ」を参照してください。

この記事は、並列ベクトルプログラムを最適化する最も一般的な手法を述べた最初の記事であり、最後ではありません。皆様からのフィードバックやパフォーマンス・チューニング専門家の間で周知の事実として見なされたその他のパフォーマンス BKM に基いて、今後も更新する予定です。お見逃しなく!

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