(An) AND/OR graph model for parallel execution of logic program

Abstract

Current techniques for the interpretation of logic programs involve a sequential search for a global tree of procedure invocations. But the pure logic language is a concurrent language in which parallelism is embedded naturally. In this thesis, a parallel execution model based on the AND/OR Graph is presented. The backward execution procedure of the Conery``s model becomes to be included in forward execution procedure in the proposed model by the use of an algorithm which creates a current goal in an OR process. Since the number of generated messages and processes is far fewer than that of the Conery``s model, this model can be implemented on a multiprocessor architecture more efficiently. Furthermore, infinite loop can also be removed. The proposed model is applied to an abstract multiprocessor architecture. To perform the proposed model on the multiprocessor machine efficiently, the machine requirements are also described.