Logic Programming Research

Determinacy Driven Optimizations of And-Parallel Prolog Systems

New Mexico State University, Technical Report.

Gopal Gupta, Enrico Pontelli, DongXing Tang,

And-parallelism arises in Prolog programs when conjunctive subgoals in a query or the body of a clause are executed in parallel. In this paper we present three optimizations, namely, the last parallel call optimization, the shallow parallelism optimization, and the processor determinacy optimization that take advantage of determinacy to improve efficiency of and-parallel execution of Prolog programs. All three optimizations depend on a posteriori knowledge of determinacy rather than on a priori knowledge detected at compile-time. The last parallel call optimization (lpco) is triggered when the body of a clause that matches a goal in a parallel conjunction contains a parallel conjunction at the end. The lpco is inspired by the last call optimization found in traditional Prolog systems and can result in savings of space as well as much faster parallel backtracking. The shallow parallelism optimization and the processor determinacy optimizations allow the implementation to avoid allocation of parallel control frames on the (control) stack. They both lead to savings of time and space. The shallow parallelism optimization is triggered when an and-parallel goal is determinate while the processor determinacy optimization is triggered when the same processor executes two consecutive and-parallel goals. With the help of these optimizations, data-and parallel Prolog programs can be efficiently executed on very general and-parallel system (such as &ACE and &-Prolog) with the efficiency of dedicated data-and parallel systems (such as Reform Prolog system). While all three optimizations are very general in nature, and can be applied to both dependent- as well as independent and-parallel systems, in this paper we explain them in the context of independent and-parallelism. These optimizations have been implemented in the &ACE system, and the results are also presented.

The whole paper can be downloaded from our server.

Logic Prog. Page Research Page Lab Home Page