主页 / coding / 问题 / 79495301
Accepted
smilingbuddha
Asked: 2025-03-09 10:04:21 +0800 CST

在 C 语言中使用 OpenMP 中的包容性扫描语法

  • 772

我想使用 OpenMP 中的包容性扫描操作来实现一个算法。下面是我尝试这样做的描述，但未能获得比温和的加速更多的效果。

包含运算定义如下：对于输入向量，[x1,x2,x3,x4]它输出部分和的序列[x1, x1+x2, x1+x2+x3, x1+x2+x3+x4]。这是一个高度可并行化的操作，表面上看，这已经在 OpenMP 中得到了很好的实现。

我查看了以下参考资料：https://theartofhpc.com/pcse/omp-reduction.html#Scanprefixoperations （手册参考https://www.openmp.org/spec-html/5.0/openmpsu45.html#x68-1940002.9.6现在对我来说似乎太神秘了）

artofhpc 网站说，reduction 子句得到了一个修饰语inscan：

#pragma omp parallel for reduction(inscan,+:sumvar)`

在并行循环的主体中，有一个扫描指令，允许您存储部分结果。对于包含性扫描，reduction 变量在扫描指令之前更新：

  sumvar // update
#pragma omp scan inclusive(sumvar)
  partials[i] = sumvar

我尝试遵循相同的语法，以测量与标准串行缩减相比的性能，结果令人非常失望。我的代码位于文章底部。

在代码中，我只是做了一个简单的测试，考虑一个由区间 [-1,1] 中的随机值组成的 9000 万个非常大的向量，并使用越来越多的线程对其进行扫描并测量加速比。这是我的结果（我在重复运行时得到了相同的答案）。我的笔记本电脑 CPU 有 16 个硬件线程，但总体加速比令人失望，只有 1.36。（我本来期望会有更大的加速比！）

我使用 OpenMP 语法进行缩减的方式有问题吗？

➜  Desktop gcc -fopenmp scantest.c  && ./a.out

NumThreads  Speedup
1        0.458
2        1.173
3        1.424
4        1.686
5        1.635
6        1.501
7        1.522
8        1.499
9        1.455
10       1.416
11       1.395
12       1.393
13       1.352
14       1.336
15       1.353
16       1.357

#include<stdio.h>
#include<omp.h>
#include<math.h>
#include<stdlib.h>
#include<assert.h>

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

  int N = 9e7;     // vector size 
  double* x;                   // vector to reduce
  double* partials_s;          // vector to scan into
  double* partials_p;          // vector to scan into
  
  double end, start;           // timing variables
  double sumvar;
  
  int tmax = argc>1? atoi(argv[1]):35;
  int threadcount ;

  // Allocate space for all vectors
  x           = (double*) malloc(sizeof(double)*N);
  partials_s  = (double*) malloc(sizeof(double)*N);
  partials_p  = (double*) malloc(sizeof(double)*N);
    
  // Populate the input vectors
  for(int i=0 ; i<N ; ++i){
    x[i] = -1+2.0*rand()/(double)RAND_MAX;
    partials_s[i] = 0.0;
    partials_p[i] = 0.0;
  }

  //-----------------------------------------
  // Serial inclusive scan
  //-----------------------------------------
  start = omp_get_wtime(); 
  sumvar = 0.0;
  for(int i=0 ; i<N ; ++i){
      sumvar += x[i];
      partials_s[i] = sumvar;
  }
  end = omp_get_wtime();
  double stime = end-start; // Time to run the serial code


  //-----------------------------------------------------------------------------
  // Performance of parallel inclusive scan. Print ratio of serial/parallel time
  //----------------------------------------------------------------------------
  printf("\nNumThreads  Speedup \n");
  for(threadcount=1;threadcount<=tmax;++threadcount){

    start = omp_get_wtime();

    sumvar = 0.0;
    #pragma omp parallel for num_threads(threadcount) reduction(inscan,+:sumvar)
    for(int i=0 ; i<N ; ++i){

      sumvar = sumvar + x[i]; // updating the value of sumvar
      #pragma omp scan inclusive(sumvar)
      partials_p[i] = sumvar;
    }
    end = omp_get_wtime();
    double ptime = end-start;

    printf("%d \t %.3f\n",threadcount,stime/ptime);

  }

  //for(int i=0 ; i<N ; ++i){
  //  printf("%.4f  %.4f\n", partials_s[i], partials_p[i]);
  //}

  // Deallocate
  free(x);
  free(partials_s);
  free(partials_p);
  
  return 0;
}
c

