An Evaluation of DRete on CUPlD for OPSS Matching

1. Introduction

With the increasing use of production systems, there is growing interest in improving their execution speed. A number of researchers are working toward this goal, some concentrating on customized uniprocessor designs[Quin85,Lehr86] and others on multiprocessor architectures[Hill84,Stol84,Ramn86,Gupt87 ,Oshi87].

The work reported here involves the CUPID[Kell87] multiprocessor architecture running a distributed matching algorithm, DRete[Kell87b]. DRete and CUPID were designed in tandem, each tak­ ing advantage of characteristics of the other to ensure optimum performance from the union of the two. DRete is based on the Rete[Forg82] algorithm, a many-pattern/many-object matching algorithm designed for the OPS family of production languages running on a uniprocessor. The performance of CUPID executing DRete has been assessed with respect to expected performance and theoretical limitation,and using a test simulation. The simulated program is the Monkey and Bananas problem. It was chosen because it has been used in the past to grade the performance of several machines, although it does not contain a high potential for parallelism. The OPS program used is shown as an example in the OPS83 User's Guide[Forg85] . As a basis for comparison, this program was also run on a VAX 11/785 using a stan­ dard OPS83 compiler.

The next section contains a brief review of pro­ duction languages, the OPS family in particular, and the Rete matching algorithm. The following two sec­ tions describe the DRete algorithm and the CUPID architecture. Sections 5 and 6 give details of the simu­ lator and the simulation results and section 7 is a dis­ cussion of these results and their implications.

2. OPS Production Languages and Rete Matching

A production system consists of three parts: 1) a set of rules, or productions, defining available operations on a problem state, 2) a set of data elements,or working memory, which describe the current problem state, and 3) a control mechanism which applies the rules to the data elements. Each rule is made up of a condi­ tion portion, describing the situation it applies to, and an action portion, describing operations to be per­ formed on the data.

It is the responsibility of the control mechanism to determine which rules apply at a particular time by matching the data elements to the rule conditions. From the result of the match - the conflict set - the most appropriate rule is selected - conflict resolution - and fired. Firing a rule changes the data, which invalidates the match. The match must be recom­ puted before another rule can be selected and so exe­ cution proceeds in a cycle of match, conflict resolution and rule firing phases.

or the three phases described, the match phase is by far the most computationally expensive[Forg84]. The Rete algorithm reduces the actual number of match operations done by taking advantage of similar­ ities among rule conditions, and the fact that each rule firing generally changes only a small portion of the data set.

Employing the Rete algorithm means compiling the rule conditions into a network of interconnected condition and memory nodes. Condition nodes may have one input for constant value tests, or two inputs to join data elements, subject to consistent variable bindings. Tokens representing changes to the problem state caused by firing a rule are injected into the top of this network. Memory nodes store partial match information for use in subsequent comparisons.

Using the Rete algorithm, the match phase becomes a large set of node activations. At the node level, activation results from the arrival of a token representing one or more data elements on an input arc . A one-input node may or may not pass a token to the next level of nodes depending on the result of the constant comparison. A memory node stores an incoming token and indicates its arrival to the two­ input node it is connected to on the next level in the network. A two-input node tests variable bindings between a newly arrived token and each of the tokens stored in the memory node above it on the opposite side. For each successful comparison, a new token will be sent further down into the network. Tokens emerging from the bottom of the network represent fully enabled rules.

3. The DRete Matching Algorithm

The DRete matching algorithm is a distributed version of the Rete algorithm. In DRete the match phase is partitioned at the token-to-token comparison level. The motivation for this method of partitioning, and the expected performance of the resulting algorithm are derived from the data contained in [Gupt83] and [Gupt87b]. This work is an analysis of a number of well known production systems of various sizes. The characteristics of these programs related to communi­ cation requirements, and the quantity of data flowing in the match phase are shown in Table 1. The differ­ ences between average and maximum values in this table reflect the variability in execution characteristics typical of production systems.

