SIAM Journal on Scientific Computing · 2012 · 206 citations · 29 references
ComputingComputer ScienceHigh-performance ComputingParallel AlgorithmsParallel ComputingScientific ComputingData ParallelismGraphics Processing Unit ComputingParallel Algorithm DesignParallel ArchitecturesParallel ComputationParallel Numerical MethodsGpu Parallel AlgorithmsParallel Linear System SolversParallel SolversParallel Sparse Linear AlgebraScalable Parallel AlgorithmsScientific Computing On GpusSparse Linear AlgebraSparse Matrix Computation
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 methods on massively parallel throughput-oriented processors, such as graphics processing units, 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 $1.8\times$ in the setup phase and $5.7\times$ in the cycling phase when compared to a representative CPU implementation.
29
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
Basic Linear Algebra Subprograms for Fortran Usage
C. L. Lawson, Richard Hanson, David R. Kincaid et al. · ACM Transactions on Mathematical Software · 1979 · 1.6K citations · Full text
A Simple Parallel Algorithm for the Maximal Independent Set Problem
Michael Luby · SIAM Journal on Computing · 1986 · 1.1K citations