article

Free access

Fast parallel implementation of lazy languages—the EQUALS experience

Authors:

C. R. Ramakrishnan,

I. V. Ramakrishnan,

R. C. SekarAuthors Info & Claims

ACM SIGPLAN Lisp Pointers, Volume V, Issue 1

Pages 335 - 344

https://doi.org/10.1145/141478.141570

Published: 01 January 1992 Publication History

Abstract

This paper describes EQUALS, a fast parallel implementation of a lazy functional language on a commercially available shared-memory parallel machine, the Sequent Symmetry. In contrast to previous implementations, we detect parallelism automatically by propagating exhaustive (normal form) demand. Another important difference between EQUALS and previous implementations is the use of reference counting for memory management instead of garbage collection. Our implementation shows that reference counting leads to very good scalability, low memory requirements and improved locality. We compare our results with sequntial SML/NJ as well as parallel (v, G-machine and GAML implementations.

References

[1]

A. Appel, J. Ellis and K. Li, t~eal-t~me concurrent collection on stock multiprocessors, PLDI, 1988.]]

Digital Library

[2]

L. Augustsson, A compiler for lazy M~, LFP,1984.]]

Digital Library

[3]

L. Augustsson and T. Johnsson, Parallel graph reduction with the (u, G) machzne, FPCA, t989.]]

[4]

J. Darlington, Alice: A multi-processor reductzon engine for the parallel evaluatzon of apphcative languages, FPCA, 1981.]]

Digital Library

[5]

L. George, An abstract machzne for parallel graph reduction, FPCA, 1989.]]

Digital Library

[6]

B. Goldberg, Buckwheat: Graph reduction on shared-memory multiprocessor, LFP, t988.]]

[7]

B. Goldberg, Multiprocessor execution of functional programs, PhD Thesis, Yale Univ. Dept of Computer Science, YALEU/DCS/RR-618, 1988.]]

Digital Library

[8]

T. Johnsson, Efficient compzlation of lazy evaluation, Compiler Construction, 1984.]]

Digital Library

[9]

G. Huet and J.J. Levy, Computatzons ~n hot, ambiguous hnear term rewriting systems, Tech Rep. No. 359, 1979, IRIA, ke Chesney, France, 1979.]]

[10]

A. L~ville, Implementation of lazy pattern matching algorithms, ESOP, LNCS 300, 1988.]]

Digital Library

[11]

L. Maranget, GAML: A parallel zmplementat~on of lazy ML, FPCA, 199t.]]

Digital Library

[12]

E. Mohr, D. Kr~nz and R. Halstead, Lazy task creation: A technique for ~ncreasing the granularity of parallel programs, LFP, 1990.]]

Digital Library

[13]

L. Puel ~nd A. Su~rez, Comp,hng pattern match- ~ng by term decomposition, LFP, 1990.]]

Digital Library

[14]

S.L. Peyton Jones, GRIP: A parallel graph reduction machine, FPCA, 1987.]]

[15]

R.C. Sekar, S. P~wagi, t.V. R~m~krishnan, Small domains spell fast strictness analysis, POP/, 1990.]]

Digital Library

[16]

R.C. Sekar, R. Ramesh and I.V. R~makrishnan, Adaptive pattern matching, to appear in ICALP, 1992.]]

Digital Library

[17]

Sequent Computer Systems, Sequent guide to parallel programming, 1987.]]

[18]

P. Watson and I. Watson, Evaluatzng fitnctzonal programs on the FLAGSHIP machine, FPCA, 1987.]]

Digital Library

Cited By

Bonacina M(2018)Parallel Theorem ProvingHandbook of Parallel Constraint Reasoning10.1007/978-3-319-63516-3_6(179-235)Online publication date: 6-Apr-2018
https://doi.org/10.1007/978-3-319-63516-3_6
Sekar RRamakrishnan I(1995)Fast strictness analysis based on demand propagationACM Transactions on Programming Languages and Systems10.1145/218570.21857317:6(896-937)Online publication date: 30-Nov-1995
https://dl.acm.org/doi/10.1145/218570.218573
Bonacina MHsiang J(1994)Parallelization of deduction strategies: An analytical studyJournal of Automated Reasoning10.1007/BF0088191013:1(1-33)Online publication date: 1994
https://doi.org/10.1007/BF00881910
Show More Cited By

