Description
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.