インテル® Cilk™ Plus 向け DPRNG とは?

この記事は、インテル® デベロッパー・ゾーンに掲載されている「A DPRNG for Cilk™ Plus?」の日本語参考訳です。

---

2013 年 3 月公開の記事では、インテル® Cilk™ Plus 向けの決定論的な並列乱数ジェネレーター (DPRNG) である DotMix を紹介しました。(DotMix のコードは、「Contributed Code」ページからダウンロードできます。) DotMix は、次の 2 つの点において rand() のような従来のシリアル乱数ジェネレーター (RNG) よりも優れています。

1. DotMix は、従来のシリアル RNG のいくつかのスケーラビリティー・ボトルネックを回避します。
2. DotMix は、同じシードとプログラムの入力値を使用する場合、ほとんどのインテル® Cilk™ Plus プログラムにおいて、決定論性のある乱数を生成します。

この記事ではこれらの利点についてさらに詳しく述べ、インテル® Cilk™ Plus 向けの決定論性のある乱数生成の問題が、想定されるよりも複雑である理由を説明します。

DotMix について

DotMix は、Charles E. Leiserson 氏からのアドバイスを取り入れ、Tao B. Schardl と筆者が開発したコードです。DotMix は、最近 MIT で行われたある研究から生まれました。Cilk の歴史をご存知ない方のために説明しますが、インテル® Cilk™ Plus は、90 年代半ばに MIT で開発された Cilk プロジェクトに由来しています。これまで、長年にわたり MIT、特に Charles E. Leiserson 教授らが率いる SuperTech 研究グループによって Cilk 関連の研究開発が行われてきました。Cilk Plus コミュニティーに関連する多数の研究プロジェクトは、MIT やその他の場所で常時進行しています。筆者は、DotMix プロジェクトに参加していたため、DotMix について最も詳しく説明できるでしょう。

本題に入る前に、筆者の経歴について少し触れたいと思います。私の本職は、インテル® Cilk™ Plus ランタイムの開発者です。つまり、インテルの社員として、インテル® Cilk™ Plus が正しく動作することを確認し、不具合があった場合には修正に携わる仕事をしています。インテルに入社する前は、MIT の学生でした。SuperTech グループの一員として、Cilk テクノロジーをよく利用していました。そのため、Cilk コードを記述し、Cilk を改良する新しい方法を試すことは私の長年の趣味の 1 つと言えます。この記事では、インテル® Cilk™ Plus ランタイム開発者としてではなく、1 人の Cilk 研究者および寄稿者として DotMix についてお話したいと思います。

私の知る限り、DotMix のきっかけとなった研究は、私が MIT の学生だった 2010 年頃に開始されました。同様のプロジェクトに携わった経験のある方ならお分かりでしょうが、どのような種類の研究であっても、その基となった特定のアイデアやテーマを特定の人やイベントに帰属させることは困難です。さらに、ソリューションを導き出すまでの道のりは、必然的に後でこうすべきであったと考えるよりも複雑に入り組んでいます。DotMix について説明するため、ここでは、我々 (MIT の共同著者と私) がとったソリューションへの道のりについて簡単に述べます。また、我々の大好きな Cilk プログラムである fib のバリエーションから調査が開始したことにします (実際に、これは真実とかけ離れていないでしょう)。

まず、次のインテル® Cilk™ Plus プログラム (とその概念) から見てみましょう。

#include <cstdio>
#include <cstdlib>
#include <cilk/cilk.h>
#include <cilk/reducer_opadd.h>

// 乱数を集計するグローバル・レデューサー
cilk::reducer_opadd<uint64_t> sum(0);

int rand_fib(int n) {
   if (n < 2) {
       // 乱数を生成し、sum に加算する
       sum += rand() * n;
       return n;
    }
    else {
       int x, y;
       sum += rand() * n;
       x = cilk_spawn rand_fib(n-1);
       sum += rand() * n;
       y = rand_fib(n-2);
       cilk_sync;
       sum += rand() * n; return x+y;
    }
} 

int main(void) {
   int n = 30;
   int ans = rand_fib(n);
   std::printf("fib(%d) = %d\n", n, ans);
   std::printf("sum is %llu\n", sum.get_value());
   return 0;
}

このプログラムで、rand_fib() メソッドは n 番目のフィボナッチ数列を計算しますが、計算の過程で (擬似) 乱数ジェネレーター (RNG) を用いて乱数も生成します。これらの乱数は、n の現在の値で乗算され、レデューサー sum に集計されます。このプログラムを効率良く並列実行するのが目標です。プログラムの並列化において重要なのは結局、実行速度を向上させることですから。

