Files in this item



application/pdf8924831.pdf (9MB)Restricted to U of Illinois
(no description provided)PDF


Title:The interprocedural analysis and automatic parallelization of scheme programs
Author(s):Harrison, Williams Ludwell, III
Doctoral Committee Chair(s):Padua, David A.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
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 thesis 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.
Issue Date:1989
Rights Information:Copyright 1989 Harrison, Williams Ludwell, III
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI8924831
OCLC Identifier:(UMI)AAI8924831

This item appears in the following Collection(s)

Item Statistics