「さよなら Cilk Plus」移行の手順 – 明日のためのその 1

2017.09.25
インテル® DPC++/C++ コンパイラーインテル® oneTBB
C/C++Cilk PlusOpenMP並列化移植
2017 年 9 月に発表されたインテル® C++ コンパイラー バージョン 18.0 で、インテル® Cilk™ Plus のサポートが将来のインテル® C++ コンパイラーのバージョンでは打ち切られることが正式になりました (V18 ではインテル® Cilk™ Plus の構文を含むソースをコンパイルすると、コンパイラーから警告が出ます))。
 

そして、OpenMP* やインテル® スレッディング・ビルディング・ブロック (インテル® TBB) など他のテクノロジーへの移行が推奨されるようになりました。gcc のブランチにあるインテル® Cilk™ Plus のサポートがどうなるかは不明ですが、日本で唯一のインテル® Cilk™ Plus 書籍 (たぶん) の著者としては若干複雑な思いです。

本稿では、4 回に分けてインテル® Cilk™ Plus のすべての機能が既存の他のテクノロジーへ移行が可能であるか検討しています。第 2 回目では、インテル® Cilk™ Plus の 3 つの キーワードとレデューサーを使用しているケースを検討していきます。

「さよなら Cilk Plus」移行の手順 – 明日のためのその 1

  1. cilk_for キーワードとレデューサーを使用しているケース

    参考文献の Case 2 で説明されていますが、for ループを cilk_for によって並列化しているケースがこれに該当します。この場合、cilk_for を OpenMP* の #pragma omp parallel for 構文に置き換えることが推奨されていますが、cilk_for のループ中でレデューサー変数を使用している場合、その変数を OpenMP* の reduction 節で表現する必要があります。

    例えば、cilk_for ループのボディーで次のような配列データをアクセスする場合には、タスク間のアクセス競合が発生しないためレデューサーは必要ありません。

    cilk_for (int i = 0; i < N; i++)
    c[i] += a[i] * b[i];

    しかし、次にようなケースを考えてみてください。

    cilk_for (int i = 0; i < N; i++)
    sum += a[i] * b[i];

    このループを複数タスクで実行すると、グローバル変数 sum に対する書き込み競合が発生します。そのため、インテル® Cilk™ Plus ではこのような変数をレデューサーとして宣言します。このケースでは次のようになります。

    cilk::reducer<cilk::op_add<float>> sum;

    これは、float 型の変数 sum が op_add (合計値を計算) のレデューサーであることを定義します。概念的には、レデューサーとは、並列に実行している複数のストランド (並列動作を含まない一連のシリアル命令) が安全に使用できる変数です。ランタイムシステムは、各ワーカーが変数のプライベート・コピーにアクセスすることを保証し、ロックを使用せずにデータ競合の可能性を排除します。ストランドが同期するときに、それぞれの変数インスタンスは 1 つの変数にマージ (レデュース) されます。このケースでは、モノイド op_add を OpenMP* の reduction(+:sum) 節に変更することで容易に対処できます。表 1 と表 2 に インテル® Cilk™ Plus のレデューサーと OpenMP* のリダクション演算子の一覧を示します。

    表 1 – インテル® Cilk™ Plus のレデューサー・タイプ

    モノイド 単位元要素 更新操作 説明
    op_list_append 空のリスト push_back() 要素を後ろに追加してリストを作成します。
    op_list_prepend 空のリスト push_front() 要素を前に追加してリストを作成します。
    op_max (暗黙) calc_max
    cilk::max_of    		 値のセットから最大値を検索します。
    rop_max_index (暗黙) calc_max
    cilk::max_of    		 値のセットから最大値と最大値を含む要素のインデックスを検索します。
    op_min (暗黙) calc_min
    cilk::min_of    		 値のセットから最小値を検索します。
    op_min_index (暗黙) calc_min
    cilk::min_of    		 値のセットから最小値と最小値を含む要素のインデックスを検索します。
    op_add 0 +、+=、++、-、-=、– 合計を計算します。
    op_and ~0 &、&= ビット単位の AND (論理積) 演算を実行します。
    op_or 0 |、|= ビット単位の OR (論理和) 演算を実行します。
    op_xor 0 ^、^= ビット単位の XOR (排他的論理和) 演算を実行します。
    op_basic_ostream 空の文字列 << 並列で書き込み可能な出力ストリームを提供します。
    op_ostream 空の文字列 << op_basic_ostream の省略形です。
    op_wostream 空の文字列 << op_basic_ostream の省略形です。
    op_basic_string 空の文字列 +=、append 最後に追加する (append) 操作または += 操作を使用して文字列を作成します。
    op_string 空の文字列 +=、append op_basic_string の省略形です。
    op_wstring 空の文字列 +=、append op_basic_string の省略形です。
    op_vector 空のベクトル push_back() 要素を後ろに追加してベクトルを作成します。

    表 2 – OpenMP* のリダクション演算子

    リダクション演算子 初期値 説明
    + 0 加算のリダクション
    * 1 乗算のリダクション
    – 0 減算のリダクション
    & ~0 ビット積のリダクション
    | 0 ビット和のリダクション
    ^ 0 ビット排他論理和のリダクション
    && 1 論値積のリダクション
    || 0 論理和のリダクション
    max リスト項目で表現できる最小値 最大値のリダクション
    min リスト項目で表現できる最大値 最小値のリダクション

    op_add は、+、+=、++、-、-=、– の更新操作をサポートしますが、これらは reduction 節で表現できます。しかしすべてのレデューサーをリダクション演算子に置き換えることはできません。そのため通常の変数に戻した場合、更新を保護する必要があります。例えば、次のようにリスト型のレデューサー result に push_back() で文字列を追加するようなケースでは、OpenMP* に移行する場合 result.push_back((char) i ); の操作を保護する必要が生じます。atomic 構文を利用できればオーバーヘッドは少なくなりますが、push_back() 操作には使用できないため、ここでは critical 構文を使用します。

    cilk::reducer_list_append&lt;char&gt; result;
