Parallelism in production systems
Anoop Gupta · Medical Entomology and Zoology · 1987
Production system programs, on the surface, appear to be capable of using large amounts of parallelism--it is possible to match each production in a program to the data memory in parallel. The thesis shows that in practice, however, the speed-up obtainable from parallelism is quite limited, around 15-fold as compared to initial expectations of 100-fold to 1000-fold. The main reasons for the limited speed-up from parallelism are: (1) there are only a small number of productions that require significant processing as a result of a change to working memory; and (2) there is a large variation in the processing requirement of these productions. To obtain a large fraction of the limited speed-up that is available, the thesis proposes a parallel version of the Rete match algorithm which exploits parallelism at a very fine grain. It further suggests that a suitable architecture to exploit the fine-grained parallelism is a shared-memory multiprocessor, with 32-64 high performance processors. For scheduling the fine grained tasks (consisting of about 50-100 instructions), a hardware task scheduler is proposed. The thesis presents a large set of simulation results for production systems exploiting different sources of parallelism. The thesis points out the features of existing programs that limit the speed-up obtainable from parallelism and suggests solutions for some of the bottlenecks. The simulation results show that using the suggested multiprocessor architecture (with individual processors performing at 2 MIPS), it is possible to obtain execution speeds of 5000-27000 working memory element changes per second. This corresponds to a speed-up of 5-fold over the best known sequential implementation using a 2 MIPS processor. This performance is also higher than that obtained by other proposed parallel implementations of production systems.