分割統治

問題

分割統治アルゴリズムを並列化する。

コンテキスト

分割統治はシリアル・アルゴリズムで広く使用されています。一般的な例は、クイックソートとマージソートです。

影響

• 問題は別々に解くことができる複数の部分問題に変形することができます。

• 問題の分割やソリューションのマージのコストは、部分問題を解くコストと比較して相対的に低くなります。

ソリューション

インテル® スレッディング・ビルディング・ブロック (インテル® TBB) で分割統治を実装する方法はいくつかあります。最適な選択肢は状況に依存します。

• 分割で同じ数の部分問題が常に生成される場合は、再帰と tbb::parallel_invoke を使用します。

• 部分問題の数が異なる場合は、再帰と tbb::task_group を使用します。

• 効率とスケーラビリティーが重要な場合は、tbb::task と継続渡し形式を使用します。

サンプル

クイックソートは古典的な分割統治アルゴリズムで、ソート問題を 2 つの部分ソートに分割します。単純なシリアルバージョンは次のようになります。¹

void SerialQuicksort( T* begin, T* end ) {
   if( end-begin>1  ) {
       using namespace std;
       T* mid = partition( begin+1, end, bind2nd(less<T>(),*begin) );
       swap( *begin, mid[-1] );
       SerialQuicksort( begin, mid-1 );
       SerialQuicksort( mid, end );
   }
}

部分ソートの数は 2 つに固定されているため、tbb::parallel_invoke を使用して単純な方法で部分ソートを並列化します。並列コードを次に示します。

void ParallelQuicksort( T* begin, T* end ) {
   if( end-begin>1 ) {
       using namespace std;
       T* mid = partition( begin+1, end, bind2nd(less<T>(),*begin) );
       swap( *begin, mid[-1] );
       tbb::parallel_invoke( [=]{ParallelQuicksort( begin, mid-1 );},
                             [=]{ParallelQuicksort( mid, end );} );
   }
}

部分ソートが小さくなりすぎるとシリアル実行のほうが効率が良くなるため、次のバージョン (変更点を太字で表示) では、以前のシリアルコードを使用して 500 未満の要素のソートを行っています。

void ParallelQuicksort( T* begin, T* end ) {
   if( end-begin>=500 ) {
       using namespace std;
       T* mid = partition( begin+1, end, bind2nd(less<T>(),*begin) );
       swap( *begin, mid[-1] );
       tbb::parallel_invoke( [=]{ParallelQuicksort( begin, mid-1 );},
                             [=]{ParallelQuicksort( mid, end );} );
   } else {
       SerialQuicksort( begin, end );
   }
}

変更は擬集化パターンのインスタンスです。

次のサンプルでは、部分問題の数が異なる問題を扱います。問題は、木構造を含んでおり、2 種類のノードがあります。

• 葉ノードは個々のパーツを表します。

• 内部ノードはパーツのグループを表します。

問題は、ターゲットのノードと衝突するノードをすべて検索します。次のコードは、ツリーを移動するシリアル・ソリューションを示しています。ここでは、Hits に Target と衝突したノードをすべて記録します。

std::list<Node*> Hits;
Node* Target;
 
void SerialFindCollisions( Node& x ) {
   if( x.is_leaf() ) {
       if( x.collides_with( *Target ) )
           Hits.push_back(&x);
   } else {
       for( Node::const_iterator y=x.begin();y!=x.end(); ++y )
           SerialFindCollisions(*y);
   }
} 

並列バージョンを次に示します。

typedef tbb::enumerable_thread_specific<std::list<Node*> > LocalList;
LocalList LocalHits; 
Node* Target;    // ターゲットノード
 
void ParallelWalk( Node& x ) {
   if( x.is_leaf() ) {
       if( x.collides_with( *Target ) )
           LocalHits.local().push_back(&x);
   } else {
       // x の子 y を並列で再帰的に処理
       tbb::task_group g;
       for( Node::const_iterator y=x.begin(); y!=x.end(); ++y )
           g.run( [=]{ParallelWalk(*y);} );
       // 再帰呼び出しが完了するまで待機
       g.wait();
   }
}
 
void ParallelFindCollisions( Node& x ) {
   ParallelWalk(x);
   for(LocalList::iterator i=LocalHits.begin();i!=LocalHits.end(); ++i)
       Hits.splice( Hits.end(), *i );
} 

再帰移動は、並列に再帰呼び出しを行うために task_group クラスを使用して並列化されます。

並列性の導入による、別の重要な変更があります。Hits を同時に更新することは安全ではないため、並列移動は変数 LocalHits を使用して結果を集積します。この変数は enumerable_thread_specific 型なので、各スレッドは個々の結果を集積します。移動が完了した後、結果が Hits に結合されます。

結果はオリジナルのシリアルコードと同じ順序になりません。

並列化のオーバーヘッドが大きい場合は、擬集化パターンを使用します。例えば、特定のしきい値未満の部分木にシリアル移動を使用します。