OpenMP嵌套循环

Question

我正在尝试使用OpenMP进行编程。看看这段代码片段：

#pragma omp parallel
{
    for( i =0;i<n;i++)
    {
        doing something
    }
}

并且

for( i =0;i<n;i++)
{
  #pragma omp parallel
  {
     doing something
  }
}

为什么第一个比第二个慢得多（大约是5倍）？从理论上讲，我认为第一个必须更快，因为并行区域只创建一次，而不像第二个那样创建n次？

有人能为我解释一下吗？

我想并行化的代码具有以下结构：

for(i=0;i<n;i++) //wont be parallelizable
{
  for(j=i+1;j<n;j++)  //will be parallelized
  {
    doing sth.
  }

  for(j=i+1;j<n;j++)  //will be parallelized
    for(k = i+1;k<n;k++)
    {
      doing sth.
    }

}

我写了一个简单的程序来测量时间并重现我的结果。

#include <stdio.h>
#include <omp.h>

void test( int n)
{
  int i ;
  double t_a = 0.0, t_b = 0.0 ;


  t_a = omp_get_wtime() ;

  #pragma omp parallel
  {
    for(i=0;i<n;i++)
    {

    }
  }

  t_b = omp_get_wtime() ;

  for(i=0;i<n;i++)
  {
    #pragma omp parallel
    {
    }
  }

  printf( "directive outside for-loop: %lf\n", 1000*(omp_get_wtime()-t_a)) ;
  printf( "directive inside for-loop: %lf \n", 1000*(omp_get_wtime()-t_b)) ;
}

int main(void)
{
  int i, n   ;
  double t_1 = 0.0, t_2 = 0.0 ;

  printf( "n: " ) ;
  scanf( "%d", &n ) ;

  t_1 = omp_get_wtime() ;

  #pragma omp parallel
  {
    for(i=0;i<n;i++)
    {

    }
  }

  t_2 = omp_get_wtime() ;

  for(i=0;i<n;i++)
  {
    #pragma omp parallel
    {
    }
  }

  printf( "directive outside for-loop: %lf\n", 1000*(omp_get_wtime()-t_1)) ;
  printf( "directive inside for-loop: %lf \n", 1000*(omp_get_wtime()-t_2)) ;

  test(n) ;

  return 0 ;
}

如果我用不同的n开始，我总是会得到不同的结果。

n: 30000
directive outside for-loop: 0.881884
directive inside for-loop: 0.073054 
directive outside for-loop: 0.049098
directive inside for-loop: 0.011663 

n: 30000
directive outside for-loop: 0.402774
directive inside for-loop: 0.071588 
directive outside for-loop: 0.049168
directive inside for-loop: 0.012013 

n: 30000
directive outside for-loop: 2.198740
directive inside for-loop: 0.065301 
directive outside for-loop: 0.047911
directive inside for-loop: 0.012152 



n: 1000
directive outside for-loop: 0.355841
directive inside for-loop: 0.079480 
directive outside for-loop: 0.013549
directive inside for-loop: 0.012362 

n: 10000
directive outside for-loop: 0.926234
directive inside for-loop: 0.071098 
directive outside for-loop: 0.023536
directive inside for-loop: 0.012222 

n: 10000
directive outside for-loop: 0.354025
directive inside for-loop: 0.073542 
directive outside for-loop: 0.023607
directive inside for-loop: 0.012292 

你能帮我解释这个差别吗？！

使用你的版本得到的结果：

Input n: 1000
[2] directive outside for-loop: 0.331396
[2] directive inside for-loop: 0.002864 
[2] directive outside for-loop: 0.011663
[2] directive inside for-loop: 0.001188 
[1] directive outside for-loop: 0.021092
[1] directive inside for-loop: 0.001327 
[1] directive outside for-loop: 0.005238
[1] directive inside for-loop: 0.001048 
[0] directive outside for-loop: 0.020812
[0] directive inside for-loop: 0.001188 
[0] directive outside for-loop: 0.005029
[0] directive inside for-loop: 0.001257 

- Biler

---

提供的信息太少了，我们不能提供有用的帮助。而且第一个问题只需要减少一层 {}，就可以使用 #pragma omp parallel for（注意 pragma 中的 for）了吧？ - Jens Gustedt

这个for循环不应该是并行的！“做某事”的部分将来会包含嵌套的for循环。在我的C代码中，for循环是空的。问题只是什么是放置openmp指令的最佳方式。 - Biler

你的测量方式有误。应该使用1000*(t_2-t_1)而不是1000*(omp_get_wtime()-t_1)。 - osgx

我的测试在您的电脑上运行得非常快，您无法测量其粗略程度。请查看我的答案更新。 - osgx

Answer 1

因为并行区域只创建一次，而不像第二个那样创建n次？

有点像。这个结构

#pragma omp parallel
{
}

这也意味着在'{'上将工作项分配给线程，并在'}'上将线程返回到线程池。它有很多线程间通信。此外，默认情况下，等待线程将通过操作系统进入睡眠状态，唤醒线程需要一些时间。

