1

大きなデータセットから非常に大きくなる有向グラフを作成する必要があります。私は確かにこれらのことを知っています：

  • 各ノードには最大で K 個の出力エッジがあります
  • unordered_mapN >> K ノードのリスト ( ) があります
  • グラフは、すべてのノードを互いに比較することによって作成されます (はい、残念ながら O(N^2))。

考えstd::threadてみれば、 を使ってグラフ作成を並列化したいのですが、これをBoost Graph Library経由で実現できないかと考えていました。

隣接行列を使用すると、行列 (K*N 要素) を事前に割り当てることができるはずなので、隣接するすべてのノードを挿入することはスレッドセーフになります。

BGL はスレッドセーフではない可能性があると読みましたが、私が見つけた投稿は 3 年前のものです。

私が考えていることができるかどうか知っていますか？それ以外の方法をお勧めしますか？

乾杯！

4

2 に答える 2

3

BGL のほとんどすべてのグラフ アルゴリズムでは、マッピングが必要です: vertex -> int は、各頂点に範囲 [0, num_vertices(g) ) 内の一意の整数を割り当てます。このマッピングは「頂点インデックス」として知られており、通常はプロパティマップとしてアクセスできます。

そうは言っても、頂点はすでに整数であるか、いくつかの整数に関連付けられていると想定できます（たとえば、unordered_mapには「mapped_type」に追加のフィールドがあります）。入力頂点が std::vector などの連続したタイトな配列に格納されている場合は、(パフォーマンスとメモリの点で) さらに優れており、インデックス付けは自然です。

頂点が[関連付けられた]整数である場合、メモリ不足のグラフの最適な選択は「圧縮されたスパース行グラフ」です。グラフは不変であるため、グラフを生成する前にエッジ コンテナーを設定する必要があります。

ravenspoint が説明したように、最良の選択は、各スレッドに独自の結果のローカル コンテナーを装備し、ローカル結果を最終結果にマージするときにのみ中央コンテナーをロックすることです。このような戦略は、TBB テンプレートtbb::parallel_reduceによってロックレスで実装されます。したがって、グラフ構築の完全なコードは、おおよそ次のようになります。

#include "tbb/blocked_range2d.h"
#include "tbb/parallel_reduce.h"
#include "boost/graph/compressed_sparse_row_graph.hpp"

typedef something vertex; //e.g.something is integer giving index of a real data

class EdgeBuilder
{
public:
    typedef std::pair<int,int> edge;
    typedef std::vector<edge> Edges;
    typedef ActualStorage Input;

    EdgeBuilder(const Input & input):_input(input){} //OPTIONAL: reserve some space in _edges
    EdgeBuilder( EdgeBuilder& parent, tbb::split ): _input(parent.input){} // reserve something

    void operator()( const const tbb::blocked_range2d<size_t>& r ) 
    { 
        for( size_t i=r.rows().begin(); i!=r.rows().end(); ++i ){
            for( size_t j=r.cols().begin(); j!=r.cols().end(); ++j ) {
                //I assume you provide some function to compute existence
                if (my_func_edge_exist(_input,i, j))
                    m_edges.push_back(edge(i,j));
            }
        }        
    } 

    //merges local results from two TBB threads
    void join( EdgeBuilder& rhs ) 
    {
        m_edges.insert( m_edges.end(), rhs.m_edges.begin(), rhs.m_edges.end() ); 
    }

    Edges _edges; //for a given interval of vertices
    const Input & _input;
};

//full flow:  
boost::compressed_sparse_row_graph<>* build_graph( const Storage & vertices)
{
    EdgeBuilder builder(vertices);
    tbb::blocked_range2d<size_t,size_t> range(0,vertices.size(), 100, //row grain size 
                                              0,vertices.size(), 100); //col grain size
    tbb::parallel_reduce(range, builder);

    boost::compressed_sparse_row_graph<> 
      theGraph = new boost::compressed_sparse_row_graph<> 
                        (boost::edges_are_unsorted_multi_pass_t, 
                         builder._edges.begin(), builder._edges.end(), 
                         vertices.size() );
    return theGraph;
}
于 2013-10-26T20:01:25.673 に答える
1

目標を 2 つのサブ目標に分割する必要があると思います。

  1. ノードのペアの N * ( N - 1 ) テストを実行して、ノード間のリンクを作成します。これを独立したスレッドに分割する方法を考えているようです。boost:graph の謎を心配することなく、スレッド セーフであることがわかっているデータ構造に結果を格納します。

  2. ノードと (作成したばかりの) リンクから boost::graph を作成します。

各スレッドで作成されたリンクの保存に関する注意: 適切なスレッドセーフなデータ構造を見つけるのはそれほど簡単ではありません。STL の動的に割り当てられた構造体を使用する場合は、スレッド セーフなアロケーターを作成することについて心配する必要がありますが、これは課題です。事前に割り当てると、割り当てを処理するための厄介なコードがたくさんあります。そのため、各スレッドによって作成されたリンクを個別のデータ構造に格納することをお勧めします。これにより、スレッド セーフである必要がなくなります。リンクがすべて作成されたら、各スレッドによって作成されたリンクを 1 つずつループできます。

もう少し効率的な設計を想像することもできますが、スレッドの安全性に関する多くの難解な知識が必要になります。私が提案する設計は、難解な知識やトリッキーなコードがなくても実装できるため、より迅速かつ堅牢に実装され、保守が容易になります。

于 2013-10-22T15:15:29.553 に答える