インテル® System Studio – インテル® Cilk™ Plus による信号処理向けマルチコア・プログラミング

この記事は、インテル® デベロッパー・ゾーンに掲載されている「Intel® System Studio – Multicore Programming with Intel® Cilk™ Plus」の日本語参考訳です。

はじめに

インテル® System Studio は、次のコンポーネントを通してさまざまな信号処理プリミティブを提供します。

• インテル® インテグレーテッド・パフォーマンス・プリミティブ (インテル® IPP)
• インテル® マス・カーネル・ライブラリー (インテル® MKL)

また、次のコンポーネントにより、ハイパフォーマンスで低レイテンシーなカスタムコードの開発を行えます。

• インテル® C++ コンパイラーとインテル® Cilk™ Plus

インテル® Cilk™ Plus はコンパイラーに組込まれた言語拡張機能です。そのため、効率良いスレッドランタイムが求められる場所で使用し、わずかな並列性であっても引き出すことができます。例えば、ライブラリー (インテル® IPP など) を使って信号処理を行う場合、ライブラリー内部がマルチスレッド化されていなくても、マルチコアの利点を得られます。この記事は、個々の主要アルゴリズムを並列化しなくても、マルチコアの並列処理を効率良く実装する方法を説明します。これには、パイプラインと呼ばれる並列パターンを使用します。

はじめに

インテル® Cilk™ Plus を利用することで、任意の数のタスクを決まった数のワーカー (スレッドプール) へ動的に割り当てるランタイム・スケジューラーにより、C/C++ でフォワード・スケーリングな (将来のスレッド増加に対応した) タスク並列性を実現できます。一連の呼び出し (入れ子の並列処理) を監視しなくても、リソースのオーバーサブスクリプションを引き起こすことなくマルチコアの並列処理を実装できる、構成可能な設計を行えます。インテル® Cilk™ Plus は、スケジュールされたタスク数に基づく未使用リソースではなく、プール内のワーカー数から潜在的な並列性を引き出します。インテル® Cilk™ Plus はインテル® C++ コンパイラーの一部であり、コードで使用する際に特別な準備は必要ありません。

組込みアプリケーションにおけるマルチコアの主な使用法は 2 つあります。

1. 実行時間が長かったり、永続的な単一のタスク (バックグラウンド・タスクを含む)。一般に、イベント処理 (例えば、ユーザー操作をキューに追加するなど) を実装します。
2. 同じデータを操作する複数のタスク。この種のデータ並列処理には優れた並列構造を含めることができますが、同期構造 (ロック) が必要になる場合があります。

1 つ目の使用法では、タスクと OS スレッドが 1 対 1 になるため、インテル® Cilk™ Plus は必要ありません。OS 固有のスレッド・インターフェイス (POSIX* スレッド/Pthreads* など) を利用できます。ただし、C++ ライブラリーは、OS スレッドと同期プリミティブを可搬性が高い方法で利用できる簡単なインターフェイスを提供しています。特に C++11 では、追加のライブラリーは必要ありません。インテル® スレッディング・ビルディング・ブロック (インテル® TBB) も、std::thread (TBB_IMPLEMENT_CPP0X。C++11 では利用不可) を含む豊富なプリミティブを提供しています。

ケーススタディーとサンプル

2 つ目の使用法では、スレッドランタイムは多数のタスクを決まった数のワーカースレッドに割り当てます。ここでは、個々の主要アルゴリズムを並列化せずに、マルチコアの並列処理を実装する方法を検討してみます。これは現実的な使用例と言えるでしょう。例えば、内部処理がマルチスレッド化されていない信号処理ライブラリーを使用する場合や、データセットが小さかったり、レイテンシーによってアプリケーションが制限されていたり、アプリケーション・レベルのスレッド化のほうが上手く制御できるといった理由により、マルチスレッド化されているライブラリーを使用すべきではない場合などです。

--------     -----------     ---------
| Read | --> | Process | --> | Print |
-------1     2---------3     4--------

サンプルの信号処理パイプラインは 3 つのステージで構成されています。
(1) 専用バッファー #1 へ信号値を読み込み/解析するステージ
(2) バッファー #2 と #3 で実際に信号のアウトオブプレース処理を行うステージ
(3) 専用バッファー #4 から読み込んで出力する最終ステージ

