More Web Proxy on the site http://driver.im/

Article

Free access

Parallel skeletons for structured composition

Authors:

John Darlington,

Jin YangAuthors Info & Claims

PPOPP '95: Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming

Pages 19 - 28

https://doi.org/10.1145/209936.209940

Published: 01 August 1995 Publication History

Abstract

In this paper, we propose a straightforward solution to the problems of compositional parallel programming by using skeletons as the uniform mechanism for structured composition. In our approach parallel programs are constructed by composing procedures in a conventional base language using a set of high-level, pre-defined, functional, parallel computational forms known as skeletons. The ability to compose skeletons provides us with the essential tools for building further and more complex application-oriented skeletons specifying important aspects of parallel computation. Compared with the process network based composition approach, such as PCN, the skeleton approach abstracts away the fine details of connecting communication ports to the higher level mechanism of making data distributions conform, thus avoiding the complexity of using lower level ports as the means of interaction. Thus, the framework provides a natural integration of the compositional programming approach with the data parallel programming paradigm.

References

[1]

G. E. Blelloch. Vector Models for Data-Parallel Computing. MIT Press, 1990.

Digital Library

[2]

G. E',. Blelloch. NESL: A nested data-parallel language (version 3.0). Technical Report CMU-CS-94 (Draft), Carnegie Mellon University, March 1994.

[3]

M. Cole. Algorithmic Skeletons: Structured Management of Parallel Computation. Pitman/MIT Press, 1989.

Digital Library

[4]

M. Danelutto, R. Di Meglio, S. Orlando, S. Palagatti, and M. Vanneschi. The p3L language: An introduction. Technical Report HPL-PSC-91-29, Hewlett-Packard Laboratories, Pisa Science Centre, December 1991.

[5]

J. Darlington, M. Ghanem, and H. W. To. Structured parallel programming. In Programming Models for Masszvely Parallel Computers. IEEE Computer Society Press, September 1993.

[6]

J. {)arlington, Y. Guo, and It. W. To. Structured parallel programming: Theory meets practice. Technical report, Imperial College, 1995. unpublished.

[7]

I. Foster and K. M. Chandy. Fortran M: A language for modular parallel programming. Journal of Parallel and Dzstributed Computzng, 25(1), 1995.

Digital Library

[8]

I. Foster, 1#. Olson, and S. Tuecke. Productive parallel programming: The PCN approach. Sczentzfic Programming, 1(1), 1992.

[9]

D. Gelernter and N. Carriero. Coordination languages and their significance. Communzcations of the ACM, 35(2):97-107, February 1992.

Digital Library

[10]

High Performance Fortran Forum. Draft High Performance Fortran Language 5pecificat,on, ver.s,on 1.0. Available as technical report CRPC-TR92225, Rice University, January 1993.

[11]

