| This dissertation studies the issues raised by the parallel execution of rules in a pattern-matching production system. There are two main areas of concern: maintaining correctness during the course of simultaneous rule executions, and controlling the execution of productions without introducing serial bottlenecks. It is demonstrated that guaranteeing program correctness using a serializability criterion introduces an unacceptable overhead and reduces the potential parallel speedup to a single order of magnitude. Instead of attempting to automatically extract coexecutable sets of parallel rules, the approach taken in this research is to define a minimal set of language constructs which allow correct parallel programs to be designed. The view that the rule-based computation has an algorithmic structure allows us to attach a semantic interpretation to rule firing. By examining the role of each rule in the overall computation, we can understand and begin to find a solution to the problems of controlling rule firing and ensuring correctness while maximizing effective use of parallel processing resources.;When rules are executed in parallel, the conventional control mechanisms applied to rule-based systems act to limit parallel activity. Two novel rule-firing policies are described: an asynchronous rule-firing policy that causes rules to be executed as soon as they become enabled, and a task-based scheduler that allows multiple independent tasks to run asynchronously with respect to each other while allowing rules to execute either synchronously or asynchronously within the context of each task. Because the asynchronous execution of rules reduces the opportunities for performing conflict resolution, methods for performing heuristic discrimination at various points in the rule execution cycle are discussed.;The experimental results of this research are presented in the context of UMass Parallel OPS5, a rule-based language that incorporates parallelism at the rule, action, and match levels, and provides language constructs for supporting the design of parallel rule-based programs including a locking scheme for working memory elements and operators for specifying local synchronization of rules and actions. Results are presented for a number of programs illustrating common AI paradigms including search, inference, and constraint satisfaction problems. |
