Parallelism profiling of an Ops5 production system interpreter

The issue of processing nonnumeric algorithms has been one of the major research foci of parallel processing. However, nonnumeric algorithms are known to be difficult to parallelize due to their inherent non-regularity. In this paper, we investigate the potential parallelism in a typical nonnumeric problem. In particular, we selected an Ops5 production system interpreter. The parallelism we investigate is a very fine-grain parallelism at the instruction level. For our implementation of a complete Ops5, we selected SISAL, a purely functional language. A complete Ops5 is implemented in SISAL. Benchmark production system programs are executed to investigate potential parallelism in the production system interpreter. Experimental results indicated that the most of the parallelism can be extracted form the matching step of production systems. This particular implementation shows that the production system interpreter can give up to 8 fold speed-up in the absence of communication overhead.