Restructuring Symbolic Programs for Concurrent Execution on Multiprocessors
Abstract
CURARE, the program restructurer described in this dissertation, automatically transforms a sequential Lisp program into an equivalent concurrent program that executes on a multiprocessor. CURARE first analyzes a program to find its control and data dependences. CURARE uses a new data-dependence algorithm, which finds and classifies these dependences. Dependences constrain the program's concurrent execution because, in general, two conflicting statements cannot execute in a different order without affecting the program's result. A restructerer must know all dependences in order to preserve them. However, not all dependences are essential to produce the program's result. CURARE attempts to transform the program so it computes its result with fewer conflicts. CURARE then examines loops in a program to find those that are unconstrained or lightly constrained by dependences. Loops that are suitable for concurrent execution are changed to execute on a set of concurrent server processes. These servers execute single loop iterations and therefore need to be extremely inexpensive to invoke. Restructured programs execute significantly faster than the original sequential programs. This improvement is large enough to attract programmers to a multiprocessor, particularly since it requires little effort on their part. Although restructured programs may not make optimal use of a multiprocessor's parallelism, they make good use of a programmer's time.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1989
- Accession Number
- ADA631680
Entities
People
- James R. Larus
Organizations
- University of California, Berkeley