计算机与现代化

• 算法设计与分析 • 上一篇    下一篇

基于CUDA的梯级泵站调度算法实现

  

  1. (中国航天系统科学与工程研究院,北京100048)
  • 收稿日期:2018-05-28 出版日期:2018-11-22 发布日期:2018-11-23
  • 作者简介:项武铭(1993-),男,浙江临海人,中国航天系统科学与工程研究院硕士研究生,研究方向:数据处理,信息系统; 李雪巍(1971-),男,山西长治人,研究员,硕士,研究方向:大数据,智慧城市。

A CUDA-based Cascade Pumping Station Scheduling Algorithm

  1. (China Academy of Aerospace Systems Science and Engineering, Beijing 100048, China)
  • Received:2018-05-28 Online:2018-11-22 Published:2018-11-23

摘要: 动态规划方法求解梯级泵站调度问题十分经典,但在计算上存在“维数灾难”问题,GPU并行计算技术能对重复性计算进行加速,提高算法计算性能。本文对梯级泵站调度问题进行动态规划方法分析,利用CUDA(统一计算设备架构)对调度算法进行改进,给出改进动态规划方法的算法实现,并比较不同计算规模下调度算法计算耗时。实验结果表明,基于CUDA改进动态规划方法实现的梯级泵站调度算法能够降低计算维度,在计算规模较大时,加速效果较好。

关键词: 梯级泵站调度, 动态规划, 并行计算, CUDA

Abstract: The dynamic programming method to solve the cascade pumping station scheduling problem is very classic, but there is a “dimensional disaster” problem in the calculation, GPU parallel computing technology can accelerate the repetitive calculations and improve the computational performance of the algorithm. This paper analyzes the dynamic planning method of cascade pumping station scheduling problems, uses CUDA (Unified Computing Device Architecture) to improve the scheduling algorithm, and gives the improved dynamic programming algorithm, and compares the time-consuming of the scheduling algorithm calculation under different computing scales. The experimental results show that the cascade pumping station scheduling algorithm based on CUDA improved dynamic programming method can reduce the calculation dimension. When the calculation scale is large, the acceleration effect is better.

Key words: cascade pumping station scheduling, dynamic programming, parallel computing, CUDA

中图分类号: