完了までの並列化: parallel_do

一部のループでは、反復空間の最後が不明であるか、あるいはループが終了する前にループボディーが反復を追加することがあります。どちらの場合も、tbb::parallel_do テンプレート・クラスを使用することで対処できます。

リンクリストは、終端が不明な反復空間の例です。並列プログラミングでは、リンクリストのアイテムへのアクセスは本質的にシリアルであるため、リンクリストの代わりに動的配列を使用するほうが効率的です。しかし、リンクリストを使用する必要があり、アイテムが安全に並列処理可能で、各アイテムの処理に少なくとも数千命令がかかる場合、parallel_do を使用して一部を並列処理します。

例えば、次のシリアルコードについて考えてみます。

void SerialApplyFooToList( const std::list<Item>& list ) {
    for( std::list<Item>::const_iterator i=list.begin() i!=list.end(); ++i ) 
        Foo(*i);
}

Foo の実行に少なくとも数千個の命令が費やされる場合、parallel_do を使用するようにループを変換することで、並列処理を高速化できます。そのためには、const 修飾された operator() を使用してオブジェクトを定義します。これは、operator() が const でなければならない点を除いて、C++ 標準ヘッダー <functional> の C++ 関数オブジェクトと似ています。

class ApplyFoo {
public:
    void operator()( Item& item ) const {
        Foo(item);
    }
};

SerialApplyFooToList の並列形式は次のようになります。

void ParallelApplyFooToList( const std::list<Item>& list ) {
    parallel_do( list.begin(), list.end(), ApplyFoo() ); 
}

parallel_do を呼び出しても、2 つのスレッドは同時に入力イテレーターで動作しません。シリアルプログラムの入力イテレーターの定義は正しく動作します。ワークのフェッチはシリアルであるため、parallel_do はスケーラブルでなくなります。しかし、多くの状況では、シリアルに処理した場合よりも高速化されます。

parallel_do でワークをスケーラブルに取得する方法は 2 つあります。

• イテレーターをランダムアクセス・イテレーターにします。

• parallel_do のボディー引数は、第 2 引数が型 parallel_do<Item>& のフィーダー の場合、feeder.add(item) を呼び出すことで、より多くのワークを追加できます。例えば、ツリーのノードを処理することは、その子孫を処理するための前提条件です。parallel_do では、ノードを処理した後、feeder.add を使用して子孫ノードを追加できます。parallel_do のインスタンスは、すべてのアイテムが処理されるまで終了しません。