Multilog and data or-parallelism

AbstractThis paper describes the design, implementation, performance, and analysis of MultiLog—a logic programming system whose distinguishing feature is the presence of multiple, concurrent binding environments (multiple substitutions) with a single thread of control. In MultiLog, for certain goals, some subset of the solutions is collected and installed as the active set of substitutions. Subsequent goals execute with unification performed concurrently on the multiple substitutions, using a single thread of control. In this way, multiple binding environments partially replace backtracking as the operational embodiment of disjunction. The slogan “one control, multiple environments” summarizes the “data or-parallelism” of MultiLog. In this paper, we present an operational semantics (multi-SLD resolution) for MultiLog; discuss MultiLog's design and implementation; display benchmark results for prototype uniprocessor, MIMD, and SIMD implementations; present performance models that explain observed speedups; and consider various extensions and generalizations. Our aim is to evaluate the viability of data or-parallelism as an alternative both to backtracking and to control or-parallel search