1. [Publications](/publications)
2. Exposing Fine-Grained Parallelism in Algebraic Multigrid Methods
 
 # Exposing Fine-Grained Parallelism in Algebraic Multigrid Methods

  ![](/sites/default/files/styles/wide/public/pubs/2011-06_Exposing-Fine-Grained-Parallelism/thumbnail.png?itok=PDtOeDZi)

 Algebraic multigrid methods for large, sparse linear systems are a necessity in many computational simulations, yet parallel algorithms for such solvers are generally decomposed into coarse-grained tasks suitable for distributed computers with traditional processing cores. However, accelerating multigrid on massively parallel throughput-oriented processors, such as the GPU, demands algorithms with abundant *fine-grained* parallelism. In this paper, we develop a parallel algebraic multigrid method which exposes substantial fine-grained parallelism in both the construction of the multigrid hierarchy as well as the cycling or solve stage. Our algorithms are expressed in terms of scalable parallel primitives that are efficiently implemented on the GPU. The resulting solver achieves an average speedup of over 2x in the setup phase and around 6x in the cycling phase when compared to a representative CPU implementation.



 ## Authors



Nathan Bell (NVIDIA)

Steven Dalton (UIUC)

Luke Olson (UIUC)

 

 

 ## Publication Date



Wednesday, June 1, 2011

 

 ## Published in



[ NVIDIA Technical Report NVR-2011-002](http://research.nvidia.com/publication/exposing-fine-grained-parallelism-algebraic-multigrid-methods)

 

 ## Research Area



[Algorithms and Numerical Methods](/research-area/algorithms)

 

 

 ## External Links



[Source Code](http://cusp-library.googlecode.com/)

 

 

 ## Uploaded Files



[nvr-2011-002.pdf](https://research.nvidia.com/sites/default/files/pubs/2011-06_Exposing-Fine-Grained-Parallelism/nvr-2011-002.pdf "Open file in new window")1.57 MB

[bibtex.txt](https://research.nvidia.com/sites/default/files/pubs/2011-06_Exposing-Fine-Grained-Parallelism/bibtex.txt "Open document in new window")327 bytes

[AMG on the GPU.pdf](https://research.nvidia.com/sites/default/files/pubs/2011-06_Exposing-Fine-Grained-Parallelism/AMG%20on%20the%20GPU.pdf "Open file in new window")513.87 KB