Abstract
Parallel skeletons intend to encourage programmers to build a parallel program from ready-made components for which efficient implementations are known to exist, making the parallelization process simpler. However, it is neither easy to develop efficient parallel programs using skeletons nor to use skeletons to manipulate irregular data, and moreover there lacks a systematic way to optimize skeletal parallel programs. To remedy this situation, we propose a novel parallel skeleton, called accumulate, which not only efficiently describes data dependency in computation but also exhibits nice algebraic properties for manipulation. We show that this skeleton significantly eases skeletal parallel programming in practice, efficiently manipulating both regular and irregular data, and systematically optimizing skeletal parallel programs.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
R. Bird. An introduction to the theory of lists. In M. Broy, editor, Logic of Programming and Calculi of Discrete Design, pages 5–42. Springer-Verlag, 1987.
Guy E. Blelloch. Scans as primitive operations. IEEE Trans. on Computers, 38(11):1526–1538, November 1989.
G. E. Blelloch. Prefix sums and their applications. Technical Report CMUCS-90-190, Carnegie-Mellon Univ., 1990.
G.E. Blelloch. NESL: a nested data parallel language. Technical Report CMU-CS-92-103, School of Computer Science, Carnegie-Mellon University, January 1992.
O. Chitil. Type inference builds short cut to deforestation. In Proceedings of 1999 ACM SIGPLAN International Conference on Functional Programming, pages 249–260. ACM Press, 1999.
M. Cole. Parallel programming with list homomorphisms. Parallel Processing Letters, 5(2), 1995.
J. Gibbons. The third homomorphism theorem. Journal of Functional Programming, 6(4):657–665, 1996.
A. Gill, J. Launchbury, and S. Peyton Jones. A short cut to deforestation. In Proc. Conference on Functional Programming Languages and Computer Architecture, pages 223–232, Copenhagen, June 1993.
S. Gorlatch. Systematic efficient parallelization of scan and other list homomorphisms. In Annual European Conference on Parallel Processing, LNCS 1124, pages 401–408, LIP, ENS Lyon, France, August 1996. Springer-Verlag.
Z. Hu, H. Iwasaki, and M. Takeichi. An accumulative parallel skeleton for all. Technical Report METR 01-05, University of Tokyo, September 2001. Available from http://www.ipl.t.u-tokyo.ac.jp/ ~ hu/pub/metr01-05.ps.gz.
Z. Hu, H. Iwasaki, M. Takeichi, and A. Takano. Tupling calculation eliminates multiple data traversals. In ACM SIGPLAN International Conference on Functional Programming, pages 164–175, Amsterdam, The Netherlands, June 1997. ACM Press.
W.D. Hills and Jr. G. L. Steele. Data parallel algorithms. Communications of the ACM, 29(12):1170–1183, 1986.
Z. Hu, M. Takeichi, and W.N. Chin. Parallelization in calculational forms. In 25th ACM Symposium on Principles of Programming Languages, pages 316–328, San Diego, California, USA, January 1998.
Z. Hu, M. Takeichi, and H. Iwasaki. Diffusion: Calculating efficient parallel programs. In 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pages 85–94, San Antonio, Texas, January 1999. BRICS Notes Series NS-99-1.
S. Peyton Jones and J. Hughes, editors. Haskell 98: A Non-strict, Purely Functional Language. Available online: http://www.haskell.org, February 1999.
G. Keller and M. M. T. Chakravarty. On the distributed implementation of aggregate data structures by program transformation. In J. Rolim et al., editor, 4th International Workshop on High-Level Parallel Programming Models and Supportive Environments (LNCS 1586), pages 108–122, Berlin, Germany, 1999. Springer-Verlag.
J. Launchbury and T. Sheard. Warm fusion: Deriving build-catas from recursive definitions. In Proc. Conference on Functional Programming Languages and Computer Architecture, pages 314–323, La Jolla, California, June 1995.
Christian Lengauer Sergei Gorlatch, Christoph Wedler. Optimization rules for programming with collective operations. In Mikhail Atallah, editor, IPPS/SPDP’99. 13th Int. Parallel Processing Symp. & 10th Symp. on Parallel and Distributed Processing, pages 492–499, 1999.
D.B. Skillicorn. Architecture-independent parallel computation. IEEE Computer, 23(12):38–51, December 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hu, Z., Iwasaki, H., Takeichi, M. (2002). An Accumulative Parallel Skeleton for All. In: Le Métayer, D. (eds) Programming Languages and Systems. ESOP 2002. Lecture Notes in Computer Science, vol 2305. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45927-8_7
Download citation
DOI: https://doi.org/10.1007/3-540-45927-8_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43363-7
Online ISBN: 978-3-540-45927-9
eBook Packages: Springer Book Archive