开放科学(资源服务)标志码(OSID):

0 概述

2003年以前，单核处理器的主频在摩尔定律的影响下不断提高，程序的执行效率主要依赖处理器的主频。2003年以后，由于功耗的原因，主频遇到技术瓶颈，多核技术成为提升硬件性能的有效方案。多核处理器的发展，一方面提高了处理器的性能，另一方面将提高实际计算能力的任务转移给了软件开发人员。

为充分发挥多核处理器的计算潜力，并行编程模型应运而生，其中OpenMP规范^[1]对现有编程语言进行了扩展，为软件开发人员提供简单、高效的编程接口，成为应用最广泛的多线程编程模型。OpenMP是一组由计算机硬件和软件供应商联合定义的应用程序接口(API)^[1]，OpenMP标准规范于1997年首次发布，最新版本为V5.0，为基于共享内存并行程序的开发人员提供一种可扩展的编程模型，目前在主流的编译器中都具有相关技术支持。在OpenMP线程执行模式下，当程序开始时单一主线程串行执行，当程序执行到并行区域时派生出一组分支线程和主线程并行执行，离开并行区域后所有线程进行同步并且自动结束，最后程序只剩一个单独的主线程，继续串行执行。

针对不同的循环结构，OpenMP规范提供了多种调度策略，但都存在不同程度的调度开销和负载均衡问题，最终影响热点循环在目标机器上的执行效率。为尽可能地减少调度开销，使得各个处理器负载趋于均衡，软件开发人员需要根据循环特征在调度开销和负载均衡之间进行权衡，找到合适的调度策略。

本文提出一种针对线性循环结构的调度策略Nonlinear_static，结合线性负载均匀变化参数与总负载、负载峰值、线程数构建Nonlinear_static调度模型，通过该模型计算每个迭代块的大小使其呈现非线性递增或递减趋势，并在开源OMPi编译器上编码实现Nonlinear_static调度策略，从而消除调度开销并实现负载的均衡分配。

1 相关工作 1.1 循环结构

科学计算中的二八法则表明，程序中20%的代码占据80%的执行时间，这些占据大量时间的代码通常是程序中的循环结构。因此，挖掘循环的并行性是提高程序执行效率的有效方法^[2]。循环分为含有依赖循环和不含依赖循环。有依赖的循环无法直接并行，因此不在本文的研究范围内。本文提到的循环均为不含依赖的循环。根据循环中负载的分布情况，常见循环分为4种不同的结构^[3]，如图 1所示，横坐标为循环索引变量i，纵坐标L(i)表示第i次迭代中负载量。

从图 1(a)可以看出，规则循环结构的负载L(i)在迭代索引i上的分布是均匀不变的。随机循环结构的负载L(i)在迭代索引i上随机分布，没有规律。递增循环结构和递减循环结构的负载L(i)在循环索引i上呈线性递增和线性递减趋势。4种循环结构基本包括绝大部分的应用场景，其中随机循环结构、递增循环结构和递减循环结构称为非规则循环结构^[4]，而递增循环结构和递减循环结构又称线性循环结构。

1.2 OpenMP循环调度策略

在共享存储体系结构中，调度开销和负载均衡是循环级并行化面临的重要问题。不同的调度策略针对特定循环的效果有好有坏，没有任何一种调度策略能够解决所有的循环调度问题^[5]，关键在于找到适合目标循环特征的调度策略。

目前，OpenMP规范中提供了4种标准的调度策略，分别是静态调度(static)、动态调度(dynamic)、指导调度(guided)以及运行时调度(runtime)，其中运行时调度根据环境变量动态选择前3种中的1种，环境变量由程序员提前指定。

静态调度在默认情况下将循环迭代划分为大小相等的块，每个线程分到的迭代块值chunksize(线程分到迭代块的大小)等于P/N(N代表循环总的迭代数，P代表使用的线程数)，当无法整除时会尽可能平均分配。静态调度还可以指定chunksize值，在这种情况下，每个线程依次得到chunksize值的迭代块，直到所有的迭代都分配完成。这种调度方法适用于规则循环结构，对于随机循环结构和线性循环结构，不同的线程负载差距较大，负载均衡性较差^[6-7]，其优点是迭代在线程上的映射编译时已经确定，所以在运行时没有调度开销。