S. Hiranandani, K. Kennedy, and C.-W. Tseng. (',ompiling Fortran D for MIMD distributed memory machines. Communications of the A CM, 35(8):66-80, August 1992.

Digital Library

[12]

H. Ishihata, T. Horie, S. Inano, T. Shimizu, S. Kato, and M. Ikesaka. Third generation message passing computer AP1000. In International b#ymposzum on Supercomputzng, pages 46-55, 1991.

[13]

Message Passing Interface Forum. Draft Document for a Standard Message-Passzng Interface. Available from Oak Ridge National Laboratory, November 1993.

[14]

S. Pelagatti. A Methodology for the Development and the Support of Massively Parallel Programs. PhD thesis, Universita Delgi Studi Di Pisa, 1993.

[15]

M. J. Quinn. Parallel Computing: Theory and Practice. McGraw-Hill, second edition, 1994.

Digital Library

[16]

J. R. Rose and G. L. Steele Jr. C*: An extended C language for data parallel programming. Technical Report PL 87-5, Thinking Machine Corporation, 1987.

[17]

J. M. Sipelstein and G. E. Blelloch. Collectionoriented languages. Proceedings of the IEEE, 79(4):504-523, April 1991.

Cited By

Miller JTrümper LTerboven CMüller M(2021)A Theoretical Model for Global Optimization of Parallel AlgorithmsMathematics10.3390/math91416859:14(1685)Online publication date: 17-Jul-2021
https://doi.org/10.3390/math9141685
Danelutto MMencagli GTorquati MGonzález–Vélez HKilpatrick P(2020)Algorithmic Skeletons and Parallel Design Patterns in Mainstream Parallel ProgrammingInternational Journal of Parallel Programming10.1007/s10766-020-00684-wOnline publication date: 9-Nov-2020
https://doi.org/10.1007/s10766-020-00684-w
Tóth MBozó IKozsik T(2017)Pattern Candidate Discovery and Parallelization TechniquesProceedings of the 29th Symposium on the Implementation and Application of Functional Programming Languages10.1145/3205368.3205369(1-26)Online publication date: 30-Aug-2017
https://dl.acm.org/doi/10.1145/3205368.3205369
Show More Cited By

Index Terms

Parallel skeletons for structured composition
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures
      2. Language types
        Concurrent programming languages

Recommendations

Parallel skeletons for structured composition

In this paper, we propose a straightforward solution to the problems of compositional parallel programming by using skeletons as the uniform mechanism for structured composition. In our approach parallel programs are constructed by composing procedures ...
Formalized structured analysis specifications
Implementing fusion-equipped parallel skeletons by expression templates
IFL'09: Proceedings of the 21st international conference on Implementation and application of functional languages

Developing efficient parallel programs is more difficult and complicated than developing sequential ones. Skeletal parallelism is a promising methodology for easy parallel programming in which users develop parallel programs by composing ready-made ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPOPP '95: Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming

August 1995

234 pages

ISBN:0897917006

DOI:10.1145/209936

Chairmen:
Jeanne Ferrante
Univ. of California, San Diego
,
David Padua
Univ. of Illinois at Urbana-Champaign, Urbana
,
Editor:
Richard L. Wexelblat
IRS IS:AO, Washington, DC

ACM SIGPLAN Notices Volume 30, Issue 8
Aug. 1995
226 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/209937
Editors:
Richard L. Wexelblat
IRS IS:AO, Washington, DC
,
Jeanne Ferrante
Univ. of California, San Diego
,
David Padua
Univ. of Illinois at Urbana-Champaign, Urbana
Issue’s Table of Contents

Copyright © 1995 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PPoPP95

Sponsor:

SIGPLAN

PPoPP95: Principles & Practices of Parallel Programming

July 19 - 21, 1995

California, Santa Barbara, USA

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
756
Total Downloads

Downloads (Last 12 months)132
Downloads (Last 6 weeks)32

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Miller JTrümper LTerboven CMüller M(2021)A Theoretical Model for Global Optimization of Parallel AlgorithmsMathematics10.3390/math91416859:14(1685)Online publication date: 17-Jul-2021
https://doi.org/10.3390/math9141685
Danelutto MMencagli GTorquati MGonzález–Vélez HKilpatrick P(2020)Algorithmic Skeletons and Parallel Design Patterns in Mainstream Parallel ProgrammingInternational Journal of Parallel Programming10.1007/s10766-020-00684-wOnline publication date: 9-Nov-2020
https://doi.org/10.1007/s10766-020-00684-w
Tóth MBozó IKozsik T(2017)Pattern Candidate Discovery and Parallelization TechniquesProceedings of the 29th Symposium on the Implementation and Application of Functional Programming Languages10.1145/3205368.3205369(1-26)Online publication date: 30-Aug-2017
https://dl.acm.org/doi/10.1145/3205368.3205369
Darlington JField AHakim L(2017)Tackling Complexity in High Performance Computing ApplicationsInternational Journal of Parallel Programming10.1007/s10766-016-0422-945:2(402-420)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s10766-016-0422-9
Ni JChen YSha JZhang M(2015)SoSE Architecture of Data Intensive Computing for Healthcare Information System2015 Eighth International Conference on Internet Computing for Science and Engineering (ICICSE)10.1109/ICICSE.2015.37(159-167)Online publication date: Nov-2015
https://doi.org/10.1109/ICICSE.2015.37
Bozó IFordós VHorvath ZTóth MHorpácsi DKozsik TKöszegi JBarwell ABrown CHammond KCastro LSvensson H(2014)Discovering parallel pattern candidates in ErlangProceedings of the Thirteenth ACM SIGPLAN workshop on Erlang10.1145/2633448.2633453(13-23)Online publication date: 3-Sep-2014
https://dl.acm.org/doi/10.1145/2633448.2633453
Bozó IFördős VHorpácsi DHorváth ZKozsik TKőszegi JTóth M(2014)Refactorings to Enable ParallelizationTrends in Functional Programming10.1007/978-3-319-14675-1_7(104-121)Online publication date: 27-Dec-2014
https://doi.org/10.1007/978-3-319-14675-1_7
Brown CDanelutto MHammond KKilpatrick PElliott A(2013)Cost-Directed Refactoring for Parallel Erlang ProgramsInternational Journal of Parallel Programming10.1007/s10766-013-0266-542:4(564-582)Online publication date: 3-Sep-2013
https://doi.org/10.1007/s10766-013-0266-5
Aldinucci MCampa SKilpatrick PTordini FTorquati M(2013)An Abstract Annotation Model for SkeletonsFormal Methods for Components and Objects10.1007/978-3-642-35887-6_14(257-276)Online publication date: 2013
https://doi.org/10.1007/978-3-642-35887-6_14
González-Vélez HLeyton M(2010)A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablersSoftware—Practice & Experience10.5555/1890754.189075740:12(1135-1160)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.5555/1890754.1890757
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents