基于循环分块的流水粒度优化算法

摘 要：当计算划分层迭代数目较大，或是循环体单次迭代工作量较大，但可用的并行线程数目较小时，传统的基于循环分块的流水粒度优化方法无法进行处理。为此，提出一种基于循环分块减小流水粒度的方法，并根据流水并行循环的代价模型实现最优流水粒度的求解，设计实现了一个流水计算粒度的优化算法。对有限差分松弛法（FDR）的波前循环和时域有限差分法（FDTD）中典型循环的测试表明，与传统的流水粒度选择方法相比，所提算法能够得到更优的循环分块大小。

关键词：自动并行化；流水并行；流水粒度；循环分块；代价模型

中图分类号： TP314

文献标志码：A

0 引言

随着主频的提高，处理器功耗以指数速度急剧上升，使得以提高主频来提升处理器性能的方法不再有效[1]。多核处理器已成为处理器体系结构发展的一个主要方向[2]。尽管多核处理器能够提升多线程程序的性能，但早已存在的诸多单线程程序无法从中获益，程序员也习惯于编写单线程程序。自动并行化技术[3]是将单线程程序移植到多核上的重要手段，通过对单线程程序中蕴含并行性的分析与发掘，采用程序变换技术自动生成适合多核处理器运行的多线程程序。根据Amdahl定律[4]，应用程序通过并行获得的性能提升受限于程序中串行执行部分所占的比例。因此，充分发掘程序的并行性是提升程序并行性能的有效手段。计算机科学中的二八法则表明，程序中20%的代码占据了程序80%的执行时间，这些花费大量时间开销的代码往往是程序中的循环。因此，循环是发掘程序并行性的主要对象。

根据蕴含并行性的不同，Cytron[5]将循环分为串行循环、能够完全并行的DOALL循环和DOACROSS循环。DOACROSS循环因为携带跨迭代的依赖关系，并行性介于DOALL循环和串行循环之间。Chen等[6]通过测试表明，将程序中的DOACROSS循环串行执行会带来程序并行性的巨大损失。因此，发掘DOACROSS循环中蕴含的并行性，选择合适的策略将其并行执行对提升程序的并行性能非常重要。通过判定循环携带依赖的依赖距离是可精确确定的常量还是变量，DOACROSS循环可分为规则DAOCROSS循环和不规则DAOCROSS循环[7]。与不规则DOACROSS循环相比，规则的DOACROSS循环因为携带依赖关系的规则性，更适合通过编译器实现自动并行。流水并行是指将循环的各次迭代分配给不同的线程，线程间流水执行来获得并行性，迭代间的依赖通过某种方式的同步得到维持。流水并行是规则DOACROSS循环并行的重要方式。本课题在前期工作中以多核处理器为目标平台，在Open64[8]编译器后端实现了基于OpenMP[9-10]的规则DOACROSS循环流水并行代码的自动生成，并通过测试对其有效性进行了验证。

在循环流水并行过程中，线程间的同步能够维持循环携带依赖，保证循环执行的正确性，但同时也会带来额外的开销。同一线程两次同步之间的计算工作量大小称为流水计算粒度，简称流水粒度。流水粒度的大小与同步开销在循环执行总开销中所占的比例有直接关系，影响着流水并行循环的性能。根据流水粒度的大小，流水并行可分为细粒度流水和粗粒度流水。细粒度流水时，线程两次同步之间的计算量较小，下一线程能够较快获得所需数据进行计算，减少了线程的空闲等待时间；但因为粒度较小，会引起较多次数的同步，从而导致较高的同步代价和较低的流水并行性能。粗粒度流水增大了同步之间的计算量和同步数据量，因此减少了同步次数，同步代价相对较小，但后续的计算节点在开始计算之前需要更多的等待时间，降低了循环的并行性。

