Article

Free access

A simple and efficient implmentation approach for single assignment languages

Authors:

Kourosh Gharachorloo,

John L. HennessyAuthors Info & Claims

LFP '88: Proceedings of the 1988 ACM conference on LISP and functional programming

Pages 259 - 268

https://doi.org/10.1145/62678.62718

Published: 01 January 1988 Publication History

Abstract

Functional and single assignment languages have semantically pure features that do not permit side effects. This lack of side effects makes detection of parallelism in programs much easier. However, the same property poses a challenge in implementing these languages efficiently. A preliminary implementation of a compiler for the single assignment language, SISAL, is described. The compiler uses reference counts for memory management and copy avoidance. Performance results on a wide range of benchmark programs show that SISAL programs compiled by our implementation run 2-3 times slower on average than the same programs written in C, Pascal, and Fortran, and orders of magnitude faster than other implementations of single assignment languages. Extensions of these techniques for multiprocessor implementations are proposed.

References

[1]

W. B. Ackerman and J. B. Derails. VAZ - A Value Oriented Algorithmic Lar~guage. Technical Report LCS/TIl-128, MIT, June 1979.

[2]

Arvind et al. An A.wnchronous Programming Language and Computing Machine. Technical Report 114A, UC Irvine, December 1978.

[3]

Arvind and R. E. Thomas. }-Structures: An Ej~cient Data Type for Functional Languages. Tedmical Report MIT/LCS/TM-210, MIT, i981.

[4]

J. Backus. Can programming be liberated fi'om the von neumann style? a fiu~ctiona, l style a,nd its algeb,'a of progra.ms. Communication.s of the A CM, 21(8), August, 1978.

Digital Library

[5]

James R. Celoni a.nd John L. Hennessy. SAL : A Single A~aignment Language for Parallel Algorithms. Technical Report CLaSSic-83-01, Stanford University, September 1983.

[6]

F. C. Chow. A Portable Machine-Independent Global Optimizer - De~igr, and Measurements. PhD thesis, Sta. xfford University, December 1983.

Digital Library

[7]

