Title: Reconsidering algorithms for iterative solvers in the multicore era

Authors: Dan Wallin, Henrik Lof, Erik Hagersten, Sverker Holmgren

Addresses: Department of Information Technology, Uppsala University, P.O. Box 337, SE-751 05 Uppsala, Sweden. ' Department of Information Technology, Uppsala University, P.O. Box 337, SE-751 05 Uppsala, Sweden. ' Department of Information Technology, Uppsala University, P.O. Box 337, SE-751 05 Uppsala, Sweden. ' Department of Information Technology, Uppsala University, P.O. Box 337, SE-751 05 Uppsala, Sweden

Abstract: Efficient solution of computational problems require a match between the algorithm and the underlying architecture. New multicore processors feature low intra-chip communication cost and smaller per-thread caches compared to single-core implementations, indicating that data locality issues are more important than communication overheads. We investigate the impact of these changes on parallel multigrid methods. We present a temporally blocked, naturally ordered, smoother implementation that improves the data locality as much as ten times compared with the standard red-black algorithm. We present results of the performance of our new algorithm on an SMP system, an UltraSPARC T1 (Niagara) SMT/CMP, and a simulated CMP processor.

Keywords: multicore processors; data locality; parallel multigrid.

DOI: 10.1504/IJCSE.2009.029163

International Journal of Computational Science and Engineering, 2009 Vol.4 No.4, pp.270 - 282

Published online: 08 Nov 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article