OpenMP并行for循环显示性能提升很少

Question

我正在学习如何在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;
}

Answer 1

这种表现正在发生,因为:

1. is_prime(i)需要更长的时间i,并且
2. 对于parallel for没有schedule子句的构造,您的OpenMP实现默认使用静态调度,即它将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 wihtepaper中有一个关于调度粒度的更深入的讨论.

还要感谢Jens Gustedt和Mahmoud Fayez为这个答案做出的贡献.