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

Article

Free access

Parcel: project for the automatic restructuring and concurrent evaluation of LISP

Author:

L. HarrisonAuthors Info & Claims

ICS '88: Proceedings of the 2nd international conference on Supercomputing

Pages 527 - 538

https://doi.org/10.1145/55364.55416

Published: 01 June 1988 Publication History

Abstract

Parcel (Project for the Automatic Restructuring and Concurrent Evaluation of Lisp) is an investigation of the problem of compiling Lisp for evaluation on a shared memory multiprocessor. In this paper, we present an overview of the process of compilation in Parcel. This process consists, broadly, of an interprocedural analysis, followed by a function-level restructuring of the lambda expressions that constitute a program. We discuss both of these phases, and illustrate the steps of restructuring with a few examples. A novel representation for s-expressions is employed in Parcel, to facilitate the parallel creation and access of lists; we review this representation, and discuss its implications for the compilation process. We conclude with some preliminary performance measurements of the prototypes of the Parcel compiler and run-time system.

References

[1]

Cousot P. and Cousot R. Systematic design ofprogram analysis frameworks. Conference Record of the Sizth A CM Symposium on Principles of, Programming Languages, ACM, Jan 1979~ pp269-272.

Digital Library

[2]

Gabriel R. Performance and Evaluation of Lisp Systems, MIT Press, Cambridge Mass., 1985.

Digital Library

[3]

Darlington 3. and Bttrstall R.M. A system which automatically improves programs. Acta Ittformatica 6(41), Springer Verlag, 1976.

[4]

Gabriel R.P. and McCarthy J. Queue-based multiprocessing lisp. Proceedings of the 1984 Conference on Lisp and Functional Programming (Austin, Texas, Aug. 1984), ACM, New York, 1984, pp25-44.

Digital Library

[5]

Gajskl D., Kuck D.J., Law-tie D., and Sameh A. CEDAR - a large scale multiprocessor. Proceedings of the 1985 International Conference on Parallel Processing, IEEE Computer Society Press, 1983~ pp524-529.

[6]

Gottlieb A., Grishraan R., et al, The NYU Ultracomputer - designing an MIMD shared memory parallel computer. IEEE Transactions on Computers, C-32(2), 1983.

[7]

Harrison L. The interprocedttral flow analysis of scheme programs. CStLD Tech Report, University of illinois at Urbana- Champaign, 1988.

[8]

Harrison L. Compiling LISP for Evaluation on an Tightly Coupled Multiproeessor. CSR/) Tech Report #565, University of Illinois at Urbana*Champaign, 1986.

[9]

Halstead R.H. Multilisp: a language for concurrent symbolic computation. A CM Transactior, s on Programming Languages and Systems 7(4), October 1985, pp501-538.

Digital Library

[10]

Ha~sen W.:I. Compact list representation: definition, garbage collection and system implementation. Communications of the A CM 12(9), September 1969.

Digital Library

[11]

Krarm D., Kelsey R., et al, ORBIT: An Optimizing Compiler for Scheme. Proceedings of the SIGPLAN 1986 Symposium on Compiler Construction, ACM, 1986, pp162-175.

Digital Library

[12]

Kuck D.J., Kulm R.H., Leasure B., and Wolfe M. The Structure of an Advanced Yectorizer for PipeHned Processors. Fourth International Computer Software and Applications Conference, Oct 1980.

[13]

Larus J. and Hilfinger P.N. Restructuring Lisp Programs for Concurrent Execution (Summary). Conference Record of the A CS SIGPLAN Symposium on Parallel Programming, ACM, 1988.

Digital Library

[14]

Marti J. and Fitch J. The Bath concurrent lisp machine. EUROCAM '83 (Lecture Notes in Computer Science), Springer-Verlag, 1983.

Digital Library

[15]

McGehearty P.F. and Krall E.J., Potentials for parallel execution of common llsp programs. Proceedings of the 1986 Ir,- ternational Conference on Parallel Processing, IEEE Computer Society Press, 1986, pp696-702.

[16]

S P Midkiff S.P. and Padua D.A. The Farther Concurrentization of Parallel Programs. CSRD Tech Report, University of Illinois at Urbana-Champaign, 1988.

[17]

Padua, D. A. and Wolfe, M., Advanced compiler optirnizations for supercomputers. Communications of the A CM 29(12), December 1986.

Digital Library

[18]

Pfister G.F., Brantley D.A., et al, The IBM reseazdx parallel processor prototype (RP3). Proceedings of the 1985 International Conference on Parallel Processing, IEEE Computer Society Press, 1985, pp764-771.

[19]

Rees J.A. and Clinger W., eds., The Revised3 Report on the Algorithmic Language Scheme. Sigplan Notices 21(12)Dec 1986.

Digital Library

[20]

Roads C.B. 3600 technical summary. Symholics Corp., Cam. bridge, Mass., February 1983.

[21]

Steele G.L. Jr., RABBIT: a Compiler for Scheme. AI Memo 47'4, MIT~ May 1978.