动态调度在程序运行中每个线程会申请chunksize大小的迭代块，当某个线程执行完任务处于空闲状态但还有迭代未被执行时，它会再次请求chunksize大小的迭代块，直到所有的循环都执行完成。在默认情况下，当不指定chunksize时，其值为1。相较于静态调度，动态调度能够更好地适应非规则循环结构，但其会面临chunksize值的抉择，过大的块会引起线程间的负载不均衡，过小的块则会引起频繁的线程调度，造成严重的调度开销^[8]。

指导调度^[9]是一种启发式的自调度方法，其迭代块值不是恒定不变的而是逐渐减小的，先申请任务线程得到的迭代块会比较大，之后逐渐减小。迭代块值是一个可选参数，迭代块的变化呈指数下降，直至下降到迭代块值保持不变，当不指定迭代块值时，其值默认为1。在OMPi编译器中迭代块是按照ch=(ch+t- > nth-1)/t- > nth来计算，其中ch表示剩余迭代的值，t- > nth表示线程数。指导调度在面临递增型循环结构时表现出良好的负载均衡性，但是当遇到随机型循环特别是递减型循环时，容易造成负载集中于前面几个线程的现象。

除OpenMP规范中标准调度策略之外，梯式调度(TSS)^[3]综合了动态调度和指导调度优点，常用于处理非规则循环。相似于动态调度，梯式调度迭代块值的变化是线性的，与动态调度不同的是其迭代块值下降到一定程度后将保持不变，在一定程度上缓解了动态调度和指导调度后期调度开销大的问题。线性变化的迭代块值使得梯式调度在面对递增循环结构时相较于指导调度具有更优的负载均衡性。

Factoring调度(FSS)^[10]采用分段的方法处理循环迭代。在同一个段内，每个线程分配的迭代块值是相同的，而段与段之间是线性减小的。这种方法在面对非规则循环时相较于梯式调度负载均衡性更优，但实现复杂且开销更大。从整体上分析，Factoring调度的迭代块值同样是不断减小的，所以在处理递减型循环时，随着负载的不断减小，分配到的迭代块也是越来越小，造成严重的负载失衡。

针对指导调度和Factoring调度不适用于递减型循环的问题，文献[12]借鉴α调度策略^[11]，提出new_guided调度策略。在循环的前半段使用静态调度，后半段使用指导调度，保证调度初期迭代块值不至于过大，在一定程度上缓解了负载在最初几个线程过于集中的问题。在面对递减型循环时，new_guided调度相较于指导调度具有更优的均衡效果，但在本质上并没有解决现有调度策略迭代块递降的弊端。

在处理负载均衡问题上，一种解决方法是由用户定义的调度策略^[13-14]，使用户收集应用的负载信息再反馈给调度策略，然后进行针对性的迭代块划分，缺点是搜集负载的难度较大，增加了用户的工作量，实际操作较困难；另一种解决方法是动态循环自调度技术(DLS)^[15]，但其仅适用于计算密集型以及不规则循环的调度。

在硬件方面，硬件感知编译器增强调度^[16]结合硬件特点和调度策略，充分发挥硬件的算力，更适用于异构平台。

以上调度策略中N代表循环总的迭代数，P代表使用的线程数，迭代块值代表线程分到迭代块的值。当循环迭代数为1 000，线程数为4时，不同调度策略的迭代块值如表 1所示，动态调度的迭代块值是100，指导调度最小为100。

1.3 现有调度策略

现有调度策略无论是OpenMP标准调度策略还是梯式调度、Factoring调度策略、new_guided调度策略，迭代块值的变化主要是线性、非线性、分段线性、线性和非线性相混合。从表 1可以看出，除了静态调度和动态调度的迭代块值一直保持不变以外，其他调度策略迭代块值总体上都是不断减小，调度策略难以解决负载集中在先分配的迭代块的问题，特别是在处理递减型循环时，这种现象尤为严重。针对这种问题，本文提出一种非线性静态调度的策略，能够将负载平均划分到各个迭代块中，并没有调度开销。此外，对于递增型循环也可以用同样的方法进行处理。递增型循环动态调度和指导调度虽然负载分配较均衡，但是需要进行多次调度，调度开销较大。本文调度策略在处理线性循环时与静态调度的区别如图 2所示，迭代块的划分由原来的均分变成了非线性划分，由于迭代块的变化是非线性的，因此记为Nonlinear_static调度策略。

