Abstract

This paper presents a novel architectural model that implements the Multipath execution model of Prolog programs. Multipath performs a partial breadth-first traversal of SLD trees, which is shown to be more efficient than the standard depth-first traversal for most of the benchmarks. Its advantages can be exploited in either a sequential or a parallel implementation. In a sequential execution, Multipath reduces the number of operations by traversing more than one search path in a single control flow. Moreover, in the context of a parallel environment, Multipath exploits path parallelism, a particular case of data parallelism when exploring search trees. We present performance figures of a sequential implementation and we measure the amount of parallelism exhibited by the execution model that could be exploited by a parallel implementation.

You do not currently have access to this article.