Serial combinators: “optimal” grains of parallelism

Paul Hudak; Benjamin Goldberg

doi:10.1007/3-540-15975-4_49

Serial combinators: “optimal” grains of parallelism

Paul Hudak, Benjamin Goldberg

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

A method is described for translating a high-level functional program into combinators suitable for execution on multiprocessors with no shared memory. It is argued that the granularity of the standard set of fixed combinators is too fine, whereas the granularity of user-defined functions is too coarse. The notion of a serial combinator is introduced that in some sense has optimal granularity, and that takes into account pragmatic issues such as the complexity of expressions and communication costs between processors. The technique improves on the standard notion of super-combinators by making them larger to retain locality and improve efficiency, and by ensuring that they have no concurrent substructure that could result in lost parallelism. Simulation results demonstrate improved performance on both sequential and parallel computing models.

Original language	English (US)
Title of host publication	Functional Programming Languages and Computer Architecture
Editors	Jean-Pierre Jouannaud
Publisher	Springer Verlag
Pages	382-399
Number of pages	18
ISBN (Print)	9783540159759
DOIs	https://doi.org/10.1007/3-540-15975-4_49
State	Published - 1985
Event	2nd International Conference on Functional Programming Languages and Computer Architecture, 1985 - Nancy, France Duration: Sep 16 1985 → Sep 19 1985

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	201 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	2nd International Conference on Functional Programming Languages and Computer Architecture, 1985
Country/Territory	France
City	Nancy
Period	9/16/85 → 9/19/85

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-15975-4_49

Cite this

Hudak, P., & Goldberg, B. (1985). Serial combinators: “optimal” grains of parallelism. In J-P. Jouannaud (Ed.), Functional Programming Languages and Computer Architecture (pp. 382-399). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 201 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-15975-4_49

Serial combinators: “optimal” grains of parallelism. / Hudak, Paul; Goldberg, Benjamin.
Functional Programming Languages and Computer Architecture. ed. / Jean-Pierre Jouannaud. Springer Verlag, 1985. p. 382-399 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 201 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hudak, P & Goldberg, B 1985, Serial combinators: “optimal” grains of parallelism. in J-P Jouannaud (ed.), Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 201 LNCS, Springer Verlag, pp. 382-399, 2nd International Conference on Functional Programming Languages and Computer Architecture, 1985, Nancy, France, 9/16/85. https://doi.org/10.1007/3-540-15975-4_49

@inproceedings{066a63ac35af4fc083a754bea5c56d53,

title = "Serial combinators: “optimal” grains of parallelism",

abstract = "A method is described for translating a high-level functional program into combinators suitable for execution on multiprocessors with no shared memory. It is argued that the granularity of the standard set of fixed combinators is too fine, whereas the granularity of user-defined functions is too coarse. The notion of a serial combinator is introduced that in some sense has optimal granularity, and that takes into account pragmatic issues such as the complexity of expressions and communication costs between processors. The technique improves on the standard notion of super-combinators by making them larger to retain locality and improve efficiency, and by ensuring that they have no concurrent substructure that could result in lost parallelism. Simulation results demonstrate improved performance on both sequential and parallel computing models.",

author = "Paul Hudak and Benjamin Goldberg",

note = "Funding Information: This research was supported In part by NSF Grant MCS-8302018 and a grant from Burroughs Corporation. Publisher Copyright: {\textcopyright} 1985, Springer-Verlag.; 2nd International Conference on Functional Programming Languages and Computer Architecture, 1985 ; Conference date: 16-09-1985 Through 19-09-1985",

year = "1985",

doi = "10.1007/3-540-15975-4_49",

language = "English (US)",

isbn = "9783540159759",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "382--399",

editor = "Jean-Pierre Jouannaud",

booktitle = "Functional Programming Languages and Computer Architecture",

}

TY - GEN

T1 - Serial combinators

T2 - 2nd International Conference on Functional Programming Languages and Computer Architecture, 1985

AU - Hudak, Paul

AU - Goldberg, Benjamin

PY - 1985

Y1 - 1985

N2 - A method is described for translating a high-level functional program into combinators suitable for execution on multiprocessors with no shared memory. It is argued that the granularity of the standard set of fixed combinators is too fine, whereas the granularity of user-defined functions is too coarse. The notion of a serial combinator is introduced that in some sense has optimal granularity, and that takes into account pragmatic issues such as the complexity of expressions and communication costs between processors. The technique improves on the standard notion of super-combinators by making them larger to retain locality and improve efficiency, and by ensuring that they have no concurrent substructure that could result in lost parallelism. Simulation results demonstrate improved performance on both sequential and parallel computing models.

AB - A method is described for translating a high-level functional program into combinators suitable for execution on multiprocessors with no shared memory. It is argued that the granularity of the standard set of fixed combinators is too fine, whereas the granularity of user-defined functions is too coarse. The notion of a serial combinator is introduced that in some sense has optimal granularity, and that takes into account pragmatic issues such as the complexity of expressions and communication costs between processors. The technique improves on the standard notion of super-combinators by making them larger to retain locality and improve efficiency, and by ensuring that they have no concurrent substructure that could result in lost parallelism. Simulation results demonstrate improved performance on both sequential and parallel computing models.

UR - http://www.scopus.com/inward/record.url?scp=85034988175&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034988175&partnerID=8YFLogxK

U2 - 10.1007/3-540-15975-4_49

DO - 10.1007/3-540-15975-4_49

M3 - Conference contribution

AN - SCOPUS:85034988175

SN - 9783540159759

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 382

EP - 399

BT - Functional Programming Languages and Computer Architecture

A2 - Jouannaud, Jean-Pierre

PB - Springer Verlag

Y2 - 16 September 1985 through 19 September 1985

ER -

Serial combinators: “optimal” grains of parallelism

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this