Performance Comparison of Models for Multiple Rule Firing

1 Introduction

Multiple rule firing production systems increase the available parallelism over parallel match systems by parallelizing not only the match phase, but all phases of the inference cycle. To speedup the derivation of correct solutions by firing multiple rules in a produc­ tion cycle, two multiple rule firing problems - the compatibility and convergence problems - need to be addressed. The compatibility problem arises from the interferences between production rules. If a set of rules does not have inter-rule data dependence among themselves, they are said to be compatible and are al-

Performance Comparison of Models for Multiple Rule Firing

Steve Kuo and Dan Moldovan

skuo@gringo.usc.edu and moldovan@gringo.usc.edu Department of Electrical Engineering - Systems University of Southern California Los Angeles, California 90089-1115 DRB-363, (213) 740-9134

lowed to execute concurrently. The convergence prob­ lem arises from the need to follow the problem solving strategy used in a production program. If the problem solving strategy is ignored in a multiple rule firing sys­ tem, then two tasks may be executed out of sequence or two actions for the same task may be executed in the wrong order resulting in an incorrect solution.

There are three approaches to address the com­ patibility and convergence problems. The first ap­ proach considers only the compatibility problem and resolves it by data dependence analysis [6] [9] [11]. Both synchronous and asynchronous execution models have been proposed. In these models, rules which are compatible are fired concurrently in a production cy­ cle. Because the convergence problem is not addressed in these models, the problem solving strategy for a production program may be violated when multiple rules are fired simultaneously. The second approach addresses the compatibility and convergence problems by developing parallel production languages. CREL [9] and Swarm [4] are two such languages. Production programs written in these languages do not use control flow or conflict resolution to ensure that the right rules are fired. Instead, production rules are fired as soon as they are matched. The correctness of these parallel production programs is guaranteed by showing that for any arbitrary execution sequence the correct solutions are always obtained [2]. A potential hurdle for CREL and Swarm is the possible difficulty to prove the cor­ rectness of a large production program. In addition, to be able to fire production rules as soon as they are matched may not be the same as being able to fire multiple rules concurrently. These questions will be answered when the benchmark production programs have been translated into CREL and Swarm programs and their performance measured.

The multiple rule firing models presented in this paper represents the third approach. They address the compatibility problem by data dependence anal­ ysis and the convergence problem by analyzing the control flow in a production program to maintain the correct task ordering. In a production program, a com­ plex problem can be solved by dividing it into smaller tasks until they are easily solved. These tasks are called contexts and each context is solved by a set of context rules. The multiple rule firing models improve the performance of a production program by activat­ ing multiple contexts and firing multiple rules concur­ rently. They guarantee the correctness of the solution by determining the conditions under which multiple contexts and multiple rules can be activated and fired. The multiple rule firing models have been simulated on the RUBIC simulator and implemented on the In­ tel iPSC/2 hypercube. The results indicate that these models have successfully addressed the problems asso­ ciated with multiple rule firing.

2 Resolving the Compatibility and Convergence Problems

To resolve the compatibility and convergence problems successfully, one needs to understand how problems are solved in production programs. A useful method in general problem solving is the method of stepwise re­ finement, which resolves a complex problem by divid­ ing it into smaller and smaller subproblems (or tasks) until they are easily solved. If other subproblems need to be solved before solving a subproblem, the program control is transferred from one subproblem to another. Production programs also employ the method of step­ wise refinement to solve complex problems. First, the production rules in a production program are divided into subsets of rules, one subset for each subproblem. A subset of rules is called a context and each individ­ ual rule in the subset is called a context rule. Every context rule in the same context has a special context WME. Rules in different contexts have different con­ text WMEs. A programmer can control which context is active by adding and removing the context WMEs. Context rules are divided into domain rules and con­ trol rules. Domain rules address the subproblem asso­ ciated with the context and conflict resolution is used to select the right rule to fire. If other subproblems need to be solved before solving a subproblem, the con­ trol ruleS transfer the program control to the appro­ priate contexts by modifying the context WMEs. By analyzing the control rules, the control flow between different contexts can be determined. The problem solving strategy and the control flow diagram for an example production program is shown in Figure 1.

