微信服务号

微信订阅号

2025年3月24日 15:36 星期一
首页 > 过刊浏览>2021年第32卷第8期 >2341-2351. DOI:10.13328/j.cnki.jos.006006
PDF HTML阅读 XML下载 导出引用 引用提醒
国产异构系统上的HPCG并行算法及高效实现
作者:
作者简介:

刘芳芳(1982-),女,博士,正高级工程师,CCF专业会员,主要研究领域为高性能扩展数学库,稀疏迭代解法器,异构众核并行.
马文静(1981-),女,博士,副研究员,CCF专业会员,主要研究领域为高性能计算.
王志军(1995-),男,硕士,主要研究领域为高性能计算,并行计算.
杨超(1979-),男,博士,研究员,博士生导师,CCF高级会员,主要研究领域为高性能计算,科学与工程计算.
汪荃(1996-),女,硕士,主要研究领域为并行计算.
孙家昶(1942-),男,研究员,博士生导师,主要研究领域为科学与工程计算的方法、理论与应用,并行计算.
吴丽鑫(1994-),女,硕士,主要研究领域为并行计算.

通讯作者:

马文静,E-mail:wenjing@iscas.ac.cn

中图分类号:

TP303

基金项目:

中国科学院战略性先导科技专项（C类）（XDC01030200）；国家重点研发计划（2018YFB0204404，2016YFB0200603）


Parallel Algorithm and Efficient Implementation of HPCG on Domestic Heterogeneous Systems
Author:
Fund Project:

