A SImple PreprocessIng Scheme to Extract and Balance Impllclt Parallelism In the Concurrent Match or ProductIon Rules 1

CUCS-174-85 In this brier paper we report a. simple scheme to extract implicit parallelism in the low-level match phase of the para.lle1 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.