0

我在 C++ 中实现 Boruvka 的算法来找到图的最小生成树。该算法为每个超顶点找到一个最小权重边（一个超顶点是一个连通分量，它只是第一次迭代中的一个顶点）并将它们添加到 MST 中。一旦添加了一条边，我们更新连接的组件并重复 find-min-edge 和 merge-supervertices 过程，直到图中的所有顶点都在一个连接的组件中。

由于每个超顶点的 find-min-edge 可以并行完成，因此我想使用 OpenMP 来执行此操作。这是omp for我想用于并行查找最小值的循环。

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对应于它连接的两个节点及其权重的属性）。minedgeindex是一个向量，我希望每个线程为每个连通分量找到最小边，同时将最小边的索引（索引 j in EV）添加到向量minedgeindex中。所以我觉得minedgeindex应该分享。forest是每个顶点的结构，它有一个设置标记umark，指示它所在的超顶点。我Union-Find用来标记所有超顶点，但它与这块 omp 代码无关。

我需要这个代码块的最终目标是给我一个正确的向量minedgeindex，其中包含每个超顶点的所有最小边。

为了更清楚并忽略图形背景，我只有一个大的数字向量，我将它们分成一堆集合，然后我需要一些并行线程来找到每组数字的最小值并将索引返回给我那些分钟，将它们存储在一个向量minedgeindex中。

如果您需要更多说明，请询问我。请帮我完成这项工作，我认为主要问题是私有和共享变量的声明，我不知道我是否做得对。

先感谢您！

4

2 回答 2

2

在并行块之外分配一个数组，然后将其声明为私有是行不通的。

编辑：再次阅读您的代码后，它似乎不index应该是私有的。在这种情况下，您应该只在并行块之外声明它（就像您所做的那样），但不要将其声明为私有。但我不确定你甚至需要 index 是一个数组。我认为您可以将其声明为私有 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 回答
0

这不会在 openMP 中有效地工作，因为omp for只是在所有线程之间静态地分割工作，即每个线程都获得了超顶点的公平份额。然而，每个超顶点的工作可能是不均匀的，当胎面之间的工作共享不均匀时。

您可以尝试使用dynamic或guided调度 openMP，但更好的是完全避免使用 openMP 并TBB在tbb::parallel_for()避免此问题时使用。

OpenMP 有几个缺点：1）它是基于预处理器的 2）它的功能相当有限（这是我上面强调的）3）它不是针对 C++（特别是 C++11）的标准化

TBB 是一个完全支持 C++11 的纯 C++ 库（无预处理器 hack）。有关更多详细信息，请参阅我对这个问题的回答

于 2013-09-02T17:11:40.697 回答