2 Nonlinear_static调度策略的设计与实现 2.1 OMPi编译器

OMPi编译器^[17]是由希腊约阿尼纳大学的并行处理小组研发的OpenMP编译器，是一款轻量型、可移植的源到源C编译器，最新开发到了2.0.0版本，支持OpenMP 4.0标准。OMPi编译器将程序员编写的带有OpenMP指导语句的C代码转换为基于pthreads等线程库的C代码，然后重新调用指定的C编译器进行二次编译并生成可执行文件。由于OMPi编译器具有轻量、结构性强、易于实现OpenMP调度策略等特点，因此本文调度策略的设计以及实现都是基于OMPi编译器2.0.0版本。

OMPi代码编译示例如图 3所示，由于是静态调度，迭代块值的计算在编译阶段已经完成，每个线程迭代块的开始位置存放在指针*fiter中，结束位置存放在指针*liter中，各个线程按照迭代块并行执行互不干扰并且没有调度开销。

2.2 Nonlinear_static调度模型

Nonlinear_static调度策略是一种静态调度策略，并行程序在编译过程中确定迭代块的划分，没有调度开销。迭代块根据线性递增或线性递减的负载进行平均划分，确保每个线程在并行执行期间都能够处于工作状态，减少线程同步等待时间，提升程序执行效率。模型参数说明如表 2所示。

递减循环和递增循环负载分块示意图如图 4和图 5所示，不同灰度的色块表示不同线程分配到的迭代块。

Nonlinear_static调度策略的目的是使得每个线程的负载量保持一致，对于递减型循环f(i)的推导主要分为以下5个步骤。

1) 计算参与的常量(总负载、平均负载、斜率)，如式(1)~式(3)所示：

$ {l}_{\mathrm{l}\mathrm{a}\mathrm{o}\mathrm{d}}=\frac{{l}_{\mathrm{l}\mathrm{d}}\times {n}_{\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{s}}}{2} $

(1)

$ {a}_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}}=\frac{{l}_{\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}}}{p}=\frac{{l}_{\mathrm{l}\mathrm{d}}\times {n}_{\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{s}}}{2p} $

(2)

$ k=\frac{{l}_{\mathrm{l}\mathrm{d}}}{{n}_{\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{s}}} $

(3)

2) 列出恒等式，如式(4)、式(5)所示：

$ {l}_{\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}}\left(i\right)={a}_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}}, i\in \left\{x\left|x < p, x\in N\right.\right\} $

(4)

$ \sum\limits_0^{p - 1} f \left( i \right) = {n_{{\rm{niters}}}} $

(5)

3) 计算h(i)，如式(6)所示：

$ h\left(i\right)=k\times \sum\limits _{i}^{p-1}f\left(i\right) $

(6)

4) 计算l_load(i)如式(7)所示：

$ {l}_{\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}}\left(i\right)=f\left(i\right)\times \frac{h\left(i\right)+h\left(i+1\right)}{2} $

(7)

5) 从以上公式推理可得：

$ f\left(i\right)=\frac{{n}_{\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{s}}}{\sqrt{p}}\times \left(\sqrt{p-i}-\sqrt{p-i-1}\right) $

(8)

同理可得当循环为线性递增型循环时，f(i)如式(9)所示：

$ f\left(i\right)=\frac{{n}_{\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{s}}}{\sqrt{p}}\times \left(\sqrt{i+1}-\sqrt{i}\right) $

(9)

式(4)表明每个线程的负载l_load(i)需要等于理论上的平均负载，式(7)用于计算线程i根据本文提出的调度策略分配到的负载值。通过以上计算就可以得到f(i)，f(i)是Nonlinear_static调度策略划分迭代块的依据，不同的线程获得不同大小的f(i)，但对应到负载上每个线程是严格均衡的。在代码实现中，当计算结果不是整数时，处理方法是向下取整。

