0

グラフの最小スパニング ツリーを見つけるために、Boruvka のアルゴリズムを C++ で実装しています。このアルゴリズムは、各スーパーバーテックス (スーパーバーテックスは接続されたコンポーネントであり、最初の反復では単なる頂点です) の最小重みエッジを見つけて、MST に追加します。エッジが追加されると、接続コンポーネントが更新され、グラフ内のすべての頂点が 1 つの接続コンポーネントになるまで、find-min-edge と merge-supervertices プロセスが繰り返されます。

各スーパーバーテックスの find-min-edge は並列に実行できるので、OpenMP を使用してこれを実行したいと考えています。これは、omp for並列find-minに使用したいループです。

int index[NUM_VERTICES];
#pragma omp parallel private(nthreads, tid, index, min) shared(minedgeindex, setcount, forest, EV, umark)
{
#pragma omp for
  for(int k = 0; k < setcount; k++){  //iterate over supervertices, omp for here

        min = 9999;
        std::fill_n(index, NUM_VERTICES, -1);

    /* Gets minimum edge for each supervertex */
    for(int i = 0; i < NUM_VERTICES; i++) {
         if(forest[i]->mark == umark[k]){    //find vertices with mark k
            for(int j = 0; j < NUM_EDGES; j++) {    
//check min edge for each vertex in the supervertex k
                if(EV[j].v1==i){
                    if(Find(forest[EV[j].v1])!= Find(forest[EV[j].v2])){
                            if(EV[j].w <= min ){
                                    min = EV[j].w;
                                    index[k] = j;
                                    break;  //break looping over edges for current vertex i, go to next vertex i+1
                            }
                    }
                }
            }
         }

    }   //end finding min disjoint-connecting edge for the supervertex with mark k

        if(index[k] != -1){
            minedgeindex.insert(minedgeindex.begin(), index[k]);
        }

    }       //omp for end
}

私は OpenMP を初めて使用するため、現在、期待どおりに動作させることができません。

このコード ブロックで行っていることを簡単に説明します setcount。 は超頂点の数です。EVすべてのエッジを含むベクトルです (Edgeは以前に定義した構造体でv1, v2, wあり、接続する 2 つのノードとその重みに対応する属性を持ちます)。minedgeindexはベクトルです。各スレッドが各連結成分の最小エッジを見つけ、最小エッジのインデックス (インデックス j in EV) をベクトルminedgeindexに同時に追加するようにします。minedgeindexだから共有するべきだと思います。forestは各頂点の構造体であり、umarkどのスーパーバーテックスにあるかを示すセット マークがあります。すべてのスーパーバーテックスをマークするために使用Union-Findしますが、この omp コードのブロックでは関係ありません。

このコード ブロックに必要な最終的な目標はminedgeindex、各スーパーバーテックスのすべての最小エッジを含む正しいベクトルを提供することです。

より明確にし、グラフの背景を無視するために、私は数値の大きなベクトルを持っているだけで、それらを一連のセットに分けます。次に、数値の各セットの最小値を見つけてインデックスを返すためにいくつかの並列スレッドが必要ですそれらの分は、 vector に保存しますminedgeindex。

さらに明確にする必要がある場合は、私に聞いてください。この作業を手伝ってください。主な問題は、私が正しくやっているかわからないプライベート変数と共有変数の宣言だと思います。

前もって感謝します！

4

2 に答える 2

2

並列ブロックの外側に配列を割り当ててからそれをプライベートに宣言してもうまくいきません。

編集：indexコードをもう一度読んだ後、非公開であるべきではないようです。その場合、(あなたがしたように) 並列ブロックの外側で宣言するだけで、プライベートに宣言しないでください。しかし、インデックスを配列にする必要があるかどうかはわかりません。private int として宣言するだけでよいと思います。

さらに、あなたがしたように埋めることはできませんminedgeindex。これにより、競合状態が発生します。クリティカルセクションに配置する必要があります。個人的にはpush_back、非効率的であるため、配列の先頭から挿入しないようにして使用します。

一部の人々は、すべてを共有および非公開と明示的に宣言することを好みます。標準 C では、少なくともプライベートでは、これを行う必要があります。ただし、C99/C++ の場合、これは必要ありません。必要な場合にのみ共有/プライベートを宣言することを好みます。並列領域の外側はすべて共有され (並列ループで使用されるインデックスでない限り)、内側はすべて非公開です。これを念頭に置いておけば、データの共有または非公開を明示的に宣言する必要はほとんどありません。

    //int index[NUM_VERTICES]; //index is shared
    //std::fill_n(index, NUM_VERTICES, -1);
    #pragma omp parallel
    {   
        #pragma omp for
        for(int k = 0; k < setcount; k++){  //iterate over supervertices, omp for here
            int min = 9999; // min is private
            int index = -1;

            //iterate over supervertices

            if(index != -1){
                #pragma omp critical
                minedgeindex.insert(minedgeindex.begin(), index);
                //minedgeindex.insert(minedgeindex.begin(), index[k]);
            }
        }
    }

ここでコードが機能するようになったので、おそらく速度を上げるためのいくつかの提案があります。

criticalループ内で宣言を使用すると、非常に非効率になる可能性があります。プライベート配列 (std::vector) を埋めてから、並列ループの後でそれらをマージすることをお勧めします (ただし、まだ並列ブロック内にあります)。ループには、必要のない暗黙のバリアがあります。これは で削除できますnowait。

クリティカル セクションとは無関係に、各最小値を見つけるまでの時間は反復ごとに異なる可能性があるため、検討することをお勧めしますschedule(dynamic)。次のコードはこれをすべて行います。すべてではないにしても、これらの提案のいくつかのバリエーションにより、パフォーマンスが向上する可能性があります。

#pragma omp parallel
{
    vector<int> minedgeindex_private;
    #pragma omp for schedule(dynamic) nowait
    for(int k = 0; k < setcount; k++){  //iterate over supervertices, omp for here
        int min = 9999;
        int index = -1;

        //iterate over supervertices

        if(index != -1){
            minedgeindex_private.push_back(index);
        }
    }
    #pragma omp critical
    minedgeindex.insert(
        minedgeindex.end(),
        minedgeindex_private.begin(), minedgeindex_private.end());
}
于 2013-08-29T13:48:19.920 に答える