为平衡并行性和同步代价两者之间的关系，使得流水循环获得趋近于最优的并行性能，本课题前期实现的自动并行化算法中使用传统的流水粒度优化方法，从循环的各层（除计算划分层）中选择一层实施循环分块[11]来调节流水的粒度。然而，当计算划分层包含的迭代数目很大，或是循环体单次迭代的工作量很大，或是这两种情况同时存在，但可用的并行线程数目较小时，线程的两次同步之间的工作量很大，同步开销对并行性能的影响变得很弱。但因为流水粒度过大，对循环的并行性造成了极大的损失。传统的循环分块方法无法处理上述情况。

针对传统流水粒度选择方法的不足，本文提出一种流水粒度优化算法来进一步提升自动生成的流水并行代码的性能。首先给出了基于循环分块减小流水粒度的方法，从而避免出现线程的两次同步之间的工作量过大，给循环并行性带来损失的情况；然后基于循环流水执行时的代价模型综合考虑流水粒度过大和过小的情况，实现最优流水粒度的求解；最后设计实现了流水粒度的优化算法。对有限差分松弛法（Finite Difference Relaxation，FDR）的波前（Wavefront）循环[11]和时域有限差分法（Finite Difference Time Domain，FDTD）[12]中典型循环的测试表明，与传统的流水粒度选择方法相比，本文算法能够得到更优的循环分块大小，基于本文算法自动生成的流水并行代码能够在多核处理器上获得明显的性能提升。

然而，如果计算划分层包含的迭代数目很大，或是循环体单次迭代的工作量很大，也可能是这两种情况同时存在，但可用的并行线程数目较小。在这种情况下，线程的两次同步之间的工作量很大，同步开销对并行性能的影响变得很弱。但因为流水粒度过大，给循环的并行性带来了极大的损失，从而导致循环无法获得最优的并行性能。传统的循环分块方法无法处理上述问题。

2 基于循环分块的流水粒度优化算法

本章首先讨论如何基于循环分块减小流水粒度，从而避免出现线程的两次同步之间的工作量过大，造成循环并行性的损失，从而导致循环无法获得最优并行性能的情况；然后基于循环流水执行时的代价模型综合考虑流水粒度过大和过小的情况，实现最优流水粒度的求解；最后给出流水粒度优化算法。

2.1 基于循环分块减小流水粒度

考虑第1章给出的循环分块可调流水粒度范围的下界N1p*L，其中单次迭代的工作量L和并行线程数p是固定的，则对于流水计算粒度过大的情况，应该通过减少同一并行线程的两次同步之间的迭代次数，即N1来减小流水的粒度。因此考虑对循环的计算划分层进行循环分段[11]，并选择分段后的内层作为新的计算划分层，从而达到减少同一并行线程两次同步之间的迭代次数的目的。下面仍然以图1中的循环为例进行说明。

2.2 流水并行代价模型

本节讨论流水并行代价模型的构建，然后基于代价模型综合考虑流水粒度过大和过小的情况，实现最优循环分块大小的求解。首先基于以下几点假设建立流水计算的模型[13]：

1）线程之间的同步是阻塞的，即同步完成前，不能进行其他的工作，类似于分布存储结构下的同步通信模式。

3 实验结果与分析

本章对本文实现的流水粒度优化算法的有效性进行测试。本课题的前期工作在Open64编译器的后端实现了基于OpenMP的规则DOACROSS循环流水并行代码的自动生成。本文在此基础上实现了流水粒度优化算法，对自动生成的流水并行代码的流水粒度进行优化。

测试平台为IBM x3650系列的服务器，其中包含4个Intel Xeon X5670 CPU，每个Intel Xeon X5670 CPU中包含6个主频为2.93GHz的处理器核，内存为40GB，使用的操作系统为Red hat Enterprise 5.5。选择FDR的波前循环和求解电磁问题的FDTD的典型循环作为测试用例。物理学和其他学科领域的许多问题在被分析研究之后，往往归结为偏微分方程（Partial Differential Equation，PDE）的求解问题。直接求解PDE比较困难，所以常常使用有限差分法（Finite Differential Method，FDM）来实现PDE的数值求解，在PDE中用差商代替偏导数，得到相应的差分方程，通过解差分方程得到PDE的近似解。FDM被广泛应用于诸如气象预报、流体力学的模拟、弹力力学等研究领域。FDM中采用各种迭代法，如点逐次超松弛方法、迭代的交替方向隐式方法等，求解差分方程组，其中蕴含大量的DOACROSS并行性，适用于DOACROSS循环自动并行的测试。本章使用的两个测试用例均属于FDM的迭代求解法。

