On parallel unification for Prolog

Abstract

Parallel unification algorithms are not nearly so numerous or well-developed as sequential ones. In order to estimate the improvement in efficiency which may be expected, we define and discuss an objective measure of the effect of parallelism on a sequential algorithm. This measure, known as the potential parallel factor (PPF), is applied to parallel versions of the unification algorithms of Yasuura and Jaffar. The PPFs for these algorithms are measured on a variety of running Prolog programs to estimate what increase in speed may be expected in a Prolog environment from the use of parallelism. Other potential uses of parallelism may be evaluated by different applications of our general methods and techniques. © 1987 Ohmsha, Ltd. and Springer.