High-Level Abstractions for Symbolic Parallel Programming
Kinson Ho
(Professor P. N. Hilfinger)
(NSF) CCR-84-51213 (PYI)

I am developing a toolbox of high-level abstractions for writing
symbolic applications, including those with side effects [1].
Programs written using this toolbox may be executed without
modification on uniprocessors and multiprocessors. The toolbox is
intended for programmers who need to use their multiprocessing
hardware effectively, but are not interested or experienced in
parallel programming. Most of the parallel programming issues are
hidden from the programmer.

Each tool of the toolbox provides a sequential-looking interface, and
programs that use these tools may be parallelized by using the
parallel implementation of the toolbox. These tools may be 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.

By expressing an application using these abstractions, all the details
of parallel programming are hidden by the toolbox implementation. My
claim is that a small toolbox is sufficient for a large class of
symbolic applications, and that there are efficient implementations of
the toolbox.  The sequential toolbox implementation runs in Common
Lisp. The parallel toolbox implementation runs in a commercial version
of SPUR Lisp, a superset of Common Lisp with flexible and low-level
extensions for multiprocessing. This parallel Lisp currently runs on
Sequent Symmetry shared-memory multiprocessors. The ideas developed
are not specific to Lisp, and are directly applicable to other
languages.

An unexpected discovery from this research is an optimistic scheme for
implementing discrete relaxation (X <= f(X)) (in parallel, in problem
domains where monotonicity is a necessary correctness condition. This
scheme, which I call monotonic asynchronous iteration, is developed in
the context of parallelizing a constraint satisfaction system, but is
applicable to discrete relaxation in general [2].

[1] K. Ho, "Managing Side Effects on Shared Data Parallel Symbolic
Computing: Languages, Systems, and Applications," ed. R. H. Halstead,
Jr. and T. Ito, US/Japan Workshop Proc., Lecture Notes in Computer
Sci., Vol. 748, Springer-Verlag, November 1993.

[2] K. Ho, P. N. Hilfinger, and H. W. Guesgen, "Optimistic Discrete
Parallel Relaxation," Proc. 13th Int. Joint Conf. Artificial
Intelligence, Vol. 1, Chambery, France, August 1993, pp. 268-273.