整理您的数据和代码: 优化和内存 — 第 1 部分

该系列的两篇文章讨论了数据和内存布局如何对性能产生影响,并提出了改进软件性能的具体步骤建议。 这两篇文章中介绍的基本步骤可带来显著的性能提升。 许多关于软件性能优化的文章都解决了某一方面的并行性:分布式内存并行性(如 MPI)、共享内存并行性(如线程)或 SIMD(又称矢量化),但是真正的并行性应对三个方面都进行解决。 虽然这些项目非常重要,但是内存同样重要,而且经常被大家忽略。 软件架构和并行设计的变化会影响内存和性能。

这两篇文章的难度在中等级别。 我们假定读者想要使用常见的 C、C++ 和 Fortran* 编程选项来优化软件性能。 汇编和指令是高级用户使用的编程方式。 作者建议想要使用高级资料的用户去了解一下处理器指令集架构,并阅读一些研究类期刊上的精彩文章来学习一下如何分析和设计数据分区和布局。

整理数据和代码基于两个基本原则:尽可能减少数据移动以及将数据放在要使用的位置附近。 当数据进入或靠近处理器寄存器时,在其从处理器执行单元删除或再次移动前,应尽可能多地使用。

数据分区

我们来考虑一下数据可能会寄存的几个级别。 距离执行单元最近的点是处理器寄存器。 寄存器中的数据可能会立即激活;按照比较或布尔运算进行增量、乘、加运算。 一般而言,多核处理器中的每个核心都有一个私有一级高速缓存(称 L1)。 数据能够非常快地从一级高速缓存移动至寄存器。 可能有许多级高速缓存,通常,最小的末级高速缓存(称 LLC)在处理器的所有内核间共享。 中间级别的高速缓存会因处理器是否共享或私有而呈现差异。 在英特尔平台上,高速缓存负责维护一个平台上的一致性(即使有多个插槽)。 数据从高速缓存移动到寄存器的速度要比数据从主内存获取过来的速度快。

图 1 形象地展示了数据分区、处理器寄存器临近性和相关的访问速度。 数据块距离寄存器越近,移动速度越快,即数据进入寄存器进而执行的延迟越低。 高速缓存的速度最快,即其延迟最低。 主内存次之。 总体上有多个级别的内存,各个级别的内存在第二部分中进行了介绍。 当将页面置换为硬盘或固态盘时,虚拟内存可能会显著减少。 传统的经由互联架构(以太网、infiniband 或其他)进行发送/接收的方式比从本地获取数据的延迟要高。 远程系统上的数据移动通过类似于 MPI 变量的方式访问,其访问速度取决于互联架构 — 以太网、infiniband、英特尔® True Scale 或英特尔® Omni Scale。


图 1. 延迟内存访问,展示相关数据访问速度。

距离执行单元最近的点是处理器寄存器。 考虑到寄存器的数量、将数据加载至寄存器的延迟时间以及内存操作队列的宽度,寄存器中的每个值不可能仅使用一次,加载数据的速度也不可能快到让所有的执行单元全部都运行起来。 当数据靠近执行单元时,应该尽可能再次使用它,直到它从高速缓存或寄存器中移除为止。 事实上,一些变量仅作为变量寄存器存在,从来不会存储到主内存上。 编译器能够很好地识别一个变量作用域何时最适合作为纯寄存器变量,所以不建议在 C/C++ 中使用“寄存器”这一关键词。 编译器已经能够很好地识别该优化,因此可以允许编译器忽略“寄存器”这一关键词。

简要来讲,软件开发人员应该观察代码,思考一下如何使用数据,以及它需要存在多长时间。 问问自己: 我是否应该创建临时变量? 我是否应该创建临时阵列? 我是否需要保留这么多的临时变量? 当实施性能改进流程时,开发人员应该先收集软件性能矩阵,将精力放在模块的数据本地性或使用了绝大部分时间执行代码的代码分支上。 常见的几款性能数据收集实用程序有英特尔® VTune™ Amplifier XE、gprof 和 Tau*。

数据使用和再用

教大家如何使用这两个步骤的一个绝佳示例是矩阵乘法。 针对 3 个 n x n 平方矩阵的矩阵乘法 A = A + B*C 可表示为 3 个简单的嵌套 for 循环,如下所示:

for (i=0;i<n; i++)                      // line 136
   for (j = 0; j<n; j++)                // line 137
     for (k=0;k<n; k++)                 // line 138
         A[i][j] += B[i][k]* C[k][j] ;  // line 139

