インテル® C++ コンパイラー 18.0 デベロッパー・ガイドおよびリファレンス
このトピックは、インテル® グラフィックス・テクノロジーをターゲットとする場合にのみ適用されます。
インテル® Cilk™ Plus は古い機能 (非推奨) です。代わりに、OpenMP* またはインテル® TBB を使用してください。詳細は、「インテル® Cilk™ Plus の代わりに OpenMP* またはインテル® TBB を使用するためのアプリケーションの移行」を参照してください。
ここでは、インテル® Cilk™ Plus を使用して並列プログラムを作成する手順を説明します。
通常この作業は、C/C++ で記述された並列化の対象となる基本関数やアルゴリズムを実装したシリアルプログラムに対して行います。並列化を実装する前に、シリアルプログラムが正しく動作することを確認してください。シリアルプログラム中の問題は並列プログラムでも発生し、それらを特定して修正するのはより困難になります。
並列化による効果があるプログラム領域を特定します。独立して処理可能な実行に時間がかかるコード領域に注目するとよいでしょう。
3 つのキーワードを使用して、並列で実行可能なタスクを指定します。
_Cilk_spawn (プログラムに <cilk/cilk.h> がインクルードされている場合は cilk_spawn) は、呼び出し元 (親) と並列で実行される関数 (子) の呼び出しを示します。
_Cilk_sync (プログラムに <cilk/cilk.h> がインクルードされている場合は cilk_sync) は、スポーンされたすべての子が完了するのを待機することを示します。
_Cilk_for (プログラムに <cilk/cilk.h> がインクルードされている場合は cilk_for) は、ループのすべての反復を並列で実行できることを示します。
Windows*: icl コマンドライン・ツールを使用するか、または Microsoft* Visual Studio* からコンパイルできます。Visual Studio* を使用する場合は、プロジェクトのコンテキスト・メニューから [Use Intel C++ (インテル® C++ を使用)] を選択してください。
Linux* および macOS*: icc コマンドを使用します。
プログラムを実行します。競合状態がなければ、並列プログラムとシリアルプログラムの結果は同じになります。
競合状態がある場合は、レデューサーやロックを使用するか、コードを変更して問題を解決します。
簡単なクイックソートのプログラムを使用して、この手順を実行してみましょう。
シリアルプログラムの準備
以下に、クイックソートの簡単な実装例を並列化するための、インテル® Cilk™ Plus の記述方法を示します。
ここでは、標準 C ライブラリーの qsort 関数と区別するために、関数名を parallel_qsort としています。また、いくつかの行を削除して該当箇所のみ抜粋していますが、行番号はそのまま残しています。
9 #include <algorithm>
10
11 #include <iostream>
12 #include <iterator>
13 #include <functional>
14
15
16 // begin から end の範囲をソート
17 // "end" は範囲の最後の要素 + 1
18 // これは、インテル® Cilk™ Plus 使用前の C++ コード
19
20
21 void parallel_qsort(int * begin, int * end)
22 {
23 if (begin != end) {
24 --end; // 最後の要素を除外 (ピボット)
25 int * middle = std::partition(begin, end,
26 std::bind2nd(std::less<int>(),*end));
27
28 std::swap(*end,*middle); // ピボットを真ん中に移動
29 parallel_qsort(begin, middle);
30 parallel_qsort(++middle, ++end); // ピボットを除外
31 }
32 }
33
34 // 簡単なテストを利用
35 int qmain(int n)
36 {
37 int *a = new int[n];
38
39 for (int i = 0; i < n; ++i)
40 a[i] = i;
41
42 std::random_shuffle(a, a + n);
43 std::cout << "Sorting " << n << " integers"
<< std::endl;
44
45 parallel_qsort(a, a + n);
48
49 // a がソート済みで各要素にインデックスが
// 格納されていることを確認
50 for (int i = 0; i < n-1; ++i) {
51 if ( a[i] >= a[i+1] || a[i] != i ) {
52 std::cout << "Sort failed at location i="
<< i << " a[i] = "
53 << a[i] << " a[i+1] = " << a[i+1]
<< std::endl;
54 delete[] a;
55 return 1;
56 }
57 }
58 std::cout << "Sort succeeded."<< std::endl;
59 delete[] a;
60 return 0;
61 }
62
63 int main(int argc, char* argv[])
64 {
65 int n = 10*1000*1000;
66 if (argc > 1)
67 n = std::atoi(argv[1]);
68
69 return qmain(n);
70 }
_Cilk_spawn を使用した並列化
qsort プログラムを並列化します。
_Cilk_spawn キーワードは、関数 (子) とその後に続く _Cilk_spawn 文 (親) が並列で実行できることを示します。このキーワードは、並列化を指示しますが、必ずしも並列操作が必要なわけではありません。インテル® Cilk™ Plus は、マルチコア・プロセッサーが利用可能な場合、並列で実行する操作を動的に決定します。_Cilk_sync 文は、同じ関数内の先行するすべての _Cilk_spawn 要求が完了するまで、指示された場所以降を実行しないで待機することを指示します。_Cilk_sync は、ほかの関数内でスポーンされた並列処理には影響しません。
21 void parallel_qsort(int * begin, int * end)
22 {
23 if (begin != end) {
24 --end; // 最後の要素を除外 (ピボット)
25 int * middle = std::partition(begin, end,
26 std::bind2nd(std::less<int>(),*end));
27
28 std::swap(*end,*middle); // ピボットを真ん中に移動
29 _Cilk_spawn parallel_qsort(begin, middle);
30 parallel_qsort(++middle, ++end); // ピボットを除外
31 _Cilk_sync;
32 }
33 }
上記の例は、ヘッダーファイル <cilk/cilk.h> をインクルードすることで、より簡単な形式のキーワードを使用して書き直すことができます。以下に、簡易版の cilk_spawn と cilk_sync を使用したコードを示します。今後、このセクションではこの簡易版を使用して説明します。
19 #include <cilk/cilk.h>
21 void parallel_qsort(int * begin, int * end)
22 {
23 if (begin != end) {
24 --end; // 最後の要素を除外 (ピボット)
25 int * middle = std::partition(begin, end,
26 std::bind2nd(std::less<int>(),*end));
27
28 std::swap(*end, *middle); // ピボットを真ん中に移動
29 cilk_spawn parallel_qsort(begin, middle);
30 parallel_qsort(++middle, ++end); // ピボットを除外
31 cilk_sync;
32 }
33 }
どちらのコードでも、29 行目のスポーンで parallel_qsort を非同期に再帰呼び出ししています。そのため、29 行目が完了する前に、30 行目の parallel_qsort が再度呼び出されるかもしれません。31 行目の cilk_sync 文は、この関数内のすべての cilk_spawn 要求が完了するまでここで待機することを指示します。
各関数の最後には暗黙的な cilk_sync があり、関数内でスポーンされたすべてのタスクが戻るのを待機します。31 行目の cilk_sync は冗長的ですが、分かりやすくするためにこの位置に記述されています。
上記の変更により、再帰アルゴリズムを並列化するための一般的な分割統治アルゴリズムが実装されます。それぞれのレベルにおける再帰には、2 つの並列ストランドがあります。親ストランド (29 行目) は現在の関数の実行を継続し、子ストランドはほかの再帰呼び出しを実行します。この再帰により、並列性がかなり向上します。
実行とテスト
ここまでの手順で、インテル® Cilk™ Plus バージョンの qsort プログラムをビルドして実行できるようになりました。次の手順に従って、プログラムをビルドし実行してみましょう。
Linux* および macOS*: icc qsort.cpp -o qsort
Windows* コマンドライン: icl qsort.cpp
Windows* Visual Studio*: Release 構成でビルドします。
コマンドラインで、ビルドした qsort 実行します。例えば Windows* システムでは、次の結果が出力されます。
>qsort Sorting 10000000 integers Sort succeeded.
マルチコアシステムでのスピードアップの検証
デフォルトでは、インテル® Cilk™ Plus プログラムは、オペレーティング・システムにコア数を問い合わせ、利用可能なすべてのコアを使用します。(さらに、各コアで同時マルチスレッディングをサポートするシステムでは、インテル® Cilk™ Plus はすべての利用可能なハードウェア・スレッドを使用します。) ワーカーの数は、CILK_NWORKERS 環境変数を使用して制御することができます。
最初にシングルコアで、次にデュアルコアで qsort を実行してみます。2 つ以上のコアが搭載されたシステムでは、2 回目の実行時間が最初の約半分になることが想定されます。
Linux* および macOS*:
$CILK_NWORKERS=1 ./qsort Sorting 10000000 integers Sort succeeded. $CILK_NWORKERS=2 ./qsort Sorting 10000000 integers Sort succeeded.
Windows*:
>set CILK_NWORKERS=1 >qsort Sorting 10000000 integers Sort succeeded. >set CILK_NWORKERS=2 >qsort Sorting 10000000 integers Sort succeeded.