Symbolic applications are characterized by irregular and data-dependent patterns of control flow and data structure accesses. In this dissertation I propose a toolbox approach for writing parallel symbolic applications, including those with side effects. Programs written using the high-level abstractions in this toolbox may be executed without modification on uniprocessors and multiprocessors. The toolbox is designed and implemented by parallel programming experts, and is intended for novice parallel programmers. Most of the parallel programming issues are hidden from the programmer. Each tool of the toolbox provides a stylized sequential interface, and programs that use these tools may be parallelized by using the parallel implementation of the toolbox. These tools are divided into parallelism abstractions and data-sharing abstractions. Parallelism abstractions represent common, time-consuming operations that offer good speedup potentials for parallel implementations. Data-sharing abstractions support common side-effecting operations on shared objects, simplifying the coding of a large class of algorithms that modify shared data structures in a parallel implementation. The thesis of this research is that a small toolbox is sufficient for a large class of symbolic applications, and that there are efficient (sequential and parallel) implementations of the toolbox.
To evaluate the feasibility of the toolbox approach for symbolic parallel programming, I constructed a prototype toolbox of commonly used abstractions, and converted two significant applications to use the toolbox. The applications include a constraint satisfaction system and a type analysis system. These applications have been developed by other authors, and contain approximately 8,000 lines of Common Lisp each. They are much larger than what other researchers have typically used to evaluate their symbolic parallel programming systems.
My experience with these two applications suggests that the toolbox approach for symbolic parallel programming is indeed successful. Many toolbox abstractions are common to the applications, and the toolbox version of either application may be ported between uniprocessors and multiprocessors without modification. Furthermore, the toolbox may be used by novice parallel programmers to parallelize an application relatively easily, since all the low-level parallel programming details are hidden by the parallel toolbox implementation.
An unexpected discovery from this research is an optimistic method for implementing discrete relaxation in parallel, in problem domains where monotonicity is a necessary correctness condition. This scheme is developed in the context of parallelizing the constraint application, but is applicable to discrete relaxation in general.
Title
High-Level Abstractions for Symbolic Parallel Programming (Parallel Lisp Hacking Made Easy)
Published
1994-06-01
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
CSD-94-816
Type
Text
Extent
164 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
