An abstract machine model for multiprocessor implementation of logic programs
Prasenjit Biswas, Shyh-Chang Su · 1988
Two natural forms of parallelism, AND-parallelism and OR-parallelism, available in unannotated logic programs (particularly in AI and knowledge processing) have continued to draw the attention of researchers in parallel processing for the last few years. Unfortunately, in spite of tremendous advancement in the efficiency of Prolog implementations, most of the proposed schemes for parallel implementations have failed to achieve their goals of significant coat effective speedup. In this thesis, an abstract multiprocessor machine model has been developed for parallel execution of logic programs, which demonstrates the feasibility of a scalable architecture and significant speedup. The execution scheme is based on message passing mechanism and completely distributed control and does not require any shared global memory. There are three major contributions in this thesis. The most important one is the notion of demand-driven OR parallelism (termed as Limited OR Parallelism (LOR)) developed in this thesis. A new instruction set architecture has been proposed which supports the novel distributed processing model. The third important contribution is in an elegant integration of the LOR parallelism with Restricted-AND parallelism in the distributed framework. The effectiveness of the abstract model has been demonstrated by emulation on a multi-transputer testbed.