一方で、プログラムが決定論性のある結果 (つまり、プログラムを実行するたびに同じ sum の最終値) を出力するようにしたいと思います。rand() は決定論性のある乱数のストリームを生成するため、rand() の一般的な実装を用いることで、このプログラムはシリアル実行で決定論性のある結果を出力します。しかし、並列実行では、常に決定論性のある動作であるとは限りません。余談ですが、このプログラムにおいて乱数と n の乗算は重要です。単に乱数を集計するだけでは、整数加算は可換であるため、決定論性のある結果になる可能性があります。

皆さんも、一貫した再現性のないプログラムの不具合の追跡で、プログラムを実行するたびに動作が異なり、フラストレーションを感じた経験があるでしょう。ほかのすべてのものが等しい場合、並列実行で決定論性のある並列乱数ジェネレーター (コードを実行するたびに、並列であっても常に同じ乱数を生成する RNG) があったら便利です。そのような RNG を使うことで、並列プログラムにおける非決定性の原因が排除され、並列プログラミングが容易になります。

ここからは、決定論性のある並列乱数ジェネレーターを前述の略語 DPRNG で表します。この略語のほうが「決定論性のある並列乱数ジェネレーター」よりも言いやすいでしょう。

優れたパフォーマンスと決定論性のある実行の両方を得ることは可能でしょうか? 考察の結果、我々はこの 2 つを同時に達成するのは、当初考えていたよりも難しいことに気付きました。

ストリーム RNG と並列ループ

rand() のような一般的な RNG の実装を見直すことが、いくつかの問題を理解する助けになります。rand() のような RNG は、通常ストリーム RNG (ジェネレーターの内部状態に基づいて、数のストリームを一度に 1 つずつ出力する RNG) です。シードを受け取り RNG の内部状態を初期化します。各 rand() 呼び出しの後に、RNG はこの状態を変換して、ストリームの次の数を出力するのに使用します。

これは、もう少し数学的に説明することができます。i 番目の rand() 呼び出し後の RNG の内部状態を xi とし、rand() への各呼び出しは、ある関数 f で内部状態を変換していると仮定します。RNG への n 回の呼び出しは、次のように内部状態 xn を変換します。

x₀
x₁ = f(x₀)
x₂ = f(x₁) = f(f(x₀))
x₃ = f(x₂) = f(f(f(x₀)))
x₄ = f(x₃) = f(f(f(f(x₀))))
...
x_n = f(x_n-1) = f⁽ⁿ⁾(x₀)

長年にわたり、多くの人々が優れた RNG の設計に莫大な労力を投じ、関数 f は非常に複雑になりました。私は、これらの詳細をすべて説明できるほど理解しているわけではありません。幸いにも、ここでは、関数 f の詳細を理解する必要はありません。これらの数学的な説明で重要なことは、ジェネリックな f に対して、x0 から xn の計算で一連のシリアル依存性が存在することです。

このことを念頭に、簡単な並列ループでストリーム RNG を使用する場合について考えてみます。次のプログラムで、並列ループの各反復は乱数を生成し、それを使ってレデューサー sum を更新します。

#include <cstdio>
#include <cstdlib>
#include <cilk/cilk.h>
#include <cilk/reducer_opadd.h> 

int main(void) {
    cilk::reducer_opadd<int> sum(0);
    int n = 1000000;
    cilk_for(int i = 0; i < n; ++i) {
         sum += (i+1) * rand();
    }
    std::printf("Final sum = %d\n", sum);
    return 0; }

このプログラムはどのように動作するでしょうか? rand() の実装に応じて、次の 2 つのシナリオのいずれかになると考えられます。

1. rand() 実装がすべてのワーカースレッドに対して 1 つのストリーム RNG を使用すると仮定します。このケースでは、乱数を生成するため、Cilk の複数のワーカースレッドが同時に RNG の内部状態を操作しようとします。次の 2 つのケースが考えられます。

   1. rand() の実装が適切に同期されていない場合、複数のワーカースレッドが同時に RNG の内部状態を操作しようとするため、競合状態が発生します。私が使用している Linux* デスクトップの man ページによれば、関数 rand() はスレッドセーフではありません。そのため、厳密にはオリジナルの rand_fib() 関数にはバグがあることになります。
   2. rand() の実装がスレッドセーフな場合 (例えば、内部状態がロックで保護されている場合など)、プログラムは正しく動作するはずです。しかし、並列実行で反復 i の rand() の呼び出しにおいて、RNG の内部状態は反復がロックを取得する順番に依存し、この順番はプログラムの実行ごとに変わるでしょう。つまり、このアプローチでは決定論性のある結果が保証されません。

   上記のケース (a) と (b) には、潜在的なパフォーマンスの問題があります。(b) では、ロックで競合状態が発生することが明白です。(a) ではロックは使用していませんが、すべてのワーカースレッドが同じ RNG を共有しているため、RNG の内部状態を格納するキャッシュラインにおいてワーカースレッド間で競合状態が発生する可能性が高くなります。つまり、上記の cilk_for ループは複数のワーカースレッドで実行した場合、パフォーマンスが向上しないか、低下する恐れがあります。