3 个回答

  1. Best Answer

    TL;DR：这不具有可扩展性，因为这样的扫描操作仅仅受到内存的限制。更具体地说，它受到DRAM 带宽的限制。

    分析

    在主流 PC 上，只有少数核心能够使 DRAM 的带宽饱和。有时，单个核心就可以（通常是具有良好 CPU 和单通道 DRAM 的 PC）。顺序扫描已经是一个内存绑定操作，在我的计算机上（i5-9600KF CPU 和 2 x 3200MHz DDR4-DRAM），它离饱和 DRAM 并不远。事实上，它达到了 24 GiB/s 的吞吐量。理论上，我的 DRAM 仅内存读取可以达到 48 GiB/s，但实际上，读取通常为 40~42 GiB/s，混合读写为 36~38 GiB/s。这意味着顺序代码已经饱和了我 DRAM 带宽的约 65%！

    使用并行代码，我使用 1 个线程达到 20 GiB/s，使用 2 个线程达到 30 GiB/s，使用 3 个线程达到 35 GiB/s，使用 4 个线程达到 36 GiB/s，使用 6 个线程达到 35 GiB/s（因为我只有 6 个核心，所以这是最大值）。我们可以看到，仅 3 个线程就足以几乎饱和我机器上的带宽。2 个线程实际上还不足以饱和它（~80%）。

    事实上，这与您的程序打印的加速相当一致：

    NumThreads  Speedup 
