c++ - OpenMP 手工缩减指令
问题描述
我正在研究阶乘函数。我必须使用 OpenMP 编写它的并行版本。
double sequentialFactorial(const int N) {
double result = 1;
for(int i = 1; i <= N; i++) {
result *= i;
}
return result;
}
众所周知,该算法可以使用归约技术有效地并行化。
我知道reduction
条款的存在(标准§§ 2.15.3.6)。
double parallelAutomaticFactorial(const int N) {
double result = 1;
#pragma omp parallel for reduction(*:result)
for (int i=1; i <= N; i++)
result *= i;
return result;
}
但是,我想尝试实施“手工制作”的还原技术。
double parallelHandmadeFactorial(const int N) {
// maximum number of threads
const int N_THREADS = omp_get_max_threads();
// table of partial results
double* partial = new double[N_THREADS];
for(int i = 0; i < N_THREADS; i++) {
partial[i] = 1;
}
// reduction tecnique
#pragma omp parallel for
for(int i = 1; i <= N; i++) {
int thread_index = omp_get_thread_num();
partial[thread_index] *= i;
}
// fold results
double result = 1;
for(int i = 0; i < N_THREADS; i++) {
result *= partial[i];
}
delete partial;
return result;
}
我希望最后两个片段的性能非常相似,并且比第一个更好。但是,平均性能是:
Sequential Factorial 3500 ms
Parallel Handmade Factorial 6100 ms
Parallel Automatic Factorial 600 ms
我错过了什么吗?
感谢@Gilles 和@PW,此代码按预期工作
double parallelNoWaitFactorial(const int N) {
double result = 1;
#pragma omp parallel
{
double my_local_result = 1;
// removing nowait does not change the performance
#pragma omp for nowait
for(int i = 1; i <= N; i++)
my_local_result *= i;
#pragma omp atomic
result *= my_local_result;
}
return result;
}
解决方案
如果数组元素碰巧共享一个缓存行,这会导致错误共享,从而进一步导致性能下降。
为了避免这种情况:
- 使用私有变量
double partial
而不是double
数组partial
。 - 使用
partial
每个线程的结果来计算result
关键区域中的最终结果 - 这个 final
result
应该是一个不是并行区域私有的变量。
关键区域将如下所示:
#pragma omp critical
result *= partial;
推荐阅读
- asp.net - Azure Web 应用,自定义状态代码说明不起作用
- c - 我无法完美地完成这个循环
- android - Crashlytics 报告上传因 java.lang.OutOfMemoryError 而崩溃
- c# - 请为此 CountNumbers 算法建议不同的方法
- matlab - Matlab 编辑器变得非常慢,多项式方程具有“组合”(大量)项
- reactjs - 在 ReactJs 中使用 props 访问对象
- android - 颤振 - 重新加载时奖励视频广告错误:“ad_not_loaded,奖励视频显示失败,未加载广告,null)”
- r - R熔化/收集文件,带有2个标题行到属性中
- ruby - 使用 Hash 中的键值对作为问答
- scheme - 方案中的 Luhn 算法