The REDUCE OR Process Model for Parallel Execution of Logic Programs
Journal of Logic Programming 1991
Publication Type: Paper
A method for parallel execution of logic programs is presented. It uses REDUCE-OR trees instead of AND-OR or SLD trees. The REDUCE-OR trees represent logic-program computations in a manner suitable for parallel interpretation. The REDUCE-OR process model is derived from the tree representation by providing a process interpretation of tree development, and devising efficient bookkeeping mechanisms and algorithms. The process model is complete-it produces any particular solution eventually-and extracts full OR parallelism. This is in contrast to most other schemes that extract AND parallelism. It does this by solving the problem of interaction between AND and OR parallelism effectively. An important optimization that effectively controls the apparent overhead in the process model is given. Techniques that trade parallelism for reducing overhead are also described.
L.V. Kale, "The REDUCE OR Process Model for Parallel Execution of Logic Programs", Journal of Logic Programming, Publ: North Holland, vol. 11, July 1991, pp. 55-84.