分割統治

分割統治#

問題

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

コンテキスト

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

強制

  • 問題は、独立して解決できるサブ問題に変換できます。

  • 問題を分割したりソリューションを統合するコストは、サブ問題を解決するコストと比較すると比較的安価です。

解決方法

oneAPI スレッディング・ビルディング・ブロック (oneTBB) で分割統治を実装する方法はいくつかあります。最善の選択肢は状況によって異なります。

  • 分割によって常に同じ数のサブ問題が生成される場合、再帰と oneapi::tbb::parallel_invoke を使用します。

  • サブ問題の数が変化する場合、再帰と oneapi::tbb::task_group を使用します。

例

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

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 に固定されているため、oneapi::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] ); 
        oneapi::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] ); 
        oneapi::tbb::parallel_invoke( [=]{ParallelQuicksort( begin, mid-1 );}, 
                                [=]{ParallelQuicksort( mid, end );} ); 
    } else { 
        SerialQuicksort( begin, end ); 
    } 
}

この変更は、凝集パターンのインスタンスです。

次の例では、サブ問題の数が可変である問題を考えます。この問題には、機械アセンブリーのツリー状の記述が含まれます。ノードには次のような種類があります。

  • 末端ノードは個々の部分を表します。

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

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

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 oneapi::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 を並列に再帰 
        oneapi::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 クラスを使用して並列化されます。

並列処理が導入されたことにで、もう 1 つの重要な変更点が現れます。Hits を同時に更新するのは安全ではないため、並列ウォークでは変数 LocalHits を使用して結果を蓄積します。enumerable_thread_specific タイプであるため、各スレッドはプライベート結果を蓄積します。ウォークが完了すると、結果は Hits に結合されます。

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

並列オーバーヘッドが大きい場合、凝集パターンを使用します。例えば、特定のしきい値以下のサブツリーに対してシリアルウォークを使用します。