Parallel Processing Research

Optimizing And-Or Parallel Implementations


In Proc. of North American Conference on Logic Programming, MIT Press, Oct. 1990, pp. 737-756

Author(s)
Gopal Gupta, Bharat Jayaraman
Abstract
This paper describes ways of improving the performance of combined and-or parallel implementations. The model for and-or parallel execution of logic programs that we consider integrates the class of methods for exploiting or-parallelism which perform variable access and task-creation operations in constant-time (such as Binding Arrays method and Versions Vectors method) and the RAP method for independent and-parallelism. The major run-time overhead in such and-or parallel models can be traced back to the overhead incurred for or-parallelism during processor task switching. We present a number of techniques for reducing this overhead, by exploiting and-parallelism and the semantics of Conditional Graph Expressions (CGEs). Essentially, we reduce the overhead by reducing the number of conditionally bound variables whose bindings need to be installed during task-switching. These techniques can be easily incorporated in a compiler, and can lead to substantial savings in execution time.

The whole paper can be downloaded from our server.


Parallel Proc. Page Research Page Lab Home Page