Strategic Priority Research Program of the Chinese Academy of Sciences (Category C) (XDC01030200); National Key Research and Development Program of China (2018YFB0204404, 2016YFB0200603)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [28]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    HPCG基准测试程序是一种新的超级计算机排名度量标准.该测试基准主要用于衡量超级计算机解决大规模稀疏线性系统的能力，更贴近实际应用，近年来广受关注.基于国产超级计算机研究异构众核并行HPCG软件具有非常重要的意义，其不仅可以提升国产超级计算机HPCG的排名，还对很多应用提供了并行算法、优化技术等方面的参考.面向某国产复杂异构超级计算机开展研究，首先采用了分块图着色算法对HPCG进行并行，并提出一种适用于结构化网格的图着色算法.该算法并行性能高于传统的JPL、CC等算法，且着色质量高，运用于HPCG后，迭代次数减少了3次，整体性能提升了6%.分析了复杂异构系统各个部件传输的开销，提出一套更适用于HPCG的任务划分方法，并从稀疏矩阵存储格式、稀疏矩阵重排、访存等角度开展了细粒度的优化.在多进程计算时，还采用内外区划分算法将核心函数SpMV、SymGS中的邻居通信操作进行了隐藏.最终整机测试时，性能达到了国产超级计算机峰值性能的1.67%，与单节点相比，整机弱可扩展性并行效率达到了92%.

    Abstract:

    HPCG benchmark is a new standard for supercomputer ranking. This benchmark is used mainly for evaluating how fast a supercomputer is able to solve a large scale sparse linear system, which is closer to real applications, and has attracted extensive attention recently. Research of parallel HPCG on domestic heterogeneous many-core supercomputers is very important, not only to improve the HPCG ranking of Chinese supercomputers, but also to provide reference of parallel algorithm and optimization techniques for many applications. This work studies parallelization and optimization of HPCG on a domestically produced complex heterogeneous supercomputer, leveraging blocked graph coloring algorithm for parallelism exploration for the first time on this system, and proposes a graph coloring algorithm for structured grids. The parallelism produced by this algorithm is higher than the traditional JPL and CC algorithm, with better coloring quality. With this algorithm, successfully reduced the iteration number of HPCG by 3 times, and the total performance is improved by 6%. This study also analyzes the data transfer cost of each component in the complex heterogeneous system, providing a task partitioning method, which is more suitable for HPCG, and the neighbor communication cost in SpMV and SymGS is hidden by inner-outer region partitioning. In the whole-system test, an HPCG performance of 1.67% of the peek GFLOPS of the system is achieved, compared to single-node performance, the weak-scaling efficiency on the whole system has reached 92%.

    参考文献
    [1] Dongarra J, Heroux MA. Toward a new metric for ranking high performance computing systems. Technical Report, SAND2013-4744, Sandia National Laboratories, 2013.
    [2] Dongarra JJ, Luszczek P, Petitet A. The LINPACK benchmark:Past, present and future. Concurrency and Computation Practice & Experience, 2003,15(9):803-820.
    [3] https://www.isc-hpc.com/
    [4] http://www.supercomputing.org/
    [5] Haidar A, Tomov S, Dongarra J, et al. Harnessing GPU tensor cores for fast FP16 arithmetic to speed up mixed-precision iterative refinement solvers. In:Proc. of the Int'l Conf. for High Performance Computing, Networking, Storage and Analysis (SC 2018). IEEE, 2018. 603-613.
    [6] Haidar A, Wu P, Tomov S, et al. Investigating half precision arithmetic to accelerate dense linear system solvers. In:Proc. of the 8th Workshop on Latest Advances in Scalable Algorithms for Large-scale Systems. ACM, 2017. 1-8.
    [7] Bell N, Garland M. Implementing sparse matrix-vector multiplication on throughput-oriented processors. In:Proc. of the Conf. on High Performance Computing Networking, Storage and Analysis. 2009. 1-11.
    [8] Vazquez F, Fernandez J, Garzon E. A new approach for sparse matrix vector product on NVIDIA GPUs. Concurrency and Computation:Practice and Experience, 2011,23(8):815-826.
    [9] Ashari A, Sedaghati N, Eisenlohr J, et al. An efficient two-dimensional blocking strategy for sparse matrix-vector multiplication on GPUs. In:Proc. of the 28th ACM Int'l Conf. on Supercomputing. ACM Press, 2014. 273-282.
    [10] Yan S, Li C, Zhang Y, et al. yaSpMV:Yet another SpMV framework on GPUs. ACM SIGPLAN Notices, 2014,49(8):107-118.
    [11] Pichel JC, Rivera FF, Fernández M, et al. Optimization of sparse matrix-vector multiplication using reordering techniques on GPUs. Microprocessors and Microsystems, 2012,36(2):65-77.
    [12] Tang WT, Tan WJ, Ray R, et al. Accelerating sparse matrix-vector multiplication on GPUs using bit-representation-optimized schemes. In:Proc. of the Int'l Conf. on High Performance Computing, Networking, Storage and Analysis. 2013. 1-12.
    [13] Williams S, Oliker L, Vuduc R, et al. Optimization of sparse matrix-vector multiplication on emerging multicore platforms. Parallel Computing, 2009,35(3):178-194.
    [14] Guo D, Gropp W. Adaptive thread distributions for SpMV on a GPU. In:Proc. of the Extreme Scaling Workshop. 2012. 1-5.
    [15] Park J, Smelyanskiy M, Vaidyanathan K, et al. Efficient shared-memory implementation of high-performance conjugate gradient benchmark and its application to unstructured matrices. In:Proc. of the Int'l Conf. for High Performance Computing, Networking, Storage and Analysis (SC 2014). IEEE, 2014. 945-955.
    [16] Iwashita T, Nakanishi Y, Shimasaki M. Comparison criteria for parallel orderings in ILU preconditioning. SIAM Journal on Scientific Computing, 2005,26(4):1234-1260.
    [17] Kumahata K, Minami K, Maruyama N. High-performance conjugate gradient performance improvement on the K computer. The Int'l Journal of High Performance Computing Applications, 2016,30(1):55-70.
    [18] Phillips E, Fatica M. A CUDA implementation of the high performance conjugate gradient benchmark. In:Proc. of the Int'l Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems. Cham:Springer-Verlag, 2014. 68-84.
    [19] Liu YQ, Zhang XY, Yang C, et al. Accelerating HPCG on Tianhe-2:A hybrid CPU-MIC algorithm. In:Proc. of the 20th IEEE Int'l Conf. on Parallel and Distributed Systems (ICPADS). IEEE, 2014. 542-551.
    [20] Liu YQ. Research on key technologies of communication intensive kernels for Intel MIC architecture[Ph.D. Thesis]. Beijing:Institute of Software, Chinese Academy of Sciences, 2015(in Chinese with English abstract).
    [21] Ao YL. Research on key optimizations of sparse matrix and stencil computation for the domestic large many-core system[Ph.D. Thesis]. Beijing:Institute of Software, Chinese Academy of Sciences, 2017(in Chinese with English abstract).
    [22] Ruiz D, Mantovani F, Casas M, et al. The HPCG benchmark:Analysis, shared memory preliminary improvements and evaluation on an Arm-based platform. 2018. https://upcommons.upc.edu/bitstream/handle/2117/116642/1HPCG_shared_mem_implementation_tech_report.pdf?sequence=8&isAllowed=y
    [23] Greathouse JL, Daga M. Efficient sparse matrix-vector multiplication on GPUs using the CSR storage format. In:Proc. of the Int'l Conf. for High Performance Computing, Networking, Storage and Analysis. IEEE Press, 2014. 769-780.
    [24] Jones MT, Plassmann PE. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, 1993,14(3):654-669.
    [25] Cohen J, Castonguay P. Efficient graph matching and coloring on the GPU. In:Proc. of the GPU Technology Conf. 2012. 1-10.
    附中文参考文献:
    [20] 刘益群.MIC众核架构通信密集型函数的算法设计与性能优化研究[博士学位论文].北京:中国科学院软件研究所,2015.
    [21] 敖玉龙.国产大型众核系统上稀疏矩阵和Stencil运算的性能优化关键技术研究[博士学位论文].北京:中国科学院软件研究所,2017.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

刘芳芳,王志军,汪荃,吴丽鑫,马文静,杨超,孙家昶.国产异构系统上的HPCG并行算法及高效实现.软件学报,2021,32(8):2341-2351

复制
分享
文章指标
  • 点击次数:1772
  • 下载次数: 5450
  • HTML阅读次数: 4425
  • 引用次数: 0
历史
  • 收稿日期:2019-08-22
  • 最后修改日期:2019-12-05
  • 在线发布日期: 2021-08-05
  • 出版日期: 2021-08-06
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19728283位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号