25-02-2013, 10:15 AM
JUNCTION BASED ROUTING: A NOVEL TECHNIQUE FOR LARGE NETWORK ON CHIP PLATFORMS
JUNCTION BASED ROUTING.pdf (Size: 1.47 MB / Downloads: 40)
Abstract
To support communication among hundreds of cores on a chip, on-chip
communication must be well organized. In the embedded systems using such a chip,
the communication patterns can be profiled and routing can be well planned off-line.
Source routing, with many advantages over distributed routing, will be very suitable
in such contexts. However, source routing has one serious drawback of overhead for
storing the path information in header of every packet. This disadvantage becomes
worse as the size of the network grows. In this thesis we propose a technique, called
Junction Based Routing (JBR), to remove this limitation. In the proposed technique,
path information for only a few hops is stored in the packet header. With this
information, either the packet reaches the destination, or reaches a junction from
where the path information for on-ward path is picked up.
There are many interesting issues related to this approach. Two important issues
related to JBR, namely, number and position of junctions and path computation for
efficient deadlock free routing are discussed and solved in this thesis work. Increase
in path length by using the minimum number of junctions, link load distribution while
computing paths, path encoding for JBR and packet format in JBR are also discussed.
A few tools have been developed in MATLAB to analyze the various aspects of JBR.
A simulator has been also developed to evaluate the performance of JBR with simple
source routing. Outline of the architecture for a junction is also proposed.
The results of simulation-based experiments show that the performance of JBR is
similar to source routing. JBR is compared with source routing and the simulationbased
results show that latency does not increase so much using junctions.
Throughput also does not level off significantly. Header flit in JBR can carry payload
data and this improves the performance of JBR in terms of throughput and latency
compared to source routing which needs to store large path information. We observe
improvement in throughput as compared to basic source routing when payload is very
small.
Introduction
This thesis focuses on improvement of the communication between components of a
system which is integrated on a single chip. In this chapter, we introduce the System
on Chip and different methods for connecting components of the system. We will also
introduce the area and problems handled in the thesis.
System on Chip
A core is an individual component that has a particular, often advanced, functionality.
Today, it is possible to integrate a large number of cores (e.g. general purpose
processors, embedded memories, DSP cores, FPGA blocks, I/O blocks, ASIC blocks,
etc.) on a single silicon chip. Integrating the entire system on one chip reduces the size
and increases the performance of electronic systems. For example,
STMicroelectronics announced FLI7540, a new TV System-on-Chip lately. 1700+
DMIPS CPU with 256 KBytes of Level 2 cache offers a high performance TV [13].
These independent blocks can be of unequal size. Interconnecting pre-designed cores
(resources) or IP-cores (Intellectual Property) becomes harder and harder by
increasing the number of cores. Reducing design complexity and power consumption
are some of the most important issues for SoC design [3].
Network on Chip (NoC)
Network on Chip (NoC) has emerged as a dominant paradigm for synthesis of multicore
SoCs. As illustrated in Figure 1-4, in NoC paradigm, cores are connected to each
other through a network of routers and they communicate among themselves through
packet-switched communication. A large number of different NoC architectures have
been proposed by different research groups based on this paradigm [2][4]. Network
topology and routing algorithm are the two most important aspects which distinguish
various proposed NoC architectures. Router is the most important component for
design of the communication back-bone of a NoC system (like any other network). In
a packet switched network, the functionality of the router is to forward an incoming
packet to the destination if it is directly connected to it, or to forward the packet to
another router connected to it. The protocols used in NoC are generally simplified
versions of general communication protocols used in data networks. In the context of
NoC, scarcity of silicon resources requires that the router design should be as simple
as possible.
Project Objectives and Tasks
Source routing is not considered scalable and efficient for large networks since the
overhead of appending path information in the packet header increases with network
size. No efficient solution exists in literature regarding this problem so far.
The main objective of this project will be to develop a new routing scheme, called
Junction Based Routing, which will make source routing in large NoCs systematic,
scalable and efficient. The goal of the project will be to complete the theory regarding
this new idea for routing, work out its implementation details and evaluate and
compare the new algorithm with existing routing algorithms. The evaluation will be
simulation based.
Thesis Layout
In first chapter, we described integrating a system on one silicon chip and primitive
connection methods. Chapter 2 presents basic knowledge in network on chip
approach. Third chapter defines the concepts in the new technique, called Junction-
Based Routing (JBR). There are many interesting issues related to this technique that
are discussed and solved in Chapter 4. Path computation for efficient deadlock free
routing is the most important problem. A simulator has been developed to evaluate
the performance of JBR that is explained in Chapter 5. Chapter 6 gives conclusions
and proposals of future works.
Theoretical Background
Basic concepts related to NoC are described in this chapter. Routing algorithms are
discussed in more details due to their important role in the performance of a network.
This chapter also presents some of the parameters used to evaluate the performance of
a network.
Network on Chip
Shared buses and dedicated wires can be used to connect only a few numbers of cores.
The other disadvantages are low scalability and low reusability for new SoCs. They
are inefficient for high communication performance. In the year of 2000 a new
paradigm, called Network on Chip (NoC), was proposed for synthesis of multi-core
SoCs. As illustrated in Figure 2-1, in NoC paradigm, cores communicate to each
other through a network of routers. The pre-routed wires reduce the design complexity
and make the testing and verifying of the system easier [1][2].