×

Or-parallel PROLOG in flat concurrent PROLOG. (English) Zbl 0684.68025

Summary: We describe a simple OR-parallel execution algorithm for PROLOG that naturally collects all solutions to a goal. For a large class of programs the algorithm has O(log n) overhead and exhibits O(n/(log n)\({}^ 2)\) parallel speedup over the standard sequential algorithm. Its constituent parallel processes are indepedent, and hence the algorithm is suitable for implementation on non-shared-memory parallel computers. The algorithm can be implemented directly in Flat Concurrent PROLOG. We describe a simple interpreter-based FCP implementation of the algorithm, analyze its performance under Logix, and include initial measurements of its speedup on the parallel implementation of FCP. The implementation is easily extended. We show an extension that performs parallel demand-driven search. We define two parallel variants of cut, cut-clause and cut-goal, and describe their implementations. We discuss the execution of the algorithm on a parallel computer, and describe implementations of it that perform centralized and distributed dynamic load balancing. Since the FCP implementation of the algorithm relies on full test unification, the algorithm does not seem to have a similarly natural implementation in GHC or PARLOG.

MSC:

68N01 General topics in the theory of software
68N25 Theory of operating systems
68T99 Artificial intelligence
68N99 Theory of software
PDFBibTeX XMLCite
Full Text: DOI