THE ALLOCATION PROBLEM IN PARALLEL PRODUCTION SYSTEMS

Parallelism existing in a production system at different levels may be used to speed up the execution. In this paper, the notion of dependence between rules is introduced. It is shown that the analysis of dependences reveals the inherent parallelism and communication requirements among the rules. Techniques for automatic detection of parallelism and communication requirements are presented. A total parallel model which exploits parallelism in all the phases including matching and firing productions is assumed. The execution of a production of system on a multiprocessor involves the problem of partitioning the database and the rules among the processors. This is formulated as a 0-1 linear-quadratic programming problem and is shown to reduce to 0-1 linear programming with the penalty of increasing the size of the problem. Finally, a heuristic is given to solve the allocation problem using the A* algorithm. © 1990.