Stencil computation optimization and auto-tuning on state-of-the-art multicore architectures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Stencil computation optimization and auto-tuning on state-of-the-art multicore architectures

Full text

Pdf (372 KB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 2008 ACM/IEEE conference on Supercomputing - Volume 00 table of contents

Austin, Texas

SECTION: Papers table of contents

Article No. 4

Year of Publication: 2008

ISBN:978-1-4244-2835-9

Authors

Kaushik Datta	Lawrence Berkeley National Laboratory, Berkeley, CA and University of California at Berkeley, Berkeley, CA
Mark Murphy	University of California at Berkeley, Berkeley, CA
Vasily Volkov	University of California at Berkeley, Berkeley, CA
Samuel Williams	Lawrence Berkeley National Laboratory, Berkeley, CA and University of California at Berkeley, Berkeley, CA
Jonathan Carter	Lawrence Berkeley National Laboratory, Berkeley, CA
Leonid Oliker	Lawrence Berkeley National Laboratory, Berkeley, CA and University of California at Berkeley, Berkeley, CA
David Patterson	Lawrence Berkeley National Laboratory, Berkeley, CA and University of California at Berkeley, Berkeley, CA
John Shalf	Lawrence Berkeley National Laboratory, Berkeley, CA
Katherine Yelick	Lawrence Berkeley National Laboratory, Berkeley, CA and University of California at Berkeley, Berkeley, CA

Publisher

IEEE Press Piscataway, NJ, USA

Bibliometrics

Downloads (6 Weeks): 57, Downloads (12 Months): 582, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

Understanding the most efficient design and utilization of emerging multicore systems is one of the most challenging questions faced by the mainstream and scientific computing industries in several decades. Our work explores multicore stencil (nearest-neighbor) computations --- a class of algorithms at the heart of many structured grid codes, including PDF solvers. We develop a number of effective optimization strategies, and build an auto-tuning environment that searches over our optimizations and their parameters to minimize runtime, while maximizing performance portability. To evaluate the effectiveness of these strategies we explore the broadest set of multicore architectures in the current HPC literature, including the Intel Clovertown, AMD Barcelona, Sun Victoria Falls, IBM QS22 PowerXCell 8i, and NVIDIA GTX280. Overall, our auto-tuning optimization methodology results in the fastest multicore stencil performance to date. Finally, we present several key insights into the architectural tradeoffs of emerging multicore designs and their implications on scientific algorithm development.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	K. Asanovic, R. Bodik, B. Catanzaro et al., "The landscape of parallel computing research: A view from Berkeley," EECS, University of California, Berkeley, Tech. Rep. UCB/EECS-2006-183, 2006.
	2	M. Berger and J. Oliger, "Adaptive mesh refinement for hyperbolic partial differential equations," Journal of Computational Physics, vol. 53, pp. 484--512, 1984.
	3	Sriram Sellappa , Siddhartha Chatterjee, Cache-Efficient Multigrid Algorithms, International Journal of High Performance Computing Applications, v.18 n.1, p.115-133, February 2004 [doi>10.1177/1094342004041295]
	4	Gabriel Rivera , Chau-Wen Tseng, Tiling optimizations for 3D scientific computations, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, November 04-10, 2000, Dallas, Texas, United States
	5	Amy W. Lim , Shih-Wei Liao , Monica S. Lam, Blocking and array contraction across arbitrarily nested loops using affine partitioning, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.103-112, June 2001, Snowbird, Utah, United States
	6	Shoaib Kamil , Kaushik Datta , Samuel Williams , Leonid Oliker , John Shalf , Katherine Yelick, Implicit and explicit optimizations for stencil computations, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178605]
	7	S. Williams, J. Carter, L. Oliker, J. Shalf, and K. Yelick, "Lattice Boltzmann simulation optimization on leading multicore platforms," in Interational Conference on Parallel and Distributed Computing Systems (IPDPS), Miami, Florida, 2008.
	8	Samuel Williams , John Shalf , Leonid Oliker , Shoaib Kamil , Parry Husbands , Katherine Yelick, The potential of the cell processor for scientific computing, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128027]
	9	Michael Gschwind, Chip multiprocessing and the cell broadband engine, Proceedings of the 3rd conference on Computing frontiers, p.1-8, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128023]
	10	NVIDIA CUDA Programming Guide 1.1, November 2007. {Online}. Available: http://www.nvidia.com/object/cuda_develop.html
	11	R. C. Whaley, A. Petitet, and J. Dongarra, "Automated Empirical Optimization of Software and the ATLAS project," Parallel Computing, vol. 27(1--2), pp. 3--35, 2001.
	12	R. Vuduc, J. Demmel, and K. Yelick, "OSKI: A library of automatically tuned sparse matrix kernels," in Proc. of SciDAC 2005, J. of Physics: Conference Series. Institute of Physics Publishing, June 2005.
	13	Shoaib Kamil , Parry Husbands , Leonid Oliker , John Shalf , Katherine Yelick, Impact of modern memory subsystems on cache optimizations for stencil computations, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111589]
	14	J. D. McCalpin, "STREAM: Sustainable Memory Bandwidth in High Performance Computers," http://www.cs.virginia.edu/stream/.
	15	Samuel Williams , Leonid Oliker , Richard Vuduc , John Shalf , Katherine Yelick , James Demmel, Optimization of sparse matrix-vector multiplication on emerging multicore platforms, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362674]

CITED BY 5

	Alexander S. van Amesfoort , Ana Lucia Varbanescu , Henk J. Sips , Rob V. van Nieuwpoort, Evaluating multi-core platforms for HPC data-intensive kernels, Proceedings of the 6th ACM conference on Computing frontiers, May 18-20, 2009, Ischia, Italy
	Samuel Williams , Andrew Waterman , David Patterson, Roofline: an insightful visual performance model for multicore architectures, Communications of the ACM, v.52 n.4, April 2009
	Paulius Micikevicius, 3D finite difference computation on GPUs using CUDA, Proceedings of 2nd Workshop on General Purpose Processing on Graphics Processing Units, p.79-84, March 08-08, 2009, Washington, D.C.
	Jiayuan Meng , Kevin Skadron, Performance modeling and automatic ghost zone optimization for iterative stencil loops on GPUs, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA
	Sundaresan Venkatasubramanian , Richard W. Vuduc , none none, Tuned and wildly asynchronous stencil kernels for hybrid CPU/GPU systems, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA