Design And Implementation Of A Parallel Computer For Expert System Applications

ABSTRACT A parallel computer for high-speed execution of expert system programs has been designed and implemented at the Oak Ridge National Laboratory. Programs written in the popular OPS5 language for serial machines need not be modified by the programmer, since the compiler on this special-purpose machine automatically employs the parallelism inherent in the language. Tasks are automatically distributed to parallel rule processors which can evaluate OPS5 rules in parallel. Performance improvements of a factor of 10 over serial machines have already been demonstrated. Enhancements are under way to attain a performance improvement of 100 or more over serial machines for artificial intelligence applications requiring the evaluation of thousands of rules each recognize-act cycle.The initial hardware implementation of the parallel architecture consists of a host computer that broadcasts to 64 parallel rule processors over a transmit-only bus. The communication time is kept to a minimum by using direct-memory access and a memory-mapped addressing scheme that permit each of the parallel rule processors to receive the appropriate information simultaneously. A wired-OR completion flag signals the host whenever all of the parallel rule processors have finished their recognition tasks. The host then extracts information from those rule processors whose rules have been satisfied and, based on a global criterion, selects one of these rules. The host then carries out the actions dictated by this rule and broadcasts new information to the rule processors to begin another recognize-act cycle. Statistics detailing the activities of the host and all of the rule processors are collected and displayed in real time. Thus, the performance of the various aspects of the architecture can be readily analyzed. Also, the execution of the expert system program itself can be studied to detect situations that may be altered to permit additional speedup.1. INTRODUCTIONExpert system programs have been observed to perform tasks that rival those of recognized human experts in some domains. This level of performance can be attributed to several factors. Most important is the growing understanding of the process of capturing human expertise in computer-processible form. Important also are techniques for combining the knowledge of many domain experts into one program and for implementing recovery from, and correction of errors in, the application of this knowledge. Supporting these are the obvious speed and memory capabilities of contemporary computers.As ever larger and more complex bodies of knowledge are codified in expert systems, processing speed limitations become increasingly important. Some large expert systems are required to make complex decisions in seconds, decisions which may be based on the evaluation of hundreds or even thousands of rules. Performance of this order generally strains the limits of the current state of the art. This speed limitation problem can be addressed either by producing faster serial processors or by adopting some form of parallel processing system. A system utilizing parallelism has been developed at the Oak Ridge National Laboratory to execute programs written in the popular OPS5 language more efficiently than is possible on conventional serial systems.Rules written in the OPS5 language consist of "if-then" statements in which the "if portion consists of any number of conditions that must all be satisfied in order to execute the "then" portion. The "if conditions are commonly referred to as the "left-hand side," or LHS, of the rule while the "then" portion is known as the "right-hand side," or RHS. The actions dictated by a satisfied rule generally consist of making changes to the state of the program's working memory. Those rules whose working memory elements, or WMEs, have changed must then be reevaluated. This cycle, known as the "recognize- act" cycle, is then repeated.* Research sponsored by the U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc.* * Consultant, Oak Ridge National Laboratory* * * Electrical and Computer Engineering Department, The University of Tennessee, Knoxville, Tennessee.