SIMD, SAMD, or Cray LP

Appeared in Volume 7/1, February 1994

yk@trc.rwcp.or.jp
Yasusi Kanada
13th October 1993

Stephen Quirolgico writes:
Does anyone know of a parallel LP compiler for a SIMD (CM-2), SAMD (CM-5), or Cray T3D? I am not interested in pure MIMD machine compilers because of their associated synchronization problems.

The following papers discuss implementation techniques for LP languages running on (Japanese) pipelined vector processors.

Y, Kanada, K. Kojima, and M. Sugaya: Vectorization Techniques for Prolog, ACM Int. Conf. on Supercomputing, 1988, St. Malo.

Y. Kanada, and M. Sugaya: A Vectorization Techniques for Prolog without Explosion, Int. Joint Conf. on AI, 1989.

dsmith@cs.brandeis.edu
Donald A. Smith
20th December 1993

See the paper "MultiLog: Data Or-Parallel Logic Programming", which appeared in ICLP'93. It describes the rationale and design of the Multi-WAM, a generalization of the WAM that incorporates the notion of multiple substitutions with a single thread of control. The basic idea is to replace control or-parallelism (parallel search of an SLD tree) by data or-parallelism, the gist of which is as follows. For certain selected atoms a, a subcomputation is begun that collects a finite subset of the solutions to a. These solutions are installed as substitutions, one per (virtual) processor. Subsequent goals then execute in the context of the multiple environments, with unification performed "in parallel". With multi-SLD resolution, the abstract machine state consists of a pair <list of goals, set of substitutions>. Whereas standard SLD resolution enumerates the solutions to each atom one at a time, multi-SLD resolution enumerates the solutions to certain atoms subset by subset. Even a sequential implementation on a uniprocessor is faster than Prolog for many (most?) problems, basically because the "test" part of a generate-and-test program is performed once per set of solutions to the generator, rather than once per solution. As described in the paper, prototype implementations run on the BBN Butterfly, on the MasPar MP1, and on sequential machines. Since the paper has been written the system has also been ported to other machines (CM2, KSR1). There are lots of possible optimizations, extensions, and analyses (q.v. my dissertation).