c++ - cilk を使用してフィボナッチを計算する正しい方法は何ですか?

Question

cilk を学んでいる間、私は 2 つの反対の例で反論しました。

1. インテルから

2. ウィキ（またはネットの他の例）から：

反対は、これらの 2 行にあります。

x = spawn fib (n-1);
y = spawn fib (n-2);

最初のサイトには次のように書かれています。

fib()空の継続が作成されるため、2 番目の再帰呼び出しに cilk_spawn 属性を追加する必要はありません。

1. なぜだか分からない？
2. 正しい方法は何ですか？(spawn コマンドを 2 つ使用するか、1 つだけ使用するか?)

Answer 1

インテル ドキュメント「int x = cilk_spawn fib(n-1);」のコード 「int y = fib(n-2);」の次の行で、別の脅威で実行する許可を求めます。メインプログラムと同じ脅威で実行されます。ウィキ コードは、fib(n-2) の計算に対しても新しい脅威を要求します。そのため、メイン プログラム (fib(n)) を実行するプロセッサが 3 つ以上ある場合、fib (n-1) および fib(n-2) ）すべて別の脅威に。

プロセッサが 2 つしかない場合、両方のコードは同じように動作します。以下はウィキページより。

... プロセッサは、生成されたプロシージャを別の場所に割り当てる義務はありません。マシンに 2 つのプロセッサしかなく、 fib(2) を実行しているプロセッサがプロシージャ呼び出しに到達したときに2 番目のプロセッサがまだ fib(1) でビジーである場合、最初のプロセッサは fib(2) を中断し、fib(0) 自体を実行します。それが唯一のプロセッサであればそうなるでしょう。もちろん、別のプロセッサが使用可能な場合は、そのプロセッサが呼び出され、3 つのプロセッサすべてが別々のフレームを同時に実行します。

Answer 2

あなたが参照しているウィキペディアの例は、Cilk 関数へのすべての呼び出しを生成する必要がある MIT Cilk のものです。その要件は、Intel の Cilk Plus 実装に進化した Cilk++ によって削除されました。

盗まれるのは継続であり、生成された関数ではないことに注意してください。生成された関数の前にコードを実行するワーカーは、生成された関数を実行します。cilk_spawn継続をワーカーの両端キューにプッシュし、アイドル状態のワーカーがスチールできるようにします。

Cilk Plus での fib の完全な実装を検討してください。

int fib(int n) {
    if (n < 2)
        return n;
    int x = cilk_spawn fib(n-1);
    int y = fib(n-2);
    cilk_sync;
    return x+y;
}

fib の 2 番目の再帰呼び出しにa を配置するcilk_spawnと、アイドル状態のワーカーがその呼び出しの後に継続を盗むことができます。しかし、そのストランドはすぐに で終わるcilk_syncので、時間の無駄です。