Article

Free access

Restructuring Lisp programs for concurrent execution

Authors:

James R. Larus,

Paul N. HilfingerAuthors Info & Claims

PPEALS '88: Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems

Pages 100 - 110

https://doi.org/10.1145/62115.62126

Published: 01 January 1988 Publication History

Abstract

This paper describes the techniques that the program transformation system CURARE uses to restructure Lisp programs for concurrent execution in multiprocessor Lisp systems and discusses the problems inherent in producing concurrent programs in a flexible and dynamic programming language such as Lisp.

CURARE's overall organization is similar to other program restructuring systems: it detects potential conflicts between statements in a program, then transforms the program to improve its concurrent performance, and finally inserts synchronization to ensure the program's concurrent behavior. However, the language and programs that CURARE transforms are very different from the FORTRAN programs that are the traditional targets of program restructuring and so CURARE requires new algorithms and approaches, which are described in this paper.

References

[1]

Donald C. Allen, Seth A. Steinberg, and Lawrence A. Stabile. Recent Developments in Butterfly Lisp. In Proceedings of AAAI-87 Sixlh National Conference on Artificial Intelligence, pages 2--6, July 1987.

[2]

A. J. Bernsteln. Analysis of Programs for Parallel Processing. IEEE Transaelions on Eleelronic Computers, EC-15(5):757-763, October 1966.

[3]

R. S. Bird. Notes on Recursion Elimination. Communications of the A CM, 20(6):434-439, June 1977.

Digital Library

[4]

Michael Burke and Ron Cytron. lnterprocedural Dependence Analysis and Parallelization. in Proceedings of the A CM SIGPLAN '86 Symposium on Compiler Cons~ructiou~ pages 162-175, June 1986.

Digital Library

[5]

J. Darlington and R. M. Burstall. A System which Automatically Improves Programs. A cia Informatica, 6(1):41-60, 1976.

[6]

Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The Program Dependence Graph and its Use in Optimization. A CM Transactions on Programming Languages and Systems, 9(3):319- 349, July 1987.

Digital Library

[7]

David K. Gifford, Pierre Jouvelot, John M. Lucassen, and Mark A. Sheldon. FX-87 Reference Manual. Technical Report MIT/LCS/TR-407, MIT Laboratory for Computer Science, September 1987.

[8]

Sharon L. Gray. Using Futures to Exploit Parallelism in Lisp. Master's thesis, MIT, February 1986. MS report.

[9]

Robert H. ttalstead, Jr. Multilisp: A Language for Concurrent Symbolic Computation. A CM Transactions on Programming Languages and Systems, 7(4):501-538, October 1985.

Digital Library

[10]

W. Ludwell Harrison, III and David A. Padua. Representing S-Expressions for the Efficient Evaluation of Lisp on Parallel Processors. In Proceedings of the 1986 International Conference on Parallel Processing, pages 703-710, August 1986.

[11]

Susan Horwitz, Jan Prins, and Thomas Reps. Integrating Non-Interfering Versions of Programs. In Conference Record of the Fifteenth Annual A CM Symposium on Principles of Programming Languages, p~ges 133-145, San Diego, California, January 1988.

Digital Library

[12]

G~rard Huet and Bernard Lang. Proving and Applying Program Transformations Expressed with Second-Order Patterns. Acta Iuformatica, 11(1):31-55, 1978.

Digital Library

[13]

Morris J. Katz. ParaTran: A Transparent, Transaction Based Runtime Mechanism for Par: allel Execution of Scheme. Master's thesis, MIT, June 1986.

[14]

Tom Knight. An Architecture for Mostly Functional Languages. In Proceedings of the 1986 A CM Conference on LISP and Functional Programming, pages 105-112, Cambridge, Massachusetts, August 1986.

Digital Library

[15]

Clyde P. Kruskal, Larry Rudolph, and Marc Snir. The Power of Parallel Prefix. IEEE Transactions on Computers, C-34(10):965-968, October 1985.

[16]

James R. Larus and Paul N. Hilfinger. Detecting Conflicts Between Structure A'ccesses. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, June 1988. To appear.

Digital Library

[17]

Samuel P. Midkiff and David A. Padua. Compiler Algorithms for Synchronization. IEEE Transaclions on Compuiers, C-36(12):1485- 1495, December 1987.

Digital Library

[18]

Eugene W. Myers. A Precise Inter-Procedural Data Flow Algorithm. in Conference Record of ~he Eighth Annual A CM Symposium on Principles of Programming Languages, pages 219-230, :I anuary 1981.

Digital Library

[19]

David A. Padua, David J. Kuck, and Duncan H. Lawrie. High-Speed Multiprocessors and Compilation Techniques. IEEE Transactions on Computers, C-29(9):763-776, September 1980.

Digital Library

[20]

Guy L. Steele Jr. and W. Daniel Hillis. Connection Machine LISP" Fine-Grained Parallel Symbolic Processing. In Proceedings of the 1986 ACM Conference on LISP and Functional Programming, pages 279-297, Cambridge~ Massachusetts, August 1986.

Digital Library

[21]

