この記事は、Dr.Dobb’s に掲載されている「Understanding Parallel Performance」の日本語参考訳です。
著者紹介: Herb Sutter 氏 － ソフトウェア開発トピックにおいてベストセラー著者でコンサルタント。また Microsoft 社でソフトウェア・アーキテクトを務める。コンタクト先: www.gotw.ca
並列パフォーマンスの理解: どうしたら並列パフォーマンスが妥当であるか判断できるのか?編集注記:
本記事は、2012 年 6 月 11 日に公開されたものを、加筆・修正したものです。
この記事は並列プログラミングに取り組む開発者が、最初に取り組むべき課題と解決方法が明確に示されています。記事の初出は 2011 年ですが、現代でも十分に当てはまる内容です。
細粒度は諸刃の剣
ここまでさまざまな手法でコードを改良してきたが、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 であったと言えよう。
まとめ
コードのスケーラビリティーを理解するには、最初にワークロードに影響する主な処理とデータの種類を特定し、さまざまな組み合わせでワークロードのスループットを測定する。そして、結果から競合とオーバーサブスクリプションを見つけ、スレッドプール (現在) とワークスチール (将来) を活用する。
