On Supporting Associative Access and Processing over Dynamic Knowledge Bases

1 Associative Pattern Matching

Associative operations based on pattern matching are fundamental to many artificial intelligence appli­ cations. This paper concentrates on the broad cate­ gory of knowledge-base systems. In such systems rules are activated based on pattern matching as the ordering information- found in procedural (or com­ piled) systems - is not present. When, and how, a par­ ticular fact or rule is to be applied is typically not known until run-time.

A major contributor to this uncertainty lies in the application's interaction with the everyday world. There is also the interaction between rules and, in more complex architectures, b_etween_component rea­ soning systems. In fact it is seen as an advantage to maintain associative access within such complex sys­ tems, rather than 'hard-wired' connections, since it facilitates modularization of the component parts [Reece and Shafer, 1990].

In general, however, this lack of predictability imposes a limit on how many of these associative operations can be optimized away at compile-time. Thus the run-time component will still contain signif­ icant use of associative access to the data structures encoding the knowledge base. Unfortunately such associative operations are computationally expen­ sive. To mitigate this, various compile-time tech­ niques have been developed to translate the knowledge-base data structures into code sequences. These use indexing operations, commonly based on hashing, to handle the associative lookup, e.g. Rete for OPS5 [Forgy, 1982], WAM code for Prolog [War­ ren, 1977], HiPER for embedded knowledge-base sys­ tems [Highland and Iwaskiw, 1989].

