A Multi-ring data flow architecture for parallel execution of logic programs.

Abstract

The problems in Artificial Intelligence (AI) are highly search-intensive, requiring enormous amounts of computation time on a sequential computer. This has motivated researchers to design parallel computer architectures for the efficient execution of AI programs. The basic idea of this approach is to decompose the search space into several subspaces and search for the solution in each of these subspaces in parallel. The theme of this work is the design of a multi-ring dataflow architecture for efficient execution of logic programs. The motivation for choosing a logic language for designing parallel machines is that logic languages have good knowledge-based inferencing capabilities, making them highly suitable for AI applications. The types of parallelism exploited include:

OR-parallelism Argument parallelism Stream AND-parallelism

An elegant scheme for handling deferred read requests generated by the I-structure memory is proposed in this thesis. A novel scheme for maintaining multiple binding environments is also discussed.

Performance Evaluation The performance evaluation of the proposed multi-ring architecture for studying its efficacy in OR-parallel execution is carried out by executing a few sample logic programs on a simulator developed in the discrete event simulation language SIMULA 67, implemented on a DEC 1090 system. The performance parameters studied are:

Speedup Efficiency Resource utilization

The results obtained do not indicate a linear speedup beyond a certain number of processors (e.g., four). One possible reason for this is that problems in the domain of AI are highly unstructured, leading to excessive overheads at runtime. However, better speedups are expected for larger problems with more clauses.

Language Implementation Schemes for the dataflow implementation of two languages known as:

Flat Concurrent Prolog (FCP) FLUNLOG

are discussed.