Parallel execution on production systems

The paper proposes a scheme, dependency propagation algorithm (DPA), to analyze the parallelism of production systems, which have certain conflict resolution strategies. The scheme, based on a marked high-level Petri net, is to find out which rules can be executed in parallel without changing the semantics of OPS5-like production systems. This DPA uses explicit dependency, implicit dependency with degree 1 and dependency propagation to construct dependency matrix and parallel executable matrix. The high probability partitioning algorithm considering both load balance and maximal parallel execution uses a parallel executable matrix to map production rules into a multiprocessing system. The parallel execution model exploits not only parallel matching but also parallel firing. The initial results reveal that the performance of production systems is greatly improved