3.1 对FDR的测试

本节对FDR波前循环进行测试，测试时选择256×256的循环规模，并记录循环在不同线程数目下的三种加速比，分别是：使用手工选择最优分块大小时的并行加速比（by hand）、基于传统循环分块方法选择分块大小时的加速比（traditional）和基于本文的粒度优化算法选择分块大小时的加速比（automatic），结果如图7所示。

4 结语

本文针对流水并行代码自动生成过程中传统流水粒度选择方法的不足，提出了一种流水粒度优化算法，以进一步提升自动生成的流水并行代码的性能。本文首先介绍了传统的基于循环分块增大流水粒度的方法，然后详细讨论了在流水粒度过大的情况下如何基于循环分块减小流水粒度，之后根据流水并行代价模型得到了求解最优循环分块大小的方法，最后给出了完整的流水粒度优化算法。实验结果表明，与传统的流水粒度选择方法相比，本文算法能够得到更优的循环分块大小。下一步工作的重点是面向基准测试集进行大量测试，根据所得的实验数据，对流水并行代价模型进行进一步修正，以求得更加精确的最优分块大小，提升自动生成代码的并行性能。

参考文献：

[1]BENOIT A， MELHEM R， RENAUDGOUD P， et al. Poweraware Manhattan routing on chip multiprocessors [C]// Proceedings of 2012 IEEE 26th International Parallel and Distributed Processing Symposium. Piscataway： IEEE， 2012：189-200.

[2]JIN H Q， JESPEREN D， MEHROTRA P， et al. High performance computing using MPI and OpenMP on multicore parallel systems [J]. Parallel Computing， 2011， 37（9）：562-575.

[3]BONDHUGULA U K R. Effective automatic parallelization and locality optimization using the polyhedral model [D]. Ohio： The Ohio State University， 2008.

[4]AKHTER S， ROBERTS J. Multicore programming： increasing performance through software multithreading [M]. Hillsboro： Intel Corporation， 2006： 13-27.

[5]CYTRON R. Doacross： beyond vectorization for multiprocessors[C]// Proceedings of the 1986 International Conference on Parallel Processing. Piscataway： IEEE， 1986： 836-844.

[6]CHEN DK， YEW PC. An empirical study on DOACROSS loops [C]// Proceedings of Supercomputing. New York： ACM， 1991：620-632.

[7]HURSON A R， LIM J T， KAVI K M， et al. Parallelization of DOALL and DOACROSS loops — a survey [J]. Advances in Computers， 1997， 45：53-103.确认无期

[8]LIN YT， WANG SC， SHIH WL， et al. Enable OpenCL compiler with Open64 infrastructures [C]// 2011 IEEE 13th International Conference on High Performance Computing and Communications. Piscataway： IEEE， 2011：863-868.

[9]富弘毅， 丁滟， 宋伟，等. 一种利用并行复算实现的OpenMP容错机制[J].软件学报，2012， 23（2）： 411-427.

[10]THOMAN P， JORDAN H， PELLEGRINI S， et al. Automatic OpenMP loop scheduling： a combined compiler and runtime approach [C]// IWOMP12： Proceedings of 8th International Conference on OpenMP in a Heterogeneous World. Berlin： SpringerVerlag， 2012：88-101.

[11]ALLEN R， KENNEDY K. Optimizing compilers for modern architectures： a dependencebased approach[M]. San Francisco： Morgan Kaufmann Publisher， 2001： 63-68.

[12]TAFLOVE A. Computational electrodynamics [M]. London： Artech House Publishers， 1995.

[13]马琳.反馈指导的流水计算性能调优[D].北京：中国科学院计算技术研究所，2005.