System graph proposed by Lozinskii can represent a logic database system. It evaluates the logic database system by bottom-up approach and reduces search space. We implement a bottom-up evaluator of logic database on a tightly-coupled multiprocessor system. To execute the system graph on a multiprocessor system, nodes in system graph should be allocated on processors so that computing loads for processors are well-balanced and communication among processors is minimized. In order to achieve this goal, we propose an algorithm which guesses computing time and communication cost at each node and allocates tasks among processors with simple heuristics.
We implement the parallel evaluator on SuperCluster which is composed of 64 nodes of transputer. The result of the implementation shows that the proposed method is usable in practical situations compared with other allocation methods.
