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 study 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 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 simulation based 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.
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.
Source routing has an important disadvantage of overhead for storing the path information in header of each packet sent. This disadvantage becomes worse as the size of the network grows. In this chapter we describe a routing technique , called Junction Based Routing (JBR) to remove this disadvantage. The idea of junction based routing is basically derived from the railway networks. Railway networks generally have a few large stations, called junctions which are connected by fast railways. A long distance journeys from a small town to another small town is achieved by first going to the nearest junction close to the source and from there reaching a junction close to the destination. In this chapter concepts and issues of this new routing technique are discussed.
PATH COMPUTATIONS FOR MESH TOPOLOGY NOC WITH JUNCTIONS 35
In last chapter, we showed that it is not possible to use Turn-Model based deadlock-free routing algorithms for NoC using the minimum number of junctions. In this chapter, the required number of junctions and the positions of these junctions are computed for a mesh NoC which uses Turn-Model based deadlock-free routing algorithms. Using a tool developed in MATLAB, all possible paths are given and the adaptivity is compared with adaptivity of paths in source routing. Link load distribution is also analyzed and one path for each communicating pair is selected for different types of communications and traffic patterns. Finally, a method is suggested for encoding the paths and junction architecture is analyzed to some extent.
Arbitration and control unit consists of several blocks which are depicted in Figure 4-13.
PERFORMANCE EVALUATION OF JBR
In this chapter, JBR for mesh topology NoC is modeled using SDL and packet delay for JBR is analyzed. The simulator is a modified version of an existing simulator for source and distributed routing. JBR is evaluated using different routing algorithms and different types of traffics and the performance of JBR and source routing are compared.
Source routing, with many advantages ( including lower router cost and higher communication speed) over distributed routing, is a good candidate for mesh topology NoC platforms. But 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. In this thesis we have developed a new technique which will make source routing in large NoCs systematic, scalable and efficient.
Source: Jönköping University
Author: Shabnam Badri