面向CPU、GPU多目标机的混合求解器设计与实现

doi:10.16182/j.issn1004731x.joss.21-1317

系统仿真学报 ›› 2022, Vol. 34 ›› Issue (4): 670-678.doi: 10.16182/j.issn1004731x.joss.21-1317

• 专栏：面向复杂产品的建模仿真与优化 • 上一篇下一篇

面向CPU、GPU多目标机的混合求解器设计与实现

马琳(), 张雪松(), 雷新丽, 包铁

吉林大学计算机科学与技术学院，吉林长春 130012

收稿日期:2021-12-20 修回日期:2022-02-16 出版日期:2022-04-30 发布日期:2022-04-19
通讯作者: 张雪松 E-mail:malin20@mails.jlu.edu.cn;wetting@jlu.edu.cn
作者简介:马琳(1995-)，男，硕士生，研究方向为并行计算与复杂系统仿真。E-mail：malin20@mails.jlu.edu.cn
基金资助:
国家重点研发计划(2018YFB1701600)

Design and Implementation of A Hybrid Solver on CPU and GPU Multi-target Machines

Lin Ma(), Xuesong Zhang(), Xinlin Lei, Tie Bao

College of Computer Science and Technology, Jilin University, Changchun 130012, China

Received:2021-12-20 Revised:2022-02-16 Online:2022-04-30 Published:2022-04-19
Contact: Xuesong Zhang E-mail:malin20@mails.jlu.edu.cn;wetting@jlu.edu.cn

摘要/Abstract

摘要：

传统常微分方程的并行求解方法主要包括面向任务的并行和面向方法的并行，但是这两种求解算法，只能利用CPU，或者只能面向同质形式的ODE(ordinary differential equations)簇，存在严重不足。以RIDC(revisionist integral deferred correction)算法为基础，设计了一种面向CPU、GPU多目标机的混合求解器，基于流水线形式求解微分方程组，实现了单个方程组的内部和不同方程组之间的并行计算，进而能够充分发挥GPU的多核优势，有利于计算节点内部的负载均衡。仿真实验验证了框架的效率、准确率和精准度。

关键词: 常微分方程, 混合求解, 多目标机, CPU, GPU

Abstract:

The traditional parallel solving methods for the ordinary differential equations mainly include the task-oriented parallelism and the method-oriented parallelism. However, these two solving algorithms have serious shortcomings, which can only use CPU resource or just design for the homogeneous form of ODE(ordinary differential equations) clusters. By using RIDC(revisionist integral deferred correction) algorithm, a hybrid solver based on CPU and GPU multi-target machine is designed, which solves the differential equation system based on the pipeline form. Meanwhile, the parallel calculation within a single equation group and between the different equation groups is realized, which can give full play to the multi-core advantage of GPU, and also help to balance the load inside the computing node. The simulation experiments verify the efficiency, accuracy and precision of the framework.

Key words: ordinary differential equation, hybrid solver, multi-target machine, CPU, GPU

中图分类号:

TP391.9

马琳, 张雪松, 雷新丽, 包铁. 面向CPU、GPU多目标机的混合求解器设计与实现[J]. 系统仿真学报, 2022, 34(4): 670-678.

Lin Ma, Xuesong Zhang, Xinlin Lei, Tie Bao. Design and Implementation of A Hybrid Solver on CPU and GPU Multi-target Machines[J]. Journal of System Simulation, 2022, 34(4): 670-678.

图/表 8

图1

图2

图3

表1

表2

表3

表4

表5

参考文献 19