Ron Cytron and Jealn:te Ferran{e. What~ in a Name? -or- The Value of Renaming for Parallelism Detectior, and Storage Allocation. Techlfical l:leport RC 12785 (#55984), mM T. J. Watson Research Center, Jmuary 1987.

[8]

A. L. Davis and R. M. Keller. Data flow progrant graphs. IEEE Computer, 15(2), February 1982.

[9]

J. R. Ellis. Bulldog: A Compiler for VLIW Architectures. PhD thesis, Yale University, February 1985.

Digital Library

[10]

K. Gopinath. Optimization of Single A.,.qignment Languages. PhD thesis, Stanford University, 1988. Ill preparation.

Digital Library

[11]

J. R. Gurd, C. C. Kirkhaln, and I. Wat:son. The ma.ncheater prototype dataflow computer. Communications of the A CM, 28(1), January 1985.

Digital Library

[12]

Paul Hudak. A sema.ntic model of reference counting and its abstraction, in A CM Sympo,ium on Lisp and Functional Programming, August 1986.

Digital Library

[13]

Paul Hudak and Adrienne Bloss. The aggrega.te update problem in ~unctional programming systems. In Twelfth Annual A CM Sym, po,ium on Principles of Programming Languages, pages 300-313, Ja.mtary 1985.

Digital Library

[14]

J. S. Kowalik, editor. Parallel MIMD Computation : the HEP Supercomputer and Its Applications. MIT Press, 1985.

Digital Library

[15]

J. McGraw et a l. SISAL: Streams and Iteration.q in. a Single A,.~ignment Language~ Language 12eference Manual, Version 1.~. Technical Report M-146, LLNL, Ma.rch 1985.

[16]

Rodney R. Oldehoeft and David C. Ca llll. Applica.tive parallelism on a shared-nmlnory nmlt;iprocessor. IEEE Software, 5(1), Janua.ry 1988.

Digital Library

[17]

C. D. Polychronopoulos. On Program Restructuring, Scheduling, and Communication for Parallel Proae, sor System.q. PhD thesis, Ulfiversity of illinois, August 1986.

Digital Library

[18]

Vivek Sa.rkar. Pariitioning and Scheduling Para. Ilel Programs for Ezecution on M'ultiproce.qsor~. PhD thesis, Stanford University, April 1987. (Technical Report CSL-TR-87-328).

[19]

S. t(. Skedzielewski and J. Glauert. IF1 - An Intermediate Form for Applicative Lang~age.~, VeT, ion 1.0. Technical Report M-170, LLNL, July 1985.

[20]

S. K. Skedzielewski, R. K. Yates, and R. R. Oldehoeft. Di: an interactive debugging interpreter for applicative languages. Ill Procceding~ of the SIGPLAN '$7 Symposium on Interprcter~ and Interpretive Techniques, pages t02-109, June 1987.

Digital Library

[21]

M. L. Welcolne a.nd S. K. Skedzielewski. Data. flow editor, Functional Programming Languages and Computer Architecture, $pringer-Vcrlag, 1985.

Cited By

Budimlic ZChandramowlishwaran AKnobe KLowney GSarkar VTreggiari LPetersen LChakravarty M(2009)Declarative aspects of memory management in the concurrent collections parallel programming modelProceedings of the 4th workshop on Declarative aspects of multicore programming10.1145/1481839.1481846(47-58)Online publication date: 20-Jan-2009
https://dl.acm.org/doi/10.1145/1481839.1481846
Odersky M(2005)Observers for linear typesESOP '9210.1007/3-540-55253-7_23(390-407)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-55253-7_23
Schnorf PGanapathi MHennessy J(1993)Compile-time copy eliminationSoftware—Practice & Experience10.1002/spe.438023110223:11(1175-1200)Online publication date: 1-Nov-1993
https://dl.acm.org/doi/10.1002/spe.4380231102
Show More Cited By

Index Terms

A simple and efficient implmentation approach for single assignment languages
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Functional languages

Recommendations

A simple separate compilation mechanism for block-structured languages

A very simple and efficient technique for the introduction of separate compilation facilities into compilers for block-structured languages is presented. Using this technique, programs may be compiled in parts while the compile-time checking advantages ...
Languages as libraries
PLDI '11: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation

Programming language design benefits from constructs for extending the syntax and semantics of a host language. While C's string-based macros empower programmers to introduce notational shorthands, the parser-level macros of Lisp encourage ...
Languages as libraries
PLDI '11

Programming language design benefits from constructs for extending the syntax and semantics of a host language. While C's string-based macros empower programmers to introduce notational shorthands, the parser-level macros of Lisp encourage ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

LFP '88: Proceedings of the 1988 ACM conference on LISP and functional programming

January 1988

351 pages

ISBN:089791273X

DOI:10.1145/62678

Chairman:
Jerome Chailloux
INRIA, Rocquencourt

Copyright © 1988 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1988

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

LISP88

Sponsor:

LISP88: Lisp & Functional Programming 88

July 25 - 27, 1988

Utah, Snowbird, USA

Acceptance Rates

Overall Acceptance Rate 30 of 109 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
342
Total Downloads

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

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Budimlic ZChandramowlishwaran AKnobe KLowney GSarkar VTreggiari LPetersen LChakravarty M(2009)Declarative aspects of memory management in the concurrent collections parallel programming modelProceedings of the 4th workshop on Declarative aspects of multicore programming10.1145/1481839.1481846(47-58)Online publication date: 20-Jan-2009
https://dl.acm.org/doi/10.1145/1481839.1481846
Odersky M(2005)Observers for linear typesESOP '9210.1007/3-540-55253-7_23(390-407)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-55253-7_23
Schnorf PGanapathi MHennessy J(1993)Compile-time copy eliminationSoftware—Practice & Experience10.1002/spe.438023110223:11(1175-1200)Online publication date: 1-Nov-1993
https://dl.acm.org/doi/10.1002/spe.4380231102
Odersky MWise D(1991)How to make destructive updates less destructiveProceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/99583.99590(25-36)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/99583.99590
Baker H(1991)Shallow binding makes functional arrays fastACM SIGPLAN Notices10.1145/122598.12261426:8(145-147)Online publication date: 1-Aug-1991
https://dl.acm.org/doi/10.1145/122598.122614
Sarkar VCann DSameh Avan der Vorst H(1990)POSC—a partitioning and optimizing SISAL compilerProceedings of the 4th international conference on Supercomputing10.1145/77726.255152(148-164)Online publication date: 1-Jun-1990
https://dl.acm.org/doi/10.1145/77726.255152
Sarkar VCann D(1990)POSC—a partitioning and optimizing SISAL compilerACM SIGARCH Computer Architecture News10.1145/255129.25515218:3b(148-164)Online publication date: 1-Jun-1990
https://dl.acm.org/doi/10.1145/255129.255152
Larus J(1990)Compiling Lisp programs for parallel executionLisp and Symbolic Computation10.1007/BF018060614:1(29-99)Online publication date: 1-Dec-1990
https://dl.acm.org/doi/10.1007/BF01806061

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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