Abstract
Wavefront computations, characterized by a data dependent flow of computation across a data space, are receiving increasing attention as an important class of parallel computations. Though sophisticated compiler optimizations can often produce efficient pipelined implementations from sequential representations, we argue that a language-based approach to representing wavefront computations is a more practical technique. A language-based approach is simple for the programmer yet unambiguously parallel. In this paper we introduce simple array language extensions that directly support wavefront computations. We show how a programmer may reason about the extensions’ legality and performance; we describe their implementation and give performance data demonstrating the importance of parallelizing these codes.
This research was supported in part by DARPA Grant F30602-97-1-0152, NSF Grant CCR 9710284 and the Intel Corporation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Jeanne C. Adams, Walter S. Brainerd, Jeanne T. Martin, Brian T. Smith, and Jerrold L. Wagener. Fortran 90 Handbook. McGraw-Hill, New York, NY, 1992.
Bradford L. Chamberlain, Sung-Eun Choi, E Christopher Lewis, Calvin Lin, Lawrence Snyder, and W. Derrick Weathersby. ZPL’s WYSIWYG performance model. In Third IEEE International Workshop on High-level Parallel Programming Models and Supportive Environments, pages 50–61, March 1998.
Bradford L. Chamberlain, Sung-Eun Choi, E Christopher Lewis, Lawrence Snyder, W Derrick Weathersby, and Calvin Lin. The case for high-level parallel programming in ZPL. IEEE Computational Science and Engineering, 5(3):76–85, July–September 1998.
Bradford L. Chamberlain, E Christopher Lewis, Calvin Lin, and Lawrence Snyder. Regions: An abstraction for expressing array computation. In ACM SIGAPL/SIGPLAN International Conference on Array Programming Languages, pages 41–49, August 1999.
W Crowley, C. P. Hendrickson, and T. I. Luby. The SIMPLE code. Technical Report UCID-17715, Lawrence Livermore Laboratory, 1978.
Ron Cytron. Doacross: Beyond vectorization for multiprocessors. In International Conference on Parallel Processing, pages 836–844, 1986.
High Performance Fortran Forum. High Performance Fortran Language Specification, Version 2.0. January 1997.
Seema Hiranandani, Ken Kennedy, and Chau-Wen Tseng. Compiler optimizations for Fortran D on MIMD distributed-memory machines. In Supercomputing’ 91, pages 96–100, Albuquerque, NM, November 1991.
Seema Hiranandani, Ken Kennedy, and Chau-Wen Tseng. Evaluation of compiler optimizations for Fortran D on MIMD distributed-memory machines. In International Conference on Supercomputing, pages 1–14, Washington, DC, July 1992.
K. R. Koch, R. S. Baker, and R. E. Alcouffe. Solution of the first-order form of three-dimensional discrete ordinates equations on a massively parallel machine. Transactions of the American Nuclear Society, 65:198–9, 1992.
Charles H. Koelbel, David B. Loveman, Robert S. Schreiber, Guy L. Steele Jr., and Mary E. Zosel. The High Performance Fortran Handbook. The MIT Press, Cambridge, Massachusetts, 1993.
E. Christopher Lewis, Calvin Lin, and Lawrence Snyder. The implementation and evaluation of fusion and contraction in array languages. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 50–59, June 1998.
E Christopher Lewis and Lawrence Snyder. Pipelining wavefront computations: Experiences and performance. Submitted for publication, November 1999.
C. Lin, L. Snyder, R. Anderson, B. Chamberlain, S. Choi, G. Forman, E. Lewis, and W. D. Weathersby. ZPL vs. HPF: A comparison of performance and programming style. Technical Report 95-11-05, Department of Computer Science and Engineering, University of Washington, 1994.
TonA. Ngo. The Role of Performance Models in Parallel Programming and Languages. PhD thesis, University of Washington, Department of Computer Science and Engineering, 1997.
Hiroshi Ohta, Tasuhiko Saito, Masahiro Kainaga, and Hiroyuki Ono. Optimal tile size adjustment in compiling general DOACROSS loop nests. In International Conference on Supercomputing, pages 270–9, Barcelona, Spain, 1995.
Anne Rogers and Keshav Pingali. Process decomposition through locality of reference. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 69–80, June 1989.
Marc Snir, Steve Otto, Steven Huss-Lederman, David Walker, and Jack Dongarra. MPI—The Complete Reference. The MIT Press, Cambridge, Massachusetts, 2nd edition, 1998.
Lawrence Snyder. The ZPL Programmer’s Guide. The MIT Press, Cambridge, Massachusetts, 1999.
David Sundaram-Stukel and Mark K. Vernon. Predictive analysis of a wavefront application using LogGP. In Seventh ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, May 1999.
Michael Wolfe. High Performance Compilers for Parallel Computing. Addison-Wesley, Redwood City, CA, 1996.
ZPL Project. ZPL project homepage. http://www.cs.washington.edu/research/zpl.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chamberlain, B.L., Lewis, E., Snyder, L. (2000). Language Support for Pipelining Wavefront Computations. In: Carter, L., Ferrante, J. (eds) Languages and Compilers for Parallel Computing. LCPC 1999. Lecture Notes in Computer Science, vol 1863. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44905-1_20
Download citation
DOI: https://doi.org/10.1007/3-540-44905-1_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67858-8
Online ISBN: 978-3-540-44905-8
eBook Packages: Springer Book Archive