1	Kindratenko V. Numerical Computations with GPUs[M]. Springer International Publishing, 2014: 159-182.
2	Ahnert K, Demidov D, Mulansky M. Solving Ordinary Differential Equations on GPUs[M]. Springer International Publishing, 2014: 125-157.
3	Stone C, Davis R. Techniques for Solving Stiff Chemical Kinetics on GPUs[C]//51st AIAA Aerospace Sciences Meeting Including the New Horizons Forum and Aerospace Exposition. Texas: AIAA, 2013: 369.
4	Sewerin F, Rigopoulos S. A Methodology for the Integration of Stiff Chemical Kinetics on GPUs[J]. Combustion and Flame(S0010-2180), 2015, 162(4): 1375-1394.
5	Curtis N J, Niemeyer K E, Sung C J. An Investigation of GPU-Based Stiff Chemical Kinetics Integration Methods[J]. Combustion and Flame(S0010-2180), 2017, 179: 312-324.
6	Stone C P, Alferman A T, Niemeyer K E. Accelerating Finite-Rate Chemical Kinetics with Coprocessors: Comparing Vectorization Methods on GPUs, MICs, and CPUs[J]. Computer Physics Communications(S0010-4655),
	2018, 226: 18-29.
7	Burrage K. Parallel Methods for ODEs[J]. Advances in Computational Mathematics (S1019-7168), 1997, 7(1/2): 1-31.
8	Vandewalle S, Roose D. The Parallel Waveform Relaxation Multigrid Method[C]//Third SIAM Conference on Parallel Processing for Scientific Computing. Los Angeles: SIAM, 1987: 152-156.
9	Lions J L, Maday Y, Turinici G. A "parareal" in Time Discretization of PDE's[J]. Comptes Rendus De l Académie des Sciences-Series I-Mathematics(S0764-4442), 2001, 332(7): 661-668.
10	Gander M J, Vandewalle S. On the Superlinear and Linear Convergence of the Parareal Algorithm[M]//Domain Decomposition Methods in Science and Engineering XVI. Springer, Berlin: Heidelberg, 2007: 291-298.
11	Miranker W L, Liniger W. Parallel Methods for the Numerical Integration of Ordinary Differential Equations[J]. Mathematics of Computation(S0025-5718), 1967, 21(99): 303-320.
12	Enenkel R F. DIMSEMS: Diagonally Implicit Single-Eigenvalue Methods for the Numerical Solution of Stiff Ordinary Differential Equations on Parallel Computers[D]. Toronto: University of Toronto, 1997.
13	Ketcheson D, Waheed U B. A Comparison of High Order Explicit Runge-Kutta, Extrapolation, and Deferred Correction Methods in Serial and Parallel[J]. Mathematics(S2227-7390), 2013, 9(2): 175-200.
14	Kappeller M, Kiehl M, Perzl M, et al. Optimized Extrapolation Methods for Parallel Solution of IVPs on Different Computer Architectures[J]. Applied Mathematics and Computation(S0096-3003), 1996, 77(23): 301-315.
15	Christlieb A, Ong B, Qiu J M. Integral Deferred Correction Methods Con-Structed with High Order Runge-Kutta Integrators[J]. Mathematics of Computation(S0096-3003), 2010, 79(270): 761-783.
16	Christlieb A, Ong B. Implicit Parallel Time Integrators[J]. Journal of Scientific Computing(S0885-7474), 2011, 49(2): 167-179.
17	Dutt A, Greengard L, Rokhlin V. Spectral Deferred Correction Methods for Ordinary Differential Equations[J]. BIT Numerical Mathematics(S0006-3835), 2000, 40(2): 241-266.
18	Christlieb A J, Macdonald C B, Ong B W. Parallel High-Order Integrators[J]. SIAM Journal on Scientific Computing(S1064-8275), 2010, 32(2): 818-835.
19	Simos T E, Tsitouras C. On High Order Runge-Kutta-Nyström Pairs[J]. Journal of Computational and Applied Mathematics, 2022, 400: 113753.

处理器	显式欧拉	龙格库塔	隐式欧拉
CPU	0.03	0	0.02
GPU	0	0	0.01

