Abstract
We introduce a new reusable component for parallel programming, the double- scan skeleton. For this skeleton, we formulate and formally prove sufficient conditions under which the double-scan can be parallelized, and develop its efficient MPI implementation. The solution of a tridiagonal system of equations is considered as our case study. We describe how this application can be developed using the double-scan and report experimental results for both absolute performance and performance predictability of the skeleton-based solution.
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
H. Bischof, S. Gorlatch, and E. Kitzelmann. The double-scan skeleton and its parallelization. Technical Report 2002/06, Technische Universität Berlin, 2002.
G. Botorog and H. Kuchen. Efficient parallel programming with algorithmic skeletons. In L. Bougé et al., editors, Euro-Par’96: Parallel Processing, Lecture Notes in Computer Science 1123, pages 718–731. Springer-Verlag, 1996.
S. Breitinger, R. Loogen, Y. Ortega-Mallén, and R. Peña. The Eden coordination model for distributed memory systems. In High-Level Parallel Programming Models and Supportive Environments (HIPS). IEEE Press, 1997.
M. I. Cole. Algorithmic Skeletons: A Structured Approach to the Management of Parallel Computation. PhD thesis, University of Edinburgh, 1988.
E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design patterns: elemets of reusable object-oriented software. Addison Wesley, 1995.
S. Gorlatch. Systematic efficient parallelization of scan and other list homomorphisms. In L. Bougé, P. Fraigniaud, A. Mignotte, and Y. Robert, editors, Euro-Par’96: Parallel Processing, Vol. II, Lecture Notes in Computer Science 1124, pages 401–408. Springer-Verlag, 1996.
C. A. Herrmann and C. Lengauer. HDC: A higher-order language for divide-and-conquer. Parallel Processing Letters, 10(2-3):239–250, 2000.
F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publ., 1992.
S. Pelagatti. Structured development of parallel programs. Taylor&Francis, 1998.
M. J. Quinn. Parallel Computing. McGraw-Hill, Inc., 1994.
C. Szyperski. Component software: beyond object-oriented programming. Addison Wesley, 1998.
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
Bischof, H., Gorlatch, S. (2002). Double-Scan: Introducing and Implementing a New Data-Parallel Skeleton. In: Monien, B., Feldmann, R. (eds) Euro-Par 2002 Parallel Processing. Euro-Par 2002. Lecture Notes in Computer Science, vol 2400. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45706-2_88
Download citation
DOI: https://doi.org/10.1007/3-540-45706-2_88
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44049-9
Online ISBN: 978-3-540-45706-0
eBook Packages: Springer Book Archive