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

Question

>我有一个递归函数，它调用自己两次。我并行化函数的尝试最终会起作用，但在此期间会进行大量冗余计算，从而抹去了并行性的所有收益。

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

几个月来我一直在解决这个问题，我只是决定在这里寻求帮助作为最后的手段。我将不胜感激任何为我指明正确方向的意见或建议;我不一定在盘子上寻找解决方案。

我尝试使用 #pragma omp 单个 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);
}

我的目标是让所有进程/线程协同工作以完成递归。

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

也就是说，特定示例不会显示性能改进，因为它本身非常快，并且以内存分配为主。因此，如果您没有看到应用此功能的好处，请随时使用更具体的示例更新或发布新问题。