2. rand() の実装で、(例えば、スレッド・ローカル・ストレージに) ワーカースレッドごとに個別のストリーム RNG を保持していると仮定します。この実装は、各スレッドが個別のプライベート RNG 状態を保持するため、前述のシナリオのパフォーマンス問題は回避されます。しかし、プログラムの実行ごとに、ランタイム・スケジューラーが cilk_for ループの反復を異なるワーカーで実行する可能性があるため、生成される乱数が非決定論的であるという問題は残ります。

   具体例として、3 ワーカーで同じインテル® Cilk™ Plus プログラムを続けて 2 回実行した場合、ワーカースレッドの割り当ては次のようになる可能性があります。

   
実行 1:

   反復 0 ～ 499999 はワーカー 0

   反復 750000 ～ 999999 はワーカー 1
   反復 500000 ～ 749999 はワーカー 2

   実行 2:
   反復 0 ～ 249999 はワーカー 0

   反復 500000 ～ 749999 はワーカー 1

   反復 750000 ～ 999999、250000 ～ 499999 はワーカー 2

   実行 1 はワーカー 0 の RNG から 500,000 個の数を受け取り、実行 2 は 250,000 個のみ受け取ります。そのため、2 つの実行間で sum の最終値は異なるでしょう。

2 番目のケースの非決定性は、動的ロードバランスとスレッド・ローカル・ストレージの組み合わせによるものです。特に、インテル® Cilk™ Plus ランタイムは、ワーカーの処理がなくなった場合にほかのワーカーから作業をスチールする、ランダムなワークスチール・スケジューラーを使用します。このスキームは、各ループ反復の作業量が大きく異なる場合でも効率良くスケジュールできるという利点があります。ただし、動的ロードバランスとの組み合わせにより、このサンプルプログラムは実行ごとに反復を実行するワーカー ID が変わります。

余談ですが、この非決定論的な動作こそが、一般にインテル® Cilk™ Plus でスレッド・ローカル・ストレージの使用を避けるべき理由です。デフォルトでは、インテル® Cilk™ Plus のスレッド・ローカル・ストレージは、特定のワーカースレッドに状態が関連付けられるため、ある意味「ワーカー・ローカル・ストレージ」と言えます。ワーカー・ローカル・ストレージの使用は、インテル® Cilk™ Plus の設計の趣旨に反し、ランタイム・スケジューラーの非決定性をインテル® Cilk™ Plus アプリケーションを記述するプログラマーにさらすことになります。このトピックは、本題から逸れるため、別の機会にお話したいと思います。

DotMix の説明に戻りましょう。この簡単な並列ループの調査を行ったところ、これら 2 つの rand() の実装によってインテル® Cilk™ Plus プログラムが非決定論的になることが分かりました。これは、理想的な状況とは言えません。これらのプログラムを決定論的にすることはできるでしょうか?

ストランドローカル RNG

並列ループの例について考察したところ、「ストランドローカル」 RNG に基づいた 3 番目の決定論性のある rand() の実装を思いつきました。前述のコード例で、cilk_for ループの各反復は個別のストランド (並列動作を含まない一連のシリアル命令) を表しています。また、各ストランド には、プログラムの実行間で変わらない明白な名前 (反復のループ・インデックスの値) が付けられます。ループ・インデックスを RNG のシードとして各ループ反復ごとに新しい RNG を作成する場合、各反復はインテル® Cilk™ Plus ランタイムがその反復の実行に使うワーカーとは独立した ID を持つ RNG を使用します。そのため、並列ループで決定論性のある並列 RNG が得られます。

各ストランドごとに新しい RNG を作成することで、これを汎用化して任意のインテル® Cilk™ Plus プログラムで利用することができます。RNG の初期シード値として用いる一意の決定論的な名前を各ストランドに付けることができる限り、決定論性のある RNG になります。このアプローチは、各ストランドが個別の RNG を保持するため、「ストランドローカル」 RNG と考えることができます。