In this paper, we present three multiple rule firing models: the rule dependence {RDM} model, the single­ context-multiple-rules {SCMR) model, the multiple­ contexts-multiple-rules {MCMR) model. They resolve the compatibility and convergence problems at two levels: the rule level and the context level. At the rule level, the compatibility problem is resolved by data dependence analysis. A set of rules is allowed to fire concurrently and are said to be compatible if execut­ ing them either sequentially or concurrently, the same state is reached. This is the case if there are no data dependences among rules in the set. The data depen­ dence analysis is performed at compile time to con­ struct a parallelism matrix P = [p,i] and a communi­ cation matrix C = [cij]· Rules Rs and Rj are compat­ ible if Pij = 0; they are incompatible if Pii = 1. The communication matrix C is used for communication purpose when production rules are partitioned and mapped onto different processing nodes in a message­ passing multiprocessor. Rules Rs and Rj need to ex­ change messages to update the database if Cij = 1; they do not need to if Cij = 0.

The convergence problem is resolved at the rule level by dividing contexts in a production program into three different types: {1) converging contexts, {2) par­ allel nonconverging contexts and (3) nonconverging or sequential contexts. A context C is a converging con­ text if starting at a state satisfying the initial condition INIT for that context, all execution sequences result in states satisfying the post condition POST for that context [2] [4]. Otherwise context Cis a nonconverging context. The conflict resolution can be eliminated for a converging context because all execution sequences converge to the correct solution. Compatible rules can be fired simultaneously within a converging context without error. This is because firing a set of compati­ ble rules concurrently is equivalent to executing them in some sequential order and all execution sequences reach the correct solution for a converging context (for proof, see [8]). For a nonconverging context, conflict resolution must be used to reach the correct solution. The performance of a nonconverging context can be improved by parallelizing its conflict resolution. A parallel nonconverging context is a nonconverging con­ text whose conflict resolution is parallelizable and as a result multiple rules may be selected. The conflict resolution for a sequential context is not parallelizable and only sequential execution is possible. By dividing contexts into different types and applying the correct execution model for each type, the compatibility and convergence problems are resolved at the rule level.

The compatibility and convergence problems are resolved on the context level by analyzing the control flow diagram to determine which contexts are allowed to be active at the same time. These contexts are called compatible contexts. Two contexts are compati­ ble if their reachable sets do not intersect and rules in the two reachable sets do not have data dependences (for proof, see [7]). The reachable set for a context C; is the set of contexts which are reachable by following the directed arcs in the control flow diagram starting from C;. Context C; is included in its own reachable set. The reachable set for context C1 for the example production program in Figure 1 is {Cl> Ca, C4, Cs}.

The production rules are analyzed at compile time to generate the compatibility context matrix CC = [cc;j]· Two contexts C; and Cj are compat­ ible and are allowed to be active at the same time if CCij = 0; they are incompatible if cc;i = 1. The programmer then consults the CC matrix and mod­ ifies the production rules if needed so that only the compatible contexts will be activated concurrently in production program execution. In this way, the com­ patibility and the convergence problems are resolved on the context level.

3 Multiple Rule Firing Models

In this section, we present three pmltiple rule firing models which incorporate the solutions presented in Section 2 in varying degrees. The RDM model resolves the compatibility problem by data dependence analy­ sis. It does not address the convergence problem. The SCMR and MCMR models address both the compat­ ibility and convergence problems. The difference be­ tween the two models is that only one context is active at a time for the SCMR model but multiple contexts may be active simultaneously for the MCMR model. A new parallel inference cycle, shown in figure 2, is needed for the RDM, SCMR and MCMR models. It consists of four phases: the match phase, the conflict resolution (CR) phase, the compatibility determination (CD) phase, and the act phase. The RDM, SCMR, and MCMR models follow this new parallel cycle with some modifications, depending on how each handles contexts.

3.1 Data Dependence Model

The rule dependence (RDM) model addresses only the compatibility problem, not the convergence problem.

The data dependence analysis is performed at com­ pile time to construct the parallelism matrix P = (p;i] and the communication matrix C = [ Cij ]. To cap­ ture the maximum parallelism, all four phases of the new parallel inference cycle are parallelized. For the match phase, either parallel shared-memory match al­ gorithm [5] or parallel message-passing algorithm [1] is used, depending on the underlying architecture. At the conflict resolution phase, a dominant rule Rd is se­ lected according to the conflict resolution strategy or at random. At the compatibility determination phase, a compatible set is chosen. Initially the compatible set contains only Rd. For each eligible rule R; , if R; is compatible with all rules in the compatible set ac­ cording to the parallelism matrix P, it is added to the compatible set. This step is repeated until every eli­ gible rule is checked. At the act phase, all the rules in the compatible set are fired concurrently. The data dependence model is similar to the models proposed by Ishida [6], Miranker [9] and Schmolze [11].

