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.