並列乱数生成についての事前調査で、我々はこのストランドローカル RNG がすでに実装し利用しているソリューションと概念的に等価であることに気付きました。例えば、並列乱数生成用の有名なライブラリーである SPRNG は、新しい RNG をスポーンする API を提供します。rand_fib で各 cilk_spawn 文ごとに新しい RNG をスポーンする場合、決定論性のある並列 RNG になります。これで問題解決...と言えるでしょうか?

皆さんが予想されたとおり、まだ解決したとは言えません。ストランドローカル RNG の使用は、インテル® Cilk™ Plus でいくつかの問題を引き起こしますが、我々が直面した最も大きな問題はオーバーヘッドです。新しいストリーム RNG の作成はコストのかかる処理であり、cilk_spawn 処理自体のオーバーヘッドよりもコストがかかる恐れがあります。rand_fib のようなプログラムにおいて、各実行ストランドごとに新しい RNG を作成することは、休暇先で車を借りる代わりに買うことに似ています。旅行中に自分の車に乗れるのは素晴らしいことですが、よほど長い休暇でなければこれは合理的とは言えません。

一般的なストリーム RNG はこれに似ています。優れたストリーム RNG は、n 個の乱数からなる長いストリームを生成できるように設計されています。n は、通常、少なくとも数百万または数十億単位です。一方、rand_fib のような一般的なインテル® Cilk™ Plus プログラムには数百万のストランドがありますが、各ストランドは最大で 10 個または 100 個の乱数しか必要としません。各ストランドごとに新しいストリーム RNG を作成し、シードを指定するには大きなコストがかかり、そのほとんどは無駄になります。

ユーザーが Pthreads* を明示的に作成し管理する並列プログラムでは、多くの場合、新しい Pthreads* の作成は比較的コストがかかるため、各 Pthreads* ごとに新しいストリーム RNG を作成する価値があります。一方、インテル® Cilk™ Plus のストランドは cilk_spawn または cilk_sync ごとに作成され、通常、新しい RNG の作成にかかるコストを相殺できません。各ストランドごとに新しいストリーム RNG を使用することはできますが、RNG の本来の使用方法とは異なります。

DPRNG のハッシュ

これまでのことを踏まえ、最終的にインテル® Cilk™ Plus で DPRNG を実装するアプローチを採用し、ハッシュおよびぺディグリー の 2 つのアイデアに基づいて DotMix DPRNG を実装することになりました。

ハッシュにより、DotMix はインテル® Cilk™ Plus プログラムでストランドに対して乱数を生成することができます。各ストランドが 1 つの乱数のみ生成する必要がある特別なケースについて考えてみましょう。複数の乱数が必要な場合は、概念的にストランドを複数に分割することができます。各ストランドごとに新しいストリーム RNG を作成する代わりに、「適切な」ハッシュ関数をストランドに適用することで乱数を生成できます。極端な場合、SHA や md5sum のバリエーションのような暗号ハッシュ関数を用いて、十分にランダムに見える数を生成することができます。あるいは、単純なハッシュ関数を使用して、「十分にランダムではない」ものの、より効率良く計算できる数を生成することもできます。「ストランド」のハッシュとは、何を意味するのでしょうか? ここで、ぺディグリー (インテル® Cilk™ Plus プログラムの実行におけるストランドの名前) が登場します。

ぺディグリーは、DotMix の決定論性のある実行を保証する上で重要です。インテル® Cilk™ Plus ランタイムは、現在実行中のストランドのぺディグリーを特定できるように支援します (ストランドは、プログラムの異なる実行で一意な名前を保持します)。そのため、ストランドのぺディグリーをハッシュすることで乱数を生成できます。概念的に、ぺディグリーの考え方は単純で直観的です。大変なのは、もちろん、実際にぺディグリーを割り当てることです。このトピックについてもう少し詳しく説明します。

我々の研究では、ストランドにぺディグリーを割り当てる方法を見つけ、ぺディグリーをハッシュすることで、インテル® Cilk™ Plus で DPRNG を実装できるようになりました。出来上がった DPRNG は、事前に生成された乱数の小さなテーブルを使ってぺディグリーのドット積を計算することでぺディグリーをハッシュし、結果を混合して乱数を出力するため、DotMix と呼びます。論文では、ハッシュ関数の有用な数学的特性として、衝突の確率がかなり小さいことを示しました。

また、Dieharder テストスイートを利用して DotMix のハッシュ関数のテストをいくつか行い、DotMix がかなり高品質な乱数を生成することを確認しました。DotMix は、乱数の品質に対して厳しい要件が求められるアプリケーションには適していません。しかし、単にランダムに「見える」数を出力しなければいけないコードでは、DotMix のハッシュ関数を問題なく使用できます。