关于您的中间示例：您可以尝试使用for的外部并行性限制...

#pragma omp parallel private(i,k)
{
for(i=0;i<n;i++) //w'ont be parallelized
{
  #pragma omp for
  for(j=i+1;j<n,j++)  //will be parallelized
  {
    doing sth.
  }
  #pragma omp for    
  for(j=i+1;j<n;j++)  //will be parallelized
    for(k = i+1;k<n;k++)
    {
      doing sth.
    }
  // Is there really nothing? - if no - use:
  // won't be parallelized
  #pragma omp single
  { //seq part of outer loop
      printf("Progress... %i\n", i); fflush(stdout);
  }

  // here is the point. Every thread did parallel run of outer loop, but...
  #pramga omp barrier

  //  all loop iterations are syncronized:
  //       thr0   thr1  thr2
  // i      0      0     0
  //     ----   barrier ----
  // i      1      1     1
  //     ----   barrier ----
  // i      2      2     2
  // and so on
}
}

一般而言，在for循环嵌套的最高层（外层）放置并行性比放置在内部循环更好。如果您需要一些代码的顺序执行，请使用高级编译指示（例如omp barrier、omp master或omp single）或omp_locks进行此代码。任何一种方式都比多次启动omp parallel快。

- osgx

---

谢谢您的回复。为什么要将变量i明确声明为共享变量？这不是默认情况吗？根据我给出的整个示例，您是否会像上次发布的那样设置openmp指令？我想知道通常和一般情况下的最佳方式是什么。 - Biler

请重新阅读答案，因为最初版本是错误的。仅在 omp for 指示符后的迭代变量将被更改可见性。您还可以使用类似 C++ 风格的循环语句：for(int i=0; i<n;i++); - osgx

谢谢，这正是我从OpenMP书中记得的，但是在没有内部for循环的情况下测试，它仍然比另一种尝试慢5倍。另一个版本几乎和串行版本一样快。为什么？我不明白。 - Biler

Biler，什么是“other attempt”？第一段代码吗？你测试了什么“n”？运行时间是多少？线程数等于CPU数吗？它们是什么？你使用的编译器和编译器版本是什么？ - osgx

另一个尝试是在外层for循环内使用#pragma omp parallel。线程数量相等。 - Biler

Answer 2

您的完整测试非常错误。您计算了两部分代码的时间和第二部分的时间，而不是第一部分的时间。另外，printf的第二行测量了第一个printf的时间。

第一次运行非常缓慢，因为这里有线程启动时间、内存初始化和缓存效应。此外，在几个并行区域之后，omp的启发式算法可能会自动调整。

我的版本测试：

$ cat test.c
#include <stdio.h>
#include <omp.h>

void test( int n, int j)
{
  int i ;
  double t_a = 0.0, t_b = 0.0, t_c = 0.0 ;
  t_a = omp_get_wtime() ;
  #pragma omp parallel
  {
    for(i=0;i<n;i++) { }
  }
  t_b = omp_get_wtime() ;
  for(i=0;i<n;i++) {
    #pragma omp parallel
    { }
  }
  t_c = omp_get_wtime() ;
  printf( "[%i] directive outside for-loop: %lf\n", j, 1000*(t_b-t_a)) ;
  printf( "[%i] directive inside for-loop: %lf \n", j, 1000*(t_c-t_b)) ;
}

int main(void)
{
  int i, n, j=3  ;
  double t_1 = 0.0, t_2 = 0.0, t_3 = 0.0;
  printf( "Input n: " ) ;
  scanf( "%d", &n ) ;
  while( j --> 0 ) {
      t_1 = omp_get_wtime();
      #pragma omp parallel
      {
        for(i=0;i<n;i++) { }
      }

      t_2 = omp_get_wtime();

      for(i=0;i<n;i++) {
        #pragma omp parallel
        { }
      }
      t_3 = omp_get_wtime();
      printf( "[%i] directive outside for-loop: %lf\n", j, 1000*(t_2-t_1)) ;
      printf( "[%i] directive inside for-loop: %lf \n", j, 1000*(t_3-t_2)) ;
      test(n,j) ;
  }
  return 0 ;
}

我对程序本身进行了每个 n 的 3 次运行。

结果：

$ ./test
Input n: 1000
[2] directive outside for-loop: 5.044824
[2] directive inside for-loop: 48.605116
[2] directive outside for-loop: 0.115031
[2] directive inside for-loop: 1.469195
[1] directive outside for-loop: 0.082415
[1] directive inside for-loop: 1.455855
[1] directive outside for-loop: 0.081297
[1] directive inside for-loop: 1.462352
[0] directive outside for-loop: 0.080528
[0] directive inside for-loop: 1.455786
[0] directive outside for-loop: 0.080807
[0] directive inside for-loop: 1.467101

只有第一次运行test()会受到影响。对于test和main()，所有后续结果都是相同的。

更好和更稳定的结果来自这样的运行（我使用了gcc-4.6.1和静态构建）

