MultiLog: Data Or-Parallel Logic Programming.
Donald A. Smith · International Conference on Logic Programming · 1992
This thesis describes the design and implementation of MultiLog--a parallel logic programming language whose distinguishing feature is the presence of multiple binding with a single thread of control. MultiLog is particularly suited to exploit massive parallelism for the solution of combinatorial search problems. In a MultiLog program, certain goals are annotated with the unary operator disj; the goal disj G indicates that some subset of the solutions to G should be collected and turned into a set of (substitutions). Subsequent goals then execute in this set of environments, with unification performed 'in parallel' on multiple bindings. Multiple partially replace back-tracking as the operational embodiment of disjunction. The slogan, one control, multiple environments summarizes the 'data OR-parallelism' of MultiLog. We define precise operational semantics for MultiLog by formalizing the notion of Multi-SLD resolution, which we prove to be a sound and complete inference rule. We present a Scheme interpreter of MultiLog that elegantly expresses the abstract operational semantics and that suggests several important generalizations. We discuss abstract models for representing and analyze their time and space complexity. For concrete implementation, we describe the Multi-WAM architecture, which extends the standard Warren Abstract Machine that was originally designed for sequential execution of Prolog. The Multi-WAM consists of two main components: a Prolog engine executing Multi-WAM instructions, and a set of unification workers performing unifications and environment manipulation requests. A major optimization is the distinction between engine (sequential) variables and multi (parallel) variables. Implementations run on various uniprocessor computers, on the BBN Butterfly TC2000, and on the MasPar MP1. Benchmarks show useful speedups and good absolute performance for a range of search problems. We develop a formal model to explain the observed speedups; for both uniprocessor and SIMD MultiLog, the predicted speedups match the observed speedups to within a small constant factor.