大规模线性问题求解算法的高可扩展性研究
|
摘要
针对大规模线性问题的迭代求解算法在100PF乃至E级超级计算机上的高可扩展性问题进行研究.首先分析了数理模型、数值方法、体系结构的耦合和非均衡特性,将高可扩展性问题归结到的权重图的剖分问题上.然后对若干图剖分算法与软件包进行分析,基于Petal-剖分算法实现了全局通信开销近似优化的大规模聚类分组算法.与基于舒尔补架构的线性问题求解方法相结合,给出了具有高可扩展性的线性问题求解架构(Schur-KS).最后通过大规模环境下的高可扩展性测试和中小规模环境下针对典型实际应用问题用例的强可扩展性测试,分别验证了基于Schur-KS架构的求解算法的高可扩展性以及对典型实际应用问题的求解性能.
The iterative solution algorithm for large-scale linear problems is studied on the high scalability problem of 100 PF and even E-class supercomputers. Firstly, the coupling and non-equilibrium characteristics of the mathematical model, numerical method and computer architecture are analyzed, and the high scalability problem is attributed to the partitioning problem of the weighted graph. Then, some graph partitioning algorithms and software packages are analyzed. Based on Petal-decomposition algorithm, the algorithm of largescale clustering with approximate optimization of global communication overhead is given.Combined with the solving method of linear problem based on Schur complement framework,a solving framework of linear system(named Schur-KS) with high scalability is designed.Finally, through the high scalability test in large-scale parallel computing environment and the strong scalability test of typical practical application problem cases in small and medium scale environment, the high scalability of the algorithm based on Schur-KS framework and the performance of typical practical application problems are verified respectively.
The iterative solution algorithm for large-scale linear problems is studied on the high scalability problem of 100 PF and even E-class supercomputers. Firstly, the coupling and non-equilibrium characteristics of the mathematical model, numerical method and computer architecture are analyzed, and the high scalability problem is attributed to the partitioning problem of the weighted graph. Then, some graph partitioning algorithms and software packages are analyzed. Based on Petal-decomposition algorithm, the algorithm of largescale clustering with approximate optimization of global communication overhead is given.Combined with the solving method of linear problem based on Schur complement framework,a solving framework of linear system(named Schur-KS) with high scalability is designed.Finally, through the high scalability test in large-scale parallel computing environment and the strong scalability test of typical practical application problem cases in small and medium scale environment, the high scalability of the algorithm based on Schur-KS framework and the performance of typical practical application problems are verified respectively.
引文
[1]汲培文,江松,张平文.可计算建模[J].中国科学,2012, 42(6).
[2] Saad Y. Iterative methods for sparse linear systems(2nd edition)[M]. SIAM, 2003.
[3] Metis[CP]. http://glaros.dtc.umn.edu/gkhome/metis/metis/overview.
[4] Cai Xiao-Chuan. David E. Keyes. Nonlinearly Preconditioned Inexact Newton Algorithms[J].SIAM J. Sci. Comput., 2002, 24(1):183-200.
[5] Abraham I, Bartal Y and Neiman O. Using petal-decompositions to build a low stretch spanning tree[J]. in In Proceedings of the 44th Annual ACM Symposium on the Theory of Computing STOC, 2012, 395-406.
[6]张慧荣.大型稀疏线性方程组的新型预条件算法研究[D].中国科学院大学,2017.
[7] Pal Andras Papp, Low-Stretch Spanning Trees[D]. Eotvos Lorand University, 2014.
[8] hmetis[CP]. http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview.
[9] parmetis[CP]. http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview.
[10] SCOTCH[CP]. http://www.labri.fr/perso/pelegrin/scotch.
[11] Tom Leighton, Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms[J]. J. ACM, 1999, 46(6):787-832.
[12] Arora S, Rao S, Vazirani U. Expander flows, geometric embeddings and graph partitioning[J]. J.ACM, 2009, 56(2):5:1-5:37.
[13] Sherman S. Breaking the multicommodity flow barrier for o(vlogn)-approximations to sparsest cut[J]. in Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, ser. FOCS'09. Washington, DC, USA:IEEE Computer Society, 2009, 363-372.
[14] Alon N, Karp R M, Peleg D and West D. A graph theoretic game and its application to the k server problem[J]. In Proceedings of the 44th Annual ACM Symposium on the Theory of Computing STOC, 1995, 24:78-100.
[15] Elkin M, Emek Y, Spielman D A and Teng S H. Lower-stretch spanning trees[J]. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing(STOC), 2005, 494-503.
[16] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer and Peter Sanders. A Parallelization of Di.jkstra's Shortest Path Algorithm. Lecture Notes in Computer Science[J]. 1998, 1450:722-731.
[17] Parallel Boost Graph Library[CP]. https://www.boost.org/doc/libs/1_67_0/libs/graph_parallel/doc/html/index.html.
[18] Yamazaki I, Li X S. On techniques to improve robustness and scalability of the Schur complement method[J]. Proc. of VECPAR 2010, 2011:421-434.
[19] Giraud L, Haidar A, Watson L T. Parallel scalability study of hybrid preconditioners in three dimensions[J]. Parallel Computing, 2008, 34:363-379.
[20] Dominique LaSalle, George Karypis. Efficient Nested Dissection for Multicore Architectures[J].Euro-Par 2015:Parallel Processing, 2015, 467-478.
[21] Ichitaro Yamazaki, Xiaoye S. Li, Francois-Henry Rouet, Bora Ucar. On Partitioning and Reordering Problems in a Hierarchically Parallel Hybrid Linear Solver[C]. 2013 IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum(IPDPSW), May2013, Cambridge, MA, United States. IEEE Computer Society.
[22] Petsc[CP]. http://www.mcs.anl.gov/petsc/.
[23]神威太湖之光[OL]. http://www.nsccwx.cn/.
[24] Duc Thai Nguyen. Parallel-Vector Equation Solvers for Finite Element Engineering Applica-tions[M]. Springer Science, Business Media, 2012.
[25] Bai. Krylov subspace techniques for reduced-order modeling of large-scale dynamical systems[J].Applied Numerical Mathematics, 2002, 43:9-44.
[26] Hiptmair R. Finite elements in computational electromagnetism[J]. Acta Numerica, Cambridge University Press, 2002, 237-339.
[27] J. SteppelerR. HessU. SchattlerL. Bonaventura. Review of numerical methods for nonhydrostatic weather prediction models[J]. Meteorology and Atmospheric Physics, 2003, 82:287-301.
[28] Yeh K S, Cote J, Gravel S, Methot A, Patoine A, Roch M, Staniforth A. The CMC-MRB global environmental multiscale(GEM)model. Part III:Nonhydrostatic formulation[J]. Monthly Weather Review, 2002, 130:339-356.
[29] Joao Pedro Lopes. Convection, Diffusion and Reaction:Bridging Scales in Science and Engineering[D]. UNIVERSITY OF PORTO, 2011.
[30] Janna C, Comerlati A, Gambolati G. A comparison of projective and direct solvers for finite elements in elastostatics[J]. Advances in Engineering Software, 2009, 40(8):675-685.
[31] Pacull F, Aubert S, Buisson M. A Study of ILU Factorization for Schwartz Preconditioners with Application to Computational Fluid Dynamics[C]. Proceedings of the 2nd Intl Conf on Parallel,Distributed, Grid, and Cloud Computing for Engineering, 2011, Paper 39.
[2] Saad Y. Iterative methods for sparse linear systems(2nd edition)[M]. SIAM, 2003.
[3] Metis[CP]. http://glaros.dtc.umn.edu/gkhome/metis/metis/overview.
[4] Cai Xiao-Chuan. David E. Keyes. Nonlinearly Preconditioned Inexact Newton Algorithms[J].SIAM J. Sci. Comput., 2002, 24(1):183-200.
[5] Abraham I, Bartal Y and Neiman O. Using petal-decompositions to build a low stretch spanning tree[J]. in In Proceedings of the 44th Annual ACM Symposium on the Theory of Computing STOC, 2012, 395-406.
[6]张慧荣.大型稀疏线性方程组的新型预条件算法研究[D].中国科学院大学,2017.
[7] Pal Andras Papp, Low-Stretch Spanning Trees[D]. Eotvos Lorand University, 2014.
[8] hmetis[CP]. http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview.
[9] parmetis[CP]. http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview.
[10] SCOTCH[CP]. http://www.labri.fr/perso/pelegrin/scotch.
[11] Tom Leighton, Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms[J]. J. ACM, 1999, 46(6):787-832.
[12] Arora S, Rao S, Vazirani U. Expander flows, geometric embeddings and graph partitioning[J]. J.ACM, 2009, 56(2):5:1-5:37.
[13] Sherman S. Breaking the multicommodity flow barrier for o(vlogn)-approximations to sparsest cut[J]. in Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, ser. FOCS'09. Washington, DC, USA:IEEE Computer Society, 2009, 363-372.
[14] Alon N, Karp R M, Peleg D and West D. A graph theoretic game and its application to the k server problem[J]. In Proceedings of the 44th Annual ACM Symposium on the Theory of Computing STOC, 1995, 24:78-100.
[15] Elkin M, Emek Y, Spielman D A and Teng S H. Lower-stretch spanning trees[J]. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing(STOC), 2005, 494-503.
[16] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer and Peter Sanders. A Parallelization of Di.jkstra's Shortest Path Algorithm. Lecture Notes in Computer Science[J]. 1998, 1450:722-731.
[17] Parallel Boost Graph Library[CP]. https://www.boost.org/doc/libs/1_67_0/libs/graph_parallel/doc/html/index.html.
[18] Yamazaki I, Li X S. On techniques to improve robustness and scalability of the Schur complement method[J]. Proc. of VECPAR 2010, 2011:421-434.
[19] Giraud L, Haidar A, Watson L T. Parallel scalability study of hybrid preconditioners in three dimensions[J]. Parallel Computing, 2008, 34:363-379.
[20] Dominique LaSalle, George Karypis. Efficient Nested Dissection for Multicore Architectures[J].Euro-Par 2015:Parallel Processing, 2015, 467-478.
[21] Ichitaro Yamazaki, Xiaoye S. Li, Francois-Henry Rouet, Bora Ucar. On Partitioning and Reordering Problems in a Hierarchically Parallel Hybrid Linear Solver[C]. 2013 IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum(IPDPSW), May2013, Cambridge, MA, United States. IEEE Computer Society.
[22] Petsc[CP]. http://www.mcs.anl.gov/petsc/.
[23]神威太湖之光[OL]. http://www.nsccwx.cn/.
[24] Duc Thai Nguyen. Parallel-Vector Equation Solvers for Finite Element Engineering Applica-tions[M]. Springer Science, Business Media, 2012.
[25] Bai. Krylov subspace techniques for reduced-order modeling of large-scale dynamical systems[J].Applied Numerical Mathematics, 2002, 43:9-44.
[26] Hiptmair R. Finite elements in computational electromagnetism[J]. Acta Numerica, Cambridge University Press, 2002, 237-339.
[27] J. SteppelerR. HessU. SchattlerL. Bonaventura. Review of numerical methods for nonhydrostatic weather prediction models[J]. Meteorology and Atmospheric Physics, 2003, 82:287-301.
[28] Yeh K S, Cote J, Gravel S, Methot A, Patoine A, Roch M, Staniforth A. The CMC-MRB global environmental multiscale(GEM)model. Part III:Nonhydrostatic formulation[J]. Monthly Weather Review, 2002, 130:339-356.
[29] Joao Pedro Lopes. Convection, Diffusion and Reaction:Bridging Scales in Science and Engineering[D]. UNIVERSITY OF PORTO, 2011.
[30] Janna C, Comerlati A, Gambolati G. A comparison of projective and direct solvers for finite elements in elastostatics[J]. Advances in Engineering Software, 2009, 40(8):675-685.
[31] Pacull F, Aubert S, Buisson M. A Study of ILU Factorization for Schwartz Preconditioners with Application to Computational Fluid Dynamics[C]. Proceedings of the 2nd Intl Conf on Parallel,Distributed, Grid, and Cloud Computing for Engineering, 2011, Paper 39.