网格化分布式新安江模型并行计算算法

doi:10.11772/j.issn.1001-9081.2022111760

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (11): 3327-3333.DOI: 10.11772/j.issn.1001-9081.2022111760

• 2022年全国开放式分布与并行计算学术年会(DPCS 2022) • 上一篇

网格化分布式新安江模型并行计算算法

刘乾¹, 张洋铭¹^,², 万定生¹()

^1.河海大学计算机与信息学院，南京 211100
^2.南京银行股份有限公司，南京 210019

收稿日期:2022-11-24 修回日期:2023-02-15 接受日期:2023-02-17 发布日期:2023-03-08 出版日期:2023-11-10
通讯作者: 万定生
作者简介:刘乾（1998—），男，江苏南京人，硕士研究生，CCF会员，主要研究方向：分布式水文模型并行计算
张洋铭（1997—），男，江苏徐州人，硕士研究生，CCF会员，主要研究方向：分布式水文模型并行计算
万定生（1963—），男，江苏溧阳人，教授，CCF会员，主要研究方向：数据管理、数据挖掘。 dshwan@hhu.edu.cn
基金资助:
国家重点研发计划项目(2018YFC1508106)

Parallel computing algorithm of grid-based distributed Xin’anjiang hydrological model

Qian LIU¹, Yangming ZHANG¹^,², Dingsheng WAN¹()

^1.College of Computer and Information Engineering，Hohai University，Nanjing Jiangsu 211100，China
^2.Bank of Nanjing Company Limited，Nanjing Jiangsu 210019，China

Received:2022-11-24 Revised:2023-02-15 Accepted:2023-02-17 Online:2023-03-08 Published:2023-11-10
Contact: Dingsheng WAN
About author:LIU Qian， born in 1998， M. S. candidate. His research interests include parallel computing of distributed hydrological models.
ZHANG Yangming， born in 1997， M. S. candidate. His research interests include parallel computing of distributed hydrological models.
WAN Dingsheng， born in 1963， professor. His research interests include data management， data mining.
Supported by:
National Key Research and Development Program of China(2018YFC1508106)

摘要/Abstract

摘要：

近年来，网格化分布式新安江模型（GXM）在洪水预报中发挥了重大作用，但在进行洪水过程模拟时，模型数据量与计算量巨大，GXM的计算时间随着模型预热期的增加呈指数增长，严重影响GXM的计算效率。因此，提出一种基于网格流向划分与动态优先级有向无环图（DAG）调度的GXM并行算法。首先，对模型参数、模型构件、模型计算过程进行分析；其次，从空间并行性的角度提出了基于网格流向划分的GXM并行算法以提高模型的计算效率；最后，提出一种基于动态优先级的DAG任务调度算法，通过构建网格计算节点的DAG并动态更新计算节点的优先级以实现GXM计算过程中的任务调度，减少模型计算中数据倾斜现象的产生。在陕西省大理河流域与安徽省屯溪流域对提出的算法进行实验，在预热期为30 d、数据分辨率为1 km的情况下，相较于传统的串行算法，所提算法的最大加速比分别达到了4.03和4.11，有效提升了GXM的计算速度与资源利用率。

关键词: 网格化分布式新安江模型, 网格流向划分, 并行计算, 有向无环图, 任务调度

Abstract:

In recent years， the Grid-based distributed Xin’anjiang hydrological Model （GXM） has played an important role in flood forecasting， but when simulating the flooding process， due to the vast amount of data and calculation of the model， the computing time of GXM increases exponentially with the increase of the model warm-up period， which seriously affects the computational efficiency of GXM. Therefore， a parallel computing algorithm of GXM based on grid flow direction division and dynamic priority Directed Acyclic Graph （DAG） scheduling was proposed. Firstly， the model parameters， model components， and model calculation process were analyzed. Secondly， a parallel algorithm of GXM based on grid flow direction division was proposed from the perspective of spatial parallelism to improve the computational efficiency of the model. Finally， a DAG task scheduling algorithm based on dynamic priority was proposed to reduce the occurrence of data skew in model calculation by constructing the DAG of grid computing nodes and dynamically updating the priorities of computing nodes to achieve task scheduling during GXM computation. Experimental results on Dali River basin of Shaanxi Province and Tunxi basin of Anhui Province show that compared with the traditional serial computing method， the maximum speedup ratio of the proposed algorithm reaches 4.03 and 4.11， respectively， the computing speed and resource utilization of GXM were effectively improved when the warm-up period is 30 days and the data resolution is 1 km.

