The Search Ahead Conflict Resolution for Parallel Firing of Production Systems

Abstract

To explore the parallelism among rules is one of the ways to increase the speed of production systems. In this paper, an Object Pattern Matching model is proposed to interpret the dependency between production rules, and based on the rule dependency analysis, we develop a new conflict resolution principle, Search Ahead Conflict Resolution (SACR), which can select more than one rule to frre at each execution cycle. The so called Search Ahead Parallelism is thus achieveable by applying the SACR principle at run time. It is proved that the results of running programs in the new production system inference mechanism with SACR principle are the same as those running in the sequential inference mechanism with conflict resolution principle that is based on Last-In First-Out (LIFO) strategy. As a consequence, with the SACR principle, a program composed of a large set of production rules can run in a multiprocessor system and get the same result as those running in a uniprocessor system.