The Search Ahead Conflict Resolution for Parallel Firing of Production Systems

1. Introduction

Forward-chaining production systems are used extensively in artificial intelligence and expert system areas. Many tools for building production systems have been developed, such as OPSS [Forg81] and ORBS [Fick85]. Especially, over the past several years, improvements in the OPS production systems from software approach have brought about substantial speed increase [Forg79][Forg8l][ScLe80][NeMa86]. The speed-up from OPS2 to OPS83 resulted from a number of factors, including changing important data structures, embedding special codes, compiling left-hand sides, etc. OPS83 is at least 120 to 180 times faster than OPS2, and further substantial improvements in software techniques have become difficult to achieve. So a hardware support for OPSS interpreter is essential [FoWe84]. As OPSS is widely used in constructing expert systems, it is taken as a tool to discuss the topics presented in this paper.

A parallel production system machine named DADO [StSh82][StSh83][StMi86] is another architectural approach trying to increase the speed of production systems. The processors in DADO are organized as a binary tree, and the full production rule level parallelism is explored by simultaneous matching of rulesn on the processors dedicated in the rule level. Many algorithms implemented on DADO to improve the speed of matching are proposed in [Stol84][Gupta84]. NON-VON [Hish86] is another example of production machine which is likely to DADO. In addition to the speed-up of rule matching, another speed-up we can obtain is through the parallel firing of production rules, which can reduce the total execution cycles of production systems, and the total speed-up may be the product of these two kinds of profit which will be quite significant.

Although nondeterminism of production rule firing is the major Assume that there are two rule instantiations ri and rj in the conflict set In sequential inference scheme, no matter which rule is selected to fire, working memory C1 will always be removed, and thus causes the other rule instantiation to be removed from the conflict set. This is the effect of rule interference. In addition, rule interference may be indirect. For example, the firing of rule fj may trigger another rule rk· and ~ interferes rule rj· This kind of rule interference is of lev~! 2. Similarly, rule interference may be of level n. On the other way, tf the two rule instantiations are selected to fire simultaneously, then when ri wants to modify c 1 , c 1 may have been removed by rj· This is the problem of data inconsistency.

Now, consider the following three rules q. r2, r3:

With Cl,C2 and C3 are available, Fig! shown below is the search tree of this example. There are totally six sequential firing sequences in this search tree, but all these sequences get the same result (final working memory is (Cl, C2, C3. C4. Cs. C6)) and take three execution cycles. On the other way, if the three rules are fired simultaneously, then the result is also (C1, C2, C3, C4, Cs. C6), taking only one cycle.

So, suppose that a rule firing sequence in sequential inference mechanism is ( fJ, r2, r3, .. , rn), and the last working memory is WM. We develop a new conflict resolution which considers the interefrence relation and parallelism among the rules, such that when it is applied in production systems, the result is also WM but with less execution cycles ( < n).

3. Categories of rule dependency

At first, we define the following important terms and concepts which are essential for rule dependency analysis.

[definition 1]

An Object Pattern OP is an n-tuple with an object body. It has the following general format :

OP(x 1,x2····xn) : object body where OP is the calss-name of this object pattern, and xi is the value of the i'th attribute in OP, and xi must meet some constraint Ci. Object body is an associated list composed of object calss and attribute-value pairs. It has the following format :

