假设我有一个f(i)
依赖于索引的函数i
(以及其他无法预先计算的值)。我想填充一个数组,a
以便a[n] = sum(f(i)) from i=0 to n-1
。
编辑:在Hristo Iliev发表评论后,我意识到我正在做的是一个累积/前缀总和。
可以用以下代码编写:
float sum = 0;
for(int i=0; i<N; i++) {
sum += f(i);
a[i] = sum;
}
现在,我想使用OpenMP并行执行此操作。我可以使用OpenMP做到这一点的一种方法是f(i)
并行写出值,然后照顾串行的依赖关系。如果f(i)
函数很慢,则由于非并行循环很简单,因此可以很好地工作。
#pragma omp parallel for
for(int i=0; i<N; i++) {
a[i] = f(i);
}
for(int i=1; i<N; i++) {
a[i] += a[i-1];
}
但是有可能在没有OpenMP非并行循环的情况下执行此操作。但是,我想出的解决方案很复杂,甚至有些棘手。所以我的问题是,使用OpenMP是否有更简单,更轻松的方法来做到这一点?
下面的代码基本上运行了我为每个线程列出的第一个代码。结果是,a
给定线程中的值在一个常量之前都是正确的。我将每个线程的总和保存到suma
带有nthreads+1
元素的数组中。这使我可以在线程之间进行通信,并确定每个线程的常量偏移量。然后,我a[i]
用偏移量校正的值。
float *suma;
#pragma omp parallel
{
const int ithread = omp_get_thread_num();
const int nthreads = omp_get_num_threads();
const int start = ithread*N/nthreads;
const int finish = (ithread+1)*N/nthreads;
#pragma omp single
{
suma = new float[nthreads+1];
suma[0] = 0;
}
float sum = 0;
for (int i=start; i<finish; i++) {
sum += f(i);
a[i] = sum;
}
suma[ithread+1] = sum;
#pragma omp barrier
float offset = 0;
for(int i=0; i<(ithread+1); i++) {
offset += suma[i];
}
for(int i=start; i<finish; i++) {
a[i] += offset;
}
}
delete[] suma;
只需设置一个简单的测试即可f(i) = i
。然后的解是a[i] = i*(i+1)/2
(并且在无穷大处是-1/12)。
您可以使用以下任务将策略扩展到任意数量的子区域,并递归地减少它们:
#include<vector>
#include<iostream>
using namespace std;
const int n = 10000;
const int baseLength = 100;
int f(int ii) {
return ii;
}
int recursiveSumBody(int * begin, int * end){
size_t length = end - begin;
size_t mid = length/2;
int sum = 0;
if ( length < baseLength ) {
for(size_t ii = 1; ii < length; ii++ ){
begin[ii] += begin[ii-1];
}
} else {
#pragma omp task shared(sum)
{
sum = recursiveSumBody(begin ,begin+mid);
}
#pragma omp task
{
recursiveSumBody(begin+mid,end );
}
#pragma omp taskwait
#pragma omp parallel for
for(size_t ii = mid; ii < length; ii++) {
begin[ii] += sum;
}
}
return begin[length-1];
}
void recursiveSum(int * begin, int * end){
#pragma omp single
{
recursiveSumBody(begin,end);
}
}
int main() {
vector<int> a(n,0);
#pragma omp parallel
{
#pragma omp for
for(int ii=0; ii < n; ii++) {
a[ii] = f(ii);
}
recursiveSum(&a[0],&a[n]);
}
cout << n*(n-1)/2 << endl;
cout << a[n-1] << endl;
return 0;
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句