$ OMP_WAIT_POLICY=active GOMP_CPU_AFFINITY=0-15 OMP_NUM_THREADS=2  ./test
Input n: 5000
[2] directive outside for-loop: 0.079412
[2] directive inside for-loop: 4.266087
[2] directive outside for-loop: 0.031708
[2] directive inside for-loop: 4.319727
[1] directive outside for-loop: 0.047563
[1] directive inside for-loop: 4.290812
[1] directive outside for-loop: 0.033733
[1] directive inside for-loop: 4.324406
[0] directive outside for-loop: 0.047004
[0] directive inside for-loop: 4.273143
[0] directive outside for-loop: 0.092331
[0] directive inside for-loop: 4.279219

我设置了两个OMP性能环境变量，并将线程数限制为2。

此外，你的“并行”循环是错误的。（我在我的^^^版本中重现了这个错误）这里共享了i变量：

      #pragma omp parallel
      {
        for(i=0;i<n;i++) { }
      }

您应该将其设置为：

您应该这样设置

。

      #pragma omp parallel
      {
        for(int local_i=0;local_i<n;local_i++) { }
      }

更新7，n=1000时的结果如下：

[2] directive inside for-loop: 0.001188 
[1] directive outside for-loop: 0.021092
[1] directive inside for-loop: 0.001327 
[1] directive outside for-loop: 0.005238
[1] directive inside for-loop: 0.001048 
[0] directive outside for-loop: 0.020812
[0] directive inside for-loop: 0.001188 
[0] directive outside for-loop: 0.005029
[0] directive inside for-loop: 0.001257 

您的代码输出的0.001或0.02是秒数乘以1000后的毫秒数。这相当于大约1微秒或20微秒左右。某些系统时钟的粒度（time实用程序的user time或system time输出字段）为1毫秒、3毫秒或10毫秒。1微秒等于2000-3000个CPU时钟周期（对于2-3GHz CPU）。因此，如果没有特殊设置，您无法测量如此短的时间间隔。您应该：

1. 禁用CPU的节能功能（Intel SpeedStep，AMD???），这会通过降低其时钟（频率）将CPU置于较低功率状态；
2. 禁用CPU的动态超频（Intel turbostep）；
3. 不借助操作系统进行时间测量，例如通过读取TSC (rdtsc汇编指令)；
4. 在rdtsc之前和之后添加一个cpuid指令（或其他指令）来禁止乱序CPU上的指令重新排序（当前世代中只有Atom不是OOO CPU）；
5. 在开始测试之前，确保系统完全空闲（两个CPU的CPU负载均为0%）；
6. 以非交互方式重写测试（不要使用scanf等待用户输入，而是通过argv [1]传递n）；
7. 不要使用Xserver和慢终端输出结果；
8. 使中断数量更低（关闭网络，物理上；不要在后台播放电影，不要触摸鼠标和键盘）；
9. 进行大量运行（我的程序中j = 100），并对结果进行统计计算。
10. 不要经常运行printf（在测量之间）；它会污染缓存和TLB。将结果内部存储，并在完成所有测量后输出它们。

更新8： 统计意味着：取几个值，7个或更多。丢弃第一个值（如果您有高数量的测量值，则甚至可以丢弃2-3个第一个值）。对它们进行排序。丢弃最大值和最小值的10-20%。计算平均值。字面意思。

double results[100], sum=0.0, mean = 0.0;
int count = 0;
// sort results[5]..results[100] here
for(it=20; it< 85; it ++) {
  count++; sum+= results[it];
}
mean = sum/count;

- osgx

---

哇，谢谢你的快速和详细的回答！噢，是的，时间测量很糟糕...应该注意到这一点。我正在使用gcc 4.4.5。所以，在for循环中初始化i变量时，它不是共享的吗？即使使用您的版本，我仍然得到互补的结果，我不知道为什么。请查看主要问题以获取结果。我在这台机器上有双核处理器！ - Biler

尝试增加j的值并重新运行。是的，如果您编写int i; \n #pragma omp parallel \n {for(i...)} - i将被共享。如果您编写int i; \n #pragma omp parallel for \n {for(i...)}（请注意pragma中的for），i将是私有的。您的时间测量不准确，因为您尝试使用不太精确的系统调用来测量非常短（快）的代码部分。此外，您没有对嘈杂的结果进行任何统计处理。 - osgx

误解...显然，使用pragma中的for循环变量将是私有的。我的意思是你对for(int local_i=0;local_i<n;local_i++)的更正。我看不出有什么区别，而且在需要它们的地方初始化变量不是不好的C编程风格吗？我把j设为20，它收敛了...仍然没有变化。请解释一下可能的统计操作和什么是嘈杂的结果？ - Biler

OMP FOR或OMP PARALLEL FOR会将迭代器更改为“private”；OMP PARALLEL则不会。引用OpenMP 3.0“2.5.1 Loop Construct”第39页第29-30行：“如果此变量本来应该是共享的，那么在循环结构中它隐式地被定义为私有的。”循环结构是（第38页，第11行）“#pragma omp for”。Pragma Omp parallel不会将任何变量更改为私有（标准的第2.4节）。 - osgx