A data-driven parallel execution model and architecture for logic programs
Chien‐Chao Tseng · 1990
Logic Programming has come to prominence in recent years after the decision of the Japanese Fifth Generation Project to adopt it as the kernel language. A significant number of research projects are attempting to implement different schemes to exploit the inherent parallelism in logic programs. Data flow architectural model has been found to attractive for parallel execution of logic programs. In this research, five dataflow execution models available in literature, have been critically reviewed. The primary aim of the critical review was to establish a set of design issues critical to efficient execution. Based on the established design issues, the abstract data-driven machine model, named LogDf, is developed for parallel execution of logic programs. The execution scheme supports OR-parallelism, Restricted-AND parallelism and stream parallelism. Multiple binding environments are represented using stream of streams structure (S-stream). Eager evaluation is performed by passing binding environment between subgoal literals as S-streams, which are formed using non-strict constructors. The hierarchical multi-level stream structure provides a logical framework for distributing the streams to enhance parallelism in production/consumption as well as control of parallelism. The scheme for compiling the dataflow graphs, developed in this thesis, eliminates the necessity of any operand matching unit in the underlying dynamic dataflow architecture. The details of binding representation and efficient representation for structures/lists have also been developed. In this thesis, an architecture for the abstract machine LogDf is also provided and the performance evaluation of this model is based on this architecture. An extensive simulation facility has been developed and performance of LogDf for a number of benchmark programs has been measured. Four different token distribution strategies for the proposed multi-ring dynamic dataflow architecture has been studied. These results indicate the effectiveness of the proposed LogDf model and the architecture.