Logic Programming Research
Shared Paged Binding Array: A Universal
Data-Structure for Parallel Logic Programming
In Proc. NSF/ICOT Workshop on Parallel Logic Programming,
T. Chikayama and E. Tick (Eds),
University of Oregon CIS-TR-94-04, Mar. 1994.
Author(s)
Gopal Gupta,
Enrico Pontelli,
Vitor Santos Costa
Abstract
Two major problems that arise in parallel logic programming
systems are: (i) redundant computation
during and-parallel execution of dependent goals, and,
(ii) efficient representation of multiple
environments at runtime. Both these problems are caused by
non-determinism present in logic programs---responsible for much of the
power of logic programming.
This paper is mainly concerned with solving the second problem,
namely,
the efficient representation of multiple environments at runtime
in parallel logic programming systems. We present a datastructure called
the Shared Paged Binding Array that arguably is most suited
for implementing any arbitrary parallel logic programming system
(i.e., a system that exploits any arbitrary combination of dependent-and
parallelism, independent and-parallelism and or-parallelism). This
datastructure can also be used for and-or parallel execution of
Committed Choice Languages with Deep Guards as well as for realizing
the implementations of more advanced models of parallel execution
such as the Extended Andorra
Model and the Andorra Kernel Language. Details of the Shared Paged Binding
Array are presented, its merits over other techniques are shown, and, finally,
implementations that combine different flavors of and- and or-parallelism
using Shared Paged Binding Arrays are briefly sketched.
The whole paper
can be downloaded from our
server.
Logic Prog. Page Research Page Lab Home Page