Key words: Grid-based distributed Xin’anjiang hydrological Model (GXM), grid flow direction division, parallel computing, Directed Acyclic Graph (DAG), task scheduling

中图分类号:

P333

刘乾, 张洋铭, 万定生. 网格化分布式新安江模型并行计算算法[J]. 计算机应用, 2023, 43(11): 3327-3333.

Qian LIU, Yangming ZHANG, Dingsheng WAN. Parallel computing algorithm of grid-based distributed Xin’anjiang hydrological model[J]. Journal of Computer Applications, 2023, 43(11): 3327-3333.

图/表 11

图1 GXM并行框架

Fig. 1 Parallel framework of GXM

图2 GXM构件分类

Fig. 2 Component classification of GXM

图3 网格单元流向标记

Fig. 3 Grid cell flow direction markers

图4 网格流向矩阵和水流流向矩阵

Fig. 4 Grid flow direction matrix and water flow direction matrix

图5 累计汇水面积矩阵及水系矩阵生成过程

Fig. 5 Generation process of cumulative catchment area matrix and water system matrix

图6 数据倾斜现象

Fig. 6 Data skew phenomenon

图7 流域有效网格单元的DAG

Fig. 7 DAG of effective grid cells in basin

图8 GXM并行计算过程中的任务调度

Fig. 8 Task scheduling in GXM parallel computing process

图9 串行算法与GXM并行算法在大理河流域和屯溪流域的计算时间比较

Fig.9 Computing time comparison between serial algorithm and GXM parallel algorithm in Dali River Basin and Tunxi Basin

表1 调度算法对并行计算的影响

Tab. 1 Influence of scheduling algorithms on parallel computing

预热期/d	原并行计算时间/s	调度后并行计算时间/s
30	180.65	160.22
60	268.21	187.53
90	310.89	200.12

表2 并行效率对比

Tab. 2 Parallel efficiency comparison

线程数	调度后的并行效率	未调度的并行效率
2	0.95	0.95
4	0.90	0.86
6	0.88	0.82
8	0.84	0.80
10	0.78	0.63
12	0.72	0.42
14	0.70	0.38
16	0.57	0.34

参考文献 19

1	芮孝芳. 对流域水文模型的再认识［J］. 水利水电科技进展， 2018， 38（2）： 1-7. 10.3880/j.issn.1006-7647.2018.02.001
	RUI X F. More discussion of watershed hydrological model［J］. Advances in Science and Technology of Water Resources， 2018， 38（2）： 1-7. 10.3880/j.issn.1006-7647.2018.02.001
2	芮孝芳. 论流域水文模型［J］. 水利水电科技进展， 2017， 37（4）：1-7， 58. 10.3880/j.issn.1006-7647.2017.04.001
	RUI X F. Discussion of watershed hydrological model［J］. Advances in Science and Technology of Water Resources， 2017， 37（4）：1-7， 58. 10.3880/j.issn.1006-7647.2017.04.001
