並列パフォーマンスの理解 パート 3

この記事は、Dr.Dobb’s に掲載されている「Understanding Parallel Performance」の日本語参考訳です。

著者紹介: Herb Sutter 氏 － ソフトウェア開発トピックにおいてベストセラー著者でコンサルタント。また Microsoft 社でソフトウェア・アーキテクトを務める。コンタクト先: www.gotw.ca

並列パフォーマンスの理解: どうしたら十分な並列パフォーマンスかどうか判断できるのか?

パート1 パート2 パート3

細粒度は諸刃の剣

ここまでさまざまな手法でコードを改良してきたが、Example 4 の並列コードでも 3 コアまでしかスケーリングしない。もっと向上できないだろうか? 処理の粒度をより細かくする (つまり、より小さなチャンクに処理を分割する) ことで、さらなるスケーリングが可能だ。

1 つの方法として、Example 4 の CalcWholesale、CalcRetail、および TotalReturns 内で各タスクを並行に処理されるサブタスクに分解することができる。最良の方法は、アルゴリズム (例えば、クイックソートの分割統治アルゴリズムなど) とデータ構造 (ツリーやグラフなど) にすでに備わっている並列性を活用して、与えられたデータ量でスケーリングするように処理を細かく分割することだ。

しかし、ここでスケーラビリティーとオーバーヘッドとの間に葛藤が生じる。タスクのサイズが小さくなるとその数が増えるため、より多くのコアにタスクを分配し解を速く得られるようになるが、タスクあたりのオーバーヘッドも増え、パフォーマンス・コストにも影響を及ぼすことになる。

一般的なクイックソートについて考えてみよう。このコードのパフォーマンス問題はどこだろうか?

// Example 5 (flawed, today): Naïve parallel quicksort,
// sorts left and right subranges in parallel
//
void ParallelQuicksort( Iterator first, Iterator last ) {
  Iterator pivot = Partition( first, last );
  future f1 = pool.run( [&]{ ParallelQuicksort( first, pivot ); } );
  future f2 = pool.run( [&]{ ParallelQuicksort( pivot, last ); } );
  wait_all( f1, f2 );
}

このコードを改善する方法は 2 つある。1 つ目は、前にも紹介したが、最後のタスクをスレッドプールに渡さずに実行することで、それに伴うオーバーヘッドを軽減する方法だ。

次に、分配される処理のほとんどは 1 個または数個の要素の部分的な範囲を含む計算であることが分かる。シーケンシャル・コードでも、部分的な範囲のサイズがしきい値以下の場合はバブルソートなどに切り替えるのが一般的だが、並列コードでも同じことがいえる。範囲が小さい場合はシーケンシャル・ソートに切り替えるべきである。これが 2 つ目の方法だ。Example 6 ではこの 2 つの方法を取り入れている。

// Example 6: An improved parallel quicksort, still
// sorts subranges in parallel but more efficiently
//
void ParallelQuicksort( Iterator first, Iterator last ) {
  if( distance(first,last) <= threshold ) {
    SequentialSort( first, last );
  } else {
    Iterator pivot = Partition( first, last );
    future f1 = pool.run( [&]{ ParallelQuicksort( first, pivot ); } );
    ParallelQuicksort( pivot, last );
    f1.wait();
  }
 }

一般に、処理はできるだけ細かく分割することが望ましいが、処理量がオーバーヘッドと同程度になるまで細かくするべきではない。

今後の展望: ワークスチール

将来のランタイムシステムでは、タスクあたりのオーバーヘッドや並行性が活用されない場合のコストなど、あらゆるコストが大幅に低下し、多くの場合は無視できるようになると考えられる。そして、ほとんどの場合、パフォーマンスを心配することなく、Example 5 のようなコードを記述できるようになるだろう。

これは、ワークスチールの使用により実現可能だ。デフォルトでは、”潜在的に非同期な処理” はほかのスレッドに分配されることなく、オリジナルのスレッドで実行されるようにキューに追加される。そして、ほかのコアに処理がなく、キューに待機中の処理がある場合のみ、利用可能なコアにその処理が “スチール” され、効率的に分配される。

この概念では、特定の状況下において (マシンがほかの処理で占められている場合など) 別のコアで実行したほうが良い場合のみ、別のコアで実行するためのオーバーヘッドが発生するので、並行性が活用されない場合のコストを軽減できる。つまり、次回同じハードウェアで同じ関数を実行しても、すべてのコアがすでに利用されている場合、スチールは発生しない。

ランタイムでワークスチールを実現するための現代および次世代のテクノロジーは、インテル® スレッディング・ビルディング・ブロック、Microsoft* の並列パターンライブラリ (PPL)、タスク並列ライブラリ (TPL)、および PLINQ、Java* 7 の Fork/Join フレームワークなどさまざまだが、その中でも極めつけは開発者の間で普及しつつある Cilk だ。

まとめ

コードのスケーラビリティーを理解するには、最初にワークロードに影響を与える主な処理とデータの種類を特定し、さまざまな組み合わせでワークロードのスループットを測定する。そして、結果から競合とオーバーサブスクリプションを見つけ、スレッドプール (現在) とワークスチール (将来) を活用する。

パート1 パート2 パート3