ハッシュを用いる DPRNG が有効なアプローチかどうか疑問に思われる方は、Supercomputing 2011 で Best Paper Award (最優秀論文賞) を受賞した並列乱数生成に関する論文をご覧になることを推奨します。この論文は、我々の研究とは別に同時期に行われたもので、カウンター値をハッシュすることで乱数を生成する方法について述べています。このアプローチは、ぺディグリー (並列ループのループ・インデックス) のハッシュと概念的に等価です。この論文は、複雑な並列構造を利用してプログラムでぺディグリーを保持する方法よりも、優れたハッシュ関数の選択に注目しています。

DPRNG のハッシュについてはさまざまな意見がありますが、興味のある方は関連論文をご覧ください。以降のセクションでは、ぺディグリーについて述べたいと思います。ぺディグリーは、私の個人的見解では、インテル® Cilk™ Plus にとってより興味深い概念であると考えられます。

インテル® Cilk™ Plus のぺディグリーとは?

予測可能な優れた並列構造を持つプログラムでは、通常、概念的にストランドにぺディグリーを割り当てる明白な方法があります。例えば、各反復で 1 つの乱数を必要とする単純な cilk_for ループでは、ループ・インデックスをぺディグリーとして使用できます。反復 i で ni 個の乱数を必要とするやや複雑なケースでは、ループ・インデックス i を、反復 i でこれまでに使用した乱数の数と組み合わせてぺディグリーに使用できます。この場合、並列実行において、ほかの反復で必要な乱数の数と関係なく、各反復 i のぺディグリーを特定できなければいけないため、概念的にぺディグリーには 1 語ではなく 2 語が必要になります。

より複雑な構造のインテル® Cilk™ Plus プログラムでは (例: rand_fib)、どのようにぺディグリーを定義したら良いでしょうか? 前回の記事で紹介した DotMix を用いたサンプルプログラム rand_fib を思い出してください (以下に再度掲載します)。このコードにはぺディグリーに関する記述が全くありません。つまり、インテル® Cilk™ Plus と DotMix ライブラリーは、内部でぺディグリーを維持し利用しています。

どのような仕組みなのでしょうか? この記事はすでに長くなってしまったので、詳しくは次回の記事で述べたいと思います。次回の課題として、1 つの問題を提示して締めくくりたいと思います。

以下に、rand_fib(4) の実行における DotMix DPRNG への呼び出しを表した有向非巡回グラフ (DAG) を示します。各アルファベットは乱数生成の呼び出しを表します。例えば、A は rand_fib(4) において rand_fib(3) の cilk_spawn の前に実行される get() への最初の呼び出しで、K は cilk_spawn 直後の get() への呼び出しです。get() への各呼び出しは、一意の決定論的なぺディグリーを読み込む必要があります。ぺディグリーの値を各アルファベットに割り当てるには、どうしたら良いでしょうか?

int rand_fib(int n) { if (n < 2) { sum += global_rng.get() * n; return n; } else { int x, y; sum += global_rng.get() * n; x = cilk_spawn rand_fib(n-1); sum += global_rng.get(); y = rand_fib(n-2); cilk_sync; sum += global_rng.get() * n; return x+y; } }

一般に、さまざまな可能性があります。次回の記事で、我々が採用した方法について述べます。ぺディグリーの割り当てスキームは、以下の DAG に依存関係を追加すべきではありません。例えば、K のぺディグリーの値は、rand_fib(3) 内の get() の呼び出し回数に依存してはいけません。今すぐに詳細をご覧になりたい方は、我々の論文かその他のドキュメントを参照してください。

まとめ

決定論的な並列乱数ジェネレーター (DPRNG) である DotMix は、インテル® Cilk™ Plus で従来のシリアル・ストリームベースの乱数ジェネレーターを利用する場合に発生する、パフォーマンスの問題と非決定性を回避します。DotMix は、ぺディグリー (インテル® Cilk™ Plus プログラムの実行におけるストランドの名前) をハッシュすることで決定論性のある乱数を生成します。次回の記事では、ぺディグリーとインテル® Cilk™ Plus におけるぺディグリーの使用方法について詳しく説明します。お見逃しなく!

インテル® Cilk™ Plus に関する詳細は、http://cilkplus.org (英語) を参照してください。インテル® Cilk™ Plus に関する質問や意見交換は、フォーラム (http://software.intel.com/en-us/forums/intel-cilk-plus (英語)) を参照してください。

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