时空间混合并行框架及其在并行计算实验教学中的应用

肖 健, 于 策, 孙济洲, 李健增, 孟祥飞

(1. 天津大学 软件学院, 天津 300350； 2. 天津大学 计算机科学与技术学院, 天津 300350； 3. 国家超级计算天津中心, 天津 300457)

我国高性能计算技术的发展日新月异。在基础软硬件层面,自主研发的超级计算机正在向Exascale(百万兆) 级迈进,处于国际领跑地位,但在大规模高性能应用软件的数量和质量方面,与国际领先水平尚有一定差距[1-2]。作为大规模科学与工程计算、数据分析的基础工具,并行计算是一门综合性和实践性都很强的前沿应用类课程。要保证并行计算课程的应用性和前沿性,必须将理论、实验以及实际问题有机地结合起来,其中实验实践环节是连接理论与实际的桥梁[3]。常规的实验模式多以概念和知识点为导向,将已有的串行代码并行化,较少涉及科学计算、数值模拟等实际问题的求解和性能优化。为此,参考国外高校有针对性地应用教学代码库的做法,尝试构建了一个并行计算教学用代码框架,本文主要围绕该套框架的设计与应用范例方面展开,并探讨如何在实验教学中促进学生实现并行计算、数值分析、软件工程等相关专业知识的融会贯通。

1 框架的设计原则

作为教学范例和课程实践的代码框架,除了涵盖知识点要全面,还要突出重点,可以适应不同层次的教学要求。所以在开发这套代码时,从兼顾通用性和实用性的角度出发，确定了3个主要设计原则。

首先,根据分布式计算和并行计算技术的发展趋势,在巩固必修理论知识的基础上采用模块化设计,学生可以从不同的层次和角度看待问题,从而加速对各类知识的融会贯通。近年来,随着大数据和云计算技术的发展,出现了新型的大规模分布式计算框架,比如Hadoop、Spark等[4],此类框架提供了完整的任务调度和容错机制,允许开发人员在更高的抽象层次上对实际问题进行建模,极大地简化了开发和运维。相比之下,以MPI为代表的传统并行计算技术,几乎只提供了通信层的接口,程序开发过程不得不在问题模型与实现细节之间来回切换,这种较低的抽象层次极大地影响了工作效率。但MPI、OpenMP等作为大规模科学计算软件或程序的底层工具库,仍需要学生熟练掌握,才能胜任实际问题中程序调试、性能优化,尤其是专用代码开发工作。为弥补传统并行计算技术在实际问题快速建模方面的不足,框架要能够贯穿整个并行程序设计方法学,使学生既能快速理解整体上的解决方案,又可以有针对性地练习具体技术。

其次,注重引入并行计算领域的前沿研究成果,实现简化的教学版本,引导学生在实际问题中使用,激发学生的探索热情。目前,传统的空间并行技术已经接近性能极限,导致实际应用的并行加速比趋于饱和,难以高效地利用持续增加的硬件资源。近10年来,国际上对时间并行理论和技术的研究一直在持续增长,国内虽有少量关注,但尚没有真正的大型应用出现[5-7]。美国能源部和橡树岭国家实验室明确指出了时间并行技术在未来超级计算中的必要性[8],并开发了相对通用的时空间混合计算框架[9]。为此,选取了相对易于理解和应用的Parareal算法[5],在传统的空间并行维度中,增加了时间并行维度,旨在通过这个方兴未艾的研究分支抛砖引玉,激发学生的创新思路。

最后,教学代码还需要具有一定的实用性和良好的扩展性。实用性体现在能够与实际问题紧密结合,并为解决实际问题提供参考,快速地达到学以致用的目的。扩展性体现在能够方便集成学生的优秀代码,不断丰富教学实验案例,有效地实现教学相长。这种模式在国外高校已经屡见不鲜,许多成熟的开源代码库,甚至是Linux操作系统也是以类似的方式成长起来的,希望这个框架能够引发学生对并行计算应用开发的兴趣,孵化出实用性成果。

2 时空间混合并行框架

