Combining depth-first and breadth-first search in Prolog execution.
Jordi Tubella, Antonio M. González · 1994
A new model for the execution of Prolog programs, called MEM (Multipath Execution Model), which combines a depth-first and breadth-first exploration of the search tree is presented. The breadth-first search allows more than one path (multiple potential solutions) to be explored at the same time. In this way, the computational cost of traversing the whole search tree associated to a program can be decreased because the MEM model reduces the overhead due to the execution of control instructions. This paper focuses on the description of the MEM model and its sequential implementation. Moreover, the MEM execution model can easily extended to exploit a new kind of parallelism, called path parallelism, which allows the parallel execution of unify operations related to simultaneously explored paths. Since these operations do not have any dependence among them, this type of parallelism can always be exploited. An architecture (PMA) to implement the MEM execution model on a parallel environment...