Abstract
Map- and fold-like skeletons are a suitable abstractions to guide parallel program execution in functional array processing. However, when it comes to achieving high performance, it turns out that confining compilation efforts to individual skeletons is insufficient. This paper proposes compilation schemes which aim at reducing runtime overhead due to communication and synchronization by embedding multiple array skeletons within a so-called spmd meta skeleton. Whereas the meta skeleton exclusively takes responsibility for the organization of parallel program execution, the original array skeletons are focussed to their individual numerical operation. While concrete compilation schemes assume multithreading in a shared memory environment as underlying execution model, ideas can be carried over to other settings straightforwardly. Preliminary performance investigations help to quantify potential benefits.
Most of the work described in this paper was done while the author was affiliated with the University of Kiel.
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
J.C. Adams, W.S. Brainerd, J.T. Martin, B.T. Smith, and J.L. Wagener. Fortran-95 Handbook—Complete ANSI/ISO Reference. Scientific and Engineering Computation. MIT Press, 1997.
G.H. Botorog and H. Kuchen. Efficient High-Level Parallel Programming. Theoretical Computer Science, 196(1–2):71–107, 1998.
B.L. Chamberlain, S.-E. Choi, E.C. Lewis, C. Lin, L. Snyder, and W.D. Weathersby. Factor-Join: A Unique Approach to Compiling Array Languages for Parallel Machines. In D.C. Sehr, U. Banerjee, D. Gelernter, A. Nicolau, and D.A. Padua, editors, Proceedings of the 9th Workshop on Languages and Compilers for Parallel Computing (LCPC’96), San José, California, USA, volume 1239 of Lecture Notes in Computer Science, pages 481–500. Springer-Verlag, 1997.
B.L. Chamberlain, S.-E. Choi, E.C. Lewis, C. Lin, L. Snyder, and W.D. Weathersby. The Case for High Level Parallel Programming in ZPL. IEEE Computational Science and Engineering, 5(3):76–86, 1998.
W. Chin. Towards an Automated Tupling Strategy. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantic-Based Program Manipulation (PEPM’97), Copenhagen, Denmark, pages 119–132. ACM Press, 1993.
W. Chin. Fusion and Tupling Transformations: Synergies and Conflicts. In Proceedings of the Fuji International Workshop on Functional and Logic Programming, Susono, Japan, pages 106–125. World Scientific Publishing, 1995.
M.I. Cole. Algorithmic Skeletons: Structured Management of Parallel Computation. Reserach Monographs in Parallel and Distributed Computing. Pitman, 1989.
J. Darlington, A.J. Field, P.G. Harrison, P.H.J. Kelly, D.W.N. Sharp, Q. Wu, and R.L. While. Parallel Programming using Skeleton Functions. In Proceedings of the Conference on Parallel Architectures and Reduction Languages Europe (PARLE’93), volume 694 of Lecture Notes in Computer Science, pages 146–160. Springer-Verlag, 1993.
A. Gill, J. Launchbury, and S.L. Peyton Jones. A Short Cut to Deforestation. In Proceedings of the Conference on Functional Programming Languages and Computer Architecture (FPCA’93), Copenhagen, Denmark, pages 223–232. ACM Press, 1993.
S. Gorlatch and C. Lengauer. (De)Composition Rules for Parallel Scan and Reduction. In Proceedings of the 3rd International Working Conference on Massively Parallel Programming Models (MPPM’97), London, UK, pages 23–32. IEEE Computer Society Press, 1997.
S. Gorlatch and S. Pelagatti. A Transformational Framework for Skeletal Programs: Overview and Case Study. In J. Rohlim et al., editors, Parallel and Distributed Processing. IPPS/SPDP’99 Workshops Proceedings, volume 1586 of Lecture Notes in Computer Science, pages 123–137. Springer-Verlag, 1999.
S. Gorlatch, C. Wedler, and C. Lengauer. Optimization Rules for Programming with Collective Operations. In M. Atallah, editor, Proceedings of the 13th International Parallel Processing Symposium and the 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP’99), San Juan, Puerto Rico, pages 492–499, 1999.
C. Grelck. Shared Memory Multiprocessor Support for SAC. In K. Hammond, T. Davie, and C. Clack, editors, Proceedings of the 10th International Workshop on Implementation of Functional Languages (IFL’98), London, UK, selected papers, volume 1595 of Lecture Notes in Computer Science, pages 38–54. Springer-Verlag, 1999.
C. Grelck. Implicit Shared Memory Multiprocessor Support for the Functional Programming Language SAC-Single Assignment C. PhD thesis, University of Kiel, Kiel, Germany, 2001. Logos Verlag, Berlin, 2001.
C. Grelck, D. Kreye, and S.-B. Scholz. On Code Generation for Multi-Generator WITH-Loops in SAC. In P. Koopman and C. Clack, editors, Proceedings of the 11th International Workshop on Implementation of Functional Languages (IFL’99), Lochem, The Netherlands, selected papers, volume 1868 of Lecture Notes in Computer Science, pages 77–94. Springer-Verlag, 2000.
W. Gropp, E. Lusk, and A. Skjellum. Using MPI: Portable Parallel Programming with the Message Passing Interface. MIT Press, Cambridge, Massachusetts, USA, 1994.
E. Hagersten and M. Koster. WildFire: A Scalable Path for SMPs. In Proceedings of the 5th International Conference on High-Performance Computer Architecture (HPCA’99), Orlando, Florida, USA, pages 172–181. IEEE Computer Society Press, 1999.
K. Hammond and G. Michaelson. Research Directions in Parallel Functional Programming. Springer-Verlag, 1999.
H. Han, C.-W. Tseng, and P. Keleher. Eliminating Barrier Synchronization for Compiler-Parallelized Codes on Software DSMs. International Journal of Parallel Programming, 26(5):591–612, 1998.
M.F.P. O’Boyle (HP), L. Kervella (HP), and F. Bodin. Sronisation Mininimisation in a SPMD Execution Mode. Journal of Parallel and Distributed Computing, 29(2):196–210, 1995.
Z. Hu, H. Iwasaki, M. Takeichi, and A. Takano. Tupling Calculation Eliminates Multiple Data Traversals. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP’97), Amsterdam, The Netherlands. ACM Press, 1997.
F.A. Rabhi. Exploiting Parallelism in Functional Languages: A “Paradigm-Oriented” Approach. In T. Lake and P. Dew, editors, Abstract Machine Models for Highly Parallel Computers. Oxford University Press, 1993.
S.-B. Scholz. On Defining Application-Specific High-Level Array Operations by Means of Shape-Invariant Programming Facilities. In S. Picchi and M. Micocci, editors, Proceedings of the International Conference on Array Processing Languages (APL’98), Rome, Italy, pages 40–45. ACM Press, 1998.
S.-B. Scholz. With-loop-folding in SAC—Condensing Consecutive Array Operations. In C. Clack, K. Hammond, and T. Davie, editors, Proceedings of the 9th International Workshop on Implementation of Functional Languages (IFL’97), St. Andrews, Scotland, UK, selected papers, volume 1467 of Lecture Notes in Computer Science, pages 72–92. Springer-Verlag, 1998.
P. Trinder, K. Hammond, H.-W. Loidl, and S.L. Peyton Jones. Algorithm + Strategy = Parallelism. Journal of Functional Programming, 8(1):23–60, 1998.
P. Wadler. Deforestation: Transforming Programs to Eliminate Trees. Theoretical Computer Science, 73(2):231–248, 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
Grelck, C. (2002). Optimizations on Array Skeletons in a Shared Memory Environment. In: Arts, T., Mohnen, M. (eds) Implementation of Functional Languages. IFL 2001. Lecture Notes in Computer Science, vol 2312. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46028-4_3
Download citation
DOI: https://doi.org/10.1007/3-540-46028-4_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43537-2
Online ISBN: 978-3-540-46028-2
eBook Packages: Springer Book Archive