使用OpenMP为并行的集合找到最小值，C ++ [英] Use OpenMP to find minimum for sets in parallel, C++

问题描述

我在C ++中实现Boruvka的算法来找到图表的最小生成树。该算法针对每个超级数据找到最小权重边（超级数是连接的组分，它只是第一次迭代中的一个顶点），并将它们添加到MST中。一旦边添加，我们更新连接的组件，并重复查找最小边和合并超处理，直到图中的所有顶点都在一个连接的组件。

I'm implementing Boruvka's algorithm in C++ to find minimum spanning tree for a graph. This algorithm finds a minimum-weight edge for each supervertex (a supervertex is a connected component, it is simply a vertex in the first iteration) and adds them into the MST. Once an edge is added, we update the connected components and repeat the find-min-edge, and merge-supervertices process, until all the vertices in the graph are in one connected component.

由于每个supervertex的find-min-edge可以并行完成，我想使用OpenMP来做到这一点。这是 omp for 循环我想用于并行查找。

Since find-min-edge for each supervertex can be done in parallel, I want to use OpenMP to do this. Here is the omp for loop I would like to use for parallel 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，我目前无法按照预期的方式工作。

Since I'm new to OpenMP, I currently cannot make it work as I expected.

让我简单解释一下我在这个程式码块中所做的事：
setcount 是超级引号的数量。 是一个包含所有边的向量（ Edge 是我之前定义的结构，具有属性 v1，v2，w ，它们对应于它连接的两个节点及其权重）。 minedgeindex 是一个向量，我想让每个线程为每个连接的组件找到最小边，并添加索引（ EV ）的min边缘到向量 minedgeindex 。所以我认为 minedgeindex 应该共享。 forest 是每个顶点的结构，它有一个集合标记 umark ，表明它是在哪个supervertex。 c $ c> Union-Find 来标记所有超级标题，但它在这个omp代码块中不相关。

Let me briefly explain what I'm doing in this block of code: setcount is the number of supervertices. EV is a vector containing all edges (Edge is a struct I defined previously, has attributes v1, v2, w which correspond to the two nodes it connects and its weight). minedgeindex is a vector, I want each thread to find min edge for each connected component, and add the index (index j in EV) of the min edge to vector minedgeindex at the same time. So I think minedgeindex should be shared. forest is a struct for each vertex, it has a set mark umark indicating which supervertex it's in. I use Union-Find to mark all supervertices, but it is not relevant in this block of omp code.

需要这个代码块是给我正确的向量 minedgeindex 包含每个supervertex的所有min边。

The ultimate goal I need for this block of code is to give me the correct vector minedgeindex containing all min edges for each supervertex.

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

To be more clear and ignore the graph background, I just have a large vector of numbers, I separate them into a bunch of sets, then I need some parallel threads to find the min for each set of numbers and give me back the indices for those mins, store them in a vector minedgeindex.

如果你需要更多的澄清，请帮助我做这个工作，我认为主要的问题是私人和共享变量的声明，我不知道如果我做的正确。

If you need more clarification just ask me. Please help me make this work, I think the main issue is the declaration of private and shared variables which I don't know if I'm doing right.

谢谢提前！

推荐答案

在并行块外部分配数组，然后声明它是私有的不会工作。

Allocating an array outside of a parallel block and then declaring it private is not going to work.

修改：再次阅读代码后， index 甚至是私人的。在这种情况下，你应该声明它在并行块之外（如你所做），但不声明它是私有的。但我不知道你甚至需要索引成为一个数组。我认为你只能将它声明为一个私人int。

After reading through your code again it does not appear that index should even be private. In that case you should just declare it outside the parallel block (as you did) but not declare it private. But I am not sure you even need index to be an array. I think you can just declare it as an private int.

此外，你不能填充 minedgeindex 像你没有。这导致竞争条件。你需要把它放在一个关键的部分。我个人会尝试使用 push_back ，而不是从数组的开头插入，因为效率低下。

Additionally, you can't fill minedgeindex like you did. That causes a race condition. You need to put it in a critical section. Personally I would try and use push_back and not insert from the beginning of the array since that's inefficient.

更愿意明确声明所有共享和私有。在标准C你必须这样做，至少对于私人。但对于C99 / C ++这不是必要的。我更喜欢只声明共享/私有，如果有必要。在并行区域之外的所有内容都是共享的（除非它是并行循环中使用的索引），并且其中的一切都是私有的。如果您记住这一点，您很少必须显式声明共享或私有数据。

Some people prefer to explicitly declare everything shared and private. In standard C you sorta have to do this, at least for private. But for C99/C++ this is not necessary. I prefer to only declare shared/private if it's necessary. Everything outside of the parallel region is shared (unless it's an index used in a parallel loop) and everything inside is private. If you keep that in mind you rarely have to explicitly declare data shared or private.

    //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]);
            }
        }
    }

这里有一些建议，或许加速。

Now that the code is working here are some suggestions to perhaps speed it up.

使用循环中的 critical 声明可能效率很低。我建议填充一个私有数组（std :: vector），然后在并行循环后（但仍然在并行块中）合并它们。该循环具有不必要的隐式屏障。这可以用 nowait 删除。

Using the critical declaration inside the loop could be very inefficient. I suggest filling a private array (std::vector) and then merging them after the parallel loop (but still in the parallel block). The loop has an implicit barrier which is not necessary. This can be removed with nowait.

独立于关键部分，查找每个最小值的时间可以随每次迭代而变化，因此您可能需要考虑 schedule（dynamic）。下面的代码做到这一切。这些建议的一些变化（如果不是全部）可能会提高您的效果。

Independent of the critical section the time to find each minimum can vary per iteration so you may want to consider schedule(dynamic). The following code does all this. Some variation of these suggestions, if not all, may improve your performance.

#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());
}

这篇关于使用OpenMP为并行的集合找到最小值，C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！