DAP Prolog: A Set-oriented Approach to Prolog

Prolog is based on first-order predicate logic and works by generating sets of values for variables expressed as arguments to rules. However, current Prolog systems, implemented on sequential machines, work by using the Left-to-Right, Depth First (LRDF) search strategy and thus generate successive members of the solution set one at a time. This approach is unsuitable for implementation on many parallel machines. At Queen Mary College a project is under way to implement Prolog on an SIMD machine – the ICL Distributed Array Processor (DAP) – involving a set-oriented view of Prolog which is suitable for implementation on such a machine, and leads to an efficient execution of many symbolic problems. SIMD (Single Instruction, Multiple Data set) computers are a class of machines that are ideally suited to exploit the rapidly growing field of VLSI research to produce high-power computation at a low cost. They do so by replicating a simple processing unit many times. This makes them very efficient for a large class of homogeneous, regular problems as diverse as database applications and fluid-flow calculations. The set-oriented view of Prolog interpretation exploits the associative parallelism of an SIMD machine by distributing the database over the processors and implementing unification of constants on a within-processing element basis. In the first section we describe the research background to the current project involving defining and implementing DAP Prolog on the DAP. We then outline a general view of DAP Prolog and explain the set-oriented semantics in some detail. Section 3 is a brief overview of the basis of a sequential implementation of Prolog, while section 4 describes the main data structures and algorithms involved in implementing DAP Prolog on the DAP.