The Street Project Home Page

Introduction

The Street project aims to design a new processor and programming language for building cognitive architectures. Our motivation is that the design and implementation of practical artificial intelligence systems can be successfully approached in an abstracted top–down way. Cognitive architectures are an approach to modelling cognition and producing artificial intelligence systems that emphasises such an approach [1].

We call a hardware realisation of the new processor a Street Engine. A Street Engine is programmed in Street Language, a parallel production rule language that does not force any flow control or conflict resolution. Its intent is to address limitations on parallel execution in existing production rule languages currently used in several cognitive architectures [2].

The Street Engine microarchitecture is a fine grained parallel machine to implement Street Language directly. It uses many small processing elements that operate on a global memory. The state of the global memory is distributed throughout the architecture as the internal states of the processing elements. The processing elements are implemented as a flat array of identical tiles and communicate through a network-on-chip layer (the Street Network). This allows the assignment of configuration and function to particular processing elements to be altered before or during run time for optimising or modifying execution. The figure below compares the implementation of a cognitive architecture in a conventional environment to Street.

 

Aims

The principal aim of the project is to investigate how the performance of cognitive architectures can be improved with specialised hardware. We would like to show that the Street architecture is a more suitable platform for cognitive architectures than a conventional computer architecture. We would like to show that this is possible because of a better language design that does not force sequential execution and is supported by dedicated hardware[4][5]. We would like to show that the Street architecture is a good approach because of its scalability and reconfigurability. We would like to demonstrate that not only is higher performance possible, but comparable performance and ability as existing software is possible, with less computational resources, so that Street lends itself well to embedded and real-time applications.

Street Language

A Street Engine has a single global memory called Working Memory (WM) which consists of a set of tuples of primitives (currently either strings or integers). A single tuple is called a Working Memory Element (WME) and can be any length greater than zero. The basic units of the language are the production rules. The production rules define patterns to detect in WM and actions to perform when that pattern is detected. When the pattern is detected in working memory the rule ‘fires’ and the action is executed.

The left hand side (LHS) of a production rule is a set of condition elements (CEs) that specify a pattern to match in working memory. A subset of working memory matches the pattern described by the condition elements if it contains one WME for each CE so that variables in the condition elements can be bound in a consistent way. A subset of working memory that matches a rule’s pattern is called an instantiation. The right hand side (RHS) specifies an action to take for each instance of the pattern that is discovered. The actions allow the addition of new WMEs or the deletion of existing WMEs. An example Street Language production rule is shown below that detects records of objects of ‘type dog’ with an ‘age’ greater than 7 in working memory. When such a pattern is detected a WME is added that records that the dog is old.

/* Street Language consists of production rules */
st {oldDogs
    (<p> type dog)      // a rule may have one or more condition elements
    (<p> age (<a> > 7)) // condition elements are enclosed in brackets
-->
    (<p> isOld)         // then there can be one or more actions
} 

Many production languages operate in a fixed cycle whereby first every instantiation of each rule is found, then a subset of instantiations is selected by some fixed algorithm (conflict resolution), the selected rules’ actions are executed then the cycle repeats[6]. Street does not have a hard coded match, select, act cycle; instead, each rule acts as an individual thread of execution which keeps its own internal representation of working memory and acts accordingly. When a rule fires an action, the working memory changes to be made are distributed to rules that may be affected by the change. If a rule receives changes to working memory that causes a new instance of its LHS pattern to exist in working memory, then its action is executed.

Rules are not evaluated in any fixed order (in principle they are concurrent) and there is no enforced mechanism to select a subset of actions to fire. It is possible to enforce particular sequences or conflict resolution schemes or any combination of different systems by careful partitioning and use of control data structures in working memory.

Many rule based systems use a variations of the Rete Algorithm[7] to perform the matching step. Rete uses the changes to working memory to maintain a large amount of internal data about partial intantiations of each rule. It also allows sharing of this state information between rules. Street uses a variation of the TREAT[8] algorithm, an alternative to Rete, which does not track partial matches.