3	BEVEN K J， KIRKBY M J， FREER J E， et al. A history of TOPMODEL［J］. Hydrology and Earth System Sciences， 2021， 25（2）： 527-549. 10.5194/hess-25-527-2021
4	LIU Z， MARTINA M L V， TODINI E. Flood forecasting using a fully distributed model： application of the TOPKAPI model to the Upper Xixian Catchment［J］. Hydrology and Earth System Sciences， 2005， 9（4）： 347-364. 10.5194/hess-9-347-2005
5	姚成. 基于栅格的分布式新安江模型构建与分析［D］. 南京：河海大学， 2007： 16-20.
	YAO C. Development and application of grid-based distributed Xin’anjinag model［D］. Nanjing： Hohai University， 2007： 16-20.
6	姚成，李致家，张珂，等. 基于栅格型新安江模型的中小河流精细化洪水预报［J］. 河海大学学报（自然科学版）， 2021， 49（1）：19-25. 10.3876/j.issn.1000-1980.2021.01.004
	YAO C， LI Z J， ZHANG K， et al. Fine-scale flood forecasting for small and medium-sized rivers based on Grid-Xin’anjiang model［J］. Journal of Hohai University （Natural Sciences）， 2021， 49（1）：19-25. 10.3876/j.issn.1000-1980.2021.01.004
7	叶翔宇，李强，郭禹含，等. 高性能并行分布式水文模型研究进展［J］. 地理科学进展， 2022， 41（4）：731-740. 10.18306/dlkxjz.2022.04.016
	YE X Y， LI Q， GUO Y H， et al. Progress of research on high-performance parallel distributed hydrological model［J］. Progress in Geography， 2022， 41（4）： 731-740. 10.18306/dlkxjz.2022.04.016
8	LIU J， ZHU A X， QIN C Z. Estimation of theoretical maximum speedup ratio for parallel computing of grid-based distributed hydrological models［J］. Computers and Geosciences， 2013， 60： 58-62. 10.1016/j.cageo.2013.04.030
9	LIU J， ZHU A X， LIU Y， et al. A layered approach to parallel computing for spatially distributed hydrological modeling［J］. Environmental Modelling and Software， 2014， 51： 221-227. 10.1016/j.envsoft.2013.10.005
10	秦泽宁，黎曙，周祖昊，等. 分布式水文模型区域分解并行计算方法及其应用［J］. 水电能源科学， 2020， 38（10）：1-4， 12.
	QIN Z N， LI S， ZHOU Z H， et al. Domain decomposition parallel computing method of distributed hydrological model and its application［J］. Water Resources and Power， 2020， 38（10）：1-4， 12.
11	河海大学. 基于流向的分布式水文模型并行计算方法： 202210254598.1［P］. 2022-05-10.
	Hohai University. Parallel computing method for distributed hydrological models based on flow direction： 202210254598.1［P］. 2022-05-10.
12	LIU J， ZHU A X， QIN C Z， et al. A two-level parallelization method for distributed hydrological models［J］. Environmental Modelling and Software， 2016， 80： 175-184. 10.1016/j.envsoft.2016.02.032
13	王想红，刘纪平，徐胜华，等. 基于NetCDF数据模型的海洋环境数据三维可视化研究［J］. 测绘科学， 2013， 38（2）： 59-61.
	WANG X H， LIU J P， XU S H， et al. Visualization of marine environment data based on NetCDF data model［J］. Science of Surveying and Mapping， 2013， 38（2）： 59-61.
14	刘军志，朱阿兴，秦承志，等. 分布式水文模型的并行计算研究进展［J］. 地理科学进展， 2013， 32（4）： 538-547. 10.11820/dlkxjz.2013.04.006
	LIU J Z， ZHU A X， QIN C Z， et al. Review on parallel computing of distributed hydrological models［J］. Progress in Geography， 2013， 32（4）： 538-547. 10.11820/dlkxjz.2013.04.006
15	邬伦，汪大明，张毅.基于DEM的水流方向算法研究［J］. 中国图象图形学报， 2006， 11（7）： 998-1003. 10.11834/jig.200607171
	WU L， WANG D M， ZHANG Y. Research on the algorithms of the flow direction determination in ditches extraction based on grid DEM［J］. Journal of Image and Graphics， 2006， 11（7）： 998-1003. 10.11834/jig.200607171