本文的并行计算教学代码的核心是一个提供时空间混合并行功能的框架。图1显示了空间并行和时间并行的概念,菱形方块代表计算资源(MPI进程等)。传统的空间并行技术,除了空间维度外,根据具体问题,还可以有频域、能级等方向上的并行,理论上,此类并行划分中计算依赖仅限于相邻分区之间,计算按照时间顺序串行推进,在概念上易于理解和实现。时间并行可以在不同的时间点上同时开始计算,而物理上这些时间点上的数值是有严格的前后顺序依赖关系的,这在形式上不太符合直观认识,需要掌握其背后的数学原理才能更好地应用。

图1 时空间混合并行示意图

2.1 时间并行技术概述

时间并行的概念早在50年前就已经提出,但直至2001年才有实用性算法出现,近10年来获得持续关注,并开始应用于实际问题。本文中使用的Parareal算法的基本逻辑并不复杂,可以分别从牛顿法、多重网格法等经典算法中推导出来,此处只给出基本思路,详细内容可参考文献[5]。简而言之,Parareal算法由粗细2种粒度的时间积分器构成,可以看作是时间维度上的两重网格,亦可以看作是时间维度上的外推法[6]。细粒度求解器用于得到精度较高的近似解,粗粒度求解器用于得到修正项,随着时间演化反复进行修正迭代,根据残差判断是否收敛。Parareal的修正迭代公式如下：

图2形象地描述了Parareal算法的求解过程,物理模型的演化时间被划分为了5个并行的时间片,时间轴上不同间隔的刻度分别代表粗细粒度的积分步长,绿色实线表示光滑的解析解或能与其很好重合的近似解,蓝色三角形代表粗粒度的近似解,红色四边形代表细粒度的近似解,黄色五边形代表修正后的更精确的近似解,经过反复迭代,逐渐逼近时间终点的符合收敛条件的近似解(红色实心圆)。

图2 Parareal时间并行算法的基本原理

从算法的描述中可以看出,与空间并行不同,物理上时间并行中的时间依赖并不能完全消除。粗粒度求解器的作用就在为每个时间片的起点或终点提供一个估计值,这个过程是串行的,必须依赖前一个时间片的计算结果。有了这个估计值,细粒度求解器才能并行执行,起到整体加速的目的。因此,时间并行算法的加速效果主要取决于粗细求解器的相对计算量和整体的收敛速率,这些又进一步与实际的物理模型和采用的具体数值算法有关。

2.2 框架的体系结构

框架的设计遵循了第1节的3个基本原则,同时参考了Flash code等成熟的大型数值模拟框架[10],采用了插件式和模块化的结构。如图3所示,正交的空间并行和时间并行分别作为底层基础和驱动器,负责数据管理和流程控制；线性求解器、时间积分算法、输入输出、性能监控等均作为单独的模块,以插件形式集成进来。

图3 时空间混合并行框架的体系结构

在抽象层次上,借鉴了Chapel[11]等新型并行语言的应用接口模式,除了传统的MPI通信层接口,还提供了基于网格的上层抽象。这样可以锻炼学生从不同的层次和角度去解决问题,在初期建模和任务定义阶段,专心于业务逻辑和流程；在后期大规模计算和性能优化阶段,可以深入挖掘MPI在消息通信方面的潜力。

在并行功能上,可以支持单一进程的串行模式、基于OpenMP的多线程、基于MPI的多进程空间并行、时间并行等,各类并行功能可以单独使用、也可以混合使用,比如：OpenMP-MPI的两级并行、MPI时空间混合并行、OpenMP-MPI时空间混合并行等。丰富的功能组合可以让学生通过对比掌握各类并行方法的特点和适用性。

在实用性上,支持多核的普通台式机、工作站、多节点的集群环境、以及超级计算机系统。框架提供了一些通用的线性求解器以及时间积分模版,包括超松弛法(SOR)、双共轭梯度稳定法(BiCGStab)、牛顿拉夫逊法等,所有运行参数可通过配置文件指定,方便调试和快速构建原型。各个层次(空间网格、各类求解器、时间并行算法)均可单独扩展,支持HDF5格式的大文件输出、自动完成计算和通信性能的统计分析,为算法优化提供依据。

2.3 框架的实现方法

图4 框架的实现流程