Microarchitecture

Street Language is designed to run on a specialised machine that provides a direct realisation of the production rules and working memory changes. The system architecture consists of two components: a flat array of tiles each containing a single processing element (PE) with local memory and a network-on-chip, which connects the PEs in a grid topology with one router per PE. The network links between routers are fixed, but each PE is also directly connected to each of its neighbours through a switchable link, as shown below.

The PEs are identical. As shown below, each consists of a controller and a fixed set of content addressable memories. The controller is a finite state machine that implements the matching algorithm and is responsible for transmitting changes to WM and receiving changes from other processing elements. A configuration memory holds the rule’s condition elements and actions.

Each PE implements a single production rule. They store a copy of their relevant subset of WM in their local memory and update it as changes are received from other PEs. If a single PE does not contain enough memory resources to implement a rule, adjacent PEs are linked to share memory. In a set of linked PEs, only one controller is active and it makes use of the memories of all PEs in the set.

Each PE has an associated router and destination table. Active controllers send and recive changes to working memory through their associated router. Before run time, rules are allocated to PEs or linked sets of PEs. The dependencies between rules are used to fill each PE’s destination table so that every working memory change transmitted is only routed to destination PEs that store a matching subset of WM.

Rules that could effect each other's internal working memory state should be placed close together, where as rules that operate on completely different partitions of WM can be placed far apart. Initially rules are assigned to PEs by looking at the dependencies between their actions and condition elements. This shows when the firing of one will change the internal state of the other, but does not say how important that dependency actually is during run time.

Since the PEs are identical, runtime statistics can be used to optimise the assignment of rules to PEs. The initial configuration can be altered either during run time or special sleep or idle periods. Reconfiguration can also occur when we want to change the production rules during run time. Many cognitive architectures have a learning mechanism that operates by adding new rules[9][10]. Reconfiguration (again either during runtime or a sleep period) allows new rules to be added and their assignment to PEs to be optimised.

Why Street?

Street draws upon Rete and TREAT and our investigation into hardware for artificial intelligence was inspired by the work of John Laird and the Soar Group at the University of Michigan, where the Soar cognitive architecture has been in development for over 30 years[3].

Links and Downloads

Publications

News Items and Presentations

Personnel and Contacts

Key References

  1. John E Laird. The Soar Cognitive Architecture. The MIT Press, 2012.
  2. Steve Kuo and Dan Moldovan. The state of the art in parallel production systems. Journal of Parallel and Distributed Computing, 15(1):1–26, 1992.
  3. John E Laird, Allen Newell, and Paul S Rosenbloom. Soar: An architecture for general intelligence. Artificial Intelligence, 33(1):1–64, 1987.
  4. L Kanal, V Kumar, H Kitano, C Suttner, Jos’e Nelson Amaral, and Joydeep Ghosh. Speeding up production systems: From concurrent matching to parallel rule firing. 1993.
  5. Salvatore J Stolfo, Ouri Wolfson, Philip K Chan, Hasanat M Dewan, Leland Woodbury, Jason S Glazier, and David A Ohsie. Parulel: Parallel rule processing using meta-rules for redaction. Journal of Parallel and Distributed Computing, 13(4):366–382, 1991.
  6. Anoop Gupta. Parallelism in production systems. Morgan Kaufmann, 1987.
  7. Charles L Forgy. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artificial intelligence, 19(1):17–37, 1982.
  8. Daniel P Miranker. TREAT: A better match algorithm for AI production systems; long version. University of Texas at Austin, 1987.
  9. Niels A Taatgen. Learning rules and productions. Encyclopedia of cognitive science, 2003.
  10. John E Laird, Paul S Rosenbloom, and Allen Newell. Chunking in SOAR: The anatomy of a general learning mechanism. Machine Learning, 1(1):11–46, 1986.