Concepts, design, and performance analysis of a parallel prolog machine (Q1188587)

The book represents the author's thesis on building a high performance parallel Prolog machine for sequential Prolog language. In contrast to other attempts to execute sequential Prolog in parallel, this should be done without restricting the use of any of the Prolog language features such as dynamic assert/retract, cut etc. The primary objective of the book is, actually, the design of an architecture that allows the (sequential) Prolog parallel processing. Chapter 1 gives an introduction to logic programming and to the main dialects of parallel Prolog. Chapter 2 provides an overview of the Prolog compilation techniques, pointing out the most important problems and discussing the solutions from the parallelism perspective. Chapter 3 introduces a pipelined architecture of tightly coupled processors, allowing for the parallel execution of several independent operations. It is shown how (even fully deterministic) Prolog programs can be effectively mapped onto a processor pipeline, and how it is possible to reduce the effects of implementation-dependent overhead functions such as allocating/deallocating stack space, creating choice points, parameter passing, address calculating etc. Section 3.1. gives an example of how a fragment of a C program can be pipelined on a multi-processor system. Section 3.2. proposes a global pipeline architecture for Prolog, and discusses the structure of a pipeline ring buffer block. Section 3.3. investigate the execution flow model through the pipeline: communication and synchronisation of the processors, backtracking implementation, AND- parallelism restrictions. Chapter 4 shows how the occur-check problem can be solved for all practical purposes by distinguishing the context in which logical variables might occur. The question is how to detect those places where the occur-check can be safely omitted, and where an occur- check has to be done. The proposed method is discussed in terms of an actual implementation based on the Warren abstract machine instruction set. It allows one to differentiate at run-time between variables that occur once and more than once in a given goal. This information helps to decide whether a variable is possibly aliased or not. Whenever unaliased variables are unified with arbitrary terms, the occur-check can safely be omitted, and unification becomes a simple assignment operation. The conseqences entail important benefits. Chapter 5 provides the complete specification of the parallel Prolog instruction set and the processor architecture, preserving the spirit of the original Warren abstract machine instruction set. Chapter 6 provides a qualitative and quantitative analysis of the parallel Prolog machine, proved to be superior in all points to a comparable sequential machine. The two appendices contain the benchmark programs used to compare parallel and sequential compilers, and some examples of compiled Prolog procedures using the parallel Prolog instruction set.