Author(s)
Last Alternative Optimization
Laboratory for Logic, DBs, and Advanced Programming
Dept. of Computer Science
New Mexico State University
Las Cruces, NM 88003
{epontell,gupta}@cs.nmsu.edu
Abstract
We present a new optimization for or-parallel logic programming (Prolog)
systems, called Last Alternative Optimization (LAO).
The LAO follows from the Flattening Principle and the Principle of
Duality of or-parallelism and and-parallelism.
Originally LAO was conceived as the dual of the Last Parallel Call
Optimization an optimization developed by us for and-parallel systems.
LAO enables Prolog programs that have data-or parallelism to execute
more efficiently. It also enables more efficient (parallel) execution of
Constraint Logic Programs over finite domains.
LAO is a fairly general optimization and can be readily applied to
virtually any parallel system that exploits non-determinism (e.g.,
parallel search based artificial intelligence systems).
The Last Alternative Optimization has been implemented in the ACE
parallel Prolog system.
The performance results presented in this paper indeed prove the
effectiveness of LAO.
We present a second optimization based on the flattening principle,
called the Balanced Nesting Optimization (BNO), that is related to LAO,
and that also leads to reduction of parallel overhead.