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.
Key Words
System on Chip (SoC)
Core-Based Design
On Chip Communication
Network on Chip (NoC)
Packet Switched Network
Routing Algorithms
Source Routing
Junction-Based Routing
Specification and Description Language (SDL)