Determinacy Driven Optimization of And-parallel Prolog Implementations
Enrico Pontelli, Gopal Gupta, Dongxing Tang · The MIT Press eBooks · 1995
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. With the help of these optimizations, data-and parallel Prolog programs can be efficiently executed on very general andparallel system (such as &ACE and &-Prolog) with the efficiency of dedicated dataand parallel systems (such as Reform Prolog system). These optimizations have been implemented in the &ACE system, and the results are also presented. 1 Introduction Two main types of (implicit) and-parallelism have been identified and successfully exploited in ...