5

我正在学习如何在 C 中使用 OpenMP,作为 HelloWorld 练习,我正在编写一个程序来计算素数。然后我将其并行化如下:

int numprimes = 0;
#pragma omp parallel for reduction (+:numprimes)
for (i = 1; i <= n; i++)
{
    if (is_prime(i) == true)
        numprimes ++;
}

gcc -g -Wall -fopenmp -o primes primes.c -lm我使用(-lm对于math.h我正在使用的函数)编译此代码。然后我在一个上运行这段代码Intel® Core™2 Duo CPU E8400 @ 3.00GHz × 2,正如预期的那样,性能比串行程序要好。

但是,当我尝试在功能更强大的机器上运行它时,问题就来了。(我也尝试手动设置要使用的线程数num_threads,但这并没有改变任何东西。)计算所有素数10 000 000给我以下时间(使用time):

8核机:

real    0m8.230s
user    0m50.425s
sys     0m0.004s

双核机:

real    0m10.846s
user    0m17.233s
sys     0m0.004s

这种模式继续计数更多的素数,具有更多内核的机器显示出轻微的性能提升,但没有我预期的那么多可用内核。(我希望多 4 倍的内核意味着几乎少 4 倍的运行时间?)

计数质数高达50 000 000

8核机:

real    1m29.056s
user    8m11.695s
sys     0m0.017s

双核机:

real    1m51.119s
user    2m50.519s
sys     0m0.060s

如果有人能为我澄清这一点,将不胜感激。

编辑

这是我的主要检查功能。

static int is_prime(int n)
{
  /* handle special cases */
  if      (n == 0) return 0;
  else if (n == 1) return 0;
  else if (n == 2) return 1;

  int i;
  for(i=2;i<=(int)(sqrt((double) n));i++)
    if (n%i==0) return 0;

  return 1;
}
4

3 答案 3

6

这种表现之所以发生,是因为:

  1. is_prime(i)更高的需要更长的时间i,并且
  2. 默认情况下,您的 OpenMP 实现对parallel for没有该schedule子句的构造使用静态调度,即将 for 循环切成大小相等的连续块。

换句话说,编号最高的线程正在执行所有最困难的操作。

使用该子句显式选择更合适的调度类型schedule可以让您在线程之间公平地分配工作。

这个版本会更好的分工:

int numprimes = 0;
#pragma omp parallel for schedule(dynamic, 1) reduction(+:numprimes) 
for (i = 1; i <= n; i++)
{
    if (is_prime(i) == true)
        numprimes ++;
}

有关调度语法的信息可通过MSDNWikipedia获得。

schedule(dynamic, 1)正如高性能标记在他的回答中指出的那样,可能不是最佳的。此OpenMP 白皮书中对调度粒度进行了更深入的讨论。

还要感谢Jens GustedtMahmoud Fayez对这个答案的贡献。

于 2013-03-17T16:30:16.733 回答
3

正如@naroom 所建议的那样,程序的扩展性明显不佳的原因是每次调用is_prime函数的运行时间的可变性。运行时间不会简单地随着 的值而增加i。您的代码显示,一旦i找到第一个因素,测试就会终止,因此最长的运行时间将是具有很少(和较大)因素的数字,包括素数本身。

正如您已经被告知的那样,并行化的默认计划将一次将主循环的迭代分配给可用线程。对于要测试的整数和要使用的 8 个内核的情况,第一个线程将获取要测试5*10^7的整数,第二个线程将获取,依此类推。这将导致线程之间的负载严重不平衡,因为当然,素数不是均匀分布的。1..62500006250001..12500000

与其使用默认调度,不如尝试动态调度。以下语句告诉运行时一次将主循环m迭代的迭代分配给计算中的线程:

#pragma omp parallel for schedule(dynamic,m)

一旦一个线程完成了它的m迭代,它将被赋予m更多的工作。你的诀窍是找到sweet spotfor m。太小,您的计算将被运行时在分配迭代时所做的工作所支配,太大,您的计算将恢复到您已经看到的不平衡负载。

不过请放心,通过完成所有这些工作,您将学到一些有关并行计算的成本和收益的有用课程。

于 2013-03-17T17:39:00.127 回答
1

我认为您的代码需要使用动态,因此每个线程都可以消耗不同数量的迭代,因为您的迭代具有不同的工作负载,因此当前代码是平衡的,这对您的情况无济于事,请尝试一下:

int numprimes = 0;
#pragma omp parallel for reduction (+:numprimes) schedule(dynamic,1)
for (i = 1; i <= n; i++){
    if (is_prime(i) == true)
    ++numprimes;
}
于 2013-03-17T17:27:03.107 回答