この記事は、インテル® ソフトウェア・ネットワークに掲載されている「Expose Parallelism by Avoiding or Removing Artificial Dependencies」(https://software.intel.com/content/www/us/en/develop/articles/expose-parallelism-by-avoiding-or-removing-artificial-dependencies.html) の日本語参考訳です。
編集注記:
本記事は、2011 年 5 月 4 日に公開されたものを、加筆・修正したものです。
スレッド間でアプリケーションのワークロードをロードバランスすることは、パフォーマンスにとって非常に重要です。ロードバランスの主な目的は、スレッドのアイドル時間を最小限に抑えることです。最小限のワークシェアのオーバーヘッドですべてのスレッド間でワークロードを均等に分割すると、スレッドがアイドル状態のサイクルが少なくなり、パフォーマンスの向上につながります。しかし、完全なロードバランスを達成することは困難であり、アプリケーション内の並列性、ワークロード、スレッド数、ロード・バランス・ポリシー、およびスレッド実装に依存します。
この記事は、「マルチスレッド・アプリケーションの開発のためのガイド」の一部で、インテル® プラットフォーム向けにマルチスレッド・アプリケーションを効率的に開発するための手法について説明します。
はじめに
マルチスレッドによる並列化はパフォーマンスを向上する上で重要ですが、スレッドを効率良く実行することも同じく重要です。コンパイラーによる最適化でこの大半を行うことができます。また、データの再利用やマシンの長所を活かす命令を使用するなど、プログラマー自身がソースコードを変更することでパフォーマンスを向上できることもあるでしょう。
ただ、残念なことにシリアル・アプリケーションではパフォーマンスが向上する手法でも、マルチスレッドでは意図しないデータの依存関係により、パフォーマンスの向上が難しいことがあります。
処理の重複を避けるため中間結果を再利用するのがその例です。ぼかしによる画像処理を例にとってみましょう。隣接するピクセルの加重平均を取って画像ピクセルを置き換えることでぼかしを表現します。次の擬似コードは 3×3 のステンシルのぼかしです。
for each pixel in (imageIn)
sum = value of pixel
// imageIn から 9 ピクセルの平均を計算
for each neighbor of (pixel)
sum += value of neighbor
// imageOut の結果を保存
pixelOut = sum / 9
それぞれのピクセル値が複数の計算で使用されると、データの再利用によってパフォーマンスが向上します。次の擬似コードでは、計算された中間結果が 3 回使用されて、シリアル・パフォーマンスが向上しています。
subroutine BlurLine (lineIn, lineOut)
for each pixel j in (lineIn)
// lineIn から 3 ピクセルの平均を計算して
// lineout の結果を保存
pixelOut = (pixel j-1 + pixel j + pixel j+1) / 3
declare lineCache[3]
lineCache[0] = 0
BlurLine (line 1 of imageIn, lineCache[1])
for each line i in (imageIn)
BlurLine (line i+1 of imageIn, lineCache[i mod 3])
lineSums = lineCache[0] + lineCache[1] + lineCache[2]
lineOut = lineSums / 3
しかし、この最適化では、出力イメージの近接線の計算に依存関係があります。このループの反復を並列に行うと、この依存関係によって誤った結果が生成されます。
もう 1つ、一般的な例を挙げましょう。ループ内のポインターオフセットです。
ptr = &someArray[0]
for (i = 0; i < N; i++)
{
Compute (ptr);
ptr++;
}
ptr のインクリメントにより、レジスター割り当てによる高速インクリメントが行われ、someArray[i] を反復ごとに計算せずに済みます。Compute の呼び出しは互いに独立しているため、ポインターには明示的な依存関係 (それぞれの反復処理の値が前の反復に依存している) があります。
最後に、アルゴリズムに並列処理が導入されても、データ構造が別の目的で設計されているために意図せずに並列化を妨げるといった状況もあります。疎行列アルゴリズムがその例です。行列要素はたいていゼロなので、行列式は一般に「パックド」形式で置換されます。要素値と相対オフセットが構成され、ゼロ値の項目を省略するのに用いられます。
ここでは、これまでに説明したような状況で、効果的に並列処理を導入する方法を紹介します。
アドバイス
もちろん既存の最適処理を無駄にすることなく、またソースコードを大幅に変更せずに並列化によって性能を引き出すに越したことはありません。並列化の際、シリアル・アプリケーションの最適化をあきらめる前に、既存のカーネルを処理全体のサブセットに適用して、既存の最適処理を維持できないか考えてみてください。通常は元のアルゴリズムに並列性が備わっていれば、サブセットを独立したタスクとして定義して並列に処理することができます。
ぼかし操作では、効率よくスレッド化するためにイメージを固定サイズのサブイメージ、またはブロックに分割することを検討します。ぼかしのアルゴリズムではデータブロックを独立して計算できるようになっています。下記は、イメージをブロック化する擬似コードです。
// 一度の操作:
// イメージを重複しないブロックに分解
blockList = Decompose (image, xRes, yRes)
foreach (block in blockList)
{
BlurBlock (block, imageIn, imageOut)
}
BlurBlock の実装によってイメージ全体をぼかす既存のコードを再利用できます。OpenMP や明示的なスレッドを使用して、複数のブロックを並列に処理すると、マルチスレッドによる利点が得られると同時に元の最適化されたカーネルも維持されます。
既存のシリアルコードでの最適化が反復全体のコストと比べると小さく、ブロック化が不要なこともあり、その多くは反復処理が適切な粒度で並列化による速度向上が期待できる場合です。ポインターのインクリメントがその例です。明示的なインデックス処理でインダクション変数を簡単に置換できるため、依存関係を取り除き、またループの単純な並列化が可能になります。
ptr = &someArray[0]
for (i = 0; i < N; i++)
{
Compute (ptr[i]);
}
小さいとはいえ、元の最適化が必ずしも損なわれていないことに注意してください。コンパイラーではインクリメントやその他の高速処理を用いてインデックス計算の最適化を積極的に行い、シリアル・パフォーマンスと並列パフォーマンスの双方から利点を得られるようにします。
パックド疎行列などのコードでは、スレッド化はさらに難しくなります。通常、データ構造をアンパックするのは実用的ではありませんが、行列をブロックに分けてポインターを各ブロックの先頭に置くことは可能です。このような行列と適切なブロックベースのアルゴリズムを組み合わせると、パックド表現と並列化からの利点を同時に実現できます。
上記のブロック化手法は、一般的な手法である「領域分割法 (Domain Decomposition)」の事例です。分割後は、スレッドは 1 つの領域、あるいは複数の領域で独立して動作します。領域ごとの処理を決定するアルゴリズムの性質とデータがほぼ一定なこともあれば、処理量が領域ごとに異なることもあります。異なる場合、領域とスレッドの数が同じだとロード・インバランスによって並列パフォーマンスが制限されることがあります。一般に領域数はスレッド数よりもかなり多くします。これによって、スレッドにかかる負荷のバランスを保つための動的スケジュール手法などを使用できるようになります。
利用ガイド
シリアル処理の最適化によって大きなパフォーマンス・ゲインが得られることがあります。対象となるプロセッサー数を考慮し、並列化から得られる速度向上が、最適化されなかったことによって失われたパフォーマンスを上回るようにします。
ブロック化アルゴリズムが導入されることで、エイリアスされていないデータとエイリアスされているデータを区別するコンパイラーの判断が阻害されることがあります。もし、ブロック化した後にコンパイラーがエイリアスされていないデータを特定できなくなると、パフォーマンスは損なわれます。restrict キーワードを使用して明示的にエイリアスを禁止できないか検討してください。また、プロシージャー間の最適化を有効にすることも役立ちます。
関連情報
- OpenMP* 仕様 (英語)
