Author:

Keywords:

and or parallelism, andorra, kernel andorra prolog

Abstract:

This paper describes the design of a parallel implementation for Kernel Andorra Prolog (KAP) named kappaalphapipialpha. The main features of kappaalphapipialpha are AND/OR parallelism, committed choice guard evaluation combined with don't know nondeterminism and constraint operations on variables. The design is based on the Warren Abstract Machine with some important extensions. One of the main problems involving AND/OR parallel systems is the efficient handling of variables. We have adopted the PEPSys hashing scheme with additional mechanisms for handling guard blocking and waiting. A kappaalphapipialpha computation is divided into a number of steps. Every step contains a deterministic phase and a nondeterministic phase. The deterministic phase is executed in a normal Prolog-like way. The nondeterministic phase prunes the tree or divides the tree into a number of OR-branches, which share a common part of the tree. Each OR-branch is executed in the usual Prolog-like manner.