tbb::task::allocate_continuationによるループ処理オーバーラップ

Intel TBBタスク tbb::task のallocate_continuationによる継続タスク利用に関するメモ。TBB公式リファレンスにある推奨タスクパターン*1とは異なる例を取り上げるが、必ずしも望ましいユースケースとなっていない可能性がある（と思う）。

直列化されたイテレーション

LoopTask::executeメンバ関数の戻り値として明示的に継続タスクを返すため、TBBスケジューラをバイパスすることで常に単一スレッド（最初のLoopTaskが実行されたスレッド）上で実行される。

#include <iostream>
#include <thread>
#include "tbb/task.h"

struct LoopTask : tbb::task {
  int counter_;
  LoopTask(int c) : counter_(c) {}

  tbb::task* execute() {
    // ループ内処理
    std::cout << std::this_thread::get_id()
      << ":" << counter_ << std::endl;

    if (counter_ > 0) {
      // 自タスクの継続タスクとして生成(allocate_continuation)し、
      // execute関数の戻り値として返すことで同一スレッド上で実行させる
      return new(allocate_continuation()) LoopTask(counter_ - 1);
    } else {
      // 継続タスクを生成しない
      return NULL;
    }
  }
};

int main()
{
  tbb::task& root = *new(tbb::task::allocate_root()) LoopTask(5);
  tbb::task::spawn_root_and_wait(root);
}

メモ：普通のfor/whileループ構文を使えばよろしい。

オーバーラップするイテレーション

LoopTask::executeメンバ関数の処理途中で自タスクの継続タスクをspwanすることで、自ループ内処理2と次イテレーション以降の開始が並列実行可能な状態となる。TBBワーカースレッドが十分に供給される場合、実行クリティカルパスは「全イテレーションのループ内処理1の総和」＋「最終イテレーションのループ内処理2」まで短縮可能。

struct LoopTask : tbb::task {
  int counter_;
  LoopTask(int c) : counter_(c) {}

  tbb::task* execute() {
    // ループ内処理1
    std::cout << std::this_thread::get_id()
      << ":" << counter_ << std::endl;

    if (counter_ > 0) {
      // 自タスクの継続タスクとして生成(allocate_continuation)し、
      // spwanにより自スレッドの実行待ちプール(ready pool)へ追加する。
      // 同継続タスクは他スレッドにスチール(steal)される可能性がある。
      task& c = *new(allocate_continuation()) LoopTask(counter_ - 1);
      spawn(c);
    }

    // ループ内処理2
    std::cout << std::this_thread::get_id()
      << ":" << counter_ << std::endl;

    // 次実行タスクの選択はTBBスケジューラに任せる
    return NULL;
  }
};

tbb::parallel_doアルゴリズム版

tbb::parallel_do関数テンプレートを使って同じ並列化構造を実装したコード例。同アルゴリズムはInputIteratorを要求するので本要件にとっては少々面倒…（ここではBoost.Iteratorライブラリを利用している）

#include "boost/iterator/counting_iterator.hpp"
#include "tbb/parallel_do.h"

typedef boost::counting_iterator<int> citr;

const int n = 5;
tbb::parallel_do(citr(0), citr(1),
  [&](int i, tbb::parallel_do_feeder<int>& feeder) {
    // ループ内処理1
    if (i < n)
      feeder.add(i + 1);
    // ループ内処理2
  }
);

*1:http://www.threadingbuildingblocks.org/docs/help/reference/task_scheduler/catalog_of_recommended_task_patterns.htm