推奨するタスクパターンのカタログ

このセクションでは、推奨するタスクパターンを説明します。各パターンで、T クラスは task クラスから派生すると仮定されます。サブタスクは、t1、t2、... tk と表記します。添字は、並列処理できない場合にサブタスクを実行する順序を示します。並列処理が可能な場合、サブタスクの実行順は、t1 が生成されるスレッドによって実行されることが保証される以外、実行の順番に再現性はありません。

再帰タスクパターンは、タスク・スケジューラーが潜在的な並列処理を明らかにして利用可能な並列処理にできるため、効率的でスケーラブルな並列処理に推奨されます。再帰タスクパターンは、ルートタスク t0 を作成して次のように実行することで始まります。

 T& t0 = *new(allocate_root()) T(...);
 task::spawn_root_and_wait(t0);

ルートタスクの execute() メソッドは、この後に記述されているように多くのタスクを再帰的に作成します。

ブロックスタイルと k の子

次のコードは、各レベルが k の子を生成する T 型の再帰タスクの推奨スタイルを示しています。

 task* T::execute() {
     if( not recursing any further ) {
         ...
     } else {
         set_ref_count(k+1);
         task& tk = *new(allocate_child()) T(...);  spawn(tk);
         task& tk-1= *new(allocate_child()) T(...);  spawn(tk-1);
         ...
         task& t1= *new(allocate_child()) T(...);
         spawn_and_wait_for_all(t1);
     }
     return NULL;
 }

タスクの生成前にタスクが構築される場合、子の構築と生成の順序は変更できます。

このパターンの重要なポイントは次のとおりです。

継続渡しスタイルと k の子

2 つの推奨するスタイルがあります。これらのスタイルは、継続して親を再利用するほうが便利なのか、子として親を再利用するほうが便利なのかという点で異なります。継続と子のどちらがより親のように働くか、という判断に基づいて決定します。

次の例では、オプションで、子を作成する代わりに子の 1 つのポインターを返すことができます。ポインターを返すようにした場合、親がリターンした直後に子が実行されます。タスクプールにタスクを格納して取り出す無意味なオーバーヘッドをスキップできるため、このオプションを選択すると効率が向上することがあります。

継続して親を再利用

継続が親の状態の多くを継承する必要があり、子が状態を必要としない場合、このスタイルが便利です。継続は親と同じ型を持っていなければなりません。

 task* T::execute() {
     if( not recursing any further ) {
         ...
         return NULL;
     } else {
         set_ref_count(k);
         recycle_as_continuation();
         task& tk  = *new(allocate_child()) T(...); spawn(tk);
         task& tk-1 = *new(allocate_child()) T(...); spawn(tk-1);
         ...
         // 不必要なオーバーヘッドを削除するため、タスクを
         // 作成する代わりに最初の子のポインターを返す
         task& t1 = *new(allocate_child()) T(...);
         return &t1;
     }
 }

このパターンの重要なポイントは次のとおりです。

子として親を再利用

子が親からのその状態の多くを継承し、継続が親の状態を必要としない場合、このスタイルが便利です。子は親の型を持っていなければなりません。例では、C は継続の型で、task クラスから派生します。C が、すべての子が完了するのを待つ以外に何もしない場合、C は empty_task クラスです。

 task* T::execute() {
     if( not recursing any further ) {
         ...
         return NULL;
     } else {
         // 継続を構築
         C& c = allocate_continuation();
         c.set_ref_count(k);
         // 最初の子として自身を再利用
         task& tk = *new(c.allocate_child()) T(...); spawn(tk);
         task& tk-1 = *new(c.allocate_child()) T(...); spawn(tk-1);
         ...
         task& t2 = *new(c.allocate_child()) T(...);  spawn(t2);
         // タスク t1 は再利用された自身
         recycle_as_child_of(c);
         t1 で解決される下位の問題のために *this のフィールドを更新
         return this;
     }
 }

このパターンの重要なポイントは次のとおりです。

子タスクの実行中にメインスレッドを実行する

子タスクの実行中にメインスレッドの実行を続けることが望ましい場合があります。次の例は、ダミータスク empty_task を使用してこの処理を行っています。

 task* dummy = new( task::allocate_root() ) empty_task;
 dummy->set_ref_count(k+1);
 task& tk = *new( dummy->allocate_child() ) T;  dummy->spawn(tk);
 task& tk-1 = *new( dummy->allocate_child() ) T;  dummy->spawn(tk-1);
 ...
 task& t1 = *new( dummy->allocate_child() ) T;  dummy->spawn(t1);
 ...do any other work...
 dummy->wait_for_all();
 dummy->destroy(*dummy);

このパターンの重要なポイントは次のとおりです。

  1. ダミータスクはプレースホルダーであり、動作しません。
  2. set_ref_count の呼び出しはその引数として k+1 を使用します。
  3. ダミータスクは明示的に破棄しなければなりません。
親トピック: タスク・スケジューラー

関連情報

empty_task クラス