4

これは長い話になるでしょうが、おそらくあなた方の何人かはこのケースを研究したいと思うでしょう。

並列グラフアルゴリズムの開発に取り組んでいます。STINGERという名前の最先端のHPC並列グラフデータ構造を選択しました。STINGERのミッションステートメントは次のとおりです。

「STINGERは、大規模なグラフコミュニティが互いの研究開発を迅速に活用できるように、共通の抽象データ構造を提供する必要があります。[...] STINGER用に作成されたアルゴリズムは、複数の言語やフレームワーク間で簡単に変換/移植できます[...]すべてのグラフアルゴリズムに最適な単一のデータ構造はないことが認識されています。STINGERの目的は、ほとんどのアルゴリズムを適切に実行できる適切なデータ構造を構成することです。他の一般的なデータ構造と比較した場合、STINGERを使用してもパフォーマンスが大幅に低下することはありません。典型的なグラフアルゴリズムの幅広いセット。」

STINGERはおそらくかなり効率的で、共有メモリの並列処理に適しています。一方で、それはあまり抽象的でも、汎用的でも、簡潔でもありません。STINGERが提供するインターフェースは、いくつかの理由で私には不十分です。冗長すぎます（関数には私の場合は重要ではないパラメーターが必要です）。有向グラフのみをモデル化しますが、無向グラフが必要です。およびその他の理由。

ただし、新しい並列グラフデータ構造を自分で実装することは躊躇します。

そのため、私はすでにSTINGERインスタンスを自分のGraphクラスでカプセル化し始めています。たとえば、無向エッジが存在するかどうかを確認するためGraph::hasEdge(node u, node v)に、アルゴリズムに書き込む代わりに呼び出すことができるようになりました。

int to = stinger_has_typed_successor(stinger, etype, u, v);
int back = stinger_has_typed_successor(stinger, etype, v, u);
bool answer = to && back;

これまでのところ、これはうまく機能しています。次に、反復のトピックに移ります。

STINGERは、マクロを介してトラバーサル（ノード、エッジ、ノードの入射エッジなどの反復）を実現します。たとえば、あなたは書く

STINGER_PARALLEL_FORALL_EDGES_BEGIN(G.asSTINGER(), etype) {
    node u = STINGER_EDGE_SOURCE;
    node v = STINGER_EDGE_DEST;
    std::printf("found edge (%d, %d)", u, v);
} STINGER_PARALLEL_FORALL_EDGES_END();

ここでSTINGER_PARALLEL_FORALL_EDGES_BEGIN展開します

do {                                    \
                            \
                            \
    for(uint64_t p__ = 0; p__ < (G.asSTINGER())->ETA[(etype)].high; p__++) {    \
      struct stinger_eb *  current_eb__ = ebpool + (G.asSTINGER())->ETA[(etype)].blocks[p__]; \
      int64_t source__ = current_eb__->vertexID;            \
      int64_t type__ = current_eb__->etype;             \
      for(uint64_t i__ = 0; i__ < stinger_eb_high(current_eb__); i__++) { \
    if(!stinger_eb_is_blank(current_eb__, i__)) {                   \
      struct stinger_edge * current_edge__ = current_eb__->edges + i__;

マクロは、効率的な（並列）反復のために完全に公開する必要があると思われるデータ構造の腸を非表示にします。STINGER_FORALL_EDGES_BEGIN、、..STINGER_READ_ONLY_FORALL_EDGES_BEGINを 含むさまざまな組み合わせのマクロがあります。STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_BEGIN

はい、これらのマクロを使用することはできますが、反復を実装するためのより洗練された方法があるのではないかと思います。インターフェイスが必要な場合は、次のようになります。

G.forallEdges(readonly=true, parallel=true, {..})

GraphIterTools.forallEdges(G, readonly=true, parallel=true, {...})

ここで、{...}は単に関数、クロージャ、または「コードのブロック」であり、これらは適切に実行されます。ただし、これを実装するためのC++の経験が不足しています。この問題についてあなたが私にどんなアドバイスを与えることができるのだろうか。たぶん、「マクロを使うべきだから…」。

4

1 に答える 1

2

既存のマクロを利用して、次のようにグラフクラスにメンバー関数を実装できます。

template<typename Callback>
void forallEdges(int etype, Callback callback)
{
    STINGER_PARALLEL_FORALL_EDGES_BEGIN(this->asSTINGER(), etype) {
        node u = STINGER_EDGE_SOURCE;
        node v = STINGER_EDGE_DEST;

        // call the supplied callback
        callback(u, v);

    } STINGER_PARALLEL_FORALL_EDGES_END();
}

次に、コールバック関数を定義し、それを新しいメソッドに渡します。

void my_callback(node u, node v) { ... }
...
G.forallEdges(etype, my_callback);

または、C ++ 11では、ラムダ関数を使用できます。

G.forallEdges(etype, [](node u, node v) { ... });
于 2012-12-05T21:45:10.733 に答える