LISP and Symbolic Computation, 2(3/4)179-396
The Interprocedural Analysis and Automatic Parallelization of Scheme ProgramsWilliams Ludwell Harrison III, Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, 305 Talbot Laboratory, 104 South Wright Street, Urbana, IL 61801
|
Abstract: Lisp and its descendants are among the most important
and widely used of programming languages. At the same time,
parallelism in the architecture of computer systems is becoming
commonplace. There is a pressing need to extend the technology of
automatic parallelization that has become available to Fortran
programmers of parallel machines, to the realm of Lisp programs and
symbolic computing. In this paper we present a comprehensive approach
to the compilation of Scheme programs for shared-memory
multiprocessors. Our strategy has two principal components:
interprocedural analysis and program restructuring. We introduce
procedure strings and stack configurations as a framework in which to
reason about interprocedural side-effects and object lifetimes, and
develop a system of interprocedural analysis, using abstract
interpretation, that is used in the dependence analysis and memory
management of Scheme programs. We introduce the transformations of
exit-loop translation and recursion splitting to treat the control
structures of iteration and recursion that arise commonly in Scheme
programs. We propose an alternative representation for s-expressions
that facilitates the parallel creation and access of lists. We have
implemented these ideas in a parallelizing Scheme compiler and
run-time system, and we complement the theory of our work with
"snapshots" of programs during the restructuring process, and some
preliminary performance results of the execution of object codes
produced by the compiler.
Keywords: interprocedural analysis abstract interpretation, automatic parallelization, program transformation, parallel processing, symbolic computation, Lisp, Scheme |
This article is not available online.
![[picture of journal cover]](../LISP.JPG)