我需要并行计算数字代码π使用莱布尼茨公式π使用OpenMP任务指令。
因此,我得到了一个顺序代码:
double sequential_execution(long long n)
{
long long i;
double factor;
double sum = 0.0;
double startTime = omp_get_wtime();
for (i = 0; i < n; i++) {
factor = (i % 2 == 0) ? 1.0 : -1.0;
sum += factor / (2 * i + 1);
}
double endTime = omp_get_wtime();
printf("Sequential execution took %f seconds\n", endTime - startTime);
sum = 4.0 * sum;
return sum;
}
我的第一个想法是将for循环的内容捕获为n = 100000000的单个任务:
double parallel_execution(long long n)
{
long long i=0;
double factor;
double sum = 0.0;
long long index;
long squareRootN = ceil(sqrt(n));
double startTime = omp_get_wtime();
#pragma omp parallel default(none) private(i,factor) shared(n,sum)
{
#pragma omp single
{
for ( i = 0; i < n; i++) {
#pragma omp task
{
factor = (i % 2 == 0) ? 1.0 : -1.0;
#pragma omp atomic
sum += factor / (2 * i + 1);
}
}
}
}
double endTime = omp_get_wtime();
printf("Parallel execution took %f seconds\n", endTime - startTime);
sum = 4.0 * sum;
return sum;
}
但是顺序执行的方式要快得多(顺序时间:0.3 s,参数时间:87 s)
第二个想法是增加一个任务的粒度并减少任务数量,方法是将一个从0开始执行n-1的for循环拆分为两个嵌套循环,每个循环从0执行到sqrt(n)-1。现在,每个任务都有一个从0到sqrt(n)-1的for循环,并且生成了sqrt(n)任务,再次为n = 100000000。
double parallel_execution(long long n)
{
long long i=0;
double factor;
double sum = 0.0;
long long index;
long squareRootN = ceil(sqrt(n));
double startTime = omp_get_wtime();
#pragma omp parallel default(none) shared(sum,n,squareRootN) private(i,factor,index)
{
#pragma omp single
{
for (i=0;i<squareRootN;i++)
#pragma omp task
{
for (long j=0;j<squareRootN;j++)
{
index = i*squareRootN + j;
if (index > n) break;
factor = (index % 2 == 0)?1.0 : -1.0;
#pragma omp atomic
sum += factor / (2*index + 1);
}
}
}
}
double endTime = omp_get_wtime();
printf("Parallel execution took %f seconds\n", endTime - startTime);
sum = 4.0 * sum;
return sum;
}
现在,我得到了更好的时间,但是又比顺序执行要慢得多(Seq:0.3s,Par:11s)。
在这一点上,我开始认为不可能使用Task指令来加快速度,但是再次,我做错了什么吗,还是有某种方法可以重组问题以获得更好的性能?谢谢
编辑:迄今为止最好的功能:
double parallel_execution(long long n)
{
double factor;
int totalThreads = 0;
long squareRootN = ceil(sqrt(n));
double master_sum = 0;
double *sum;
double startTime = omp_get_wtime();
#pragma omp parallel default(none) shared(sum,n,squareRootN,totalThreads) private(factor)
{
#pragma omp single
{
totalThreads = omp_get_num_threads();
sum = (double*)calloc(totalThreads,sizeof(double));
for (long long i=0;i<squareRootN;i++)
#pragma omp task
{
for (long long j=0;j<squareRootN;j++)
{
long long index = i*squareRootN + j;
if (index > n) break;
factor = (index % 2 == 0)?1.0 : -1.0;
sum[omp_get_thread_num()] += factor / (2*index + 1);
}
}
}
}
for (int i=0;i<totalThreads;i++) master_sum += sum[i];
double endTime = omp_get_wtime();
printf("Parallel execution took %f seconds\n", endTime - startTime);
master_sum*=4;
return master_sum;
}
输入大小:n = 1000000000 Seq。时间:3.19秒标准杆 时间:4 s
您要承担atomic
操作以及任务创建和管理的开销。您可以通过更简单parallel for
的减少获得更好的加速,即:
#pragma omp parallel default(none) shared(n) reduction( + : sum )
for ( i = 0; i < n; i++) {
double factor = (i % 2 == 0) ? 1.0 : -1.0;
sum += factor / (2 * i + 1);
}
我们可以通过预先将几率与偶数分开来稍微改善顺序代码:
#pragma omp parallel default(none) shared(n, sum) nowait
{
#pragma omp for reduction( + : sum )
for (int i = 0; i < n; i+=2 ) {
sum += 1.0 / (2 * i + 1);
}
#pragma omp for reduction( + : sum )
for (int i = 1; i < n; i += 2) {
sum += -1.0 / (2 * i + 1);
}
}
您可以通过使用一个循环来对该循环的每次迭代执行偶数和赔率计算来进一步改善它。
您不需要'i'
从循环开始private
,它将private
在OpenMP中隐式地进行。
如果你真的要使用的任务,你可以尝试通过复制变量,以尽量减少同步开销sum
线程之间,并手动减少它在的结束parallel region
,(我假设n >= 2
,并n
为even
只是为了简单起见):
double sum[total_threads];
#pragma omp parallel default(none) shared(n, sum)
{
int threadID = omp_get_thread_num();
sum[threadID] = 0.0;
#pragma omp single
{
for ( i = 0; i < n; i+=2) {
#pragma omp task
{
sum[threadID] += 1.0 / (2 * i + 1);
sum[threadID] += -1.0 / (2 * (i + 1) + 1);
}
}
}
}
double master_sum = 0.0;
for(int i = 0; i < total_threads; i++)
master_sum += sum[i];
如果您使用的C
是支持OpenMP的编译器,则4.5
可以使用更复杂的构造函数,即taskloop Construct
,并将其与reduction
变量的组合sum
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句