(object-class "attr1 value 1 "attr2 valuez .. "attrn valuen) where va/uei can be a constant or a variable with some constraint. Let P(x 1 ,x 2 , .. ,xn) be an object body, then we call P(CJ,C2····cn) is an object instance of P, where Ci is a constant and must meet the constraint of valuei. Its instance body is

(object-class "attr1 c1 "attr2 c2 .. "attrn cn) I(P) denotes the set of all possible object instances of object pattern P.

Condition elements in the LHS or the actions in the RHS of a production rule can both be object patterns. The example below illustrates the terms listed in this definition.

[Example]

Here is an object pattern :

classl(xJ.X2.X3): (class! "atrl 3 "atr2 { <x> <> 2) "atr3 {<>tag)) where x1 is a constant 3, x2 is associated with a numeric constraint (numeric values not equal to 2 ), x3 is associated with a symbol constraint (symbol values not equal to string "tag" ) .

class1(3,1,lin) is an object instance of classl(xl, x2,x3), whose instance body is:

(class! "atrl 3 "atr2 1 "atr3 lin )

[definition 2]

The precondition set PRESETi of a rule i is a set of marked object patterns, ie, the condition elements (positively/negatively referenced) in the left-hand side of rule i. If an object pattern Ci is positively referenced, then it will be marked as +Ci in PRESETi ; if negatively referenced, then marked as -Cj.

[definition 3]

The changed set CHANGEi of a rule i is a set of marked object patterns, ie, the added or deleted object patterns in the right-hand side of rule i. If an object pattern W i is added by a make action, then it will be marked as +Wi in CHANGEi; if deleted by a remove or a modify action, then marked as -Wi·

[definition 4]

Rule ri has interference dependency on rule rj (abbreviated as 1-DEP) iff the set formed by all the negated mstances of the changed set of rule ri and the set formed by all the instances of the precondition set of rule rj are disjoint. That is,

-I(CHANGEi) n I(PRESETj) :z: cp ,

Let IN be the set formed as follows : IN= {pIpE PRESETj, I(p) n -I(CHANGEi) :z: cp

where -I(CHANGEi) means to negate the elements in I(CHANGEi), ie, added( deleted) object pattern will become deleted( added).

If rule ri has interference dependency on rule rj w .r.p to the set IN, then in the i_dependency augmented digraph, there exists one subdigraph shown below :

[definition 5]

Rule ri has input-output dependency on rule rj w.r.p to a set 10 (abbreviated as 10-DEP) iff I(C~�Ei) n I(PRES~_!.i? ~ cp ,

where 10= {pIpE PRESETj, I(p) n I(CHANGEi) :z: cp )

If rule ri has input-output dependency on rule rj w.r.p IO, then in the io dependency augmented digraph, there exists one subdigraph shown below :

[definition 6]

The Following Rule Set of a ruler, Follow(r), is the set of all rules that are reachable from rule r in the io dependency augmented digraph unioned with the ruler itself.

[definition 7]

If rule r E Follow(ri)· then we call rule r is a descendent rule ofri.

[Example]

The contents of rule ri and rj are listed below :

where CJ.C2,C3 are all object patterns listed below:

then

and because

rule ri has IO-DEP on rule rj w.r.t ( C3 ) . This implies that the firing of rule ri may trigger the match work of rule rj by making an object instance of C3 (but not necessarily make the rule rj firable).

rule rj has 1-DEP on rule ri w.r.t ( Cr, -C2 ). This implies that the firing of iule rj may cause the LHS of rule ri unsatisfiable, and thus interferes the firing of rule ri.

Note that 10-DEP impiles an sequential order of execution, that is, if rule q is 10-DEP on rule r2, then the execution order may be (q,r2).

For those rules that may be satisfied simultaneously, they need to be further analyzed to detect possible synchronization.

[definition 8]

Rule ri has interference relation on rule rj (abbreviated as 1-R) if there exists at least one ruler, r E Follow(ri), such that ruler has 1-DEP on rule rj or rule rj has I-DEP on ruler.

If rule ri has 1-R on rule rj· this implies that the firi~g of rule ri may interfere the firing of rule rj> or the fmng of rule rj may mterfere the firing of some descendent ruler of ri.

[Example]

Suppose we have four rules listed below :

Then by the previous definitions, we get a rule dependency graph shown below :

and the 1-R matrix is shown below:

The entry in this matrix is 1 (eg. [ri,rjl = 1) if rule fj has 1-R on rule rj and is 0 if rule ri doesn't has 1-R on rule rj. For example, rule rz has 1-R on rule r3 (because in the following set of rule rz, r4 has 1-DEP on r3), so I_ R [rz,r31= 1.

In this example, suppose we are running the above rules in a sequential inference engine. The firing of rule q causes the rules rz and r3 to be in the conflict set. At this time, if the inference engine selects the rule rz to fire, it will then triggers the firing of rule q , which will interferes the firing of r3. In this case, the firing sequence is q ->rz->q. In another case, after firing r1 , the rule selected to fire may be r3, then rz and finally q. The firing sequence is q ->r3->rz->r4. At run time, if the first case occurs, then rz and r3 can not be fired simultaneously. If the second case occurs, r2 and r3 can be fired simultaneously. This is fully dependent on the selection principle of the sequential inference engine at run time. So, in the next session, we will propose a new conflict resolution principle that considers the characteristics of the sequential inference engine to predict the possible parallel firing at run time.

4. The SACR conflict resoltion principle

In this session, we will propose a new conflict resolution principle that can choose more than one rule to fire. The adventage of this new selection scheme is that for any sequential conflict resolution principle that is based on LIFO (Last-In First-Out) strategy, we can easily expand it to our new one to achieve the goal of parallel firing and get the same result as in the sequential case. For example, one of the conflict resolurion principles of OPS5 is LEX, which is based on the LIFO starategy. As a result, the programs written in original sequential language(eg. OPS5) can now be portable to the new system with SACR conflict resolution principle without further modification.

If the conflict resolution adopted by OPS5 is LEX, then the time recency (represented by time_tag) of the rule instantiations is the major factor when considering the selection of the rules in the conflict set. To fit into the parallel processing model, we first extend the concept of time_tag as follows :

time_tag: major_time_tag . minor_time_tag

where major_time_tag: an ordered number of a rule instantiation in the conflict set, which represents the time recency order of the rule instantiation.

minor_time_tag: an ordered number of a working memory element created in the RHS of aproduction rule.

For example, the time_tag of the frrst working memory element created by a rule whose major_time_tag is 3 will be 3.1.

We assume that initially there is only one rule in the conflict set, which starts the execution of the production system. Let the rule be denoted as INIT_RULE, then we assign 0 to be the major_time_tag assocated with the rule INIT_RULE.

Let the tim_tag, xi·Yi , be the time tag associated with the i'th positive condition element (CE) of rule instantiation r, then we define the parent_time_tag of rule instantiation r as P(r) = x.y, where

That is, x.y is the time_tag with smallest major_time_tag component among all the time_tags of the positive CEs in the LHS of ruler.

We call rule instantiation ri has data dependency on rj if the parent_time_tag associated with rj is just the major_time_tag associated with rule ri . The data dependency means that the firing of rule ri makes rj flfllble immediately. Let P( ri) be the parent_time_tag associated with ri , M( ri ) be the major_time_tag with ri . If P(ri) > P( rj ), then M( ri ) > M( rj ). This implies that if the time recency of ri is more recent than that of r· , then the time recency of the descendent rules of ri is more recent fuan that of the descendent rules of rj_ . This, in terms of sequential search strategy, is the LIFO (or depth frrst) search strategy, in which the events with most recent time tag is searched frrst The basic concepts of our algorithm for conflict resolution to select parallel frrable rules to frre such that the results of parallel firing is the same as the sequential case is : at each conflict resolution cycle, if M(ri) > M( rj ) , this means that in sequential firing, the firing of ri must be ahead of rj . So, if ri has no I_R relation on rj , they are parallel frrable. The marking phase in the step 3 of our algorithm below is just for this purpose. Following is the outline algorithm of our new conflict resolution principle :

Algorithm SACR conflict resolution

Step I : current_major_time_tag : the ordered number of rule instantiations up to now. CS is the current conflict set, suppose there are n rule instantiations in the conflict set, which are sorted in descending order by the value of the parent_time_tag if the rule instantiation is a newly created one, or by the value of the major time tag of the rule instantiation at the last cycle if the rule instantiation is a propagated one from last cycle.

r all the rule instantiations in cs are not marked, but are divided into CSl-1>--· CSz, cs1· CSo as descrived above, while the rule instantiations in CSi are sorted in descending order by the minor_time_tag. *I selected_rule_list = ~ .

Step 2 : Let ro , r1, .... , rn-1. denote the n rule instantiations sorted in CS, then assign (current_major_time_tag+n-i ) to be the major_time_tag of rule instantiation ri.

Step 3 : FOR i = 0 TO n-1 DO

If ( ri is marked) then continue ;

else

FOR j = i+l TO n-1 DO

If ( ri has 1-R on rj ) them mark r· .

ENDofFOR

J

ENDofFOR

Step 4 : Select those rule instantiations not marked into the selected_rule_list

Step 5 : current_major_time_tag = current_major_time_tag + n

To demonstrate our algorithm, let r1 +rz+ r3+r4 denotes the parallel frring of rule rl ,rz, r3 and q. In the example in section 3, after r1 is frred, the contents of the conflict set will be ( r3 , rz } . By step 4 in this algorithm, the original selection principle of OPS5 will select r3 to frre (because the time_tag of C3 is the most recent). At this time, by step 3, we know that r3 doesn't has 1-R on rz, so rz is the next rule instantiation selected to frre. when r3 and rz are frred parallelly, q will be triggered to frre. So the total firing sequence is r1 ->r3+rz ->r4 , taking only three cycles; while the original frring sequence is r1 ->r3 ->rz ->r4, taking 4 cycles.

[Definition 9]

r Let GO be a set of object instantiations. We call GO ->Gl is a derivation step if

for all p E PRESET r ,

if pis marked+ , and there exist one element x of I(p) , such that x E Go , or

if p is marked - , and for all x in I(p) , x is not in G0, And, G1 =Go+ A(r)- D(r) where

A(r) is the set of all object instances added by rule r, and D(r) is the set of all object instances deletedby rule r. And let ILHS(r) be the set of positive marked object instances, then D(r) is a subset of ILHS(r) . And if

We call r1 ->r2 -> ... ->rn is a derivation sequence , which can be denoted by r* , then

[Definition 10]

We call two derivation sequences, q * and r2* are equivalent, if

Theorem 1:

If rule b E Follow(a) , then Follow(b) «;;;; Follow(a).

proof:

Because b E Follow( a), so there eixst in the io dependency augmented digraph a path from rule a to rule b, say path (a,b). And let rb E Follow(b), then there eixst in the io dependency augmented digraph a path from rule b to rule ~· say path (b, rb ) .

So, there eixst in the io dependency augmented digraph a path from rule a to rule rb, which is composed of path (a,b) and path (b, ~).And we get~ E Follow( a), QED .

Theorem 2:

If rule Tj has no 1-R on rj , then 'v' r E Follow(ri), r has no 1-R on rj either.

proof:

· If 3 r E Follow(ri), and r has I-R on rj , then by defmition 6, 3 r' E Follow(r) such that r' has I-DEP on r· orr· has I-DEP on r'. But by theorem I, Follow(r) «;;;; ~ollowiri), and r' E Follow( ri ), then by definition 6, ri has I-Ron rj- This is a contradiction. QED.

Theorem 3:

proof:

Because ri has no I-R on rj, so the firing of ri will not interfere the firing of rj and the firing of rj will not interfere the firing of ri either .

ri rj let Go ->G ->Gt , because ri , rj E CS , so ri and rj is both firable in the context of Go. Then,

G= Go + A(ri) - D(ri),

and D(ri) and ll..HS( rj) are disjoint, so rj is also ftrable in G.

By firing rule rj, we get

G1= G + A(r")- D(r·),

= Go + ACri) - DCri) + A(r") - D(rj)

= Go + ( A(ri) + A(rj)) - (JO(ri) + D(rj))

= Go + A( ri+rj) - D( ri+rj)

r·+r·

G I JG th . . . . . so 0 -> 1 , at Is n ->rJ = n + rJ. By the same way, we can prove rj ->ri = ri + rj. QED.

Theorem 4:

The results of running programs in the new production system inference mechanism with SA C R principle are the same as those running in the original sequential inference mechanism with LIFO strategy.

proof :

We denote a parallel derivation step by ==>. Suppose the parallel derivation sequence is k steps, as shown below :

and the transition state of conflict set is shown as below :

cs 0 -> cs1 -> ... -> csk-I --> cp (we assume that halting of production system is due to the empty of conflict set).

If we can prove that the parallel derivation from CSo is equivalent to the sequential deriv~tion from CSo , then the theorem is proved. At first, let 1 rk denotes the i'th rule instantiation selected at k'th cycle in the parallel derivation sequence ( ie, the rule instantiation whose majo~_time_tag is the i'th largest among the rule in the conflict set); 1 rk * denotes the possible sequential derivation sequence after the firing of rule 1 rt by applying sequential conflict resolution principle, then

• 1). jrk has no I-Ron irk, 'v' j=l , .. , i-1. Clearly, we can see it from step 3 and 4 in the SACR conflict resolution algorithm.
• . ~rk* has no I-Ron irk! 'v' j=l , .. ,i-1. 'v' j=l , .. , i-1, because Jrk has no I-~ on 1 rk, by the~rem 2, all the rule ~nstantiations in Jrk * have no I-R ~n 1 rk, that is, the firing of Jft * will not interefre the C:lring of 1 rk. .
• 3). If the major_time_tag o_f 1 rk is larger than that of Jrk, then the parent_time_tag of 1 rk is larger than or equal to that of jrk. In this algorithm the rule instantiation with higher parent_time_tag will be preferred (step 4 in the algorithm) and assigned higher major~time_tag (step 2 in the algorithm), so the parent_time_tag of 1 rk is larger than or equal to that of
• jlk if the.major_time_tag of ilk is larger than that of jft· . 4). If 1 rk > Jrk ( in relation with major_time_tag), then Jrk has no data dependency (by definition of data dependency) on every rule instance r in irk*. In other words, rule instantiation r is not added to the conflict set by the firing of jrk. . . .
• 5). kl < k2, and 1 rk2 has no I7R on J.rkl an!f Jrkl . has no data dependeJ!CY on 1 ft2· then Jrkl -> 1 rk2 = 1 l}c2 ->Jrkl· This is "!Jecause Jrkl has no data depend~ncy on 1 rk2, By .defnition, Jftl does!l't trigger the firing o.f 1 rk2, so if (Jrkl , 1 fk2) is in ~S. an!f 1 rk2. has no I-Ron Jrkl· by theorem 2, Jrkl -> 1 ft2 = 1 fk2 ->Jft I ·
• 6). Because the sequential inference mechanism is LIFO strategy, the rule instantiation with higher major_time_tag will be executed before those with lower major_time_tag, then,

Now we prove the theorem by induction on cycle numbers. First, without loss of generality, we can assume that the total execution cycles of a program running in the parallel version of production system with SACR conflict resolution principle is k.

a). for cycle number = k, by 6).