DRete is designed to meet the requirements of the average data with the flexibility to manage the maximums. (These data, and the form of DRete, guided the design decisions in the development of the CUPID architecture.)

In DRete, partitioning of one-input nodes is not necessary since their activations do not involve any stored data. The partitioning is done at the two-input nodes where approximately 80% of the match phase time is spent. This partitioning is carried out in two stages. The first step is to isolate the two-input nodes from each other by providing separate memory nodes for each input they are attached to, as shown in Fig­ ure 1.

Each two-input node with its two memory nodes is now an independent process with three ports. In the second partitioning step, the two-input nodes are repli­ cated; the number of replicated copies is equal to the number of tokens stored at the two memory nodes connected to it. In this way, each copy of a two-input node is associated with only one data token - either a left or a right token. One node copy on each side is designated the generative copy; it is responsible for storing new tokens. An example of this is shown in Figure 2.

G®

Figure 2: Comparison Node Replication

It is important to note that the size of the image of a two-input node is directly dependent on the amount of data associated with it. Thus, the level of parallelism associated with a node activation is deter­ mined by the amount of data it must process.

The node copies are numbered as consecutive pairs; the left side is even-numbered and the right side is odd-numbered. This numbering scheme makes it easy to activate both sides of a node from a single des­ tination address, while allowing for a distinction of which side of the node the node copy represents and to which side the token is arriving.

The operation of the node copies for an AND node is as follows:

1) A positive or negative token arriving at a node copy on the opposite side to its stored token per­ forms a token comparison (if required) between the arriving and stored tokens. It passes a token of the same polarity further into the network if the com­ parison is successful.

1. A positive token arriving at a node copy on the same side as the stored token will cause the gen­ eration of a duplicate node copy with the arriving token attached, if the node copy activated is genera­ tive. The generative quality of the activated node copy is then passed to the new node copy. IC the node copy activated is not generative, the arriving token is ignored.

3) A negative token arriving at a node copy on the same side as the stored token will cause the dele­ tion of that node copy if it is not generative, or the deletion of only its stored token if the node copy is generative. The negative token will be retransmitted if the node copy had been activated (not necessarily successfully) by a positive token from the opposite side earlier in the same match phase. This second function is performed to insure the correct formation of conju­ gate pairs by the node as a whole.

For a NOT node, the activity is similar to that described above for the AND node (which keeps node interpretation code to a minimum), but a different node formation is used; it is a two-level structure involving three different types of node copy is used. In the top level, the left node copies (the positive side of the node) store tokens and the right side stores nothing. In the bottom level, only the right node copies, which store tokens potentially blocking the pas­ sage of left-side tokens, exist. In a NOT node, the retransmission of negative tokens as described above is not used. Instead, the bottom node copies are put in the path of tokens generated by the top portion of the node. The function of the bottom node copies is to transmit tokens cancelling positive ones sent by the top portion of the node, if data exists which makes the positive tokens invalid.

With two-input nodes partitioned as described, the storing of an arriving token and the comparison of this token with each opposite-side stored token can all be done in parallel.

The level of parallelism available in the match phase as a whole using DRete is related to the product of the number of nodes activated and the number of tokens at each node - with an adjustment for the serial nature of some operations. It is approximately 300, without hashing of tokens, as discussed in [Kell87b]. The effect of hashing is to reduce this number, but it provides an overall advantage in execu­ tion characteristics, as described in the next sub­ section.

An important consideration in distributing the match operation is how to balance the workload over a set of processing elements. In DRete, node/token pairs are continually being produced and eliminated as new match state is computed. A dynamic load balancing algorithm[Kell87b] is used to move new node/token pairs away from the processing elements that created them. This increases the probability that node copies activated at the same time are processed in different places.

Recall that new node copies, which are gen­ erated during a match phase, are completely indepen­ dent of each other and their generators. Load balanc­ ing, which is done while the host performs the conflict resolution and act phases of the production cycle, con­ sists of transfering the new node copies to other (nearby) processing elements in the multiprocessing environment. Since the generative attribute of a node copy is given to a new node copy before it is transfered to a new processing element, the source of new node copies is not fixed at one processing element.