struct { size_t i, n; } stage[] = { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 } };
for (size_t i = 0; i <= nsteps && (0 < stage[1].n || 0 == i); ++i) {
   read_signal   (size,       x + stage[0].i, y + stage[0].i, stage[0].n);
   process_signal(stage[1].n, x + stage[1].i, y + stage[1].i,
                              x + stage[2].i, y + stage[2].i);
   print_signal  (stage[3].n, x + stage[3].i, y + stage[3].i, std::cout);

   stage[2].n = stage[1].n;  
   std::rotate(stage, stage + 4 - 1, stage + 4); // クワッドバッファリング
}  

このパイプラインは、間接的に 4 つのバッファーのうち 1 つを各ステージに割り当てます。このクワッド・バッファリング・アプローチは、実際には 2 つのクアッドバッファー x と y を使って複数のコンポーネントで構成される信号を処理します。ループの各反復で、ステージのデスティネーション・バッファーはリングバッファー (ステージ) 内で 1 ポジション分回転され、次のステージの入力になります。

インテル® Cilk™ Plus

for (size_t i = 0; i <= nsteps && (0 < stage[1].n || 0 == i); ++i) {
cilk_spawn read_signal   (size,       x + stage[0].i, y + stage[0].i, stage[0].n);
cilk_spawn process_signal(stage[1].n, x + stage[1].i, y + stage[1].i,
                                         x + stage[2].i, y + stage[2].i);
              print_signal  (stage[3].n, x + stage[3].i, y + stage[3].i, std::cout);
cilk_sync;

   stage[2].n = stage[1].n;  
   std::rotate(stage, stage + 4 - 1, stage + 4); // クワッドバッファリング
}  

前節のコードと比べると、cilk_spawn と cilk_sync が追加されていることが分かります。インテル® Cilk™ Plus (キーワード、レデューサーなど) を使用するプログラムのシリアルバージョンを生成するには、"-cilk-serialize" オプションを指定してコンパイルします (cilk_spawn、cilk_sync、および cilk_for のみ使用している場合は、プリプロセッサーでこれらのキーワードを無効にすることができます)。上記のマルチバッファリング・アプローチは、read_signal、process_signal、print_signal を任意の順序で呼び出すことができます。これは、インテル® Cilk™ Plus の継続渡しスタイルでは重要になります。

cilk_spawn が非同期に呼び出しを開始すると考えると、cilk_sync で同期される前に同時に実行している処理が分かります。ただし、最初の cilk_spawn を開始するワーカースレッドは、スポーンされる関数 (つまり、サンプルコードの read_signal) も実行します。これは、ライブラリー・ベースのスレッドランタイムの動作とは異なります。継続処理は、最終的に (read_signal の後、つまり次のスポーンで) 別のワーカーによってスチールされます。また、(cilk_sync を省略できる) 暗黙の同期ポイントがいくつかあります。そのほとんどは明白で、例外発生時の言語拡張の定義を完全なものにします。

for (size_t i = 0; i < N; ++i) {
    cilk_spawn  little_fuwork(i);
}

/*A*/

cilk_for (size_t i = 0; i < N; ++i) {
    little_work(i);
 }

/*B*/

for (size_t i = 0; i < N; i += G) {
cilk_spawn work(i, std::min(G, N - i));
 }

/*C*/

void work(size_t I, size_t N) {
     for (size_t i = I; i < N; ++i) little_work(i);
 }

/*D*/

