Logic Programming Research
Optimizing And-Or Parallel Implementations
In Proc. of North American Conference on Logic Programming,
MIT Press, Oct. 1990, pp. 737-756
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
Logic Prog. Page Research Page Lab Home Page