The load balancing scheme described above was chosen for its effectiveness but also because it is very simple to execute. A more complex load balancing scheme could be too time consuming and so reduce the value of speeding the match phase itself. The simula­ tions revealed that the amount of time spent in the load balancing phases of operation is never greater than 49% of the match time. Since the load balancing phases occur between match phases, overlapping con­ flict resolution and act phases, they have no serious effect on overall execution speed.

The replication of node and token information and the demands of the load balancing algorithm make a concise encoding of this information very important. The size of a node copy is minimized by storing it as a template to be interpreted by a matching processor. The amount of token information stored is minimized by keeping only those values that are required for matching further down in the network. (For the two program simulated, the average node size is 11.9 16-bit words; the average token size is 6.6 16-bit words. In contrast, the compiled OPS83 versions of this program uses about 250 bytes to encode each comparison node because it generates inline code instead of templates to increase execution speed.)

3.1. DRete and Hashing

Recent research has shown that the number of comparisons between tokens that are necessary during a match phase can be reduced using hashing of tokens[Gupt87b]. Using this method of token parti­ tioning, a node's (node copy's) responsibility during a match phase is reduced from a case where it compares all incoming tokens to all stored tokens to a case where one hash bucket of tokens is compared with a corresponding hash bucket of tokens on the opposite side. (The responsibility Cor storing tokens is similarly divided.) Comparing an incoming token to only a frac­ tion of the corresponding tokens on the opposite side of the node both reduces the comparisons required and, very importantly, reduces the number of com­ parisons involved in a single node copy activation. Hashing, however, cannot be used in all cases of two­ input node types and cannot always be done in a way which results in equally sized buckets for all data cases.

Using DRete to parallelize the match operation reduces the number of token-token comparisons done during a single node copy activation to one. Over an entire match phase, a node copy's responsibility is to compare all incoming tokens to one stored token. Hashing does not increase a node copy's activation expense significantly, and can be added to DRete at very little increase in storage expense since the size of a node's image is already dependent on the number of tokens with which it is associated. With a combina­ tion of DRete and hashing, a node copy's responsibility during a match phase is reduced to matching one hash bucket of tokens to only one ·other token. Overall, the level of parallelism in DRete is reduced from the 300 previously mentioned, but the net effect is a beneficial one.

DRete with token hashing is potentially much faster than either concept applied alone since it both reduces the total number of comparisons done, and exploits the greatest degree of parallelism available. The work done with DRete to date does not include hashing, but preparations are being made to explore this very promising alternative.

4. The CUPID Architecture

CUPID is a matching processor attached to a host. The host executes the conflict resolution phase of the production cycle and fires the chosen rules. In firing a rule, the host sends changes to the current data set to CUPID. As the new match state is computed, CUPID responds with corresponding changes to the conflict set.

The CUPID architecture is comprised of a large set of small processing elements connected by two independent communication schemes. The number of processing elements in the set is in the order of hun­ dreds to take advantage of the expected level of paral­ lelism available in large programs. The processing ele­ ments are arranged as a single two dimensional array, with all node information distributed evenly among them.

One of CUPID's communication systems consists of a pair of unidirectional trees with the processing ele­ ments at the leaf positions in both trees. One of these trees is used to broadcast match information to all processing elements over parallel paths. This high speed path ensures fast activation of all network nodes by new match information. The second tree collects the responses of the processing elements to incoming match information. The data path width in this tree widens from serial at the processing element to word­ width at the root of the tree to accommodate the expected volumes of data at each level in the tree. Responses which represent data movement within the network of comparison nodes are fed back into the processing elements via a path between the roots of the collection and broadcast trees. Responses representing changes to the set of enabled rules are removed from this stream and sent to a host processor, which awaits such responses from the match phase.

