Street is a recon gurable parallel computer architecture. It executes a production language directly in hardware with the aim of realising advanced cognitive agents in a more energy e cient manner than conventional computers. Street requires frequent communication between many processing elements and to make this communication more energy e cient, a network-based communication platform, StreetNet, is proposed in this paper. It maps the processing elements onto a 2D mesh architecture optimized according to the data dependencies between them. A deadlock-free deterministic routing function is considered for this platform along with the concept of sleep period, analogous to human sleeping, to reorganize the placements of processing elements based on runtime tra c statistics. These mechanisms serve to reduce total network tra c and hence minimise energy consumption.
Street is a recon gurable, at, parallel architecture designed for symbolic
cognitive workloads [
Street executes a parallel production language directly in hardware. This
language, which we call Street Language, is inspired by Forgy's OPS5 [
Street Language
An intelligent system is implemented using a set of production rules written in
Street Language [
A subset of working memory that satis es all of the CEs in a production rule with consistent variable assignments is called an instantiation of the rule. So instantiations of the rule above will be pairs of WMEs in working memory such as: {(pet1 type dog), (pet1 age 8)}. Note that the rst attributes must be
Cognitive architecture
production rules Cognitive Architecture Street language Kernel
Street language so trcud o r P
Network on Chip Working memory distributed among local memories in productors
Street Engine
I/O
the same as they were speci ed by the same variable <p>. The WMEs must join
on any shared variables. The actions of a production rule are performed for each
new instantiation of the rule. An action such as (<p> isOld) adds a WME to
working memory. Actions can also remove WMEs from working memory. This
change in working memory may cause other production rules to instantiate, and
all new instantiations are executed.
The Street architecture consists of a large number of identical and simple
microcoded processing elements (PEs) with a single production rule assigned to
each. A PE contains a controller, a block of content-addressable memories (CAMs)
and an Arithmetic Logic Unit (ALU). The PEs communicate using tokens to
notify each other of changes to working memory. The local memory of a PE stores
just the subset of working memory that may lead to instantiations of its rule.
Each PE matches the associated production rule against its own local memory
with an algorithm similar to TREAT [
StreetNet: The Communication Platform When a PE produces tokens these are transmitted to other PEs and may cause new rule instantiations and yet more tokens. There may be a large amount of token tra c between PEs or small clusters of PEs so e cient data interconnect is
Dest.
Table Productor
Switch required. For a device with a large number of PEs a network based interconnect, named the StreetNet, is proposed in this paper. 3.1
Network Architecture A regular tile-based 2D network architecture is considered for StreetNet. Each tile contains a single PE and router, however adjacent tiles may be linked to share memory resources (discussed below in 3.6). Every PE has a destination table generated from the dependency graph. It lists the desired destinations and corresponding tokens to those destinations. Each router is connected to its local PE and four neighbouring tiles. Each router also has a routing table that is checked for destination. The tokens are broken into packets and forwarded to the neighboring tile towards the destination. A crossbar switch is used as the switching fabric in the router. Fig. 3 shows the structure of a StreetNet. 3.2
Dependency Graph
The mapping of PEs onto network architecture is based on a dependency graph.
A dependency graph is a directed graph, where each vertex pi represents a PE.
Directed arcs represent non-zero communication paths between two PEs and
are assigned a weight characterising the communication rate between the PEs.
Fig. 4 shows an example of a dependency graph of nine PEs. This graph is used
to map the PEs onto the network so that the most dependent PEs are placed
close together in the expectation this will reduce communication latency and
power consumption. The PEs are sorted by total incoming and outgoing tra c
that was recorded during runtime, and mapped in this order. This is useful since
the positions of the PEs with high tra c requirement have higher impact on the
overall energy consumption. This dependency graph is updated during a sleep
period (described in subsection 3.5) depending on runtime tra c statistics.
In [
E = ES + EB + EL
where ES , EB and EL are the energy consumed at the switch, bu er and link.
Since the energy consumed for bu ering is negligible compared to EL [
E = ES + EL Now, if the bit traverses n hops to reach tile tj from tile ti, the average energy consumption is
Eti;tj = n
ES + (n 1)
EL
For a system that involves a large number of processing elements, it is
important to adopt e cient mapping and routing techniques so that total energy
consumption is minimized and communication tra c does not exceed available
bandwidth. Two di erent mapping techniques have been considered in this work:
one is based on Simulated Annealing (SA) and the second is based on
Branchand-bound (BB) technique.
(1)
(2)
(3)
Simulated Annealing based Mapping Simulated Annealing (SA) [
C=new_cost - current_cost; if (random(0,1) exp(- C/current_cost current_temp))
current_cost=new_cost; else g if(toleranceTest(previous_cost,current_cost)kcurrent_temp MIN_TEMPERATURE) done=1; elsef previous_cost=current_cost; current_temp=getNextTemperature(current_temp); g gwhile(!done); a random feasible solution and searches for better solutions with lower cost. This is a greedy algorithm. A tolerance test is done in every iteration to check if the cost is changing insigni cantly over the last few temperatures or the temperature reaches a certain limit. Eventually, when the temperature goes below the minimum limit, it defaults to the greedy algorithm only. Fig. 5 illustrates the SA algorithm for PE mapping.
Branch-and-bound based Mapping In this mapping technique, a search tree is generated that represents the solution space. The root node corresponds to the state where no PEs are mapped. Each internal node represents a partial mapping and each leaf node is a complete mapping of PEs onto tiles. Fig. 6 shows the search tree of the solution space. For example, the node labelled t0tn 1t1:::tn 2 represents the placement in which PEs P0, P1, P2, ... Pn 1 are mapped to tiles t0, tn 1, t1, ... tn 2 respectively.
The branch-and-bound (BB) mapping nds the solution node which has the minimum cost. The cost of mapping is calculated by the total energy consumed by all the PEs that are already mapped. The PEs are initially sorted based on their tra c demand obtained from the dependency graph. As the PEs with higher tra c demands dominate the overall energy consumption, they are mapped rst to the unoccupied tiles to generate new child nodes. Each node has a table that stores the routing paths between its occupied tiles. When a child node is generated, the table from its parent node is inherited, and the routing t0xx...x t1xx...x
tn-1xx...x t0t1x...x t0t2x...x t0tn-1x...x
Internal nodes with partial mapping t0t1t2...tn-1
Leaf nodes t0tn-1t1...tn-2 with complete mapping path to the new tile is added to the table. Then, each of the newly generated child nodes are examined to see if it is possible to generate the best leaf node later. The upper and lower bounds of the nodes are calculated to detect candidate optimal nodes. The upper bound of a node is the value that is no less than the minimum cost of its leaf nodes; the lower bound is de ned as the lowest cost that its descendant leaf nodes can possibly achieve. If the cost or lower bound of a node is higher than the lowest upper bound that is already found so far, it is deleted without any expansion, because it is guranteed that the node cannot lead to the best mapping solution. The lower and upper bounds are updated after every step. All the nodes are traversed this way, and nally the node with minimum cost is accepted as the best mapping. 3.4
Routing
Wormhole routing is considered in this work because of limited bu ering
resources. In wormhole routing, packets are broken down into ow control digits
( its) and the its are routed over the network in a pipelined fashion. The
header it contains routing information and leads the packet to the destination.
Deterministic dimension-ordered routing is chosen in this work. In comparison
to adaptive routing, deterministic routing requires less bu ering space since no
ordering is required for received packets [
Sleep Period
Street stores tra c statistics during runtime which are used periodically to
update the dependency graph. The assignments of rules to PEs and their location
within the network are re ned based on this so that total tra c energy
consumption is minimized. During this period, the execution is paused, analogously
to human sleeping [
Clustered PEs If memory content exceeds the capacity of a PE, the at architecture of Street's tiles allows the PE to use the memory resources of adjacent unused tiles. One of the PEs in the group of tiles acts as a master PE, and the destination table attached to it remains active. This master PE acts as source or destination of packets, the other routers of the cluster are used to forward the packets only. The PEs inside the cluster communicate through a local bus. If there are no unused adjacent tiles, the rule is moved to a new PE with free adjacent tiles and the contents are transferred during a sleep period. 4
StreetNet was tested over network architectures ranging from 4 to 196 processing elements. As we have not yet developed any large-scale agents, dependencies were arti cially created. For every architecture, 10 random dependency sets were generated. Each dependency set was used for mapping using both simulated annealing and branch-and-bound techniques. Fig. 7 shows the total energy consumption comparison between the mapping techniques. This shows that SA based mapping performs slightly better than BB based mapping, but when compared in terms of computation time, the latter signi cantly outperforms the former, as seen in Fig. 8. This indicates that BB mapping works much faster than SA mapping but the energy savings at execution time from the SA mapped solution may warrant the extra mapping time. StreetNet creates routing tables for all the routers as well. Since deterministic dimension-order routing has been considered in this work, routing tables do not change over time. As a result, ordered packet delivery and simplicity are ensured. 5
In this paper, a network-based communication platform, StreetNet, is proposed for the Street cognitive computer in which the PEs are mapped onto a 2D mesh architecture. The mapping is derived from a dependency graph that is obtained from runtime tra c statistics. This work introduces the concept of a periodic sleep period, during which the placement of the PEs is updated to improve overall energy e ciency. Branch-and-bound and simulated annealing based mapping techniques are discussed here. Experiments indicate that branch-andbound mapping signi cantly outperforms simulated annealing based mapping when compared in terms of computation time. Clustered PEs are implemented in this work to accommodate large memories. The number and orientation of 8 12 ) c e (s10 e m iittton 8 a u p 6 m o C 4 2 00
Branch−and−bound Simulated annealing Branch−and−bound Simulated annealing 50
100 StreetNet size 150 200 the tiles of a clustered PE will a ect the overall energy consumption of the system to an extent that is yet to be investigated. Moreover, we plan to implement the mapping algorithm using Street Language so that Street can update PE mapping using its own resources.