As applications and their rules and queries become more complex, so too can the indexing schemes neces­ sary to support the associative access. With simple data structures, finding one or two keywords to index on is fairly straightforward. As the structures and queries become more complex -possibly including the use of variables ('don't cares'), and with any of their elements being potential keywords- then correspond­ ingly complex indexing structures are required (e.g. discrimination nets [Charniak et al., 1980]). Other­ wise a performance hit is taken every time a query does not conform to the chosen indexing scheme. Since the alternative is usually exhaustive linear search, such penalties can be costly.

These indexing schemes have acceptable perfor­ mance when the database is reasonably static. How­ ever the more dynamic the knowledge base used by the application the greater the frequency of index table updates. Furthermore, the more complex the indexing scheme the greater the overhead involved in performing each individual update. Even relatively simple indexing schemes can be rendered impractical when the update rate of the entry indexed upon is too high. In [Stormon, 1989] the example is given of applying complex queries to the value entries of a stocks and commodities database. With this value being up®ted hundreds of times a second it is not practical to index on it, and so answering such que­ ries requires a sequential scan of the database records.

With the intricate indexing schemes necessary to efficiently access complex knowledge bases, even less dynamism can be tolerated. Examples of such appli­ cations include intelligent control or monitoring sys­ tems such as in computer integrated manufacturing (CIM), medical and process monitoring, and autono­ mous vehicle and robot control systems. Typically such applications are required to reason about com­ plex time varying systems - including themselves (e.g. dynamic resource allocation)- and face real-time constraints on the utility of their actions or decisions. The overhead involved in maintaining associative access in such dynamic applications severely impedes the ability of the system to meet its perfor­ mance goals.

Even in systems where there is little pressure from outside events the internal dynamics can be consider­ able. Consider a system that reasons via hypothesis generation and test, or via constructing possible world scenarios. This involves adding new rules to the knowledge base at run-time, and employing them to test their efficacy. These rules may then be modi­ fied, or deleted and new ones added in their place. Maintaining an indexing scheme over such transi­ tory data can entail considerable overhead.

In summary, these characteristics of unpredictabil­ ity and dynamism move the onus of associative com­ putation squarely back into the run-time system, where the associated overhead severely impacts sys­ tem performance. The problem then is to support associative knowledge retrieval when the data struc­ tures encoding that knowledge can be quite complex and dynamic, with minimal overhead devoted to cast­ ing the structures into an efficiently accessible form.

2 Hardware: The Cache Analogy

Run-time being the domain of special purpose hard­ ware, a solution is proposed based on associative memory techniques [Yau and Fung, 1977]. Software indexing schemes and their upkeep are by-passed altogether, and associative hardware is ·used to implement a rapid exhaustive search. The advantage of this approach is that the data structures are dealt with directly, with minimal to no encoding. Such use of associative hardware is not without precedent: consider the ubiquitous cache memory. The same characteristics of unpredictability and dynamism, though in this case of data and its location, gives rise to the requirement for run-time hardware to associa­ tively match on addresses and return the associated data (or a signal that the data is not present - a 'miss').

This paper describes a cache-like system designed to operate with data structured in the form of sym­ bolic expressions. Whilst a conventional cache sup­ ports rapid access based simply on memory addresses; this system has to support complex, non­ predetermined, access to expressions of various lengths and structural complexity. By allowing con­ trol over access and modification of cached expres­ sions some measure of associative processing can be supported. These additional capabilities lead the systern to be configured as a co-processor rather than as a part of the host's memory system. Thus associative operations are off-loaded from the host CPU, just as graphics and floating-point co-processors off-load their particular tasks.

A significant body of work exists relating to hard­ ware associative memories for such applications. Such hardware has typically been based on the tradi­ tional content-addressable memory (CAM) [Kogge et al., 1989; Stormon, 1989; Wade and Sodini, 1989]. By comparison these suffer from restrictions on expres­ sion format, in some cases forcing entire stored expressions to be encoded into fixed length fields. Such approaches also tend to rely on comparators alone for the matching function, which presents prob­ lems when trying to capture the full syntax of sym­ bolic expressions - both stored and used as queries. Lastly the storage organization used in the co-proces­ sor described here permits a significantly increased capacity over CAM-based architectures.

3 The Chameleon Board

Figure 1 shows a photograph of a wire-wrap proto­ type of this associative co-processor. Called the 'Cha­ meleon board' (named after that creature's ability to pattern match with its environment) it is designed to be compatible with commercially available worksta­ tions, plugging in to the system's backplane.

The computational heart of the system is the array of custom 'smart memory' chips called pattern addressable memories (PAM's). These combine mem­ ory for symbol storage with parallel and distributed processing logic. This logic is in the form of process­ ing elements (PE's) replicated through the on-chip storage. The array of PAM chips acts as one combined storage system. All the PE's operate in a SIMD fash­ ion on their respective areas of memory. The op-code and any data for the operation, e.g. match query, are broadcast by a central array controller (located in the center of the board in the photograph).

This 'logic in memory', or 'smart memory', approach has the advantage of not requiring data to be trans­ ferred from storage to a remote - i.e. off-chip -process­ ing site; and thus avoids the ensuing bandwidth limitations. Moreover, since the processing logic is replicated throughout the memory, the resultant par­ allelism gives rise to a very large effective processor bandwidth (each of the current PAM chips has an effective bandwidth in excess of 10Gb/s). This facili­ tates the rapid search of the chip's contents.

The array controller is responsible for maintaining the interface with the host system. It converts instructions from the host to the necessary op-code sequences, mediates data traffic between the array and the host, and controls the PEs' progress over its portion of storage.

A library of C-routines completes the implementa­ tion providing a high-level interface to the Chame­ leon hardware. For example, the instruction insert (expression) takes the expression pointed to by its argument and inserts it into the PAM array. Other instructions are provided for debugging pur­ poses and allow access to the PAM chips', and the controller's, state.

4 Expression Syntax and Storage Format

Before outlining the various functions the Chame­ leon supports, the nature of the expressions stored and matched upon is first described. The symbols that go together to make up expressions are stored as 32-bit words. The most significant four bits denote a particular type, the remaining 28 a name. With the exception of integers, which are passed on unen­ coded, this name is a unique ID generated and main­ tained by the application running on the host. The name field can also be used to hold an integer range. This is encoded using bit-wise don't-cares [Wade and Sodini, 1989] so that, for instance, the quantity '<16' is represented as 'OOOOOOOOOOxxxx'. Each '0', '1' or 'x' requires 2 name bits to encode it.

The symbol types identified by the type tag bits are illustrated in the example expressions of Figure 2 (taken from a simple day-planner database). The syntax is similar to that of Prolog for clauses - con­ sisting essentially of constants, variables and sub­ structure. This covers the requirements of most applications in the domains of interest. If the pattern match operation requires the internal components of sub-structure to be considered in the same pass, rather than just pointer comparisons, then that sub­ structure must be expanded out in place. For exam­ ple the list ( group_mtg Room_303 ) in Figure 2 is rep­ resented by the actual sequence of symbols rather than by a pointer. The 'header' symbol indicates the start of a new expression - somewhat like a functor, though its use is predominantly structural. The list­ variable is a special case of the normal variable, the difference being in what they pattern match with (the pattern matching rules will be described in the next section). Lastly it should be noted that expres­ sions can be of arbitrary length.

The storage within each PAM chip is managed as a stack of symbol-wide slots. This management is inter­ nal to the PAM chip which possesses no address pins in the usual sense, since all access is associative. Expressions are stored one after another as sequences of symbols in the format described. Inser­ tion is performed by the controller enabling a partic­ ular chip and then supplying the expression to be input a symbol at a time, each time along with a 'stack_push' op-code. Included in this on-chip storage management is support for a garbage-collect process which is used to compact deleted expressions out of the stack. Garbage collection takes place in parallel over the array of PAM chips.

5 Chameleon functions

Given a database of expressions stored in the PAM chips the Chameleon board supports the following basic operations: insertion (covered above), pattern match, modification, output and deletion. Pattern matching is the primary mechanism for selecting expressions, or specific slots within them, for subsequent operations. ·

The pattern match is computed on the fly as the query expression is broadcast, as a stream of sym­ bols, to the PAM chips. For each query symbol entered, every PE scans its portion of memory for a match. The progress of this matching during the entry of the query expression is kept track of via 'match tokens' - storage for which is provided along­ side every slot. A match token is only generated at a matching slot when the slot before it · was itself marked previously; the only exception being the ini­ tial match on the header symbol. If the slot does not match, the token disappears. Thus when the query input terminates the only surviving match tokens will flag the ends of responders. This process is illus­ trated in Figure 3.

The rules for the pattern matching of expressions are illustrated in Figure 4 which shows how the three expressions of Figure 2 pattern match with each other. It should be emphasized that one of the strengths of this hardware system is that query and stored expressions can both use the full syntax, so any one of the expressions in Figure 4 could serve as the query. Briefly the pattern matching rules are as follows (using the labels from Figure 4): equal sym­ bols match each other (=). A normal variable will match a constant or another variable (a), or a piece of sub-structure enclosed by parentheses (b). A list­ variable on the other hand will match any sequence of non-header symbols, including none at all (c). The list-variable can be used to represent the cdr of a list. It can also simply be used as a 'don't-care' that stands in for multiple symbols, as in Figure 4.

Once a set of symbols or expressions has been selected by pattern matching, one possible subse­ quent action is to output them to the host. Output is guided by the match tokens: storage is scanned for flagged symbols, or the whole expressions in which they lie. Alternatively flagged symbols can be over­ written (modified) either on a case by case basis, via a read-modify-write sequence (such as in increment­ ing a value), or all together in parallel. The latter is particularly useful as it allows all responders to be recorded within the PAM. If all the expressions are stored with an extra tag word at the end (matched by a variable in the query) then all the responders' tags can be subsequently overwritten with some value denoting their new state.

Finally flagged expressions can be deleted by over­ writing them with a special 'empty' symbol. When necessary the physical space that these deleted expressions occupy can be reclaimed via garbage col­ lection.

The bulk of the logic required to support this func­ tionality is contained in the PE's, one of which is illustrated in Figure 5. The comparator and attached logic ('L' in the diagram) handle most of the pattern matching rules. The 'jump wire' and its associated control logic ('J') is there to handle, for example, vari­ able H sub-structure matches (case (b) in Figure 4). In that case the match token must be effectively jumped from the beginning of a stored sub-structure to its end. This same mechanism is used for scanning the chip for responders during output. Query input and data i/o are handled over the global data bus.

Figure 5 shows only the current slot connected to the PE, as briefly described at the outset each PE actually deals with a small portion of memory. This multiplexing offsets the area penalty due to the com­ plexity of the PE. The current prototype is roughly 50% logic, 50% memory 1 . A consequence of this orga­ nization is that the PAM's memory array is divided into pages, the number of pages being equal to the number of slots attached to a PE. During matching, pages are discarded when they cease to contain match tokens. This reduces the performance impact of multiplexing the PE logic over the memory.

One final hardware mechanism is responsible for generating a cache-like 'miss' signal when the page being processed contains no match tokens. As well as facilitating the page pruning scheme above, this also permits an early response in cases where there are no responders to a query. Conversely, in Section 7 it will also be shown how this signal is used to alert the sys­ tem to the presence of a responder.

1 It is interesting to compare this with commercial RAM's, which are roughly only 60% memory.

In the last three sections a hardware system has been presented that meets the stated requirements. The system supports inserting, deleting, modifying and associative matching on and with complex sym­ bolic expressions, using parallelism to achieve high system performance. The current prototype PAM chip contains 1024 32-bit-symbol-plus-2-bit-status slots and 64 PE's, dividing the storage into 16 pages. The chip has been designed and fabricated using a 1.2!! scalable design rule CMOS process, and has a die size of just 5.4mm x 4.9mm (approximately 140mils x 120mils). Using commercial design rules and die sizes, a PAM with a capacity of 1Mb and 128 PE's is quite practical.

The current PE cycle time is 200ns, this encom­ passes query symbol input, reading the current page, evaluation of the comparators and the jump wire, and the subsequent write back of the new match token state. The prototype Chameleon board con­ tains an array of up to 32 PAM chips. Provisions are made for extending the SIMD operation of the array over multiple boards connected to the same host.

6 An Example: Scheduling in a CIM environment

By way of an example consider part of a simple fac­ tory floor scheduling application controlling mobile palettes. Entries in the database for each palette denote its location/destination, its current state and its contents. Thus the expressions loaded into Cha­ meleon have the following form:

@palette(<#> <dest.> <State> (<list_of_contents>))

@palette ( 1 Bay _14 moving (bifrucated_congle_pins lug_nuts))

Such a database can then be queried with the fol­ lowing expressions:

• @palette ( ?# ?where idle ())
• ... find an empty palette.
• @palette ( ?# Bay _17 ?state ( & lug_nuts & ) )
• ... any lug nuts coming to, or currently at, Bay 17?

Times for the match and read out functions will depend on the number and distribution of partial and full responders through the chips and pages of PAM storage (the palette database is assumed to com­ pletely fill the Chameleon board, corresponding to roughly three to four thousand palettes). Table llists the match and read-out times as a function of the number of responders for these two queries.

Although this is a fairly trivial example it should be noted that the @palette's and the slot values within them can be subject to constant insertion, deletion and modification via simple read/write operations on the PAM's storage. Also the complexity of the query, in terms of variables used, has little affect on the match performance. Using the results above such a scheduling system would be able to sustain inter­ leaved update and query rates of 40,000 expressions per second each.

7 Knowledge Bases and other Application Areas

The above example considered some application que­ rying a dynamic database of facts or events. By add­ ing rules to create a true knowledge base, the foundations are established for a hardware black­ board system. Blackboard systems [Hayes-Roth, 1985] are popular mechanisms for supporting the intelligent control systems described in Section 1. The blackboard provides a central knowledge base shared, transparently, by a number of knowledge sources. It serves to establish the context for knowl­ edge processing actions, provide a repository for hypotheses and control the problem solving process. Knowledge sources are scheduled based on events posted to the blackboard. All of these processes are associative in nature and commonly involve dynamic data.

Typically invocation of knowledge sources is an event-driven process, leading to the concept of asso­ ciative triggering. Other examples can be found in production systems, and interrupt-driven behavior in robot control systems [Reece and Shafer, 1990]. Both require actions to be triggered on complex combina­ tions of events. From the pattern matching system's point of view these triggers form the database against which external events are matched. The match is signalled by the absence of the 'miss' signal. So, for example, "@temperature >400" supports range checking on a temperature value or, referring back to the simple palette example, a trigger could be entered to await a palette becoming empty at a cer­ tain location. It is also possible to look for conjunc­ tions of events posted in any order. The mechanism to support this uses the tag words described earlier. Every sub-clause of the conjunction ends in a tag denoting its state - 'satisfied' or 'not_ satisfied'. This symbol is modified appropriately after each event expression is broadcast. A short sequence of instruc­ tions can then be run to test for conditions that do not contain any 'not_satisfied' symbols. By implementing these triggers in the PAM new conditions can be entered at run-time, and existing ones modified or deleted, all with no associated re-compilation. Full blown Rete-style systems can be implemented by replacing the 'satisfied' tag with an associative pointer to the corresponding beta node, where the join operation is also supported in the PAM (a scheme similar to Kogge et al. [1989]).

Other Chameleon applications include direct sup­ port for declarative languages such as Prolog, where pattern matching constitutes a large part of the fun­ damental execution mechanism [Kogge et al., 1989; Robinson, 1986]. Although compilers exist for such languages, the Chameleon system again provides the capability to handle dynamically created clauses.

Lastly there are fields such as memory-based rea­ soning [Stanfill and Waltz, 1986] and genetic algo­ rithms [Davis, 1987] in which systems attempt to reason or adapt themselves in the absence of rules. Such applications rely almost entirely on pattern matching and appear to be well suited to the capabil­ ities of the Chameleon system.

It should be borne in mind when considering the capacity of Chameleon that, like a cache, it need only be of sufficient size to manage the transitory data in an application, not the entire database. Thus it could be viewed as filling the role of short term memory or as a support for a focus of attention. The end result is a system that allows complex applications to be run faster; or, as a corollary, real-time applications to be more complex.

8 Conclusions

In general, hardware has been perceived as an expensive and unpromising direction - much hoped for functionality being usurped by new compilation techniques. However, as long as there are dynamic and unpredictable environments then associative hardware, such as the Chameleon system, will have a role in meeting system performance needs. The PAM architecture is also poised to take advantage of the trend towards application-specific memories. Yes­ terday's off-the-shelf memories are beginning to be replaced by libraries of off-the-shelf RAM blocks for semi-custom ASIC's.

This paper has described, and demonstrated the applications of, an associative co-processor which in prototype form contains 1Mb of storage. The sub­ system plugs into the backplanes of Hewlett Packard 9000/300 or 400 series workstations and acts as a hardware accelerator for a variety of symbolic pat­ tern matching functions. Currently a PCB version of the board is being constructed so that these proto­ types can be evaluated in a number of applications. As an alternative, a simulator is being completed which will maintain a log file describing execution times given the actual hardware.

Lastly, it is interesting to consider the potential of such a system 'using the 1Mb chips proposed earlier. Coupled with denser (SIMM-style) packaging the same 8" x 11" Chameleon board could have a capacity of 16M bytes and contain 16k PE's. Such a system would have an aggregate processor bandwidth of 5 x 10 12 bits per second (per board).