A parallel architecture for serializable production systems
José Nelson Amaral · 1995
This dissertation introduces a new parallel architecture for implementing production systems. Key innovations include the elimination of global synchronization before each production firing and the overlapping between the matching and the select-act phases of Production Systems. These innovations are made possible by the use of modern associative memory devices as control supporting structures. Allowing a production to fire before the matching of previous production firings is complete proved to be very efficient. The results produced by the architecture are proven to be correct according to the serializability criterion. The development of a new benchmark addresses the lack of good benchmarks for the study of novel production system architectures. This benchmark allows for variations in the number of productions, database size, size of local data clusters, and ratio between local and global data. A study of the production partition problem resulted in four different algorithms. These algorithms take into consideration processor workload balance, production interdependency, replication of data in memory, and reduction of communication traffic. Experimental studies with a comprehensive event driven simulator indicate that the use of dynamic information from previous runs produces more successful algorithms. A comparative study with a parallel architecture that does global synchronization before every production firing shows that both improvements, namely the elimination of global synchronization and the overlapping between matching, selecting and firing, are very effective in improving the performance of production systems. Further measurements indicate that only a modest amount of associative memory is needed for this architecture and that the use of a bus as an interconnection network does not constitute a bottleneck. Finally, a multiple functional unit Rete Network is considered within each processor of the architecture. New synchronization problems appear when multiple tokens are concurrently propagated through the Rete Network. Two synchronizing buffers assure correct operation of the architecture. Performance evaluations through system simulation and through analytical modeling indicate that using a modest number of functional units in the Rete Network is cost effective, but the architecture clearly yields diminishing returns when tens of functional units are used.