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.

Gopal Gupta, Enrico Pontelli, Vitor Santos Costa

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