Logic Programming Research

Last Parallel Call Optimization and Fast Backtracking in And-Parallel Logic Programming Systems

Manuel Carro, DonXing Tang, Gopal Gupta, Enrico Pontelli

In this paper we present a novel optimization called Last Parallel Call Optimization. The last parallel call optimization can be regarded as an extension of last call optimization, found in sequential systems, to and-parallel systems. The last parallel call optimization leads to improved time and space performance for a majority of and-parallel programs. The last parallel call optimization is presented in detail in this paper and its advantages discussed at length. The last parallel call optimization can be incorporated in a parallel system (such as RAPWAM) through relatively minor modifications to the runtime machinery. We also present some experimental results from a limited implementation of last parallel call operation done on the DDAS System. These experimental results prove that last parallel call optimization is indeed effective and produces better speed-ups with respect to an unoptimized implementation. We also discuss the problem of efficiently performing the kill operation in and-parallel systems. We present two approaches for efficiently propagating the kill signal to other parallel calls subsumed by the subgoal that received the kill signal. The first approach, implemented in the and-parallel component of the ACE system, propagates the kill lazily while the second one propagates the kill signal eagerly. The advantages and disadvantages of both these approaches are presented. The implementation and optimization techniques presented in this paper are very pragmatic and we believe that they will be of considerable utility to implementors of and-parallel systems.

The whole paper can be downloaded from our server.

Logic Prog. Page Research Page Lab Home Page