这种定序方式的主要问题是其包含归约运算(138 行和 139 行)。 139 行左侧是一个单值。 虽然编译器在 138 行处部分展开循环,以填写 SIMD 寄存器的宽度,并通过元素 B 和 C 产生 4 个或 8 个乘积,这些乘积必须相加到一个单值中。 将 4 个或 8 个乘积加到一个位置是一次约减运算,无法提供相同的并行性能或有效利用 SIMD 设备的全部宽度。 尽可能减少使用或不使用约减运算可以提升并行性能。 看到循环左侧出现单值则表示可能会出现约减。 137 一次迭代的数据访问模式如下图 2 所示(i,j=2)。


图 2. 定序;展示矩阵 A 中的单值。

有时,通过重新定序操作可以取消约减。 比如对换两个内部循环的定序。 浮点运算的数量亦是如此。 但是,由于约减运算或将值加到左侧的操作取消,处理器每次都能够利用 SIMD 执行单元的全部宽度和寄存器。 这可以显著提升性能。

for (i=0;i<n; i++)                    // line 136
   for (k = 0; k<n; k++)              // line 137new
     for (j=0;j<n; j++)               // line 138new
       a[i][j] += b[i][k]* c[k][j] ;  // line 139

该操作完成后,元素 A 和 C 将可连续访问。


图 3. 更新的定序,展示连续访问。

最初的 ijk 定序采用的是点积方法。 两个矢量的点积用来计算每个 A 元素的值。ikj 定序使用 saxpy 或 daxpy 运算。 一个矢量的倍数添加到另一个矢量上。 点积和 axpy 运算均为 1 级 BLAS 程序。 ikj 定序中无需约减运算。 C 行的子集乘以矩阵 B 的标量,再加到 A 行的子集上(编译器将根据目标 SIMD 寄存器(SSE4、AVX 或 AVX512)的宽度来决定子集大小)。 循环 137new 一次迭代的内存访问上图 3 所示(同样,i,j=2)。

取消点积视图中的约减运算可显著提升性能。 借助 O2 级优化,英特尔编译器和 gcc* 都可以利用 SIMD 寄存器和执行单元生成矢量代码。 此外,英特尔编译器还可自动置换 jk 循环的顺序。 这可以在编译器优化报告中看到,该报告可使用 opt-report 编译器选件(Linux* 中的 -qopt-report)获取。 优化报告(默认)存入名为 filename.optrpt 的文件。 对于本案例,优化报告包含以下文本片段:

LOOP BEGIN at mm.c(136,4)
   remark #25444: Loopnest Interchanged: ( 1 2 3 ) --> ( 1 3 2 )

该报告还显示,互换循环进行了向量化运算:

LOOP BEGIN at mm.c(137,7)
    remark #15301: PERMUTED LOOP WAS VECTORIZED
 LOOP END

gcc 编译器(版本 4.1.2-55)无法自动执行该循环置换, 需要开发人员手动执行。

此外,将循环分为几块可改进数据再利用,从而帮助提升性能。 在上述展示(图 3)中,对于中间循环每次迭代,引用了两个长度为 n 的矢量(以及标量),这两个矢量的每个元素仅使用一次! 对于较大的 n,将每个矢量元素从中间循环迭代之间的高速缓存中删除是非常常见的。 当将循环划分为多块以提供数据再利用时,性能会再次提升。

最后的代码展示了对换的 j 和 k 循环以及添加的块。 代码每次都是在子矩阵或矩阵块上运行,大小为 blockSize,在这一简单案例中,blockSizen 倍的代码。

for (i = 0; i < n; i+=blockSize)
   for (k=0; k<n ; k+= blockSize)   
      for (j = 0 ; j < n; j+=blockSize)      
         for (iInner = i; iInner<j+blockSize; iInner++)     
            for (kInner = k ; kInner<k+blockSize; kInner++)
               for (jInner = j ; jInner<j+blockSize ; jInner++)
                 a[iInner,jInner] += b[iInner,kInner] *
                    c[kInner, jInner]

在本示例中,循环 j 的一次迭代的数据访问如下:


图 4 块模型展示。

如果块尺寸选择合适,那么可以假定在三个内部循环运行期间,每个块仍在高速缓存内,甚至在 SIMD 寄存器内。 每个值或 A、B、C 元素在从 SIMD 寄存器或高速缓存中删除前都会使用 blockSize 次。 这可将数据复用率提升 blockSize 倍。 当使用中等大小的矩阵时,将很少或不会由于划分块而得到性能提升。 随着矩阵尺寸增加,性能差异也会更加明显。

