A Macro Actor/Token Implementation of Production Systems on a Data-Mow Multiprocessor

1. Introduction

A major obstacle in the processing of artificial intelligence applications lies in the large search/match time. In rule-based production systems, for example, it is often the case that the rules and the database needed to represent a particular pro­ duction system in a certain problem domain would be on the order of hundreds to thousands of rules and assertions. It is thus known that simply applying software techniques to the matching process would yield intolerable delays. Indeed, as it has been pointed out [Forgy, 1982], the time taken to match patterns over a set of rules can reach 90% of the total compu­ tation time spent in the processing of expert systems. This need for faster execution of production systems has spurred research in both the software and hardware domains.

From the software perspective, not only the matching step, but also the parallel firing of many productions have been studied. 1be Rete match algorithm has been developed to utilize the temporal redundancy in production systems [Forgy, 1982]. Further optimization of the Rete algorithm has been studied in the TREAT algorithm [Miranker, 1989], which supports the conflict set. Parallelization of the Rete al­ gorithm has been reported to suit the multiprocessor environ­ ment [Tenorio and Moldovan, 1985.

s wor ts support 10 part y t e under Grant No. DE-FG03-87ER25043

From the hardware perspective, many studies have been reported, including shared memory multiprocessors and mes­ sage passing architectures [Gupta and Tambe, 1988]. The performance of the conventional control-flow model of exe­ cution is however limited by the "von Neumann bottleneck" [Backus, 1978]. Indeed, architectures based on this model cannot easily deliver large amounts of parallelism [ Arvind and Iannucci, 1983]. The data-driven model of execution has therefore been proposed as a solution to these problems. The applicability of data-flow principles of execution to matching operations for production systems has been studied in [Gaud­ iot and Sohn, 1990; Gaudiot and Bic, 1991 ].

In this paper, we further explore the applicability of data­ flow principles of execution to production systems. It has been our observation that AI problems exhibit a behavior characteristically different from conventional numeric com­ putations. We demonstrate in this paper that a macro actor/to­ ken approach will best match these characteristics. We shall start our discussion in section 2 by introducing two funda­ mental approaches to AI processing. Section 3 describes those characteristics of production systems from the parallel processing perspective, which we optimize by the utilization of macro data-flow principles. A brief analysis is presented to show why medium grain macro actors are preferred to fme grain micro actors. Section 4 discusses several strategies about how to derive well-formed macro actors from micro ac­ tors for production systems. Section 5 gives simulation re­ sults based on our execution model, the macro data~flow sim­ ulator. Performana: evaluation is also discussed in the sec­ tion. Conclusions as well as future research issues are offered in the last section.

2. Parallel Processing of Production Systems

A production system (PS) consists of a Production Memory (PM), a Working Memory (WM), and an Inference Engine (IE). PM (or rulebase) is composed of productions (or rules), each of which performs predefined actions (right-hand side, RHS) if all the necessary conditions (left-hand side, UIS) are satisfied. The productions operate on WM which is a data­ base of assertions, called Working Memory Elements (WMEs). The inferena: engine repeatedly executes an inference cycle which consists of three steps: pattern matching, conflict resolution, followed by rule firing. The inference en­ gine halts either when no rules can be satisfied or when the solution is found.

From the parallel processing perspective the PS para­ digm can be viewed as a composition of local- and globalla­ teneies. The local latency, t, is the processing time of an in­ ference cycle in the PS paradigm. Each step in the production cycle is considered a local latency, as shown in Fig.1(a). The global latency, T, depicted in Fig.1(a), is the processing time incurred for searching the state space. Given an initial state the inference engine finds the next state by executing an in~ ference cycle. Based on some heuristic control strategies, the system decides which state in the search tree should be ex­ plored. The global latency T is thus linearly proportional to the number of states n to be explored in the search tree.

. Techniques to reduce the global latency Tin the PS par­ adigm can be basically classified into two categories: (1) hardware/software parallel processing, (2) adaptive/ heuris­ tic processing [Wah et al., 1989]. A straightforward tech­ nique would be to use as many ProCessing Elements (PEs) as needed. This would allow all branches to be explored in par­ allel as the search tree grows. This simple hardware approach with an infinite number of PEs can eliminate problems asso­ ciated with backtracking and would hopefully find a solution in a finite amount of time. However, this technique is clearly impractical and too costly since for most AI problems the number of possible states in the search tr:ee would be expo­ nential even for modestly sized problems.

A way of reducing T from the adaptive/heuristic perspec­ tive is to prune unpromising branches in the search tree by de­ riving heuristics at compile time (or learning them at run time) and applying them. This second approach has been in­ vestigated by implementing neural network production sys­ tems [Sohn and Gaudiot, 1990a; 1990b] and will not be con­ sidered here since it is beyond the scope of this paper.

Our approach is centered around the data-flow principles of execution, more specifically, the macro data-flow principles [Gaudiot and Ercegovac, 1985]. As we shall see below, PSs exhibit distinctive characteristics. Indeed, one of the characteristics found in pattern matching is a list processing from which medium grain parallelism can be extracted.

3. Macro Data-flow Principles

A macro actor is a collection of scalar instructions. The ob­ jective behind lumping instructions into one larger unit is to improve performance by exploiting locality within these larg­ er units. Similarly, a macro token is a collection of primitive data tokens. Consider an assertion IS(X Y). This assertion, when implemented, can be represented as a list of three ele­ ments (Is X Y). If we break it into three elements and form three data tokens (Is), (x), and (Y) as basic elements to operate on, each of these three tokens carry little useful information.

When viewed from the architectural perspective, macro actors will substantially reduce the overhead in matching tags of data tokens. When using dynamic data-flow principles [Arvind and Iannucci, 1983], tokens carry tags which consist of the context, code block, or instance of a loop to which the token belongs. If the fact (Is x Y) is split into three data tokens and is compared with another three data tokens (Is), (X), and (z), the tag matching time for three pairs of six data tokens is no less than three time units. However, when the two facts are compared in two lists, the tag matching time is only 1!

Consider a typical match operation, shown in Fig.2, which compares two lists, (a1, ... ,an) and (bl>····bn)· To achieve the maximum parallelism existing in the fine grain micro approach, the n-pairs can be simultaneously compared inn PEs, each of which is connected through a (log n)-dim hypercube. Assume that two neighboring PEs must commu­ nicate through three facilities (two communication nodes and a link) and that each PE consists of four facilities connected in a pipeline fashion. If each facility take 't to execute, the to­ tal time to process n comparisons on n PEs would be

= 4(1 +rlogzml)'t +3rlog2n lt = (4+ 1r1og2n l)'t

where tc=eomparison time, t 1 =addition time, and tr=routing time. Note that in this simple calculation, it is assumed that no token waits in the matching/store unit of each PE. Further­ more, all the comparison actors are ideally allocated to neigh­ boring PEs (which may not be realizable). The total time to compare 2 lists on 1 PE for the macro approach becomes

The ratio of the time taken for macro actors with 1 PE to micro actors with n PEs is

R = tmacro,l/tmicro,a = 4(2n-1 )/( 4+ 1r1og2n 1) = O(n/log2n).

Note that in the micro-actor approach, we assumed that the token routing would be done in 1 step, i.e., 3t. In general, such one-step routing is impractical for a 6-dim hypercube to­ pology. Considering that the average number of elements in a list is five for production systems, the ratio becomes R·5! (logS) ·1.7. The macro actors will outperform since there is no communication overhead involved in macro actors (for details, see [Sohn and Gaudiot, 1991 ]).

There are, however, drawbacks in using macro actors. Putting too many micro actors into a macro actor will de­ crease the degree of parallelism, resulting in some perfor­ mance degradation. Conversely, forming a macro actor with too few micro actors will not give a noticeable improvement in performance. However, the PS paradigm which we are considering for our application domain provides data paral­ lelism which exists in many patterns and WMEs. By putting too many micro actors into a macro actor, the data parallelism will likely diminish. There must be a set of guidance criteria for the formation of macro actors. In the following section, we shall identify several rules from the PS paradigm and es­ tablish criteria to guide the grouping process, thereby produc­ ing efficient and well-formed macro actors.

4. Formation of Macro Actors

4.1. Guidelines for weD-formed macro actors

Let A be a set of micro (or primitive) actors, {a1, ... ,a 8 }, and TA be a set of data tokens, {t1, ... ,tm}, manipulated by A. Let B be a macro actor derived from A such that ~. Let t 1 be the time taken to process a micro actor on a PE. Let t 0 be the time taken to process A on n PEs. Let T1 be the time taken to process a macro actor on a PE. Let r be a ratio of T 1 to t 8 , i.e., r=T11t ·. A macro actor B is said to be well-formed if r<E, Es2.

An objective behind setting such a ratio is in the fact that if the processing time of the macro actor is not more than twice of the processing time for the corresponding micro ac­ tors in an ideal environment, we shall form a macro actor from micro actors. 1be ideal environment refers to the ideal allocation of micro actors on n PEs and ideal routing policy on data tokens. As we discussed earlier in section 3, achiev­ ing such an ideal environment would be impractical. The macro actors would outperform because of no data token routing, no waiting for the mating data token (for two operand instructions), etc. In this paper, we simply set E to 2 for macro actor formation. We now briefly describe the formation of well-formed macro actors (wfms).

Let /1 be a set of tokens input to a1 and 0 1 be a set of to­ kens output from actor a 1 · We denote the dependence relation for a1,ajEA as follows: If O{~Jj such that t,-j, a 1 Laj for all i andj, where Lis a dependence operator which implies that a1 must be executed before aj. By applying the dependence rela­ tion DjLD:J to A, we obtain an ordered set of actors, B={bl, ... ,bm}, where bi={a I DjLD:J is not true}. The depen­ dence distance for b1,bjEB is defmed as d(b1,bj)=~J=i-j. The maximum dependency distance dmax forB is m-1 .

We list below five guidelines for the formation of wfms (the proof of correctness can be found in [Sohn and Gaudiot, 1991]):

1. (Flow Dependency) Let a1 and aj be two actors. A macro actor M={ Dj,aj} tan be defmed if O{dj and ~J=1, where 0 1 is an output of a1, 11 is an input to aj, and ~.j is a de­ pendence distance between a1 and aj.
2. (Encapsulation Effect) Let a be a comparison actor and b be a set of true/false actors {bl' ... ,b 0 }. A macro actor M={a,b} can be defmedif0 1 9bandd 1 b=l. This guide-' line eliminates unnecessary true/false actors.
3. (List Processing) Let A={ a1, ... ,a 0 }, and L be a list of m data tokens {th ... ,tm}· Let l=ItU ... U/ 8 and 0 = 0 1U ... U0 0 · A macro actor M={a1, ... ,a 0 } can be defined if/1WOUL for 1sisn and Okf# for k=dmax· This guide preserves the semantics of a list.
4. (Array Operations) Let A={ a1, ... ,a 0 } and B = { Append, Select, Create, Copy}. IfAnB .. 0, a macro actor M can be formed on A -B. Separating array operations from the macro actors removes the potential bottleneck in array operations.
5. (Interconnection Topology) Let A={ah ... ,a 8 } such that dmax = Max{~j} =1 for all a1,ajEA. Let m be a dimen­ sion of hypercube interconnection network. If msn, a set of macro actors {M1, ... ,Mk} is defined where M 1 ={- al, .... ~}. k= rn/ml, and 1sisk.

4.2. An example on the conversion process

Using these five guidelines, we shall now write several macro actors to implement a simple rule. The functionality of the rule that are important to implement production systems will be taken into account. Consider the following OPS5-like rule:

Rule: [A (Y Z)]

[B (c X) (d Y)]

[C (p 1) (q 2) (r X)] - [Modify B (c Y) (d X)]

;;Condition Element 1

;;Condition Element 2

;;Condition Element 3

;;Action Element 1

Suppa>e that we have a Rete condition-dependency net­ work constructed for the above rule [ Gaudiot and Sohn, 1990]. Fig.3 shows a conversion process for the first condition element. A micro data-flow graph for the comparison op­ erations on two elements, [A (Y Z)] and [A (B C)], is depicted in Fig.3(a) and the corresponding macro actor in Fig.3(b).

Rule Guide3 is applied to this conversion process as fol­ lows: Let A be a set of five actors { a1, ··· ,a5} (three compari­ son actors and two AND actors), andL be a list of six data to­ kens {A,Y,Z,A,B,C}. Let ri be the output token of an actor tlj. Applying a dependency distance to the set A, we partition A into three setsA1oA2, andA3, whereA1={at>~a3},A2={a4}, and A3={a5}. We then find ~ax=2 because Max{dA1,A2, dA1,A3> dA2,A3} = Max{1,2,1} = 2. We also observe that

From (1), we have /{dUO for 1sis5, and 0A3=r5f#. Therefore, Guide3 is satisfied and a· macro actor M = { a1, ... ,a5} can be formed. After Guide5 is applied to the data­ flow graph for the first condition element of the above rule, we obtain a graph shown in Fig.4. Note that for the sake of simplicity, five comparison micro actors of Fig.3(a) have been replaced by a single actor #1, comp, in Fig.4(a).

In Fig.4(a), there are 2 actors related to array operations: 'append' and 'select.' Guide5 states that if there exists an a~ tor ai in A such that aiE{ append,select, ... }, then a macro actor M is considered on the setA-ai. Applying the GuideS to the graph partitions it into 3 sets of micro actors A 1, A2, and A3, where A1={a1, ... ,a12}, A2={a13}, and A3={a14}. In the first step of the conversion process, the set of actors {a1, ... ,a5} however is converted to a macro actor M1. We therefore treat M 1 as a micro actor in the following discussion. Partitioning the graph into three graphs is shown in Fig.4(a).

The last rule we apply to the data-flow graph stems from the fact that there are six true/false actors inA 1 (see Fig.4(a)).

Guide] states that if there is a comparison actor A which im­ mediately affects a set of true/false actors B such that 0 AQB and dA,a=1, then we should form a macro actor M={A,B}.

Let A be a macro comparison actor M 1 defmed in the sec­ ond step and B be a set of true/false actors, {a6, ... ,au}· We observe from the graph that

OA={rs} andla={a,b,c,d,(A,Y,.l),r5} (2) From (2), we have 0 AgB and dA,a=l. Therefore, Guide] is satisfied and a macro actor M = {A,B} = {MI>a6, ··· ,au} = {a1, ... ,au} can be formed. The data-flow graph shown in Fig.4(a) is now completely converted into three macro actors {M1,M2,M3} and one micro actor au, whereM1={a1, ... ,a10}, M2={a12}, andM3={a12}. The three macro actors are shown in Fig.4(b). The conversion process we have demonstrated thus far is for the fll"St condition element. However, the same argument discussed above applies to other condition elements and we shall not discuss it any further. The set of guidelines described above is by no means a complete set. It can, how­ ever, serve as a starting point for the formation of wfms for other applications.

5. Simulation and Performance Evaluation

A simulation has been performed on the Macro Data-Flow Multiprocessor (MDFM) [Yoo and Gaudiot, 1989]. The rnachine contains 64 PEs interconnected by a 6-dim hypercube network. The target production system, which we call a 'ge­ neric production system,' has 15 rules, all of which are writ­ ten in micro actors based on the parallel version of the RETE algorithm [Gaudiot and Sohn, 1990].

A typical OPS5-like rule was shown in the previous sec­ tion. Each rule has on the average 5 condition elements, 2 ac­ tion elements, and 3 two-input nodes. Each condition element has on the average 3 one-input nodes and at least one variable in the value-part (see [Forgy, 1982) for details). With the guidance criteria we developed, the micro actors for the rules are written in macro actors, each of which contains on the av­ erage 50 micro actors.

Tables 1 through 3 show simulation time, network load, and speedup. Table 1lists simulation time units and network load for sequential and parallel distribution of WMEs with various number of PEs. Table 2 derives the ratio of sequential distribution (SD) to parallel distribution (PD). PD of WMEs yields a maximum of 4.4 speedup and reduces a maximum of 2.5 times the network load over SD of the original Rete algo­ rithm. Regardless of the number of PEs used, PD provides an average of 2.5 speedup and reduces the network load on the average 2.4 times. Table 3 shows simulation results on speed­ up of using different number of PEs. Various curves for the simulations results are depicted in Fig.5.

NP& .I.

SD1

PDl SD2

PD2

.1..

.I.

.1..

.I.

.1..

.I.

.1..

1 23619

0 8955

0 23544

0 8912

0

2 13269 9510 4589 4017 12161 9432 4840 3792

4 7239 15738 2614 6901 5873 15078 2895 6406

8 5047 22491 1701 9643 3296 21389 1545 8935

16 3519 26568 1423 11841 2101 26822 1038 11101

32 3336 33364 1314 14157 1434 31991 763 12874

No. of PEs SD1

PD1

SD2

PD2

1

1.00

1.00

1.00

1.00

2

1.78

1.95

1.94

1.84

4

3.26

3.43

4.00

3.08

8

4.68

5.26

7.14

5.77

16

6.71

6.29

11.21

8.59

32

7.08

6.82

16.42

11.68

From the simulation results, we verify that: First, our parallel network with multiple root nodes reported in [Gaud­ iot and Sohri, 1990] gives an impressive improvement over the original sequential RETE network: the number of grou(l'> we had among condition elements of our generic production system is 3. The simulation time of the sequential RETE net­ work, regardless of the number of PEs used, is almost always three times that of our parallel network, as seen from Table 1 and Fig.5(c). Second, the data-flow principles of execution can, not only efficiently perform the symbolic computation, but also yield an impressive performance over the conven­ tional von Neumann model of execution for production sys­ tem processing. From the speedup curve of Fig.5(e), we find that the data-flow principles of execution can indeed yield a 17-fold speedup when 32 PEs are used, regardless of the type of matching algorithms.

6. Conclusions

In this paper, a macro actor approach for AI problems, specif­ ically production systems, has been demonstrated as an effi­ cient implementation tool. Characteristics of production sys­ tems from parallel processing have been discussed to suit the macro data-flow multiprocessor environment. A simple ex­ ample on comparison operations has been explained in detail from the macro perspective. Several guidelines have been demonstrated to form wfms. A condition element of a rule in PSis converted to macro actors. The results of a deterministic simulation with 15 rules with more than 100 condition and action elements on the macro data-flow simulator have re­ vealed that the macro approach is an efficient implementation for the AI production systems. Indeed, the macro approach gives a 17 -fold speedup on 32 PEs. Furthermore, our parallel matching algorithm with multiple root nodes gives an addi­ tional speedup of 3, regardless of the machine used. Assessments of the data-flow systems on productions systems have proven effective and we are currently investigating issues re­ lated to parallel firing of multiple rules toward true parallel production systems.