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.