1    0.456
2    0.686
3    0.765     <---- optimal speed-up for the parallel code
4    0.749
5    0.700
6    0.666

    如果线程数超过 3 个，性能实际上会下降。这可能是因为从 CPU 的角度来看，DRAM 访问（以及 L3 缓存的访问）看起来更加随机，而随机访问效率稍低（预取更困难）。此外，缓存破坏会导致从 DRAM 加载更多数据，因此效率会下降，而吞吐量则大致保持稳定。

    还有一件有趣的事情：在我的计算机上，即使有 6 个线程，并行实现实际上也比顺序实现慢！这是因为并行实现需要执行更多工作。事实上，据我所知，并行扫描需要多个内存步骤：例如，一个步骤用于计算部分减少，另一个步骤用于根据之前计算的部分总和计算实际的块扫描。对于这种实现，如果内存已经是瓶颈，则意味着必须从内存中读取更多数据（两倍以上），从而使操作变慢。还有其他可能的实现，但我能想到的所有实现都需要在此循环中从 DRAM 读取/写入更多数据（使用默认的静态调度）。

    注意我使用带有标志的 GCC-fopenmp -O3来编译被分析的程序（-mavx2不影响分析结果）。实际上，GOMP（在我的计算机上用于分析此程序的 GCC 的 OpenMP 实现）显然执行了 2 个读/写步骤，这比上面提到的步骤效率要低一些。通过分析生成的汇编代码，我看到：我们可以在并行代码中看到两个热内存绑定循环，这两个循环似乎执行了一种类似扫描的操作（当然是本地扫描，然后是扫描更新）。这个 2 读/写步骤实现理论上应该慢两倍。这与 OpenMP 实现的加速一致，OpenMP 在 1 个线程的情况下慢了两倍（在您的机器和我的机器上都是如此）。

    可能的优化

    我们可以执行 2 项主要优化来加快速度。然而，这些优化并不容易实施，而且存在重大缺陷。

    首先，由于缓存行写入分配， x86-64 CPU 实际上会读取数据以将其写入 DRAM 。您可以执行非临时流式存储来避免这种情况。只有当您确定写入的数据无法放入缓存中时，这才值得。一般来说，开发人员无法保证这样的事情，除非他们知道目标 CPU 架构或对其做出（有时合理的）假设。例如，他们可以假设 LLC 缓存不大于几百 MiB（事实并非如此，因为有些 CPU 具有大量 LLC 缓存，如 Xeon Phi，未来的 CPU 可能会有这么大的 LLC 缓存）。OpenMP 理论上可以使用该nontemporal子句生成非临时流式存储指令。话虽如此，据我所知，在撰写本文时，主流 OpenMP 实现中尚未实现它。这种优化可以使顺序/并行代码快 50% 左右。

    另一种加快速度的方法是编写自己的更高效的缓存友好型并行实现。您可以逐块读取数据（块可以很好地容纳在 LLC 缓存中）。从内存中读取一个块后，您可以并行计算子块的部分和，然后更有效地计算扫描（因为数据应该已经适合 LLC 缓存，不需要重新加载）。这应该会大大提高并行实现的效率，使其与顺序实现相比更具竞争力（尽管 1 个线程仍然有点慢）。请注意，额外的同步可能会降低此实现的性能。此外，NUMA 效应还会使具有多个 NUMA 节点的机器上的事情变得更加复杂。理想情况下，自己做这样的优化并不好，我认为这应该是 OpenMP 实现的工作……

    这两个优化可以结合在一起。流式存储应该会减少缓存浪费，并稍微提高第二个优化的性能。在我的计算机上，我预计这 2 个优化会使并行实现比提供的顺序实现快两倍。这仍然不是可扩展的，但你对此无能为力，因为操作首先是内存绑定的，而内存绑定代码通常无法扩展。

    • 6

  2. 最初的免责声明：当对这些简单的代码进行基准测试时，您始终需要确保产生可观察到的副作用（printf("%.4f %.4f\n", partials_s[N-1], partials_p[N-1]);），以确保编译器不会优化掉漏洞代码。

    您的问题在每次迭代中都具有数据依赖性，因此很难高效地并行执行。一个简单的并行实现将有效地转化为：

        #pragma omp parallel for num_threads(threadcount) ordered
    for(int i=0 ; i<N ; ++i){
      #pragma omp ordered
      {
        sumvar = sumvar + x[i]; // updating the value of sumvar
        partials_p[i] = sumvar;
      }
    }

    该代码有效地序列化了执行并在迭代步骤之间增加了额外的线程同步成本。

    为了真正并行计算扫描，编译器可以生成将循环迭代分配给线程的代码。第一步，每个线程对本地块执行扫描。第二步，线程确定其线程的偏移量，并需要将偏移量添加到其所有数组值中。正如另一个答案中指出的那样，您的问题是内存受限的，对整个数组添加第二遍并不是很有益。

    那么，这有什么好处呢？OpenMP 通常不适用于分配细粒度和/或内存受限的工作负载。OpenMP 扫描的用例是有一个循环，其中的计算工作要分配给多个线程，因此您需要扫描迭代的结果。

        #pragma omp parallel for num_threads(threadcount) reduction(inscan,+:sumvar)
    for(int i=0 ; i<N ; ++i){
      double ires = sin(i+.5) * cos(i+.5); // calculate something for each iteration
      sumvar = sumvar + ires;
      #pragma omp scan inclusive(sumvar)
      partials_p[i] = sumvar;
    }

    从概念上来说，这可以再次理解为：

        #pragma omp parallel for num_threads(threadcount) ordered
    for(int i=0 ; i<N ; ++i){
      double ires = sin(i+.5) * cos(i+.5); // calculate something for each iteration
      #pragma omp ordered
      {
        sumvar = sumvar + ires; // updating the value of sumvar
        partials_p[i] = sumvar;
      }
    }

    它的扩展性ordered取决于每次迭代中要完成的工作，即计算ires。此外，只有当每次迭代的计算成本相同时，它的扩展性才会很好，因为我们会同步每次迭代。迭代之间的任何不平衡都会影响可扩展性。使用扫描的优点是我们不会在每次迭代之间同步，而只会在最后同步。因此，只要线程之间的不平衡不是系统性的，迭代之间的不平衡就可以平均化。

    由于每次迭代的计算成本都很大，因此最终通过的内存不会那么昂贵。

    gcc -fopenmp -O3 -lm当我在具有 4 核的笔记本电脑上执行上面修改后的代码时，我得到了以下扩展结果：

    NumThreads  Speedup 
1    0.870
2    1.849
3    2.568
4    3.607
5    2.838
6    3.247
7    3.654
8    3.031
9    3.868
10   3.568
11   3.852
12   3.759
13   3.971
14   3.961
15   4.005
16   4.016
    • 2

  3. 我尝试在带宽巨大的 CPU 上运行这个程序，但速度仍然只提高了一到两倍，从 12 个内核开始，之后再也没有提高过。我认为这是扫描的缩减部分实现不当造成的。此外，缩减量高达 20 多个级别，因此需要做大量额外工作，而且缓存行利用率很差。由于循环除了缩减之外完全没有其他工作，因此我确实认为性能会很差。尝试在循环中引入一些标量工作。

    • 1

相关问题