下表展示了在一个系统上使用不同的编译器测得的性能比率。 请注意,英特尔编译器可在 137 行和 138 行之间自动交换循环。 因此,英特尔编译器在 ijkikj 定序上不会展现出明显的差异。 这还使得英特尔编译器的基准性能更高,因此,最后在基准的基础上的加速看上去更低,这是因为英特尔基准性能已经够快了。

订序

矩阵/模块尺寸

Gcc* 4.1.2 -O2
较之基准的加速度/性能比率

英特尔编译器 16.1 -O2
较之基准的加速度/性能比率

ijk

1600

1.0(基准)

12.32

ikj

1600

6.25

12.33

ikj block

1600/8

6.44

8.44

ijk

4000

1.0(基准)

6.39

ikj

4000

6.04

6.38

ikj block

4000/8

8.42

10.53

表 1. 在 gcc* 和英特尔编译器上测量的性能比。

此处的代码示例并不复杂,两款编译器都可以生成 simd 指令。 这是较旧的 gcc 编译器(我们并非在比较编译器而是在提供一个重要的指导原则),它可帮助解释操作顺序和约减运算的影响,即使进入约减运算的数据可以并行完成也不例外。 许多循环更复杂,没有编译器可以识别全部机遇。 因此,建议开发人员考虑一下耗时的代码区域,查看编译器报告以了解编译器是否已将其完成,或考虑亲自将其完成。 第二点要注意的是,当数据变大时,应对其进行分块。 对于包含两个矩阵的小数据,这种方法无法带来性能提升。 对于较大的矩阵,可带来显著的性能提升。 因此,在对全部代码分块前,开发人员应该考虑一下相关的数据尺寸和高速缓存。 通过添加几个嵌套循环和适当的绑定,开发人员可以将性能提升到源代码片段的 2 至 10 倍。 鉴于仅进行了少量的改动,其性能的提升是非常大的。

使用优化的函数库

如要实现真正的高性能,还有一些事情需要做。 使用一个优化函数库(如英特尔® 数学核心函数库(英特尔® MKL))的第 3 级 BLAS 例程 DGEMM 所带来的性能提升远远高于上述的代码分块所带来的影响。 对于传统的线性代数和傅里叶变换,现代函数库(如英特尔数学核心函数库)带来的优化远胜于本文中介绍的简单分块和定序带来的效果。 如果可以,开发人员应利用这些性能优化的优化函数库。

虽然优化函数库适用于矩阵乘法,但是不适合任何通过分块提升性能的情况。 矩阵乘法为我们提供了一个简单、直观的例子来了解该原则。 这同样适用于有限差分模板。


图 5. 2D 块模型展示。

简单的九点模型将使用上方高亮显示的模块更新块中央的值。 引入 9 个值可以更新一个位置。 当周围的值更新后,其中 6 个值将会再次使用。 如果代码按照显示的方式在域顺序中进行,那么运行状况将会如同临近的图中所示。那么我们可以看到,如果要更新 3 个位置,则需要引入 15 个值。该比率将会逐渐趋近于 1:3。

如果我们将数据再次放到 2D 模块中,那么便会如图 5 中所示,只需要在寄存器中引入 20 个值便可更新 6 个位置;该比率将会逐渐趋近于 1:2。

我鼓励对有限差分技术感兴趣的读者可以阅读一下下面几篇精彩文章: 采用各项同性 (ISO) 的三维有限差分 (3DFD) 代码的八项优化措施,作者:Cedric Andreolli。 除了分块之外,我们还通过这两篇文章介绍了一些其他的内存优化技术。

总结

概括来讲,本文中阐述了三个主要步骤,支持开发人员轻松运用到其软件中。 首先,进行定序运算以避免并行约减。 其次,寻找数据重复使用机会,将嵌套循环重新构建到模块中,以便于数据重复使用。 这可将某些操作的性能提升 2 倍。 最后,使用优化函数库(如果可以);相较于传统的开发人员通过简单的重新定序获得的性能,优化函数库的速度明显更快。

完整代码可通过以下链接下载:https://github.com/drmackay/samplematrixcode

第二部分中,我将考虑跨多个内核的并行性,而不仅是 SIMD 寄存器,而且还会介绍一些关于伪共享和结构数组主题的内容。

有关编译器优化的更完整信息,请参阅优化通知