Combined And-Or Parallel Execution of Logic Programs

摘要

A number of approaches have recently been proposed for the parallel execution of logic programming languages, but most of them deal with either or-parallelism or and-parallelism but not both. This paper describes a high-level design for efficiently supporting both and-parallelism and or-parallelism. Our approach is based on the binding arrays method for or-parallelism and the RAP method for and-parallelism. Extensions to the binding-arrays method are proposed in order to achieve constant access-time to variables in the presence of and-parallelism. The RAP (Restricted And-Parallelism) method becomes simplified because backtracking is unnecessary in the presence of or-parallelism. The author's approach has the added effect of eliminating redundant computations when goals exhibit both and-and or-parallelism. The paper first briefly describes the basic issues in pure and-parallelism and or-parallelism, states desirable criteria for their implementation (with respect to variable access, task creation and switching), and then describes the combined and-or implementation.