19-01-2013, 12:34 PM
Network on Chip Routing Algorithms
Network on Chip.pdf (Size: 390.95 KB / Downloads: 40)
Abstract
Network on Chip (NoC) is a new paradigm to make the interconnections inside
a System on Chip (SoC) system. In traditional solutions interconnections are
realized using a bus structure. While integration increases the bus structure does
not meet the needs of the new technology. Bus starts to be narrow and in the worst
case it begins to block traffic. In NoC technology the bus structure is replaced
with a network which is a lot similar to the Internet. Segments communicate with
each other by sending packetized data over this network.
Just like a computer network, a NoC network consists of devices that use the
network, routers that direct the traffic between devices and wires that connect
devices to routers and routers to other routers. In the network design of the NoC
the most essential things are a network topology and a routing algorithm. Routers
route the packets based on the algorithm that they use. There are many kind of
different algorithms for different systems to choose. Every system has its own
requirements for the routing algorithm.
This report looks through the basics of networking on Network on Chip systems
and presents proposed routing algorithms to be used on NoCs. In the end of
the report the proposed router architectures are also presented.
Introduction
Network on Chip (NoC) is a new paradigm for System on Chip (SoC) design. Increasing
integration produces a situation where bus structure, which is commonly
used in SoC, becomes blocked and increased capacitance poses physical problems.
In NoC architecture traditional bus structure is replaced with a network
which is a lot similar to the Internet. Data communications between segments
of chip are packetized and transferred through the network. The network consists
of wires and routers. Processors, memories and other IP-blocks (Intellectual
Property) are connected to routers. A routing algorithm plays a significant role
on network’s operation. Routers make the routing decisions based on the routing
algorithm.
Routing on NoC
Routing on NoC is quite similar to routing on any network. A routing algorithm
determines how the data is routed from sender to receiver.
Routing algorithms are divided into two groups, oblivious and adaptive algorithms.
Oblivious algorithms are also divided into two subgroups: deterministic
and stochastic algorithms. Oblivious algorithms route packets without any information
about traffic amounts and conditions of the network, deterministic algorithms
route packets always along a same route and stochastic routing is based on
randomness.
Network Topologies
A network can be regular or irregular and it is non-blocking if it can manage all
the requests that are offered to it. In a packet switched case this kind of network is
also called as non-interfering network. Non-interfering network can deliver all the
packets in guaranteed time. [12] The basic regular network topologies are listed
below.
Problems on Routing
Problems on oblivious routing typically arise when the network starts to block
traffic. The only solution to these problems is to wait for traffic amount to reduce
and try again. Deadlock, livelock and starvation are potential problems on both
oblivious and adaptive routing.
Network Flow Control
Network flow control, also called as routing mode, determines how packets are
transmitted inside a network. The mode is not directly dependent to routing algorithm.
Many algorithms are designed to use some given mode, but most of them
do not define which mode should be used.
Oblivious Routing Algorithms
Oblivious routing algorithms have no information about conditions of the network,
like traffic amounts or congestions. A router makes routing decisions on
the grounds of some algorithm or for example randomly. The simplest oblivious
routing algorithm is a minimal turn routing. It routes packets using as few turns
as possible.
Source Routing
In a source routing a sender makes all decisions about a routing path of a packet.
The whole route is stored in a header of packet before sending, and routers along
the path do the routing just like the sender has determined it. Two router architectures
using source routing are presented later in this report on section 5.1.1.
A vector routing works basically like the source routing. In the vector routing
the routing path is represented as a chain of unit vectors. Each unit vector corresponds
to one hop between two routers. Routing paths do not have to be the
shortest possible.
Arbitration look ahead scheme (ALOAS) is a faster version of source routing.
The information of routing path has been supplied to routers along the path before
the packets are even sent. Route information moves along a special channel that
is reserved only for this purpose. [13, 23, 35]
A contention-free routing is a algorithm based on routing tables and time division
multiplexing (TDM). Each router has a routing table that involves correct
output ports and time slots to every potential sender–receiver pairs. Contentionfree
routing algorithm is used in PhilipsÆthereal NoC system and it is also called
as a clockwork routing. An architecture of the Æthereal router using contentionfree
algorithm is represented on section 5.1.3. [18, 28, 29]