The second communication system is a set of serial links connecting each processing element with its four nearest neighbours. These links support the dynamic load balancing algorithm, carrying node/token pairs from those processing elements that have produced them to less busy processing elements during the inter-match phase interval. Local links are used Cor this purpose because they match the nature of the transfers: Node copies need not travel further than a nearest neighour and have only one destination. The destination of a node copy is not predetermined; it can be seated and processed anywhere in the processing element array.

Figure 3 is a diagram of the CUPID architecture with a four-by-four array of processing elements. The broadcast tree is shown branching down to the top of each processing element, and the collection tree branching down from the bottom of each processing element. The local interconnect system is also shown, except - for clarity - the links joining opposing edges of the array.

A CUPID processing element consists of a set of functional blocks which combine to satisfy all of the computational requirements of the match operation. Each processing element contains a CPU and local program ROM for interpreting node activations and performing both local and global memory management

• A- Filter /Interface Node
• B- Broadcast Tree
• C- PE Array and Local Network
• D - Collection Tree

Figure 3: The CUPID Architecture

4.1. The CUPID Processing Element

functions, a local RAM area to store node/token pairs, and a CAM block with entries indicating which nodes from the original network are represented at this pro­ cessing element. A processing element also contains a set of state machines for handling data transfers over the various communication ports. One state machine conditionally stores information reaching the process­ ing element from the broadcast tree in RAM. The decision to store or ignore arriving match information is based on the CAM contents. An output state machine is used by the CPU to transfer the results of node activations onto the collection tree. From there, data is distributed to either the host, the processing element array via the broadcast tree, or both. A set of five state machines handle incoming and outgoing node copy transfers over the local links. Interactions between these state machines and the CPU are managed by an interrupt protocol.

A complete design of the CPU and ROM por­ tion of the processing element has been done using an NCR two micron CMOS standard cell library. Prelim­ inary designs of the individual communication state machines have also been done.

The processor[Bond88] is a three stage pipeline Harvard architecture design with a 16-bit wide data path. It is a RISC processor, satisfying the relatively simple processing requirements of the match operation, and the need for a compact design. It supports two levels of interruption - required by the communica­ tion mechanisms - and two special instructions. One of these instructions is a variable condition branch instruction used in place of a sequence of fixed condi­ tion branches. This instruction benefits pipeline operation by reducing the number of branches exe­ cuted. The second special instruction is included to assist in traversing the linked list structure used in storing node/token pairs in RAM. The increased com­ plexity of the processor caused by including these instructions is offset by a reduction in code size, result­ ing in an overall reduction in the size of a processing element. The CPU design required 1500 cells; the pro­ cessing element minus memories is comparable in com­ plexity to a commercial 8-bit microprocessor.

Prefabrication simulations of the CPU show a peak execution rate of 8.3 mips. Dynamic measure­ ments of instruction frequency from simulations of CUPID running DRete were used to determine memory reference frequency and branching charac­ teristics during matching. It is estimated that the CPU will execute the required software at 6.7 mips.

4.2. VAX 11/785 Mips

In order to compare CUPID results with those obtained on a VAX.. 11/785, it is necessary to establish the relative power of their respective processing units. As stated above, the CUPID CPU executes the DRete code at 6.7 mips. To normalize this to the VAX.. CPU speed, measurements were taken of the VAX.. running instructions corresponding to those in the instruction set of the CUPID CPU. The speed of the VAX.. exe­ cuting each of these instructions is combined with the frequency of their occurrence in the CUPID processing element code to establish a speed for a VAX.. 11/785 running CUPID software. Table 2 shows the execution speeds for four classes of instructions on the VAX.. and their relative frequencies in CUPID software. Instruc­ tions were run as part of a long stream to ensure that the processor pipeline was full during their execution, except, of course, for the case of the successful branch. (The memory access instruction speed was calculated by multiplying the speed of a memory update on the VAX.. by the equivalent number of instructions for a CUPID CPU performing the same function.)

From this data it is calculated that the VAX 11/785 would execute CUPID software at 2.7 mips. This is higher than the 1.5 mips rating for the machine and results from the· elimination of complex

5. The Simulator