cilk_for (std::size_t i = 'A'; i &lt; 'Z'+1; ++i){
    result.push_back((char) i );
}

    また、インテル® Cilk™ Plus のレデューサーは決定論性が保証されているため、レデューサー変数の更新順序はもとのシリアルコードと同じになります。つまり、上記の例では result には ‘A’ から ‘Z’ までがアルファベット順に格納されます。しかし、OpenMP* の parallel for だけではこれが保証されないため、ループ反復の実行順序にアルゴリズムが依存している場合、ordered 句を使用して決定論性を保証する必要があります。

    #pragma omp parallal for ordered
for (std::size_t i = 'A'; i &lt; 'Z'+1; ++i){
#pragma omp ordered
#pragma omp critical
    result.push_back((char) i );
}

    これ以外にも、浮動小数点データを計算するループを OpenMP* による for ワークシェア構文に変更した場合、計算の順番が変わることで計算精度に差が生じることも考えまれます。

  2. cilk_spawn と cilk_sync によるタスク並列を使用する場合

    インテル® Cilk™ Plus が登場した 2010 年当時、OpenMP* の 3.1 仕様が翌年の 8 月に公開され、task 構文に mergeable 節、final 節、および taskyield 句が追加されたばかりでした。taskloop 句、taskgroup 句、depend 節が追加されるのは OpenMP* 4.0/4.5 以降になります。関数呼び出しそのものをタスクとして、スポーンできる cilk_spawn の機能は画期的であったと言えます。cilk_spawn と cilk_sync を使用する例として良く紹介されるのがクイックソートやフィボナッチ数列を求める再帰関数呼び出しのコードです。参考文献でも説明されているフィボナッチ数列を求める関数ですが、インテル® Cilk™ Plus を使用したタスク並列の実装はいたってシンプルです。

    int fibonacci(int num) {
int a, b;
    if (num == 0)
        return 0;
    if (num == 1)
        return 1;
    a = cilk_spawn fibonacci(num - 1);
    b = fibonacci(num - 2);
    cilk_sync;
    return(a+b);
}

    親タスクが、cilk_spawn に到達すると子タスクとして関数 fibonacci(num – 1) をスポーンします。親タスクは cilk_spawn の完了を待たず処理を継続実行します。親は fibonacci(num – 2) を実行して cilk_sync の位置で、自身がスポーンした子タスクの完了を待機します。参考文献では次のように OpenMP* の #pragma omp task (cilk_spawn に相当) と #pragma taskwait (cilk_sync に相当) 句を使用する例が示されています。

    int fibonacci(int num) {
int a, b;
    if (num == 0)
        return 0;
    if (num == 1)
        return 1;
    #pragma omp task shared(a)
    a = fibonacci(num - 1);
    #pragma omp task shared(b)
    b = fibonacci(num - 2);
    #pragma omp taskwait
    return(a+b);
}

    ここでは 2 つほど注意点があります。1 つは変数 a と b の扱いです。OpenMP* ではこの変数を shared 属性によってスレッド間で変数を共有することを明示しなければいけません。

    もう 1 つは、ここでは 2 つの task 構文で関数をそれぞれタスクとして起動していますが、これが実際に実行環境で最適であるかどうか確かめる必要があるでしょう。この例のように演算がほとんどない処理では、task の制御がかなりのオーバーヘッドとなる可能性があります。例えば、4 コアのデスクトップやラップトップ環境では、2 つ目の #pragma omp task shared(b) を記述しないほうが 2 倍高速に実行できます (実はシングルスレッドでも十分高速です …)。

    このサンプルは分かりやすく示すため、肝心の部分が記述されていません。それは最初に fibonacci 関数を呼び出す上位ルーチンです。OpenMP* の task 構文は parallel 並列領域内で、single 構文から実行される必要があります。つまり、上位のルーチンが、

    main(){
    fibonacci(NUM);
}

    のような構造であると、fibonacci 関数内の cilk_spawn と cilk_sync を OpenMP* 構文に書き換えただけでは、コンパイルはエラーとはなりませんが、task を生成する無駄な処理を含むシングルスレッドのバイナリーが生成されてしまいます。以下のように記述する必要があります。

    main(){
    #pragma omp parallel
    #pragma omp single
        fibonacci(NUM);
}
  3. cilk_spawn した、関数内で cilk_for によってループのタスクが生成されている場合

    最初に示した cilk_for 文を含む関数が cilk_spawn でスポーンされているようなケースはどのように対応したらよいでしょう?

    spawn_func( float *a, float *b, float *c, int N){
    cilk_for (int i = 0; i &lt; N; i++)
        c[i] += a[i] * b[i];
}

    cilk_for を単純に #pragma omp parallel for や #pragma omp for に置き換えるだけではうまくスレッドを生成できない可能性があります。ここでは、タスクとスレッドの関係を詳しく説明しませんが、タスク = スレッドではないということです。ここで最も適切な方法は、OpenMP* 4.5 で追加された #pragma omp taskloop を使用することでしょう。上位ルーチンの task と taskloop で生成されるタスクはランタイムでうまく処理されます。taskloop は、for ループをスレッドに分割するワークシェアと異なり、for ループを task に分割して処理します。

    インテル® Cilk™ Plus の 3 つのキーワードを OpenMP* に移行する方法を紹介しましたが、いかがでしょう。皆さんの実装に役立ちそうですか。次回は配列表記 (Array Section) とヘルパー関数を使用するケースについて説明します。

その他の記事

第 1 回「Cilk がやってきた」から「さよなら Cilk Plus」
第 2 回「さよなら Cilk Plus」インテル® Cilk™ Plus の 3 つのキーワードを使用するケース
第 3 回「さよなら Cilk Plus」インテル® Cilk™ Plus の配列表記 (Array Section) とヘルパー関数を使用するケース
第 4 回「さよなら Cilk Plus」インテル® Cilk™ Plus の #pragma simd と要素関数 (SIMD 対応関数) を使用するケース

参考文献

  • https://software.intel.com/en-us/articles/migrate-your-application-to-use-openmp-or-intelr-tbb-instead-of-intelr-cilktm-plus (英語)

上記の記事の翻訳版を以下に用意しましたので参照ください。

タイトルとURLをコピーしました