Portal de Periódicos da CAPES

An intelligent backtracking algorithm for parallel execution of logic programs

1986; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-16492-8_64

1611-3349

Yow-Jian Lin, Vipin Kumar, Clement H. C. Leung,

Parallel Computing and Optimization Techniques

In this paper we present a simple but efficient backtracking scheme which works when AND-parallelism is exploited in a logic program. The scheme is well suited for implementation on a parallel hardware. We show that the backtracking scheme presented by Conery and Kibler in the context of AND/OR process model is incorrect, i.e., in some cases it may miss solutions while performing backtracking. Even if no AND-parallelism is exploited (i.e., all literals are solved sequentially), our scheme is more efficient than the "naive" depth-first backtracking strategy used by Prolog because our scheme makes use of the dependencies between literals in a clause. Chang and Despain have recently presented a backtracking scheme which also makes use of the dependencies between literals. We show that our scheme is more efficient than their scheme in the sense that our scheme does less backtracking.