采样点数(方程数2)	CPU单线程显式欧拉4阶	CPU单线程RK4阶	GPU显式欧拉算法
100	0.018 8	0.006 4	0.026 6
1 000	0.151 4	0.052 0	0.221 8
10 000	1.854 2	0.628 4	2.063 9
100 000	18.395 6	6.258 4	20.161 0

采样点数(方程数10)	CPU单线程显式欧拉4阶	CPU单线程RK4阶	GPU显式欧拉算法
100	0.031 0	0.012 8	0.049 8
1 000	0.304 4	0.130 4	0.451 6
10 000	3.038 3	1.298 8	4.312 1
100 000	30.305 6	12.986 4	43.526 8

采样点数(方程数2)	CPU单线程隐式欧拉4阶	GPU隐式欧拉4阶	CPU单线程隐式欧拉8阶	GPU隐式欧拉8阶
100	0.814 6	0.286 2	4.334 6	0.933 6
1 000	5.588 4	2.644 8	31.725 0	8.930 8

采样点数(方程数10)	CPU单线程隐式欧拉4阶	GPU隐式欧拉4阶	CPU单线程隐式欧拉8阶	GPU隐式欧拉8阶
100	13.498 4	0.671 8	69.640 8	2.132 2
1 000	85.591 6	6.331 6	483.671 8	20.578 2

面向CPU、GPU多目标机的混合求解器设计与实现

Design and Implementation of A Hybrid Solver on CPU and GPU Multi-target Machines

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 19

相关文章 13

编辑推荐

Metrics

本文评价

[1]	李志华, 傅东金, 李广, 樊志华. 一种带自适应量子的量化状态系统方法[J]. 系统仿真学报, 2021, 33(2): 445-452.
[2]	李志华, 江德, 吴晨佳, 樊志华. 一种基于量子化状态系统的刚性ODE求解方法[J]. 系统仿真学报, 2021, 33(1): 46-53.
[3]	邵绪强, 宋雨. 固流交互中真实感溶化现象的实时模拟[J]. 系统仿真学报, 2017, 29(3): 502-508.
[4]	刘复昌, 王双建, 潘志庚, 王金荣. 并行化碰撞检测算法综述[J]. 系统仿真学报, 2017, 29(11): 2601-2608.
[5]	向南, 张明敏, 朱凌云. 动态人群情绪感染并行仿真算法[J]. 系统仿真学报, 2016, 28(9): 1964-1969.
[6]	翟小明, 尹勇, 神和龙. 内河船舶模拟器中大尺度河流实时绘制[J]. 系统仿真学报, 2016, 28(9): 2023-2028.
[7]	韩敏, 张海超, 边茂松, 郑丹晨. 流线增强型线性积分卷积流场可视化[J]. 系统仿真学报, 2016, 28(12): 2933-2938.
[8]	刘璐, 刘箴, 何高奇, 陈田, 刘婷婷, 刘翠娟. 一种基于DirectCompute加速的实时流体仿真框架[J]. 系统仿真学报, 2016, 28(10): 2467-2475.
[9]	周昆, 刘箴, 何高奇, 陈田, 刘婷婷, 刘翠娟. 基于模块划分的GPU加速布料动画[J]. 系统仿真学报, 2016, 28(10): 2476-2484.
[10]	王圣华, 谭剑. 中国皮影体可视化仿真方法研究[J]. 系统仿真学报, 2015, 27(9): 2126-2134.
[11]	陈志佳, 朱元昌, 邸彦强, 冯少冲. 一种IaaS模式“云训练”系统设计[J]. 系统仿真学报, 2015, 27(5): 1095-1104.
[12]	赵元, 程家昌, 王璐, 胡月明. 基于GPU的一类地理多智能体系统并行仿真研究[J]. 系统仿真学报, 2015, 27(2): 396-403.
[13]	刘良平, 刘箴, 方昊, 刘翠娟, 刘婷婷. 基于GPU的三维场景表面流体碰撞检测方法研究[J]. 系统仿真学报, 2015, 27(10): 2439-2445.