簡単な例: フィボナッチ数

このセクションでは、例として n 番目のフィボナッチ数を計算します。この例では、非効率的なメソッドを使用してフィボナッチ数を計算しますが、単純な再帰パターンを使用するタスク・ライブラリーの基本も示しています。タスクベースのプログラミングでスケーラブルに速度の向上を達成するには、多くのタスクを指定する必要があります。この場合、インテル® TBB では、再帰タスクパターンを使用します。

シリアルバージョン:

long SerialFib( long n ) {
    if( n<2 )
        return n;
    else
        return SerialFib(n-1)+SerialFib(n-2);
}

並列タスクベースのバージョンのトップレベル・コード:

long ParallelFib( long n ) {
    long sum;
    FibTask& a = *new(task::allocate_root()) FibTask(n,&sum);
    task::spawn_root_and_wait(a);
    return sum;
}

このコードは、実際のワークに FibTask 型のタスクを使用します。次のようなステップで実装します。

タスクに空間を割り当てます。割り当ては、特別に "オーバーロードされた new" と task::allocate_root メソッドで行われます。名前の _root サフィックスは、作成されたタスクに親がないことを示します。このタスクは、タスクツリーのルートです。タスクの完了時に空間を効率良く再利用できるように特別なメソッドでタスクを割り当てる必要があります。
new により呼び出される FibTask(n,&sum) コンストラクターでタスクを構築します。ステップ 3 のタスクの実行時に、n 番目のフィボナッチ数を計算して、*sum に格納します。
task::spawn_root_and_wait で完了するタスクを実行します。

実際のワークは、FibTask の内部で処理されます。次にその定義を示します。

class FibTask: public task {
public:
    const long n;
    long* const sum;
    FibTask( long n_, long* sum_ ) :
        n(n_), sum(sum_)
    {}
    task* execute() {      // 仮想関数 task::execute をオーバーライド
        if( n<CutOff ) {
            *sum = SerialFib(n);
        } else {
            long x, y;
            FibTask& a = *new( allocate_child() ) FibTask(n-1,&x);
            FibTask& b = *new( allocate_child() ) FibTask(n-2,&y);
            // ref_count を "2 つの子 + 待機用" で 3 に設定
            set_ref_count(3);
            // b の実行を開始
            spawn( b );
            // a の実行を開始してすべての子 (a と b) を待つ
            spawn_and_wait_for_all(a);
            // 総和を計算
            *sum = x+y;
        }
        return NULL;
    }
};

標準 C++ の拡張機能を使用しないで並列処理を表現しているため、このコードは SerialFib よりも大きくなっています。

インテル® TBB によってスケジュールされるすべてのタスクと同様に、FibTask は task クラスから派生しています。n フィールドと sum フィールドは、それぞれ入力値と出力のポインターを保持します。これらは、FibTask のコンストラクターに渡される引数のコピーです。execute メソッドは、実際の計算を行います。すべてのタスクで、純粋な仮想メソッド task::execute をオーバーライドする execute の定義を提供しなければなりません。定義は、タスクのワークを行い、NULL または次に実行するタスクのポインターを返します。この例では、NULL を返します。NULL でない場合の詳細は、「スケジューラーのバイパス」を参照してください。

FibTask::execute() メソッドは次の処理を行います。

n が小さく、シリアル実行の方が高速かどうかを確認します。CutOff の正しい値を見つけるには、試行が必要です。この例で最も速度向上を見込める値は 16 です。問題サイズが小さくなったときに、シーケンシャルなアルゴリズムに並べ替えるのは、並列処理の分割統治法の特性です。切り替えのポイントを見つけるには試行が必要なため、試行を繰り返しても問題ないコードを記述してください。
else 文が実行される場合、コードは (n-1) 番目と (n-2) 番目のフィボナッチ数を計算する 2 つの子タスクを作成して実行します。ここで、継承した allocate_child() メソッドがタスクの空間割り当てに使用されます。トップレベルのルーチン ParallelFib が allocate_root() を使用してタスクに空間を割り当てたことを思い出してください。違いは、ここではタスクが子タスクを作成しているということです。この関係は、割り当てメソッドの選択によって示されます。
set_ref_count(3) を呼び出します。数字の 3 は、2 つの子と spawn_and_wait_for_all メソッドで必要な追加の暗黙的参照を表現しています。子を生成する前に、set_reference_count(3) を必ず呼び出してください。呼び出しが行われない場合の動作は不定です。ライブラリーのデバッグバージョンは、通常この種のエラーを検出してレポートします。
2 つの子タスクを生成します。タスクの生成は、選択したときにいつでも、あるいは別のタスクを実行しながらでも、並列にそのタスクを実行できることをスケジューラーに知らせます。実行ポリシーの詳細は、「タスク・スケジュールの動作」を参照してください。spawn メソッドによる 1 つ目の子の生成では、子タスクが実行を開始するのを待つことなくすぐにリターンします。spawn_and_wait_for_all メソッドによる 2 つ目の子の生成では、親は現在割り当てられている子のタスクが終了するまで待機します。
2 つの子タスクが完了した後、親は x+y を計算して、結果を *sum に格納します。

タスクでは 2 つの子タスクしか生成されないため、一見、並列処理に制約があるように見えます。ここでは、再帰並列処理 がポイントです。2 つの子タスクは、それぞれ 2 つの子タスクを生成し、その後も n<Cutoff になるまで処理を繰り返します。この連鎖反応は、多くの潜在的な並列処理の可能性を作り出します。タスク・スケジューラーの利点は、わずかなコンテキストの切り替えで物理スレッドが稼動状態になるように実行するタスクが選択されるため、この潜在的な並列処理の可能性を、効率的な方法で実際の並列処理にできることです。

簡単な例: フィボナッチ数

関連情報