2.3 Nonlinear_static调度实现

本文在OMPi编译器中编码实现一种不同于传统静态调度的非线性静态调度策略，具有没有调度开销以及高数据局部性的优点。Nonlinear_static调度按照f(i)进行迭代块的划分使得每个线程的负载总是等于avg_load，保证负载的均衡性。

从代码层面分析，OMPi编译器模块化清晰明了，能够更好地进行扩展，为实现OpenMP调度策略提供便利，这也是在GCC编译器和可执行文件之间选择一个源到源编译器的原因。通过OMPi编译器更改其中关于OpenMP调度的代码，进而实现自己的调度策略。在OMPi编译器中，本文实现3种基本调度策略(静态、动态、指导)的代码在文件/ompi-2.0.0/runtime/host/worksharing.c中，不同的调度策略对应各自的函数调用，其中ort_get_static_default_chunk()函数用于计算静态调度迭代块的大小f(i)，并把f(i)的开始迭代索引存放在指针*fiter中，把迭代块结束索引存放在指针*liter中。

在Nonlinear_static调度模型中计算每个线程迭代块的大小f(i)，作为分块的依据，但在调度策略代码实现中，还需要知道迭代块首尾索引的值，即为*fiter、*liter赋值。s_start(i)为线程i分配到迭代块的开始索引，推导主要用到2.2节中的变量。

1) 当循环为线性递减循环时，s_start(i)如式(10)所示：

$ {s}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}\left(i\right)={n}_{\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{s}}-\frac{f\left(i\right)}{2}-\frac{{n}_{\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{s}}^{2}}{2p\times f\left(i\right)} $

(10)

2) 当循环为线性递增循环时，s_start(i)如式(11)所示：

$ {s}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}\left(i\right)=\frac{{n}_{\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{s}}^{2}}{2p\times f\left(i\right)}-\frac{f\left(i\right)}{2} $

(11)

从f(i)以及s_start(i)的计算结果得到*fiter和*liter的值，*fiter=start(i)，*liter=*fiter+f(i)。Nonlinear_static调度策略是一种静态调度，本文在OpenMP标准静态调度的基础上进行实现的，总迭代数的获取如图 6所示，Nonlinear_static伪代码如图 7所示，其中myid对应线程i，fi对应f(i)，start对应开始索引s_start(i)。为保证计算的精确度，中间变量都定义为浮点型数据。

3 实验与结果分析 3.1 实验环境

本文采用戴尔Power Edge T640服务器作为实验平台，具有2个Intel^® Xeon^® Silver 4110 CPU，2个CPU有8个核心，共16核心，主频为2.10 GHz，内存为128 GB。操作系统使用Ubuntu16.04，编译器采用GCC 7.1.0版本，优化选项-O3，OMPi编译器使用最新的2.0.0版本。

针对1.1节提到的4种基本循环结构，本文选取典型的应用程序分别进行调度策略测试。AC(Adjoint Convolution)是一个递减型循环结构，用于计算2个向量的卷积，实验规模为600×600。CP(Compute Pots)^[18]是一个递增型循环结构，用于更新三维空间中点与点之间的数值关系，类似于模板计算，实验规模为10 000，源代码发布于2007年Intel多核平台编码优化赛事。MM(Matrix Multiplication)^[19]是一个规则循环结构，用于计算浮点矩阵乘法，实验规模为2 500×2 500。MS(Mandelbrot Set)是一个随机循环结构，能够生成复平面上分形图的点的集合，实验规模为15 000×15 000。为充分验证测试用例的性能表现，本文选取的实验规模在保证加速效果来自于调度策略而不是随机因素的前提下，尽可能进行多次实验来排除随机因素，以验证调度策略的可靠性以及扩展性。CP程序与AC程序的负载分布如图 8所示，负载的单位是核心计算的次数。

本文实验主要研究4种测试用例中的热点循环部分，针对整个热点循环从开始执行到执行完毕的时间，计时操作使用OpenMP提供的函数omp_get_wtime()，该函数返回1个双精度浮点值，等于经过的时间(以s为单位)。

