Ben*_*din 3 c++ multithreading task openmp
我在OpenMP中使用任务编写了一个递归并行函数.虽然它给了我正确的答案并且运行良好但我认为并行性存在问题.与串行解决方案相比,运行时不会在我没有任务的情况下解决的同一个其他并行问题中扩展.当为每个线程打印任务时,它们都在线程0上运行.我正在Visual Studio Express 2013上编译并运行.
int parallelOMP(int n)
{
int a, b, sum = 0;
int alpha = 0, beta = 0;
for (int k = 1; k < n; k++)
{
a = n - (k*(3 * k - 1) / 2);
b = n - (k*(3 * k + 1) / 2);
if (a < 0 && b < 0)
break;
if (a < 0)
alpha = 0;
else if (p[a] != -1)
alpha = p[a];
if (b < 0)
beta = 0;
else if (p[b] != -1)
beta = p[b];
if (a > 0 && b > 0 && p[a] == -1 && p[b] == -1)
{
#pragma omp parallel
{
#pragma omp single
{
#pragma omp task shared(p), untied
{
cout << omp_get_thread_num();
p[a] = parallelOMP(a);
}
#pragma omp task shared(p), untied
{
cout << omp_get_thread_num();
p[b] = parallelOMP(b);
}
#pragma omp taskwait
}
}
alpha = p[a];
beta = p[b];
}
else if (a > 0 && p[a] == -1)
{
#pragma omp parallel
{
#pragma omp single
{
#pragma omp task shared(p), untied
{
cout << omp_get_thread_num();
p[a] = parallelOMP(a);
}
#pragma omp taskwait
}
}
alpha = p[a];
}
else if (b > 0 && p[b] == -1)
{
#pragma omp parallel
{
#pragma omp single
{
#pragma omp task shared(p), untied
{
cout << omp_get_thread_num();
p[b] = parallelOMP(b);
}
#pragma omp taskwait
}
}
beta = p[b];
}
if (k % 2 == 0)
sum += -1 * (alpha + beta);
else
sum += alpha + beta;
}
if (sum > 0)
return sum%m;
else
return (m + (sum % m)) % m;
}
有时我希望对SO的评论可以像答案一样丰富,但唉,事实并非如此.因此,这里有一个长篇评论伪装成答案.
在编写递归OpenMP代码时,一个非常常见的错误似乎并不了解并行区域的工作原理.请考虑以下代码(使用显式任务,因此支持OpenMP 3.0或更新所需):
void par_rec_func (int arg)
{
if (arg <= 0) return;
#pragma omp parallel num_threads(2)
{
#pragma omp task
par_rec_func(arg-1);
#pragma omp task
par_rec_func(arg-1);
}
}
// somewhere in the main function
par_rec_func(10);
这段代码有问题.问题在于,除了顶级调用之外par_rec_func(),在所有其他调用中,将在封闭的外部并行区域的上下文中创建并行区域.这称为嵌套并行性,默认情况下禁用,这意味着顶级域下的所有并行区域将处于非活动状态,即它们将以串行方式执行.由于任务绑定到最里面的并行区域,它们也将以串行方式执行.这段代码会发生什么,它会在顶级调用中产生一个额外的线程(总共两个),par_rec_func()然后每个线程将执行递归树的整个分支(即整个树的一半) .如果在具有64个内核的计算机上运行该代码,其中62个将空闲.为了启用嵌套并行性,必须将环境变量设置OMP_NESTED为true或调用omp_set_nested()并将其传递给true标志:
omp_set_nested(1);
一旦启用了嵌套并行性,就会面临一个新问题.每次遇到嵌套的并行区域时,遇到的线程将生成另一个(因为num_threads(2))或从运行时的线程池中获取一个空闲线程.在每个更深层次的递归中,该程序将需要两倍于前一级别的线程.虽然可以通过OMP_THREAD_LIMIT(另一个OpenMP 3.0功能)设置线程总数的上限,并且除了开销之外,这不是在这种情况下真正想要的.
在这种情况下,正确的解决方案是在单个并行区域的动态范围内使用孤立任务:
void par_rec_func (int arg)
{
if (arg <= 0) return;
#pragma omp task
par_rec_func(arg-1);
#pragma omp task
par_rec_func(arg-1);
// Wait for the child tasks to complete if necessary
#pragma omp taskwait
}
// somewhere in the main function
#pragma omp parallel
{
#pragma omp single
par_rec_func(10);
}
这种方法的优点很多.首先,只创建一个具有指定线程数的并行区域(例如,通过设置OMP_NUM_THREADS或通过任何其他方式).当子任务以递归方式调用par_rec_func()时,只需将新任务添加到并行区域而不生成新线程.这在递归树不平衡的情况下非常有用,因为许多高质量的OpenMP运行时实现了任务窃取,例如线程i可以执行在线程中执行的任务的子任务j,其中i != j.
给定一个像VC++这样的OpenMP 2.0编译器,除了通过使用嵌套并行性来近似上述想法并在某个级别明确禁用它之外,我们做不了多少事情:
void par_rec_func (int arg)
{
if (arg <= 0) return;
int level = omp_get_level();
#pragma omp parallel sections num_threads(2) if(level < 4)
{
#pragma omp section
par_rec_func(arg-1);
#pragma omp section
par_rec_func(arg-1);
}
}
// somewhere in the main function
int saved_nested = omp_get_nested();
omp_set_nested(1);
par_rec_func(10);
omp_set_nested(saved_nested);
omp_get_level()用于确定嵌套级别,该if子句用于在嵌套的第四级或更深级别选择性地停用并行区域.当递归树不平衡时,此解决方案是愚蠢的并且不能很好地工作.
实际问题:
您正在使用Visual Studio 2013.
Visual Studio从未支持超过2.0的OMP版本(参见此处).
OMP任务是OMP 3.0的一项功能(请参阅规范).
因此,使用VS一定意味着没有OMP任务.
如果OMP任务是基本要求,请使用其他编译器.如果OMP不是必要条件,则应考虑使用备用并行任务处理库.Visual Studio包括MS并发运行时,以及在其上构建的并行模式库.我最近从OMP转到了PPL,因为我正在使用VS工作; 它不是一个简单的替代品,但它非常有能力.
我的第二次尝试解决这个问题,由于历史原因再次保留:
所以,问题几乎肯定是你在omp task一个omp parallel地区之外定义你的.
这是一个人为的例子:
void work()
{
#pragma omp parallel
{
#pragma omp single nowait
for (int i = 0; i < 5; i++)
{
#pragma omp task untied
{
std::cout <<
"starting task " << i <<
" on thread " << omp_get_thread_num() << "\n";
sleep(1);
}
}
}
}
如果省略parallel声明,则作业将按顺序运行:
starting task 0 on thread 0
starting task 1 on thread 0
starting task 2 on thread 0
starting task 3 on thread 0
starting task 4 on thread 0
但如果你把它留在:
starting task starting task 3 on thread 1
starting task 0 on thread 3
2 on thread 0
starting task 1 on thread 2
starting task 4 on thread 2
成功,完全正确滥用共享输出资源.
(作为参考,如果省略single声明,每个线程将运行循环,导致在我的4 cpu VM上运行20个任务).
原始答案包括下面的完整性,但不再相关!
在每种情况下,你omp task都是一件简单的事情.它可能会立即运行并完成:
#pragma omp task shared(p), untied
cout << omp_get_thread_num();
#pragma omp task shared(p), untied
cout << omp_get_thread_num();
#pragma omp task shared(p), untied
cout << omp_get_thread_num();
#pragma omp task shared(p), untied
cout << omp_get_thread_num();
因为在开始下一个任务之前你永远不会启动一个长时间运行的任务,所以一切都可能在第一个分配的线程上运行.
也许你打算做这样的事情？
if (a > 0 && b > 0 && p[a] == -1 && p[b] == -1)
{
#pragma omp task shared(p), untied
{
cout << omp_get_thread_num();
p[a] = parallelOMP(a);
}
#pragma omp task shared(p), untied
{
cout << omp_get_thread_num();
p[b] = parallelOMP(b);
}
#pragma omp taskwait
alpha = p[a];
beta = p[b];
}