The interprocedural analysis and automatic parallelization of Scheme programs Export

@article{Harrison:1989:Parallelization, 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 andprogram restructuring. We introduceprocedure strings andstack 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 ofexit-loop translation andrecursion 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.}, author = {Harrison, Williams L.}, citeulike-article-id = {3623280}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/BF01808954}, citeulike-linkout-1 = {http://www.springerlink.com/content/w06452201433576m}, doi = {10.1007/BF01808954}, journal = {LISP and Symbolic Computation}, keywords = {continuation, dissertation, lambda-calculus, parallelization}, month = {October}, number = {3}, pages = {179--396}, posted-at = {2009-06-20 04:26:11}, priority = {0}, title = {The interprocedural analysis and automatic parallelization of Scheme programs}, url = {http://dx.doi.org/10.1007/BF01808954}, volume = {2}, year = {1989} }

TY - JOUR ID - Harrison:1989:Parallelization L3 - citeulike-article-id:3623280 N2 - 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 andprogram restructuring. We introduceprocedure strings andstack 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 ofexit-loop translation andrecursion 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. IS - 3 JF - LISP and Symbolic Computation EP - 396 TI - The interprocedural analysis and automatic parallelization of Scheme programs VL - 2 SP - 179 KW - continuation KW - dissertation KW - lambda-calculus KW - parallelization AU - Harrison, Williams PY - 1989/10/01/ UR - http://dx.doi.org/10.1007/BF01808954 ER -