The simulator was written using N .2[Endo87], a com­ mercially available package. Register transfer level simulations of CUPID running DRete have been done to establish a coherent software structure for a pro­ cessing element. This includes both the match and load balancing algorithms as well as memory manage­ ment for all state machines. The results of these simu­ lations were important in terms of verifying the basic DRete and CUPID concepts, but are too time consum­ ing to run all but the simplest of tests. The hierarchi­ cal nature of the simulator made it possible to move to a higher level of simulation using process times and communication timing information from the original simulator. This allows the simulation of larger test programs on arrays of 1-64 processing elements. The accuracy of the higher level simulator was verified by comparing its responses to those obtained from the lower level simulations. The higher level simulator was tuned to agree with the lower level simulator to within 1-2% between individual responses, and to within 0.2% over long (mixed) strings of process activations.

It is by incorporating , timing values from the standard cell implementation of the processing element's components into the simulator that a direct comparison of CUPID execution time to that obtained on a standard commercial machine, in this case a VAX 11/785 running compiled OPS83, was possible.

In the simulations, only the match phase is simu­ lated; a dummy process is used in place of the host processor to interact with the processing element array. Changes to working memory caused by rule fir­ ings are presented to the processing element array in the order established by running the OPS83 version of the same program.

6. Simulation Results

The Monkey and Bananas benchmark executes in 117 mS on a VAX 11/785 with all output disabled. Estimating the match phase as 80% of this execution time[Forg84], it takes 94 mS.

Table 3 shows the match execution times for the Monkey and Bananas program on the VAX and on CUPID for array sizes of 1-64 processing elements. Below these are the speedup factors of CUPID over the VAX. The next line in the table shows the estimated match time of CUPID with a CPU normal­ ized to the speed of a VAX. (This normalization does not take into account that communication time becomes less of a factor in the total match time as processor speed decreases.) The next line in the table shows the speedup obtained over the VAX on the nor­ malized CUPID.

Because processor speed will continue to increase as technology advances, it is a matter or theoretical interest to calculate the potential speed of CUPID as its CPU clock speed approaches infinity. Speed is then determined by the effectiveness of the communication system and the quantity of data which must be exchanged between processing elements. The numbers for the speed of CUPID in this limiting case are shown at the bottom of Table 3; they were calcu­ lated assuming that the communication clock remains at 10 :MHz (although this too will increase with time) but that serial paths are widened to word width.

7. Conclusions

The CUPID matching time with one processing ele­ ment, from Table 3, shows that the CUPID processing element can execute the operations required by the match phase very effectively. This contrasts with other research efforts where a parallel algorithm sub­ stantially reduces match speed for the uniprocessor case. The speed of a single processing element is mul­ tiplied by the effect of using greater numbers of these processing elements in the CUPID array.

It should be noted that the Monkey and Bana­ nas problem does not contain a high degree of parallel­ ism and, in fact, is fairly sequential in nature. The diminishing returns from increasing the CUPID array size to 64 processing elements is an indication that the limit of parallelism is being reached. Further simula­ tions are under way, using programs which contain higher potentials for parallel execution, to better show the ability of the DRete/CUPID combination to speed match execution.

An 23 fold increase in speed is observed in the eight-by-eight processing element array for the Mon­ key and Bananas program despite the low availability of parallelism. This verifies that a fairly simple pro­ cessing element implemented in a modest technology can provide sufficient processing power for production system matching. At the same time, it verifies that the DRete and load balancing algorithms do not intro­ duce an inordinate amount of overhead into the match operation.

The increase in match execution speed provided by the DRete/CUPID combination results in a sub­ stantial increase in the overall production system exe­ cution speed. Executing the match phase on a compu­ tational element separate from the one executing the conflict resolution phase (the host) has the added advantage that conflict resolution can be performed partially in parallel with the match phase. Responses from the match phase can be incorporated into the conflict resolution calculation as they arrive throughout the match phase. The result of this is that the match phase still remains the dominant factor in production system execution time and so increasing its speed further merits additional effort.