10-11-2012, 02:35 PM
Embedded Transitive Closure Network for Runtime Deadlock Detection in Networks-on-Chip
[attachment=38942]
INTRODUCTION
NETWORKS-ON-CHIP (NoCs) emerged as an on-chip communication
architectural paradigm that applies networking
theory and methods to VLSI systems
incorporated on a single silicon chip [1]. Such an
architecture consists of a network constructed from multiple
point-to-point data links, namely channels, interconnected
by routers. The routers are connected to a set of
distributed Intellectual Properties cores (IPs). Communication
among these distributed IPs usually utilizes a packetswitching
method where messages are divided into
suitably sized blocks, called packets and flits. The packets
can be relayed from any source-destination communication
pairs over several data links, by making routing
decisions at routers. NoCs bring remarkable improvement
in performance, flexibility, scalability, and power efficiency
over conventional bus interconnections. However, in NoCs
communication deadlocks may appear and cause an
impasse in the network, and hence lead to performance
degradation or system failure.
Generalities on Deadlock
A deadlock is a situation in NoCs wherein two or more
packets are waiting for one another to release channels, and
are unable to make progress. The network is deadlocked if a
chain of waiting packets forms a cycle. As a simple
deadlock example, consider the dependency cycle of four
packets shown in Fig. 1. Each of the four packets in the
figure holds some channels but it cannot proceed further
until it acquires another channel currently held by one of
the rest of the packets. However, no packet can release the
channel needed by another until it acquires its own
requested channel. The packets are deadlocked and will
remain in this state halting all the occupied channels until
some intervention brings them back to life by breaking the
dependency cycle. Deadlocks can paralyze network communications
by halting the resources occupied by the
deadlocked packets which in return could increase other
packets blocking [2]. Hence, it is crucial to remove deadlocks.
There are two strategies to deal with deadlocks:
avoidance and recovery [3], [4].
METHODOLOGY
Background and Assumptions
The network of concern in this work is a collection of router
nodes connected by channels. Each router is connected to a
single IP core that can inject/consume packets via the
router. A fully adaptive routing algorithm with minimal
paths is used. A wormhole flow control technique [16] is
employed which has been widely used in NoCs. The
packets in wormhole flow control are divided into smaller
flits. A header flit is routed first and the rest will follow it in
a pipeline manner and that will allow a packet to occupy
several channels simultaneously. Thus, wormhole reduces
the number of buffers required in each router which is a
desirable feature for NoCs. However, wormhole makes
networks more prone to blocking and deadlock [2], [17].
In line with existing work on deadlock recovery [6], [9],
[10], [13], we assume that a channel buffer cannot contain
flits belonging to different packets and a packet arriving at
its destination is eventually consumed.
TCNETWORK ARCHITECTURE
TC Computation with TC Networks
Dynamic programming (DP) can yield the solution for the
transitive closure [18]. DP provides an opportunity for
solving the computation using a parallel architecture with
improved computation performance. Mapping TC computation
to a parallel computational platform can be achieved
with the introduction of a DP-network. The network has a
parallel architecture, and can be used to compute the TC
solution through the simultaneous propagation of successive
inferences. Lam and Tong [21] introduced DP-networks
to solve a set of graph optimization problems with
an asynchronous and continuous-time computational
framework. This new class of inference networks is
inherently stable in all cases and has been shown to be
robust with an arbitrarily fast convergence rate [21]. A
parallel computational network for solving the dynamic
routing problem for NoCs is also proposed in [22].
[attachment=38942]
INTRODUCTION
NETWORKS-ON-CHIP (NoCs) emerged as an on-chip communication
architectural paradigm that applies networking
theory and methods to VLSI systems
incorporated on a single silicon chip [1]. Such an
architecture consists of a network constructed from multiple
point-to-point data links, namely channels, interconnected
by routers. The routers are connected to a set of
distributed Intellectual Properties cores (IPs). Communication
among these distributed IPs usually utilizes a packetswitching
method where messages are divided into
suitably sized blocks, called packets and flits. The packets
can be relayed from any source-destination communication
pairs over several data links, by making routing
decisions at routers. NoCs bring remarkable improvement
in performance, flexibility, scalability, and power efficiency
over conventional bus interconnections. However, in NoCs
communication deadlocks may appear and cause an
impasse in the network, and hence lead to performance
degradation or system failure.
Generalities on Deadlock
A deadlock is a situation in NoCs wherein two or more
packets are waiting for one another to release channels, and
are unable to make progress. The network is deadlocked if a
chain of waiting packets forms a cycle. As a simple
deadlock example, consider the dependency cycle of four
packets shown in Fig. 1. Each of the four packets in the
figure holds some channels but it cannot proceed further
until it acquires another channel currently held by one of
the rest of the packets. However, no packet can release the
channel needed by another until it acquires its own
requested channel. The packets are deadlocked and will
remain in this state halting all the occupied channels until
some intervention brings them back to life by breaking the
dependency cycle. Deadlocks can paralyze network communications
by halting the resources occupied by the
deadlocked packets which in return could increase other
packets blocking [2]. Hence, it is crucial to remove deadlocks.
There are two strategies to deal with deadlocks:
avoidance and recovery [3], [4].
METHODOLOGY
Background and Assumptions
The network of concern in this work is a collection of router
nodes connected by channels. Each router is connected to a
single IP core that can inject/consume packets via the
router. A fully adaptive routing algorithm with minimal
paths is used. A wormhole flow control technique [16] is
employed which has been widely used in NoCs. The
packets in wormhole flow control are divided into smaller
flits. A header flit is routed first and the rest will follow it in
a pipeline manner and that will allow a packet to occupy
several channels simultaneously. Thus, wormhole reduces
the number of buffers required in each router which is a
desirable feature for NoCs. However, wormhole makes
networks more prone to blocking and deadlock [2], [17].
In line with existing work on deadlock recovery [6], [9],
[10], [13], we assume that a channel buffer cannot contain
flits belonging to different packets and a packet arriving at
its destination is eventually consumed.
TCNETWORK ARCHITECTURE
TC Computation with TC Networks
Dynamic programming (DP) can yield the solution for the
transitive closure [18]. DP provides an opportunity for
solving the computation using a parallel architecture with
improved computation performance. Mapping TC computation
to a parallel computational platform can be achieved
with the introduction of a DP-network. The network has a
parallel architecture, and can be used to compute the TC
solution through the simultaneous propagation of successive
inferences. Lam and Tong [21] introduced DP-networks
to solve a set of graph optimization problems with
an asynchronous and continuous-time computational
framework. This new class of inference networks is
inherently stable in all cases and has been shown to be
robust with an arbitrarily fast convergence rate [21]. A
parallel computational network for solving the dynamic
routing problem for NoCs is also proposed in [22].