(上記の) ケース A では、i の各インダクションにわずかなワークしかありません。ケース B では cilk_spawn を考慮し、さらにバイナリーツリーに似た起動スキームを使用するためキーワード cilk_for を追加しています。インテル® Cilk™ Plus では、ランタイム式 (#pragma cilk grainsize=) で cilk_for の粒度を調整できます。ケース C の粒度 G は、ケース D よりも多くのワークを蓄積することができます。ケース B とケース C の起動スキームは等価ではありません。バイナリーツリーに従ってループ範囲を分割することで、すべての起動オーバーヘッドが 1 つのコアに集中しないようにしています。

インテル® Cilk™ Plus の継続渡しスタイルには 2 つの注目すべき影響があります。
(1) スレッドはローカルまたは "キャッシュ上のホットな" データを利用して継続します。
(2) 1 つのスコープ (C/C++ スコープ) の命令が同じスレッドで実行されない可能性があります。

(1) は、シーケンシャル・プログラムをチューニングすることで、より簡単にチューニングされた並列プログラムとすることができます。(2) の場合、スコープによって存続期間が決まるスレッド・ローカル・ストレージ (TLS) は、インテル® Cilk™ Plus では使用できません。インテル® Cilk™ Plus は、通常の OS スレッドを使ってワークを実行します。ただし、タスクは概念的にファイバーに似た軽量なユーザー空間オブジェクトであり、この点はインテル® TBB などのほかのスレッド・ライブラリーとあまり変わりません。

動的スケジュールは必要に応じてワーカーを使用し、粒度は cilk_for ループで利用可能な並列処理の量によって異なります。当然、cilk_spawn でスポーンされる関数の数は並列処理の量 (並列に実行可能なパイプライン・ステージの数など) に直接関係しています。つまり、(以下のコード例のように) 異なる並列セクションに対してワーカー数を設定して並列処理を調整するのは正しい方法ではありません。

void main(int argc, char* argv[])
{
const char *const threads = 1 < argc ? argv[1] : 0;
const int nthreads = 0 != threads ? std::atoi(threads) : -1;

if (0 <= nthreads) __cilkrts_set_param("nworkers", threads);
}  

このコード例は次の 3 つのケースを示しています。
(1) 渡されるすべての引数でワーカー数が設定されておらず、最終的にこのステップが後に延期される場合
(2) コマンドラインから引数が全く渡されず、API が自動的にシステムとプロセスのアフィニティー・マスクに応じて利用可能なすべてのワーカーで初期化する場合
(3) 明示的にワーカー数が渡される場合。API は環境変数 CILK_NWORKERS よりも優先されます。この環境変数は便宜上、提供されています。明示的なワーカー数は、必ずしも利用可能なハードウェア・スレッド数に合わせる必要はありません。

粒度を上げることで、cilk_for ループで利用されるワーカー数を減らすことができます。デフォルトでは (プラグマが使用されない場合)、反復空間のサイズと合計ワーカー数に応じて、並列性を最大限に引き出そうとします (上記のコードを参照)。粒度を一定にすることで、この 2 つの依存性を排除できます。ただし、処理順序は不定のため、特に浮動小数点データを扱い、計算の順序が最終結果に影響する場合、結果は非決定的になります。実際には、1 つまたは複数のシステムにおいて、ビット単位で同じ結果を再現できない理由は多数あります。

まとめ

パイプライン・パターンから引き出すことができる並列性は限定的で、実行時間の最も長いステージが常にボトルネックになります。ここでは、並列に実行可能な 3 つのステージ (そのうち 2 つは I/O) のみで構成されるパイプラインを紹介しました。I/O で内部状態を保護するためにロックを利用する場合、(スケーラビリティーの観点から) 2 つの I/O ステージが問題となる可能性があります。

サンプルでは、連続する fork-join (パイプラインのすべてのサイクル) で効率良いスレッドランタイムが要求されます。並列パイプライン内のバッファーサイズを大きくしてオーバーヘッドを軽減することができますが、当然のことながら、アプリケーションのレイテンシーを増加させるのは実行時間の長い並列領域です。

プロセッサー・コア向けの最適化を含むソフトウェアの最適化により消費電力を抑え、キャッシュブロックによって不要なメモリーロードを回避することができます。マルチコアでは、キャッシュを意識しないアルゴリズムにより、この考え方をさらに応用できます。ただし、マルチコアの並列処理だけでも、次のように消費電力を抑えられます。

• マイクロプロセッサーのダイサイズが 4 倍なので、1 コアの場合 2 倍のパフォーマンスを達成
• ただし、同じダイサイズで 4 コアの場合は 4 倍のパフォーマンスを達成

パフォーマンスはクロック周波数に対して線形にスケールする可能性がありますが、消費電力はクロック周波数の約 2 乗でスケールするという事実とともに、ポラックの法則を考慮すべきです。アムダールの法則は、システムの実用的な利用を制限し、並列処理を実装できる場合のパフォーマンスのみを提供します。マルチコアを活用する信号処理アプリケーションを作成することは、信号処理自体の高速化に加えて、省電力の可能性、あるいはシステムにさまざまなタスクをロードすることによる専用ハードウェアの統合という観点から非常に魅力的です。

ケーススタディー

以下のケーススタディー (英語) をお読みになり、サンプルコードを実行することで、より理解が深まるでしょう。

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