Because the RDM model fires rules from differ­ ent contexts concurrently, it may activate incompat­ ible contexts or fire multiple rules simultaneously for sequential contexts. If all contexts are converging con­ texts and are compatible with each other, the RDM model would reach the correct solution and obtain high performance because it captures all the paral­ lelism there is in each cycle. If this is not the case, the RDM model fails .

3.2 SCMR and MCMR Models

The SCMR and MCMR models extend the RDM model and address the convergence problem by divid­ ing contexts into converging and nonconverging con­ texts and analyzing whether two contexts can be ac­ tivated concurrently. For the match phase, the same technology used for the RDM model is used for the SCMR and MCMR models. But unlike the RDM model which performs the conflict resolution, com­ patibility determination and act phases for all rules globally, the SCMR and MCMR models execute these phase for each context individually. In addition, dif­ ferent actions are performed for different types of con­ texts during the conflict resolution, compatibility de­ termination and act phases.

For a converging context, the conflict resolution phase is skipped. For a parallel nonconverging con­ text , the conflict resolution is parallelized by a spe­ cial algorithm. For a sequential context, the conflict resolution is retained. During the compatibility deter­ mination phase, compatible rules are determined by data dependence analysis and fired concurrently for a converging context . For a parallel nonconverging con­ text , a special algorithm is used to determine the set of compatible rules. For a sequential context, the com­ patibility determination phase is skipped. During the act phase, converging and parallel nonconverging con­ texts execute the set of compatible rules concurrently, and the sequential contexts fire the dominant rule se­ lected by the conflict resolution. By allowing compati­ ble contexts to be executed independently, the SCMR and MCMR models avoid unnecessary synchroniza­ tions and improve the available parallelism. The main difference between the SCMR model and the MCMR model is that only one context is active for the SCMR model , but multiple contexts may be active for the MCMR model.

4 Results

Six production programs developed at USC, CMU and Columbia have been simula.ted on the RUBIC simula­ tor using four models: the sequential, RDM, SCMR and MCMR models. The RUBIC simulator is writ­ ten in LISP and currently running on the Sun Spare workstation. By analyzing the simulation results, we can determine the validity of the RDM, SCMR and MCMR models and measure their performance.

Table 4.1lists and describes the six test programs simulated on the RUBIC simulator. The test pro­ grams were first simulated under the sequential model and the sequential simulation results are summarized in Table 4.2. The test programs were then simulated under the RDM model , in which all compatible rules were fired in a production cycle. The RDM simulation results are summarized in Table 4.3. Under the RDM model , production programs Toru-Waltz16, Cafeteria, Snap-2d and Snap-TA reached the correct solutions but Tournament and Hotel failed. The reason that Toru-Waltz16, Cafeteria, Snap-2d and Snap-TA were successful was because they contained only converg­ ing contexts. Tournament and Hotel failed because they contained nonconverging contexts and firing mul­ tiple rules concurrently violating the problem solving strategies. If the SCMR and MCMR models work, then by using a special algorithm to parallelize the nonconverging context in Tournament and executing the nonconverging context in Hotel sequentially, the two test programs should reach the correct solutions. In this way, the validity of the SCMR and MCMR models can be verified.

The test programs have been simulated under the SCMR model and the simulation results are sum­ marized in Table 4.4. All six production programs reached the correct solutions under the SCMR model as expected. By using a special algorithm for the non­ converging context in Tournament, multiple rules were fired concurrently without error and a speedup of 6.21folds was achieved. By firing rules sequentially for the sequential context and concurrently for the converg­ ing contexts for Hotel, a speedup of 8.77-folds was ob­ tained. For Toru-Waltz16, Cafeteria, Snap-2d, and Snap-TA, speedups of 3.06 to 8.94-folds have been obtained. The simulation results indicate that the SCMR model was able to capture a significant amount of available parallelism in production programs and we expected that the MCMR model would give even bet­ ter performances.