• b). for cycle number n = k-1, we want to prove the parallel deriviation step Pk-1 * ==> Pk * is equivilant to the sequential deriviation steps from cycle k-1 to cycle k :

Le~ ift-1 be the rule that has data dependency with 'rt, if ·~-1 exists, tJ:len by 4)., 5), we get (I) is equal to: Irk-!-> .. -> ·rk-1 ->Irk-> ... -> nk-lrk-1 -> 2rk -> ... -;:-nkrk

if 1 rk _1 not exist, then Irk must ~ a rule i':lstance that is passed from C~k-1· so there exist 1 rk-l andJrk-1 such that 1 rk-l > 1rk > Jrk-1 (in relation of major_time_tag), so (I) will become:

And repeating the same process on 2rk, .. nkrb (1) will be 1rk-1 ->1rk-t* ->i1rk ->2rk-1 -> 2rk-1* ->i2rk ... -> nk-1rk-1 -> ~-1l'Jc-1 * where 11 rk, l2rk .. . ,denote the rule instantiations passed from csk-1 to csk and were selected to be fired by the SACR conflict resolution principle.

c). By the same way as b), we can show that for n=k-2,k-3, ... ,1, the parallel deriviation step P n* ==> Pk * is equivilant to the sequential deriviation steps from cycle n to cycle k. QED ·

