尝试使用 OpenMP 并行化递归函数的冗余计算

Question

我有一个自调用两次的递归函数。我对函数进行并行化的尝试最终奏效了，但在此期间进行了大量冗余计算，从而消除了并行化带来的所有收益。

主程序正在尝试计算辅助图，辅助图是计算图的所有 k 边连通分量所需的中间数据结构。

几个月来我一直在努力解决这个问题，我只是在万不得已的情况下才决定在这里寻求帮助。我将不胜感激为我指明正确方向的任何意见或建议；我不一定要在盘子里寻找解决方案。

我尝试使用#pragma omp single nowait，但这只会导致代码的顺序执行。

我曾尝试使用 cilk_spawn 一次，但这只会导致我的计算机运行内存不足。我想生成了太多进程。

我将问题的精神提取到我粘贴在下面的最小工作示例中。

下面发布的代码将每个计算重复大约八次。我猜八个不同的进程运行一个单独的程序副本，而不是同时处理部分问题。

#include <iostream>
#include <omp.h>
#include <numeric>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;

int foo(std::vector<int> V, int s){
    int n = V.size();

    if (n>1){
    std::cout<<n<<" ";
    std::random_device rd; // obtain a random number from hardware
    std::mt19937 eng(rd()); // seed the generator
    std::uniform_int_distribution<int> distr(0, n-1); // define the range
    int t = 1;

    auto first = V.begin();
    auto mid = V.begin() + (t);
    auto mid_1 = V.begin() + (t);

    std::vector<int> S(first, mid);
    std::vector<int> T(mid_1, V.end());

    #pragma omp parallel
    {
    #pragma omp task
    foo(S, s);
    #pragma omp task
    foo(T, t); 
    }
    }
   return 0;
}



int main(){
    std::vector<int> N(100);
    iota(N.begin(), N.end(), 0);
    int p = foo(N,0);
    return (0);
}

我的目标是让所有processes/threads一起完成递归。

Answer 1

为您的示例应用 OpenMP 任务并行性的正确方法如下。

int foo(std::vector<int> V, int s)
{
    int n = V.size();

    if (n > 1)
    {
        std::cout << n << " ";
        std::random_device rd;                              // obtain a random number from hardware
        std::mt19937 eng(rd());                             // seed the generator
        std::uniform_int_distribution<int> distr(0, n - 1); // define the range
        int t = 1;

        auto first = V.begin();
        auto mid = V.begin() + (t);
        auto mid_1 = V.begin() + (t);

        std::vector<int> S(first, mid);
        std::vector<int> T(mid_1, V.end());

        #pragma omp task
        foo(S, s);
        #pragma omp task
        foo(T, t);
    }
    return 0;
}

int main()
{
    std::vector<int> N(10000);
    std::iota(N.begin(), N.end(), 0);
    #pragma omp parallel
    #pragma omp single
    {
        int p = foo(N, 0);
    }
    return (0);
}

也就是说，特定示例不会显示性能改进，因为它本身非常快并且受内存分配支配。因此，如果您没有看到应用此方法的好处，请随时更新或post一个带有更具体示例的新问题。

尝试使用 OpenMP 并行化递归函数的冗余计算

Redundant computations in attempt to parallelize recursive function with OpenMP

c++

parallel-processing

openmp

cilk-plus