Logic Programming Research
Determinacy Driven Optimizations of And-Parallel Prolog Systems
New Mexico State University, Technical Report.
Author(s)
Gopal Gupta,
Enrico Pontelli,
DongXing Tang,
Abstract
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