空间混合
-
2023年2月17日发(作者：)时空间混合并行框架及其在并行计算实验教学中的应用
肖健;于策;孙济洲;李健增;孟祥飞
【摘要】结合处于研究前沿的时间并行理论和传统的空间并行技术,设计开发了一
个时空混合并行计算框架,用于并行计算和数值模拟相关课程的实验教学.该框架提
供了基础的时空间并行功能和部分常用的数值求解器,又支持在更高层面完成对问
题的建模和分解,有助于学生全面理解和掌握科学计算和工程模拟的相关知识,同时
便于积累教学成果,探索和培育新课题.
【期刊名称】《实验技术与管理》
【年(卷),期】2018(035)009
【总页数】5页(P218-221,224)
【关键词】时空间混合并行;超级计算;数值模拟;编程教学
【作者】肖健;于策;孙济洲;李健增;孟祥飞
【作者单位】天津大学软件学院,天津300350;天津大学计算机科学与技术学院,天
津300350;天津大学计算机科学与技术学院,天津300350;国家超级计算天津中心,
天津300457;国家超级计算天津中心,天津300457
【正文语种】中文
【中图分类】TP391;G642.0
我国高性能计算技术的发展日新月异。在基础软硬件层面,自主研发的超级计算机
正在向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的修正迭代公式
如下：
,Tn,
[G(Tn-1,Tn,,Tn,
其中,n为时间片序号,k为迭代次数,为第n个时间片内第k次迭代后的近似
解,F(Tn-1,Tn,表示以为初值的从时间Tn-1到Tn的细粒度积分函数(求解器),G则
为对应的粗粒度求解器。
图2形象地描述了Parareal算法的求解过程,物理模型的演化时间被划分为了5个
并行的时间片,时间轴上不同间隔的刻度分别代表粗细粒度的积分步长,绿色实线表
示光滑的解析解或能与其很好重合的近似解,蓝色三角形代表粗粒度的近似解,红色
四边形代表细粒度的近似解,黄色五边形代表修正后的更精确的近似解,经过反复迭
代,逐渐逼近时间终点的符合收敛条件的近似解(红色实心圆)。
图2Parareal时间并行算法的基本原理
从算法的描述中可以看出,与空间并行不同,物理上时间并行中的时间依赖并不能完
全消除。粗粒度求解器的作用就在为每个时间片的起点或终点提供一个估计值,这
个过程是串行的,必须依赖前一个时间片的计算结果。有了这个估计值,细粒度求解
器才能并行执行,起到整体加速的目的。因此,时间并行算法的加速效果主要取决于
粗细求解器的相对计算量和整体的收敛速率,这些又进一步与实际的物理模型和采
用的具体数值算法有关。
2.2框架的体系结构
框架的设计遵循了第1节的3个基本原则,同时参考了Flashcode等成熟的大型数
值模拟框架[10],采用了插件式和模块化的结构。如图3所示,正交的空间并行和时
间并行分别作为底层基础和驱动器,负责数据管理和流程控制；线性求解器、时间
积分算法、输入输出、性能监控等均作为单独的模块,以插件形式集成进来。
图3时空间混合并行框架的体系结构
在抽象层次上,借鉴了Chapel[11]等新型并行语言的应用接口模式,除了传统的
MPI通信层接口,还提供了基于网格的上层抽象。这样可以锻炼学生从不同的层次
和角度去解决问题,在初期建模和任务定义阶段,专心于业务逻辑和流程；在后期大
规模计算和性能优化阶段,可以深入挖掘MPI在消息通信方面的潜力。
在并行功能上,可以支持单一进程的串行模式、基于OpenMP的多线程、基于
MPI的多进程空间并行、时间并行等,各类并行功能可以单独使用、也可以混合使
用,比如：OpenMP-MPI的两级并行、MPI时空间混合并行、OpenMP-MPI时空
间混合并行等。丰富的功能组合可以让学生通过对比掌握各类并行方法的特点和适
用性。
在实用性上,支持多核的普通台式机、工作站、多节点的集群环境、以及超级计算
机系统。框架提供了一些通用的线性求解器以及时间积分模版,包括超松弛法(SOR)、
双共轭梯度稳定法(BiCGStab)、牛顿拉夫逊法等,所有运行参数可通过配置文件指
定,方便调试和快速构建原型。各个层次(空间网格、各类求解器、时间并行算法)均
可单独扩展,支持HDF5格式的大文件输出、自动完成计算和通信性能的统计分析,
为算法优化提供依据。
2.3框架的实现方法
该框架的主体采用C开发,便于各类算法的模版化、提供高层的抽象接口以及提高
扩展性；底层的具体计算部分则采用了传统的Fortran语言,便于操作向量和矩阵、
灵活支持物理模型的维度切换以及提供更高的性能。框架的代码结构和使用方式如
图4所示。
图4框架的实现流程
代码在组织结构上,特别考虑了扩展性和实验教学需求。通过共享基础代码的功能
和算法模版,实验课题和物理模型均在各自的目录内独立发展。希望通过不断丰富
实验课题和实例代码,积累教学成果,并适时转化成实用的解决方案。为方便学习交
流、扩展升级以及成果积累,该框架已经采用开源项目的形式发布,目前还得到了时
间并行学术组织的认可,列入了时间并行代码资源库。开源的形式还有助于学生练
习现代软件工程的整套流程,起到综合实验的效果。
3物理模型与实验课题
为了让学生深入理解并掌握并行计算的应用方法,将物理模型经过简化,作为实验课
题集成到框架中。首先引入的是在物理模型和数值计算中具有普遍代表性的热扩散
方程,之后在扩散问题的基础上,将具有广泛实际应用的多相场(phasefield)问题作
为重点实验课题。多相场的数值求解一直是科学计算领域的研究重点,我国神威•太
湖之光超级计算机获得戈登贝尔奖的应用均涉及相场模拟[12]。通过将实验课题与
实际问题、研究前沿相结合的方式,促进学生对各类知识的融会贯通,学以致用。
扩散问题最具代表性,且数值算法简单,适合作为教学范例。在简化后的热扩散模型
中,扩散系数λ为常数,初始值和边界条件给定。在框架原型系统的开发阶段,验证了
时空混合并行算法对热扩散问题的加速效果,详细的实验结果表明在问题规模一定
的情况下,空间并行的性能(13.5倍)达到极限后,再利用时空混合并行(100个并行时
间片),最终取得了整体200倍以上的性能提升[13]。
λ2Φ(热扩散方程)
(1)
λ2Φ-κΦ(Φ-α)(Φ-β)
(Allen-Cahn方程)
(2)
在扩散项的基础上加上反应项,就得到了多相场模拟的主要方程之一的Allen-Cahn
方程。该类方程的求解过程涉及有限差分、有限元等数值计算的经典方法,且由于
计算量大、耗时长,一直是高性能计算领域的代表型应用。虽然框架针对的是常系
数的简化版,但由于增加了非线性的反应项,算法的性能优化变得极有挑战性。学生
可以从数值算法的混合并行化、时间并行的收敛性、网格结构及网络传输优化等多
个层次开展实验。初步实验结果表明,在一定条件下,时空间混合并行技术可加速多
相场的计算,但需要探索和解决的问题还很多,较适合作为开放性实验课题。
4在教学实验中的应用
一直以来,我校高性能计算教学团队都采用了案例和任务驱动型实验教学方法[14]。
除计算机专业外,还面向全校相关专业的研究生开设并行计算的高级选修课程。该
框架源自团队的内部积累,也是与国内外同行交流学习的成果[13]。基于该框架,同
时借鉴其他高校的经验[15-16],针对本科生、研究生以及不同专业的学习需求,进一
步加强了教学实验课程的细分。
对于计算机专业侧重并行技术和数值算法,实验涵盖了空间网格划分和管理、文件
并行读写、数值算法并行化等普通专业课题,也包括开发自适应网格的接口,实现其
他时间并行算法等具有较高难度的课题,鼓励学生为框架贡献自己的求解器,扩充和
优化框架的基础功能。对于相关专业的选修课,则利用框架的高层接口,侧重上层建
模能力的训练,解决学习科研中的实际问题。图4(b)展示了此类实验的流程,首先学
生利用有限差分或有限元方法,完成模型的离散化,然后从框架提供的算法中选择合
适的组合,并编写问题特有的计算代码(stencilcode),设置初值和边界条件,最后进
行实验方法的可行性验证。此类实验可以为框架增加实际的应用课题,丰富教学案
例。对于课程设计,鼓励计算机专业和其他专业的学生组队,将实际问题建模和求解
过程优化结合起来,培育实用性解决方案。目前,相场模拟作为第一个开放性实验课
题,还处于收集和优化算法阶段。
5结语
本文提出的时空间混合并行计算框架,从原型系统开发到开源项目的发布历时2年,
并在国内外的超级计算机上完成了测试和功能验证。高性能计算相关的实践教学,
可通过对源代码的学习分析、改造优化、模型求解等多种方式,有效锻炼学生综合
运用知识、解决实际问题的能力,同时开源形式有助于不断丰富教学案例和实验课
题。除了多相场之外,将陆续精选出一些难度适中的科学计算问题,引导学生广泛探
索,并以天津超算中心为平台依托,加快产学研结合。
参考文献(References)
【相关文献】
[1]葛蔚,郭力,李静海,等.关于超级计算发展战略方向的思考[J].中国科学院院刊,2016(6):614-623.
[2]邓越凡,张黎浩.E级计算之远景[J].科技导报,2016,34(21):85-94.
[3]陆枫,金海.将并行计算纳入本科教育深化计算机学科创新人才培养[J].高等工程教育研
究,2016(6):108-112.
[4]Reyes-OrtizJL,OnetoL,aanalyticsinthecloud:Sparkonhadoopvs
mpi/openmponBeowulf[J].ProcediaComputerScience,2015(53):121-130.
[5]GanderMJ,isofthepararealtime-paralleltime-integration
method[J].SIAMJournalonScientificComputing,2007,29(2):556-578.
[6]WuS,ShiB,al-RichardsonalgorithmforsolvingnonlinearODEsand
PDEs[J].CommunicationinComputationalPhysics,2009,6(4):883-902.
[7]吴树林,王志勇,黄乘明.Parareal算法的均方稳定性分析[J].计算数学,2011,33(2):113-124.
[8]DongarraJ,HittingerJ,BellJ,dmathematicsresearchforexascale
computing[M].TechnicalReport,2014.
[9]FalgoutRD,Friedhoff,S,KolevTV,eltimeintegrationwithmultigrid[J].SIAM
JournalonScientificComputing,2014,36(6):C635-C661.
[10]DubeyA,AntypasK,CalderAC,ionofFLASH,amulti-physicsscientific
simulationcodeforhigh-performancecomputing[J].InternationalJournalofHigh
PerformanceComputingApplications,2014,28(2):225-237.
[11]ChamberlainBL,CallahanD,elprogrammabilityandthechapel
language[J].TheInternationalJournalofHighPerformanceComputingApplications,2007,
21(3):291-312.
[12]杨广文,赵文来,丁楠,等.神威·太湖之光及其应用系统[J].科学,2017,69(3):12-16.
[13]-parallelperformanceevaluationofdomaindecomposition
andPararealmethodsfordiffusionproblem[D].Japan:KobeUniversity,2017.
[14]金毅.基于案例-任务驱动教学法的高性能计算课程研究[D].乌鲁木齐:新疆师范大学,2010.
[15]徐新海,唐玉华,林宇斐.跨专业并行计算基础课程教学设计[J].计算机教育,2014(23):106-109.
[16]于泠,陈波.认知负荷理论指导下的并行计算实验教学探究[J].计算机教育,2016(12):77-80.