Digital Library

[22]

Steele, G.L. Jr., and Hillis, W.D. Connection machine llsp: fine-grained parallel symbolic symbolic processing. Proceedir~gs of the 1986 Conference on Lisp and Functional Programming (Cambridge, Mass, Aug. 4-6), ACM, New York, 1986, pp279-297.

Digital Library

[23]

Steele, G.L. Jr. Common Lisp: The Language, Digital Press, 1984. Wolf82 Wolfe M.J. Optimizing supercompilers for supercomputers. Ph.D. thesis, Report 82-1104, Dept. of Computer Science, Umversity Of Illinois, Oct 1982.

Digital Library

[24]

FXfSeries Architecture Manual, Alliant Computer Systems Corp, Acton Mass., Jan 1986.

[25]

Butterfly Parallel Processor Overview, BBN Laboratories Inc., Cambridge Mass., 1985.

Cited By

Nicolay Jde Roover Cde Meuter WJonckers V(2011)Automatic Parallelization of Side-Effecting Higher-Order Scheme ProgramsProceedings of the 2011 IEEE 11th International Working Conference on Source Code Analysis and Manipulation10.1109/SCAM.2011.13(185-194)Online publication date: 25-Sep-2011
https://dl.acm.org/doi/10.1109/SCAM.2011.13
Eigenmann RHoeflinger JJaxon GLi ZPadua D(2006)Restructuring Fortran programs for CedarConcurrency: Practice and Experience10.1002/cpe.43300507045:7(553-573)Online publication date: 25-Oct-2006
https://doi.org/10.1002/cpe.4330050704
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
Show More Cited By

Index Terms

Parcel: project for the automatic restructuring and concurrent evaluation of LISP

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 Lisp programs for concurrent execution
PPEALS '88: Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems

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 ...
Standard LISP (reprint)

When it was first formulated in 1960, (1) the programming language LISP was a truly machine independent language. However, even the earliest computer implementation encountered problems in input-output control and the handling of free variables which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICS '88: Proceedings of the 2nd international conference on Supercomputing

June 1988

679 pages

ISBN:0897912721

DOI:10.1145/55364

Editor:
J. Lenfant
Rennes

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

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1988

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
332
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)6

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nicolay Jde Roover Cde Meuter WJonckers V(2011)Automatic Parallelization of Side-Effecting Higher-Order Scheme ProgramsProceedings of the 2011 IEEE 11th International Working Conference on Source Code Analysis and Manipulation10.1109/SCAM.2011.13(185-194)Online publication date: 25-Sep-2011
https://dl.acm.org/doi/10.1109/SCAM.2011.13
Eigenmann RHoeflinger JJaxon GLi ZPadua D(2006)Restructuring Fortran programs for CedarConcurrency: Practice and Experience10.1002/cpe.43300507045:7(553-573)Online publication date: 25-Oct-2006
https://doi.org/10.1002/cpe.4330050704
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
Huelsbergen L(1997)Dynamic resolution: a runtime technique for the parallelzation of modifications to directed acyclic graphsInternational Journal of Parallel Programming10.1007/BF0269988425:5(385-417)Online publication date: 1-Oct-1997
https://dl.acm.org/doi/10.1007/BF02699884
Huelsbergen L(1996)Dynamic parallelization of modifications to directed acyclic graphsProceedings of the 1996 Conference on Parallel Architectures and Compilation Technique10.1109/PACT.1996.554032(186-197)Online publication date: 1996
https://doi.org/10.1109/PACT.1996.554032
Huelsbergen LLarus JAiken A(1994)Using the run-time sizes of data structures to guide parallel-thread creationACM SIGPLAN Lisp Pointers10.1145/182590.182442VII:3(79-90)Online publication date: 1-Jul-1994
https://dl.acm.org/doi/10.1145/182590.182442
Huelsbergen LLarus JAiken AKessler R(1994)Using the run-time sizes of data structures to guide parallel-thread creationProceedings of the 1994 ACM conference on LISP and functional programming10.1145/182409.182442(79-90)Online publication date: 1-Jul-1994
https://dl.acm.org/doi/10.1145/182409.182442
Baker H(1993)Equal rights for functional objects or, the more things change, the more they are the sameACM SIGPLAN OOPS Messenger10.1145/165593.1655964:4(2-27)Online publication date: 1-Oct-1993
https://dl.acm.org/doi/10.1145/165593.165596
Banerjee UEigenmann RNicolau APadua D(1993)Automatic program parallelizationProceedings of the IEEE10.1109/5.21454881:2(211-243)Online publication date: Jan-1993
https://doi.org/10.1109/5.214548
Furnari MPolychronopoulos C(1992)Run-time management of Lisp parallelism and the Hierarchical Task Graph program representationLanguages and Compilers for Parallel Computing10.1007/BFb0038670(266-282)Online publication date: 1992
https://doi.org/10.1007/BFb0038670
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