TBB: Intel Threading Building Blocks

会社帰りに八重洲ブックセンターに立寄ってみると、O'Reilly から Intel Threading Building Blocks の解説本が出ていました。

http://www.oreilly.co.jp/books/9784873113555/

結局買わずに帰ったものの、面白そうだったので英文の Tutorial(PDF) をダウンロードして読んでみました。

http://threadingbuildingblocks.org/ver.php?fid=91

主な特徴は

  • IA 用 C++ テンプレート並列ライブラリ(Open Source)
  • テーマは大量データの「分割 & 統治」
  • スレッドよりも軽く、粒度の細かい「タスク」による並列処理を自動化
  • 汎用的な並列アルゴリズムや並列コンテナを提供
  • Windows/Linux/Mac OS X に対応
  • pthread や OpenMP とも共存可能

といったところです。まとまったデータの塊を一気に処理するような用途、例えばゲームや画像処理、シミュレーションなどに向いてそうですね。実際のコードですが、並列化した for ループなら以下のように書けます。

void ParallelApplyFoo(float a[], size_t n) {
    tbb::parallel_for(tbb::blocked_range<size_t>(0, n, IdealGrainSize), ApplyFoo(a));
}

ここでは float 配列 a の各要素に対して ApplyFoo ファンクタを適用しています。tbb::blocked_range には配列の開始位置と長さ、分割サイズを指定します。すると、IdealGrainSize で指定した値まで配列が均等に分割され、該当範囲に対して ApplyFoo が並列に呼び出されていくのです。ナイスですね。IdealGrainSize の最適値は試行錯誤で追い込んでいくこともできるし、TBB に任せることもできます。ApplyFoo ファンクタの中身は以下のようになっています。

class ApplyFoo {
    float* const a_;

public:
    ApplyFoo(float a[]) : a_(a) {}
    void operator()(const tbb::blocked_range<size_t>& range) const {
        float* a = a_;
        for(size_t i = range.begin(); i != range.end(); ++ i) { Foo(a[i]); }
    }
};

コンストラクタで配列のアドレスを保存しておいて、operator() 関数で配列の添字範囲が入った range 引数を受け取ります。あとは順次処理していくだけです。ローカル変数 a への代入は不要ですが、Tutorial 曰く、こうすることでコンパイラがループの最適化をしやすくなるそうです。

こういった並列アルゴリズムの他に、concurrent_vector や concurrent_queue といった並列コンテナ、各種 mutex、アトミック演算、CPU キャッシュ用メモリアロケータ(!!!)などのコンポーネントが用意されています。

その中でも一番そそられるのが並列アルゴリズムとその裏で動いているタスクスケジューラです。詳細については Tutorial の 10 章にありますが、並列アルゴリズムの流れはおおよそ以下のようになります。

  1. 処理対象のデータを再帰的に分割しながらグラフを生成する
  2. グラフの各ノードには対象範囲を処理するタスクを割り当てる
  3. 完成したグラフを適当なサイズに分解(?)し、各スレッドに ready pool として割り当てる
  4. 各スレッドが自分の ready pool から深さ優先でタスクを取り出して処理する
  5. ready pool が空になったスレッドは、ランダムに選択された他のスレッドから一番浅いタスクをかすめ取って処理する

一番深いタスクから処理する理由は、それが最後に生成されたタスク(≒スタック)であり、キャッシュに乗ったアツアツの状態だからです。できたての料理を冷める前に頂くわけですね。また、自分の ready pool を処理し終わったスレッドも休ませないことで並列度の向上も図ると。冒頭の parallel_for というアルゴリズムも内部ではタスクスケジューラを呼び出し、順次アクセスする範囲を二分木にマップすることで並列化していたわけです。同様にして、プログラマが独自の並列化アルゴリズムを書くこともできます。

実際に tbb20_017src というバージョンをビルドしてテストしてみたところ、1.66GHz Intel Core Duo という環境で、直列に比べて 1.5 〜 1.9 倍近い性能改善を示しました。興味深いのはこの環境だと性能改善のピークがスレッド数 3 あたりまでで、4 以降は低下していくことです。やみくもにスレッドを増やしても無意味なことがわかります。もう少し実験したら、仕事でも使ってみたいと思います(と、勝手に宣言 ;-)。

ACE_Condition

前回気になっていた条件変数について ACE を調べてみました。

http://www.cs.wustl.edu/~schmidt/ACE.html

ACE_Condition クラスは以下のようなインタフェースになっています。

template <class MUTEX> 
class Condition 
{ 
public: 
  // Initialize the condition variable. 
  Condition (const MUTEX &m, int type = USYNC_THREAD, void *arg = 0); 
  // Implicitly destroy the condition variable. 
  ~Condition (void); 
  // Explicitly destroy the condition variable. 
  int remove (void); 
  // Block on condition, or until absolute 
  // time-of-day has elapsed. If abstime 
  // == 0 use blocking wait(). 
  int wait (Time_Value *abstime = 0) const; 
  // Signal one waiting thread. 
  int signal (void) const; 
  // Signal *all* waiting threads. 
  int broadcast (void) const; 
private: 
  cond_t cond_; 
  // Reference to mutex lock. 
  const MUTEX &mutex_; 
};

http://www.cs.wustl.edu/~schmidt/PDF/ACE-concurrency.pdf

やはり mutex の参照を保持していますね。条件変数と mutex は不可分な関係である以上、内部に保持するか ctor injection を使うのが自然です。基本的な考え方は pthread::condition と同じなのでこれは納得できます。

なぜ Boost.Thread はあのインタフェースを採用したんだろう。ううむ。