A Parallel Auxiliary Grid AMG Method for GPU
作者： Jinchao Xu , Xiaozhe Hu , Jonathan Cohen , Lu Wang
DOI:
关键词: Solver 、 Multigrid method 、 Speedup 、 Rate of convergence 、 Computer science 、 Quadtree 、 CUDA 、 Parallel computing 、 Computational science 、 Grid 、 Load balancing (computing) 、 Numerical analysis
摘要: In this paper, we develop a new parallel auxiliary grid algebraic multigrid (AMG) method to leverage the power of graphic processing units (GPUs). construction hierarchical coarse grid, use simple and fixed coarsening procedure based on region quadtree generated from an grid. This allows us explicitly control sparsity patterns operator complexities AMG solver. feature provides (nearly) optimal load balancing predictable communication patterns, which makes our algorithm suitable for computing, especially GPU. We also design smoother special coloring accelerate convergence rate improve performance Based CUDA toolkit [40], implemented GPU numerical results implementation demonstrate efficiency method. The achieve average speedup over 4 quasi-uniform grids 2 shape regular when compared in CUSP.
arxiv.org
harvard.edu
jcohen.name 参考文章(38)
Jiri Kraus, Malte Förster, Efficient AMG on heterogeneous systems Facing the Multicore-Challenge II. pp. 133- 146 ,(2012) , 10.1007/978-3-642-30397-5_12
Luc Buatois, Guillaume Caumon, Bruno Lévy, Concurrent number cruncher: an efficient sparse linear solver on the GPU high performance computing and communications. ,vol. 4782, pp. 358- 371 ,(2007) , 10.1007/978-3-540-75444-2_37
Robert D. Falgout, Ulrike Meier Yang, hypre: A Library of High Performance Preconditioners international conference on computational science. pp. 632- 641 ,(2002) , 10.1007/3-540-47789-6_66
D. Braess, Towards algebraic multigrid for elliptic problems of second order Computing. ,vol. 55, pp. 379- 393 ,(1995) , 10.1007/BF02238488
Harald Grossauer, Peter Thoman, GPU-based multigrid: real-time performance in high resolution nonlinear image processing international conference on computer vision systems. pp. 141- 150 ,(2008) , 10.1007/978-3-540-79547-6_14
Gundolf Haase, Manfred Liebmann, Craig C. Douglas, Gernot Plank, A Parallel Algebraic Multigrid Solver on Graphics Processing Units Lecture Notes in Computer Science. pp. 38- 47 ,(2010) , 10.1007/978-3-642-11842-5_5
Andrew J. Cleary, Robert D. Falgout, Van Emden Henson, Jim E. Jones, Coarse-Grid Selection for Parallel Algebraic Multigrid Lecture Notes in Computer Science. pp. 104- 115 ,(1998) , 10.1007/BFB0018531
Zhuo Feng, Zhiyu Zeng, Parallel multigrid preconditioning on graphics processing units (GPUs) for robust power grid analysis design automation conference. pp. 661- 666 ,(2010) , 10.1145/1837274.1837443
Nathan Bell, Steven Dalton, Luke N. Olson, Exposing Fine-Grained Parallelism in Algebraic Multigrid Methods SIAM Journal on Scientific Computing. ,vol. 34, ,(2012) , 10.1137/110838844
Jim E. Jones, Panayot S. Vassilevski, AMG E Based on Element Agglomeration SIAM Journal on Scientific Computing. ,vol. 23, pp. 109- 133 ,(2001) , 10.1137/S1064827599361047