1-5 人工的な依存関係の回避/排除による並列性の顕在化

概要

この記事は、「マルチスレッド・アプリケーションの開発のためのインテル・ガイド」の一部で、インテル^® プラットフォーム向けにマルチスレッド・アプリケーションを効率的に開発するための手法について説明します。

はじめに

マルチスレッドによる並列化はパフォーマンスを向上する上で重要ですが、スレッドを効率良く実行することも同じく重要です。コンパイラーによる最適化でこの処理の大半を行うことができます。また、データの再利用やマシンの長所を活かす命令を使用するなど、プログラマー自身がソースコードを変更することでパフォーマンスを向上させることもあるでしょう。ただ、残念なことにシリアル・アプリケーションではパフォーマンスが向上する手法でも、マルチスレッドでは意図しないデータの依存性により、パフォーマンスの向上が難しいことがあります。

処理の重複を避けるため中間結果を再利用するのがその例です。ぼかしによる画像処理を例にとってみましょう。近傍のピクセルの加重平均を取って画像ピクセルを置き換えることでぼかしを施します。次の擬似コードは 3x3 のステンシルのぼかしです。

for each pixel in (imageIn)
  sum = value of pixel
  // compute the average of 9 pixels from imageIn
  for each neighbor of (pixel)
    sum += value of neighbor
  // store the resulting value in imageOut
  pixelOut = sum / 9

それぞれのピクセル値が複数の計算に取り込まれ、データの再利用によってパフォーマンスが向上します。次の擬似コードでは、計算された中間結果が 3 回使用されて、シリアル・パフォーマンスが向上しています。

subroutine BlurLine (lineIn, lineOut)
  for each pixel j in (lineIn)
    // compute the average of 3 pixels from line
    // and store the resulting value in 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] を反復処理毎に計算せずに済みます。計算呼び出しは互いに独立していますから、ポインターには明示的な依存関係 (それぞれの反復処理の値が前の反復に依存している) があります。

最後に、アルゴリズムに並列化が導入されても、データ構造が別の目的で設計されているために意図せずに並列化を妨げるといった状況もあります。疎行列アルゴリズムがその例です。行列要素はたいていゼロなので、行列式は一般に「パックド」形式で置換されます。要素値と相対オフセットが構成され、ゼロ値の項目を省略するのに用いられます。

ここでは、これまでに説明したような状況で、効果的に並列化を導入する方法を紹介します。

アドバイス

もちろん既存の最適化を無駄にすることなく、またソースコードを大幅に変更せずに並列化によって性能を引き出すに越したことはありません。並列化の際、シリアル・アプリケーションでの最適化を止める前に、既存のカーネルを処理全体のサブセットに適用して、既存の最適化を維持できないか考えてみてください。通常は元のアルゴリズムに並列性が備わっていれば、サブセットを独立したタスクとして定義して並列に処理することが可能です。

ぼかし操作では、効率よくスレッド化するためにイメージを固定サイズのサブイメージ、またはブロックに分割することを検討します。ぼかしのアルゴリズムではデータブロックを独立して計算できるようになっています。下記は、イメージをブロック化する擬似コードです。

// One time operation:
// Decompose the image into non-overlapping blocks.
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 キーワードを使用して明示的にエイリアスを禁止できないか検討してください。また、プロシージャー間の最適化を有効にすることも役立ちます。