An efficient OR-parallel processing scheme of Prolog: Hierarchical pincers attack search

The authors describe a Prolog OR-parallel processing scheme. An OR-tree representing an execution process of a Prolog program, is searched from the right and left sides of each subtree in the whole tree by a plurality of processors. Each processor performs the depth-first search independently. The search allows coarse task granularity to be obtained, and reduces the frequency of the task assignment or the data transfers among the processors. Introducing a special pointer (selection pointer) which indicates a position of the processors in the OR-tree minimizes the data transfer caused by each task assignment. The depth-first searches from both sides of subtrees extract the acceleration anomaly efficiently and reduce parallel processing time in some cases. The effectiveness of the scheme is demonstrated on a multiprocessor minisupercomputer Alliant FX/80.