16	李致家，姚成，汪中华. 基于栅格的新安江模型的构建和应用［J］. 河海大学学报（自然科学版）， 2007， 35（2）： 131-134. 10.3321/j.issn:1000-1980.2007.02.003
	LI Z J， YAO C， WANG Z H. Development and application of grid-based Xin’anjiang model［J］. Journal of Hohai University （Natural Sciences）， 2007， 35（2）： 131-134. 10.3321/j.issn:1000-1980.2007.02.003
17	王命全，于炯，田园，等.网格环境中基于负载均衡的工作流调度算法［J］.计算机应用，2010，30（12）：3184-3186. 10.3724/sp.j.1087.2010.03184
	WANG M Q， YU J， TIAN Y， et al. Workflow scheduling algorithm based on load balance in grid［J］. Journal of Computer Applications， 2010， 30（12）：3184-3186. 10.3724/sp.j.1087.2010.03184
18	FREITAS H R A， MENDES C L， ILIC A. Performance optimization and scalability analysis of the MGB hydrological model［C］// Proceedings of the IEEE 27th International Conference on High Performance Computing， Data， and Analytics. Piscataway： IEEE， 2020： 31-40. 10.1109/hipc50609.2020.00017
19	ZHANG A， LI T， SI Y， et al. Double-layer parallelization for hydrological model calibration on HPC systems［J］. Journal of Hydrology， 2016， 535： 737-747. 10.1016/j.jhydrol.2016.01.024

[1]	尚绍法, 蒋林, 李远成, 朱筠. 异构平台下卷积神经网络推理模型自适应划分和调度方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2828-2835.
[2]	方和平, 刘曙光, 冉泳屹, 钟坤华. 基于深度强化学习的多数据中心一体化调度优化[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1884-1892.
[3]	宁明超, 张俊勃, 陈戈. 基于面向服务架构的工业软件的任务调度算法[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 885-893.
[4]	吴仁彪, 张振驰, 贾云飞, 乔晗. 云平台下基于截止时间的自适应调度策略[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 176-184.
[5]	姜松岩, 廖晓鹃, 陈光柱. 基于可满足性模理论的多处理机通信延迟优化任务调度方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 185-191.
[6]	蔡婧雯, 韦永壮, 刘争红. 基于GPU的密码S盒代数性质评估方法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2750-2756.
[7]	王旭, 申玉民, 熊晓芸, 李鹏, 王金龙. 基于哈希图的建筑物联网数据管理方法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2471-2480.
[8]	张金泉, 徐寿伟, 李信诚, 王重洋, 徐景芝. 基于正交自适应鲸鱼优化的云计算任务调度[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1516-1523.
[9]	吴晴晴, 周丽华, 寸轩懿, 杜国王, 姜懿庭. 异质信息网络中基于有向无环图的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 895-903.
[10]	邱鑫源, 叶泽聪, 崔翛龙, 高志强. 联邦学习通信开销研究综述[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 333-342.
[11]	徐启迪, 刘争红, 郑霖. 基于GPU的低密度奇偶校验码译码加速技术[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3841-3846.
[12]	解文博, 韦永壮, 刘争红. 基于CUDA的SKINNY加密算法并行实现与分析[J]. 计算机应用, 2021, 41(4): 1136-1141.
[13]	姜琨, 刘征, 朱磊, 李晓星. 基于有向无环图的倒排链等字长划分压缩算法[J]. 计算机应用, 2021, 41(3): 727-732.
[14]	杨先凤, 贵红军, 傅春常. 统一计算设备架构下的F-X域预测滤波并行算法[J]. 计算机应用, 2021, 41(2): 486-491.
[15]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.

网格化分布式新安江模型并行计算算法

Parallel computing algorithm of grid-based distributed Xin’anjiang hydrological model

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 19

相关文章 15

编辑推荐

Metrics