3.2 实验结果分析

测试用例串行执行时间如表 3所示。为保证数据的全面性，本文分别测试线程数为4、8、12、16时不同调度策略的并行执行时间。针对同一种调度策略，本文还测试了不同迭代块值(由OpenMP指导语句指定)下的并行时间，经过测试迭代块值的选取除了对静态调度有一定的影响外，对于其他调度策略影响较小。因此，本文只列举chunksize=100的情况下，对比不同调度策略的执行时间。

3.2.1 AC程序并行执行结果

AC是线性循环中的递减型循环。AC程序并行执行时间如表 4所示，不同调度策略的AC程序并行执行时间对比如图 9所示。从表 4和图 9可以看出，表现最差的是静态调度和指导调度。静态调度把循环迭代均匀分割在各个线程，造成负载在最先分配的线程上最多，最后分配的线程上最少。指导调度由于迭代块是指数下降的，负载的不均衡度更大。表现较优的是动态调度和new_guided调度，线程动态申请迭代块，减少了线程的等待，使得线程一直处于工作状态。根据文献[20]的实验数据，梯式调度的效果与new_guided调度相当。表现最优的是Nonlinear_static调度，与动态调度和指导调度相比，Nonlinear_static调度具有更优的负载均衡且没有调度开销。

3.2.2 CP程序并行执行结果

CP程序并行执行时间如表 5所示，不同调度策略的CP程序并行执行时间对比如图 10所示。从表 5和图 10可以看出，对于CP的递增型循环结构，静态调度表现最差，指导调度略弱于动态调度和new_guided调度，根据文献[20]的实验数据，梯式调度的效果与动态调度相当，Nonlinear_static调度表现最优。

3.2.3 MS与MM程序并行执行时间

MS随机循环结构的并行执行时间如表 6所示，MM规则循环结构并行执行时间如表 7所示。从表 6和表 7可以看出，表现最优的是动态调度、指导调度以及new_guided调度。随机循环结构负载分布是随机变化，因此，需要动态分配迭代块才能实现负载均衡，静态调度以及Nonlinear_static调度的迭代块分配在编译过程中已经确定了，所以表现最差。在面对规则循环时，Nonlinear_static调度的表现也是最差的。根据文献[20]的实验数据，梯式调度在面对随机循环结构时效果优于new_guided调度，在处理规则循环结构时表现出与动态调度相同的效果。

不同调度策略的本质是对chunksize划分不同，循环结构的负载分布是变化的，因此会造成线程分配到的负载量难以明确，反映到OpenMP调度模型上使得先执行完任务的线程，并等待未执行完任务的线程进行同步操作，而这一步骤会降低程序整体的执行效率。从表 4~表 7可以看出，对于不同的测试用例，除了静态调度在指定chunksize时有明显的加速(对于规则循环是负加速)外，其他的调度策略在指定chunksize时基本没有大的变化。

从整体上分析，静态调度不能有效地平衡负载，除了规则循环结构，一般情况下效果都是最差的。

指导调度的特性导致其不适合处理递减型循环。Nonlinear_static调度由于静态的迭代块划分规则，无论是哪种类型的循环，其迭代块的划分是固定的，所以不适合随机循环以及规则循环结构。在其他情况下，动态调度和指导调度性能较优，符合其动态分配迭代块的设计原理，但额外的调度开销使得它们在线性循环时相较于Nonlinear_static调度效果较差。Nonlinear_static调度相较于其他调度策略能够更好地处理线性循环，理论与实验结果相一致。

4 结束语

本文提出静态调度策略Nonlinear_static用于消除调度开销。将线性循环负载均匀变化参数与总负载、负载峰值、线程数相结合构建Nonlinear_static调度策略的模型，并在OMPi编译器中进行编码。实验结果表明，该策略在负载均衡的基础上实现了负载的静态分配，与静态调度、动态调度、指导调度等策略相比，其总体执行时间缩短了5%~10%。后续将在处理非线性循环结构时采用迭代编译方法获得关键信息，同时重新划分迭代块的大小进行二次编译，进一步提高负载的均衡性。