The simulation results for the test programs un­ der the MCMR model are summarized in Table 4.5. Like the SCMR model, all six production programs reached the correct solutions under the MCMR model as expected. For Tournament, Toru-Waltz16 and Snap-2d, only one context can be activated at at time. As a result, their MCMR performances were the same as their SCMR performances. For Cafeteria, Snap-TA and Hotel, multiple contexts were activated concur­ rently and they achieved speedups of 6.13, 9.40 and 20.38-folds or 2.00, 1.26 and 2.32-folds better than their SCMR speedups. This indicates that the MCMR model does capture more parallelism than the SCMR model, but the additional speedups obtainable using the MCMR model over the SCMR model depend on the nature of the production programs. To compare the MCMR speedups and the RDM speedups for pro­ duction programs Toru-Waltz, Cafeteria, Snap-2d and Snap-TA is instructive. We see that for these pro­ grams, their MCMR and RDM speedups were the same. This is not surprising since the RDM model also activates multiple contexts and fires multiple rules concurrently like the MCMR model does. The prob­ lem is that sometimes it erroneously activates incom­ patible contexts and fires multiple rules concurrently for sequential context.

1 Snap is a simulator for semantic network array processor under development at USC [10] .

2 N/A =Non-applicable

4.1 Hypercube Performance Results

The MCMR model has been implemented on the In­ tel iPSC/2 hypercube because it provides the highest performance. Only eight nodes can be run concur­ rently due to the large memory requirement of LISP program. We have run two test programs, Cafete­ ria and Hotel, using two static partitioning schemes: partitioning-by-context and round-robin partitioning. When rules are partitioned by context, all rules in the same context are mapped to the same processing node. In round-robin partitioning, rules are allocated to the processing nodes in a circular fashion regardless of the contexts.

Cafeteria and Hotel were able to achieve good speedups when rules are partitioned by contexts. Their performance is shown in Figure 3. Due to the timing limitations of LISP on iPSC/2 only the real time was measured. The simulated speedup for Cafe­ teria is 6.13 and it achieved a speedup of 3.67 for 8 nodes. The simulated speedup for Hotel is 8 (only 8 nodes are available) and it achieved a speedup of 3.79. Since only eight nodes were available, the up­ ward bound for speedup is eight. For this reason, the performances for Cafeteria and Hotel were quite close. But if more nodes were available, we expect the perfor­ mance of Hotel to continue to increase with the num­ ber of the nodes while the performance of Cafeteria would stay the same.

The performance of Cafeteria using the round­ robin partitioning, shown in Figure 4, is disappoint­ ing. However it is important to understand the cause in order to prevent it. The speedups dropped as more processing nodes were added. When rules in the same context are mapped to different nodes, they need to communicate with each other to perform the conflict resolution, the compatibility determination and the RHS actions. As the number of nodes increase, the number of messages increases. This is exactly what happened in the round-robin partitioning. As more nodes were used, the number of messages increased. In fact, the number of messages proliferated and the reduction in computation time was outweighed by the message communication time.

Even though good speedups were obtained by al­ locating rules from a context to the same node, it is not clear whether this is the best partitioning. We intend to study the partitioning problem by developing an al­ location algorithm based on simulated annealing. The allocation algorithm will read in the run-time informa­ tion and use parallelism and communication matrices to estimate the computational and the communication costs for each partitioning. To accomplish this goal, we will also extend the timing functions to provide better run-time information.

5 Conclusion

In this paper, we have present three multiple rule fir­ ing models. The RDM model failed because it viewed a production program only as a collection of rules and did not consider the effect of multiple rule firing has on the problem solving strategy. On the other hand, the SCMR and MCMR models were successful because they addressed the multiple rule firing problems at both levels. Speedups of 3:18 to 8.94-folds were ob­ tained for the test programs under the SCMR model. Speedups of 3.18 to 20.38-folds have been obtained for the MCMR model. The large speedups achieved un­ der the SCMR and the MCMR models indicate that there is considerable amount parallelism in many pro­ duction programs.

The execution of production programs on real parallel machines forces us to address the allocation and message communication problems. Production programs Cafeteria and Hotel have been executed on the Intel iPSC/2 hypercube using two partitioning schemes. When Cafeteria and Hotel are allocated by context, good speedups were obtained, but when Cafe­ teria was allocated in a round-robin fashion, the per­ formance dropped as more nodes were added. We intend to use run-time traces and a simulated an­ nealing method to further study partitioning. The run-time traces will be used to estimate the compu­ tation and the communication costs for different partitions. By comparing the simulated performance with the iPSC/2 performance for different allocations, the partitioning problem will be better understood.