Fig 4.a and fig 4.b are the firing sequences of a test program running in the sequential OPS5 and in the SACR conflict resolution algorithm respectively. The program contains 23 rules and in nature has some ~egrees of parallelism, which can be shown in the sequential firing graph m fig 4.a. In that figure, there are two cycles at which parallel firing might occur, one is at cycle 3 and the other is at cycle 7. The sequential firing sequence takes 14 steps, but as shown in fig 4.b, the parallel firing sequence takes only 10 steps and the fully parallelism is exploited in this example. From this example, we can make some comments on our conflict resolution algorithm :

I. Detect parallelism at run time. If the programs have high degr~ of parallelism in nature, the parallelism can be detected as early as possible. In worse case, except that the programs are sequential in nature, the parallelism will sooner or later be detected with a little cycle delay, which depends strongly on the nature of the program structure.

2. The information needed for parallelism (ie, the I_R table) can be obtained in polynomial time computation at compile time.

3. The selection phase at run time takes only polynomial time order in size of the conflict set.

5. Conclusions

In this paper, we form the concept of a new kind of parallelism, named search ahead parallelism which is different from AND and OR parallelism, and can be exploited to reduce the execution cycles of production systems. To exploit this kind of parallelism, we need a data dependency analysis of the production rules at compile time to detect the synchronization condition among rules, and we develop a new conflict resolution principle that takes the result of data dependency analysis into consideration to anticipate the rules that can fire parallely at run time. All the work needed (either at compile time or at run time) takes only polynomial time, so the efficiency is acceptable. And the test program shows that a fuil exploitation of the run time parallelism might be achieved.