Michael :I. Wolfe. Optimizing Supercompilers for Supercomputers. Technical Report UIUCDCS- R-82-1105, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, October 1982. PhD dissertation.

Digital Library

Cited By

Griswold WOpdyke W(2015)The Birth of Refactoring: A Retrospective on the Nature of High-Impact Software Engineering ResearchIEEE Software10.1109/MS.2015.10732:6(30-38)Online publication date: 28-Oct-2015
https://dl.acm.org/doi/10.1109/MS.2015.107
Notkin DGarland DGriswold WSullivan K(2005)Adding implicit invocation to languages: Three approachesObject Technologies for Advanced Software10.1007/3-540-57342-9_91(489-510)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-57342-9_91
Gupta MMikhopadhyay SSinha N(1999)Automatic parallelization of recursive procedures1999 International Conference on Parallel Architectures and Compilation Techniques (Cat. No.PR00425)10.1109/PACT.1999.807504(139-148)Online publication date: 1999
https://doi.org/10.1109/PACT.1999.807504
Show More Cited By

Index Terms

Restructuring Lisp programs for concurrent execution
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Multiple instruction, multiple data
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Concurrency control

Recommendations

Restructuring Lisp programs for concurrent execution
Proceedings of the ACM/SIGPLAN PPEALS 1988

This paper describes the techniques that the program transformation system CURARE uses to restructure Lisp programs for concurrent execution in multiprocessor Lisp systems and discusses the problems inherent in producing concurrent programs in a ...
Restructuring Symbolic Programs for Concurrent Execution on
Restructuring symbolic programs for concurrent execution on multiprocessors

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPEALS '88: Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems

January 1988

246 pages

ISBN:0897912764

DOI:10.1145/62115

Editor:
Richard L. Wexelblat
Philips Labs., Briarcliff Manor, NY

ACM SIGPLAN Notices Volume 23, Issue 9
Proceedings of the ACM/SIGPLAN PPEALS 1988
Sept. 1988
246 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/62116
Editor:
Richard L. Wexelblat
Philips Labs., Briarcliff Manor, NY
Issue’s Table of Contents

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

SIGPLAN: ACM Special Interest Group on Programming Languages

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

PPEALS88

Sponsor:

SIGPLAN

PPEALS88: Parallel Programming: Experience with Applications, Language & Systems

July 19 - 21, 1988

Connecticut, New Haven, USA

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
476
Total Downloads

Downloads (Last 12 months)100
Downloads (Last 6 weeks)18

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Griswold WOpdyke W(2015)The Birth of Refactoring: A Retrospective on the Nature of High-Impact Software Engineering ResearchIEEE Software10.1109/MS.2015.10732:6(30-38)Online publication date: 28-Oct-2015
https://dl.acm.org/doi/10.1109/MS.2015.107
Notkin DGarland DGriswold WSullivan K(2005)Adding implicit invocation to languages: Three approachesObject Technologies for Advanced Software10.1007/3-540-57342-9_91(489-510)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-57342-9_91
Gupta MMikhopadhyay SSinha N(1999)Automatic parallelization of recursive procedures1999 International Conference on Parallel Architectures and Compilation Techniques (Cat. No.PR00425)10.1109/PACT.1999.807504(139-148)Online publication date: 1999
https://doi.org/10.1109/PACT.1999.807504
John ABrowne J(1998)Compilation of Constraint Programs with Noncyclic and Cyclic Dependencies to Procedural Parallel ProgramsInternational Journal of Parallel Programming10.1023/A:101879102365926:1(65-119)Online publication date: 1-Feb-1998
https://dl.acm.org/doi/10.1023/A%3A1018791023659
Ghiya RHendren LBoehm HSteele G(1996)Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in CProceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/237721.237724(1-15)Online publication date: 1-Jan-1996
https://dl.acm.org/doi/10.1145/237721.237724
Deutsch A(1994)Interprocedural may-alias analysis for pointersACM SIGPLAN Notices10.1145/773473.17826329:6(230-241)Online publication date: 1-Jun-1994
https://dl.acm.org/doi/10.1145/773473.178263
Deutsch ASarkar VRyder BSoffa M(1994)Interprocedural may-alias analysis for pointersProceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation10.1145/178243.178263(230-241)Online publication date: 1-Aug-1994
https://dl.acm.org/doi/10.1145/178243.178263
Giordano MFurnari MMassarotti A(1994)A parallel symbolic language for vision analysisProceedings of the First International Conference on Massively Parallel Computing Systems (MPCS) The Challenges of General-Purpose and Special-Purpose Computing10.1109/MPCS.1994.367038(518-522)Online publication date: 1994
https://doi.org/10.1109/MPCS.1994.367038
Furnari MMassarotti A(1994)Symbolic computing, Lisp languages, and parallel computingProceedings of the First International Conference on Massively Parallel Computing Systems (MPCS) The Challenges of General-Purpose and Special-Purpose Computing10.1109/MPCS.1994.367033(542-553)Online publication date: 1994
https://doi.org/10.1109/MPCS.1994.367033
Hoover R(1992)AlphonseACM SIGPLAN Notices10.1145/143103.14313927:7(261-272)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.1145/143103.143139
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

Figures

Tables

Media

View Table of Conten