代码在组织结构上,特别考虑了扩展性和实验教学需求。通过共享基础代码的功能和算法模版,实验课题和物理模型均在各自的目录内独立发展。希望通过不断丰富实验课题和实例代码,积累教学成果,并适时转化成实用的解决方案。为方便学习交流、扩展升级以及成果积累,该框架已经采用开源项目的形式发布,目前还得到了时间并行学术组织的认可,列入了时间并行代码资源库。开源的形式还有助于学生练习现代软件工程的整套流程,起到综合实验的效果。

3 物理模型与实验课题

为了让学生深入理解并掌握并行计算的应用方法,将物理模型经过简化,作为实验课题集成到框架中。首先引入的是在物理模型和数值计算中具有普遍代表性的热扩散方程,之后在扩散问题的基础上,将具有广泛实际应用的多相场(phase field)问题作为重点实验课题。多相场的数值求解一直是科学计算领域的研究重点,我国神威•太湖之光超级计算机获得戈登贝尔奖的应用均涉及相场模拟[12]。通过将实验课题与实际问题、研究前沿相结合的方式,促进学生对各类知识的融会贯通,学以致用。

扩散问题最具代表性,且数值算法简单,适合作为教学范例。在简化后的热扩散模型中,扩散系数λ为常数,初始值和边界条件给定。在框架原型系统的开发阶段,验证了时空混合并行算法对热扩散问题的加速效果,详细的实验结果表明在问题规模一定的情况下,空间并行的性能(13.5倍)达到极限后,再利用时空混合并行(100个并行时间片),最终取得了整体200倍以上的性能提升[13]。

λ2Φ(热扩散方程)

(1)

(Allen-Cahn方程)

(2)

在扩散项的基础上加上反应项,就得到了多相场模拟的主要方程之一的Allen-Cahn方程。该类方程的求解过程涉及有限差分、有限元等数值计算的经典方法,且由于计算量大、耗时长,一直是高性能计算领域的代表型应用。虽然框架针对的是常系数的简化版,但由于增加了非线性的反应项,算法的性能优化变得极有挑战性。学生可以从数值算法的混合并行化、时间并行的收敛性、网格结构及网络传输优化等多个层次开展实验。初步实验结果表明,在一定条件下,时空间混合并行技术可加速多相场的计算,但需要探索和解决的问题还很多,较适合作为开放性实验课题。

4 在教学实验中的应用

一直以来,我校高性能计算教学团队都采用了案例和任务驱动型实验教学方法[14]。除计算机专业外,还面向全校相关专业的研究生开设并行计算的高级选修课程。该框架源自团队的内部积累,也是与国内外同行交流学习的成果[13]。基于该框架,同时借鉴其他高校的经验[15-16],针对本科生、研究生以及不同专业的学习需求,进一步加强了教学实验课程的细分。

对于计算机专业侧重并行技术和数值算法,实验涵盖了空间网格划分和管理、文件并行读写、数值算法并行化等普通专业课题,也包括开发自适应网格的接口,实现其他时间并行算法等具有较高难度的课题,鼓励学生为框架贡献自己的求解器,扩充和优化框架的基础功能。对于相关专业的选修课,则利用框架的高层接口,侧重上层建模能力的训练,解决学习科研中的实际问题。图4(b)展示了此类实验的流程,首先学生利用有限差分或有限元方法,完成模型的离散化,然后从框架提供的算法中选择合适的组合,并编写问题特有的计算代码(stencil code),设置初值和边界条件,最后进行实验方法的可行性验证。此类实验可以为框架增加实际的应用课题,丰富教学案例。对于课程设计,鼓励计算机专业和其他专业的学生组队,将实际问题建模和求解过程优化结合起来,培育实用性解决方案。目前,相场模拟作为第一个开放性实验课题,还处于收集和优化算法阶段。

5 结语

本文提出的时空间混合并行计算框架,从原型系统开发到开源项目的发布历时2年,并在国内外的超级计算机上完成了测试和功能验证。高性能计算相关的实践教学,可通过对源代码的学习分析、改造优化、模型求解等多种方式,有效锻炼学生综合运用知识、解决实际问题的能力,同时开源形式有助于不断丰富教学案例和实验课题。除了多相场之外,将陆续精选出一些难度适中的科学计算问题,引导学生广泛探索,并以天津超算中心为平台依托,加快产学研结合。