Serializability Improves Parallel Execution of Production System

• José Nelson Amaral PUCRS
• Joydeep Ghosh University of Texas

DOI: https://doi.org/10.5753/sbac-pad.1995.19861

Resumo

This paper presents a new production system architecture that uses serializability as a correctness criterion to select a set of productions to be executed in parallel. The use of serializability eliminales global synchronization. This architecture takes advantage of modern associative memory devices to allow parallel production firing, concurrent matching, and overlap among matching, selection, and firing of productions. A comprehensive event driven simulator is used to evaluate the scaling properties of the new architecture and to compare it with a parallel architecture using global synchronization before every production firing. Our results indicate that the combination of serializability and associative memories can achieve substantial improvements in speed with a very modest increase in hardware cost.

Referências

J. N. Amaral. A Parallel Architecture for Serializable Production Systems. PhD thesis, The University of Texas at Austin, 1994. Electrical and Computer Engineering.

J. N. Amaral and J. Ghosh. An associative memory architecture for concurrent production systems. In Proc. 1994 IEEE International Conference on Systems, Man and Cybemetics, San Antonio, TX. October 1994.

J. N. Amaral and J. Ghosh. Speeding up production systems: From concurrent matching to parallel rule firing. In L. N. Kanal, V. Kumar, H. Kitani, and C. Suttner, editors, Parallel Processing for AI, chapter 7, pages 139-160. Elsevier Science Publishers B.V., 1994.

C. L. Forgy. On the Efficient Implementations of Production Systems. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, 1979.

M. R. Garey, L'. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theor.. Cornput. Sci., 1:237-267, 1976.

A. Gupta. Parallelism in Production Systems. PhD thesis. Carnegie Mellon University, Pittsburgh, PA, March 1986.

A. Gupta, C. Forgy, and A. Newell. High-speed implementations of rule-based systems. ACM Transactions on Computer Systems, 7:119-146, May 1989.

T. lshida and S. Stolfo. Towards the parallel execution of rules in production system programs. In Proceedings of International Conference on Parallel Processing, pages 568-575, 1985.

P. C. Jackson. Introduction to Artificial lntelligence. Dover Pub., New York, 1985.

S. Kuo and D. Moldovan. The state of the art in parallel production systems. Journal of Parallel and Distributed Computing, 15:126, June 1992.

D. P. Miranker. TREAT: A New and Efficient Match Algoritm for AI Production Systems. Pittman/Morgan-Kaufman, 1990.

D. I. Moldovan. Rubic: A multiprocessor for rule-based systems. IEEE Transactions on Systems, Man and Cybemetics, 19:699-706, July/August 1989.

P. Nayak, A. Gupta, and P. Rosenbloom. Comparison of the Rete and Treat production matchers for SOAR (a summary). In Proceedings of National Conference on Artificial Intelligence, pages 693-698, August 1988.

K. Ofiazer. Partitioning in parallel processing of production systems. In Proceedings of Intemational Conference on Parallel Processing, pages 92-100, 1984.

J. Schmolze. A parallel asynchronous distributed production system. In Proceedings of National Conference on Artificial lntelligence, pages 65-71, 1990.

J. G. Schmolze. Guaranteeing serializable results in synchronous parallel production systems. Journal of Parallel and Distributed Computing, 13:348-365, December 1991.

J. G. Schmolze and W. Snyder. Using confluence to control parallel production systems. In Second International Workshop on Parallel Processing for Artificial Intelligence (PPAI-93), August 1993.

C. P. Thacker, D. G. Conroy, and L. C. Stewart. The alpha demonstration unit: A high performance multiprocessor. Communications of the ACM, 36:5567, February 1993.

J. Xu a nd K. Hwang. Mapping rule-based systems onto multicomputers using simulated annealing. Journal of Parallel and Distributed Computing, 13:442-455, December 1991.