OPTIONS FOR INTERCONNECTING THE CORES IN A SOC

Get Complete Project Material File(s) Now! »

Network Architecture

NoC uses layered communication. Network architecture is partitioned into physical layer, data link layer, network layer, transport layer and application layer. Each layer is specifying a particular function and can implement tasks autonomously. Message represents the data to move between cores and is defined in application layer. Message size can be fixed or variable. A message consists of many packets. A packet is a group of bits for independent transfer in the network. It contains all information that is necessary to reach the destination. Packets can have different sizes. Network layer determines the routing of packets through network routers and it is responsible for performing packetization, packet buffering, congestion control, providing quality of service, etc. A packet may be partitioned into many flits. A Flow Control Digit (Flit) is a group of bits that is defined in data link layer. The flit size is constant. Data link layer is concerned with reliable node to node communication, error detection and correction, flow control, encoding scheme, etc. The electrical specifications are defined in physical layer. Phit (PHysical transfer digIT) is transferred as a unit across a channel from one router to the next. The phit size is equal to the number of wires between two routers, and thus can be considered as link width.

Junction-Based Routing

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.

Challenges in JBR

Source routing is very suitable for small NoC platforms and has many advantages over distributed routing algorithm [4]. Since the packet entering a router has information about the output port in its header field, it simplifies router design and router delay is relatively smaller. Only recently researchers have started considering source routing as a routing candidate in NoCs [4]. Although, the authors in [4] give an analysis of the overhead due to source routing, they have not proposed any solution to reduce/handle the overhead with the size of the network. Some researchers have proposed hierarchical organization of networks and proposed hierarchical routing for large on-chip communication networks [16]. The proposed technique in this paper can be considered as an alternative to their approach.

Increase in Path Length by Using Junctions

In the first section, we observed that path length between S (1,1) and D5(3,7) is increased by going through junctions. In pure source routing, distance between source and destination nodes is 8 but using JBR the distance is 10. The distance between S (source node) and J1 (first junction) is 4 and the distance between J1 and J2 (second junction) is also 4. The distance between J2 and D4 (destination node) is 2 and therefore, distance between source node and destination node become 10. Increase in path length is unavoidable while the minimum number of junctions is used. One of the future works in JBR will be to find the minimum number of junctions such that path length does not increase.

Junctions and Deadlock-Free Routing

Presence of junctions makes the network non-homogeneous in the sense that all routers are not identical. A junction router has functionality of a router plus some other functionality. If one is not careful in computing the paths, it can lead to a deadlock. Suppose we want to use negative first routing algorithm for a 7×7 mesh NoC and a given H of 7 (see Figure 3-10). Consider the communicating pair is S (1,7) and D(7,1). Packets have to go through a junction since distance between nodes S1 and D1 is more than 7 hops. The only path between S1 and D1 is shown in the figure. A junction has to be at the position (1,1), because the junction should be close enough to the source and destination nodes and the only possibility is (1,1). Suppose S is sending data to the node that is located at the position (7,2). Distance between these two nodes is more than 7 hops but the only path between these two nodes does not go through J and J cannot be used for getting the path information. Then another junction is needed for this communicating pair and one junction is not enough.

Table of Contents :

• 1 Introduction
  • 1.1 SYSTEM ON CHIP
  • 1.2 OPTIONS FOR INTERCONNECTING THE CORES IN A SOC
    • 1.2.1 Point to Point Connections
    • 1.2.2 Bus-Based System on Chip
    • 1.2.3 Network on Chip (NoC)
  • 1.3 ISSUES IN NOC-BASED SOC DESIGN
    • 1.3.1 Topology
    • 1.3.2 Routing Algorithms
  • 1.4 PROJECT OBJECTIVES AND TASKS
  • 1.5 THESIS LAYOUT
• 2 Theoretical Background
  • 2.1 NETWORK ON CHIP
  • 2.2 TERMINOLOGY OF NOC
    • 2.2.1 Network Architecture
    • 2.2.2 Direct and Indirect Networks
    • 2.2.3 Topology
    • 2.2.4 Network Diameter
    • 2.2.5 Path
  • 2.3 COMPONENTS OF NOC
  • 2.3.1 Router
    • 2.3.2 Resource Network Interface (RNI)
  • 2.4 SWITCHING
    • 2.4.1 Circuit Switching
    • 2.4.2 Packet Switching
  • 2.5 BUFFERS AND VIRTUAL CHANNELS
  • 2.6 ROUTING
    • 2.6.1 Source vs. Distributed Routing
    • 2.6.2 Deterministic vs. Adaptive Routing
    • 2.6.3 Static vs. Dynamic Routing
    • 2.6.4 Minimal vs. Non-minimal Routing
    • 2.6.5 Application Specific Routing
  • 2.7 DEADLOCK-FREE ROUTING ALGORITHMS
    • 2.7.1 Deadlock, Livelock and Starvation
    • 2.7.2 Turn-Model Routing Algorithms
    • 2.8 EVALUATION OF NOC
    • 2.8.1 Network Simulators
    • 2.8.2 Performance Parameters
    • 2.8.3 Traffic Types

• 3 Junction-Based Routing
  • 3.1 AN ILLUSTRATION OF JUNCTION-BASED ROUTING
  • 3.2 ANALYSIS OF JUNCTION-BASED ROUTING
    • 3.2.1 Packet Format and Path Information
    • 3.2.2 Header Overhead in JBR
  • 3.3 CHALLENGES IN JBR
    • 3.3.1 Number and Position of Junctions
    • 3.3.2 A Case Study: Number and Position of Junctions
  • 3.4 INCREASE IN PATH LENGTH BY USING JUNCTIONS
    • 3.4.1 Calculating Extra Overhead of Increase in Path Length
    • 3.4.2 Results of Computing Extra Overhead Using the Developed Tool

GET THE COMPLETE PROJECT
JUNCTION BASED ROUTING: A NOVEL TECHNIQUE FOR LARGE NETWORK ON CHIP PLATFORMS