平行,但速度较慢

Question

我正在使用monte carlo方法来计算pi,并使用并行编程和openmp进行基本体验

问题是,当我使用1个线程,x次迭代时,总是比n次线程,x次迭代运行得更快.谁能告诉我为什么？

例如,代码像"a.out 1 1000000"一样运行,其中1是线程,1000000是迭代

include <omp.h>
include <stdio.h>
include <stdlib.h>
include <iostream>
include <iomanip>
include <math.h>

using namespace std;

int main (int argc, char *argv[]) {

double arrow_area_circle, pi;
float xp, yp;
int i, n;
double pitg= atan(1.0)*4.0; //for pi error
cout << "Number processors: " << omp_get_num_procs() << endl;

//Number of divisions
iterarions=atoi(argv[2]); 
arrow_area_circle = 0.0;

#pragma omp parallel num_threads(atoi(argv[1]))
{
srandom(omp_get_thread_num());

#pragma omp for private(xp, yp) reduction(+:arrow_area_circle) //*,/,-,+
for (i = 0; i < iterarions; i++) {
    xp=rand()/(float)RAND_MAX;
    yp=rand()/(float)RAND_MAX;

    if(pow(xp,2.0)+pow(yp,2.0)<=1) arrow_area_circle++;
}
}

pi = 4*arrow_area_circle / iterarions;
cout << setprecision(18) << "PI = " << pi << endl << endl;
cout << setprecision(18) << "Erro = " << pitg-pi << endl << endl;

return 0;
}

Answer 1

如果您在更多线程中完成工作,那么像这样的CPU密集型任务将比系统中的CPU更慢.如果您在单个CPU系统上运行它,您肯定会看到有多个线程的减速.这是因为操作系统必须在各种线程之间切换 - 这是纯粹的开销.理想情况下,您应该像这样的任务具有相同数量的线程.

另一个问题是在线程之间共享arrow_area_circle.如果在每个核心上运行了一个线程,则递增arrow_area_circle将使其他核心的高速缓存中的副本无效,从而导致它们必须重新获取.arrow_area_circle ++应该花费几个周期才需要几十个或几百个周期.尝试为每个线程创建一个arrow_area_circle并在最后组合它们.

编辑:Joe Duffy刚刚发布了一篇关于在线程之间共享数据的成本的博客文章.

Answer 2

看起来您正在使用某种自动并行化编译器.我假设您的系统中有超过1个核心/ CPU(因为这太明显了 - 并且Pentium 4上的超线程不会被视为拥有两个内核,无论英特尔的营销会让您相信什么.)我看到有两个问题.第一个是微不足道的,可能不是你的问题:

1. 如果变量arrow_area_circle在进程之间共享,那么执行arrow_area_circle ++的行为将导致使用互锁指令以原子声音的方式同步值.您应该增加一个"私有"变量,然后在结尾处将该值仅添加到公共arrow_area_circle变量一次,而不是在内循环中递增arrow_area_circle.

2. 为了正常运行,rand()函数必须在内部执行临界区.原因是它的内部状态/种子是一个静态共享变量; 如果不是这样,那么两个不同的进程有可能以非常高的概率从rand()获得相同的输出,只是因为它们几乎同时调用了rand().这意味着rand()运行缓慢,特别是当更多线程/进程同时调用它时.与arrow_area_circle变量(只需要原子增量)不同,rand()必须调用真正的临界区,因为它的状态更新更复杂.要解决此问题,您应该获取自己的随机数生成器的源代码,并将其与私有种子或状态一起使用.大多数编译器中标准rand()实现的源代码都可以广泛使用.

我还想指出你使用pow(,)函数执行与x*x相同的操作.后者比前者快300倍.虽然这一点与您提出的问题无关.:)

Answer 3

上下文切换。