Index Terms

Fast parallel implementation of lazy languages—the EQUALS experience
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

EQUALS – a fast parallel implementation of a lazy language

This paper describes EQUALS, a fast parallel implementation of a lazy functional language on a commercially available shared-memory parallel machine, the Sequent Symmetry. In contrast to previous implementations, we propagate normal form demand at ...
Fast parallel implementation of lazy languages—the EQUALS experience
LFP '92: Proceedings of the 1992 ACM conference on LISP and functional programming

This paper describes EQUALS, a fast parallel implementation of a lazy functional language on a commercially available shared-memory parallel machine, the Sequent Symmetry. In contrast to previous implementations, we detect parallelism automatically by ...
Parallel implementation of lazy functional languages using abstract demand propagation

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Lisp Pointers

ACM SIGPLAN Lisp Pointers Volume V, Issue 1

Jan. 1992

357 pages

ISSN:1045-3563

DOI:10.1145/141478

Editor:
Jon L. White
Lucid, Inc.

Issue’s Table of Contents

LFP '92: Proceedings of the 1992 ACM conference on LISP and functional programming
January 1992
365 pages
ISBN:0897914813
DOI:10.1145/141471
Chairman:
Jon L. White
Lucid, Inc.

Copyright © 1992 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1992

Published in SIGPLAN-LISPPOINTERS Volume V, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
348
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)8

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bonacina M(2018)Parallel Theorem ProvingHandbook of Parallel Constraint Reasoning10.1007/978-3-319-63516-3_6(179-235)Online publication date: 6-Apr-2018
https://doi.org/10.1007/978-3-319-63516-3_6
Sekar RRamakrishnan I(1995)Fast strictness analysis based on demand propagationACM Transactions on Programming Languages and Systems10.1145/218570.21857317:6(896-937)Online publication date: 30-Nov-1995
https://dl.acm.org/doi/10.1145/218570.218573
Bonacina MHsiang J(1994)Parallelization of deduction strategies: An analytical studyJournal of Automated Reasoning10.1007/BF0088191013:1(1-33)Online publication date: 1994
https://doi.org/10.1007/BF00881910
Kaser O(2005)Inlining to reduce stack spaceProgamming Language Implementation and Logic Programming10.1007/3-540-57186-8_84(262-274)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-57186-8_84
Caromel DHenrio LSerpette B(2004)Asynchronous and deterministic objectsACM SIGPLAN Notices10.1145/982962.96401239:1(123-134)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1145/982962.964012
Caromel DHenrio LSerpette BJones NLeroy X(2004)Asynchronous and deterministic objectsProceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/964001.964012(123-134)Online publication date: 14-Jan-2004
https://dl.acm.org/doi/10.1145/964001.964012
Sekar RRamakrishnan IVoronkov A(2001)Term indexingHandbook of automated reasoning10.5555/778522.778535(1853-1964)Online publication date: 1-Jan-2001
https://dl.acm.org/doi/10.5555/778522.778535
Bonacina M(2001)A taxonomy of parallel strategies for deductionAnnals of Mathematics and Artificial Intelligence10.1023/A:101893211405929:1-4(223-257)Online publication date: 10-Jan-2001
https://dl.acm.org/doi/10.1023/A%3A1018932114059
Kaser ORamakrishnan CPawagi S(1993)On the conversion of indirect to direct recursionACM Letters on Programming Languages and Systems10.1145/176454.1765102:1-4(151-164)Online publication date: 1-Mar-1993
https://dl.acm.org/doi/10.1145/176454.176510

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 Issue’s Table of Contents