Parallel Processing of Production Systems: an Integrated Software and Hardware Approach.
Yifong Shih · Deep Blue (University of Michigan) · 1987
To efficiently execute logic programs in multiprocessors, several issues involving hardware support the software transformation are examined. A Petri net model of the logic program, called the connectivity graph, is proposed to reduce the time required for acquiring the conflict sets in every iteration. The transitions in a connectivity graph correspond to rules, and the arcs are labelled with associated antecedent and consequent predicates. Four classes of predicate matching are identified to enable the actual construction of the connectivity graph. Analyses are given for the performances of parallel heuristic search algorithms using a global OPEN queue or upward cost revision. It is found that algorithm EO*-binary, a parallel version of the AO* algorithm employing a global queue implemented in the form of a binary tree, has an increasing PE efficiency with an increasing number of PEs, while another algorithm FO*, which utilizes local upward cost revision, has a slowly decreasing efficiency that tapers off at 0.25. To tackle the problem of binding check in and -parallelism, a mesh-connected array called the unification array is proposed. A column of unification units unifies two subgoals at one level and passes the results to the next level. Four binding algorithms are proposed to control the flow of tokens inside an array. Two array scheduling algorithms are given for scheduling multiple arrays for the unification of a large number of subgoals. The final level in the array scheduling is found to involve the largest number of tokens, and should therefore be partitioned by using all available arrays. Finally, a topology called the Cyclic Multibus is proposed for the purpose of executing parallel heuristic search algorithms. The Cyclic Multibus is incrementally scalable, fault-tolerant and variable in the bus load and the number of I/O ports per PE. A cluster variation of the Cyclic Multibus retains most of the advantages of the Cyclic Multibus, plus a diameter that is the square-root function of the total number of PEs.