Improving the arithmetic intensity of multigrid with the help of polynomial smoothers
- 1 February 2012
- journal article
- research article
- Published by Wiley in Numerical Linear Algebra with Applications
- Vol. 19 (2) , 253-267
Abstract
SUMMARY: The basic building blocks of a classic multigrid algorithm, which are essentially stencil computations, all have a low ratio of executed floating point operations per byte fetched from memory. This important ratio can be identified as the arithmetic intensity. Applications with a low arithmetic intensity are typically bounded by memory traffic and achieve only a small percentage of the theoretical peak performance of the underlying hardware. We propose a polynomial Chebyshev smoother, which we implement using cache‐aware tiling, to increase the arithmetic intensity of a multigrid V‐cycle. This tiling approach involves a trade‐off between redundant computations and cache misses. Unlike common conception, we observe optimal performance for higher degrees of the smoother. The higher‐degree polynomial Chebyshev smoother can be used to smooth more than just the upper half of the error frequencies, leading to better V‐cycle convergence rates. Smoothing more than the upper half of the error spectrum allows a more aggressive coarsening approach where some levels in the multigrid hierarchy are skipped. Copyright © 2012 John Wiley & Sons, Ltd.Keywords
This publication has 25 references indexed in Scilit:
- Efficient multicore-aware parallelization strategies for iterative stencil computationsJournal of Computational Science, 2011
- High Performance Stencil Code Algorithms for GPGPUsProcedia Computer Science, 2011
- 3.5-D Blocking Optimization for Stencil Computations on Modern CPUs and GPUs2010
- RooflineCommunications of the ACM, 2009
- Optimization of sparse matrix–vector multiplication on emerging multicore platformsParallel Computing, 2009
- Optimization and Performance Modeling of Stencil Computations on Modern MicroprocessorsSIAM Review, 2009
- A class of parallel tiled linear algebra algorithms for multicore architecturesParallel Computing, 2009
- Cache oblivious stencil computations2005
- OSKI: A library of automatically tuned sparse matrix kernelsJournal of Physics: Conference Series, 2005
- Cache-oblivious algorithms1999