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 ++;
}

有关调度语法的信息可通过MSDN和Wikipedia获得。

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

还要感谢Jens Gustedt和Mahmoud 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 回答