1985 Reports

A simple preprocessing scheme to extract and balance implicit parallelism in the concurrent match of production rules

Stolfo, Salvatore; Miranker, Daniel P.; Mills, Russell C.

In this brief paper we report a simple scheme to extract implicit parallelism in the low-level match phase of the parallel execution of production system programs. The essence of the approach is to replicate rules while introducing new constraints within each copy to restrict each individual rule to match a potentially smaller set of data elements. Speed up is achieved by matching each copy of a rule in parallel. Variations of this approach may be applicable to logic-based programming systems, such as PROLOG, executed in a parallel environment. Indeed, sequential implementations of OPS-style production systems based on the Rete match algorithm may enjoy performance advantages as well. This scheme may be implemented by a simple preprocessing stage which requires no modification to the underlying match algorithms.