ABSTRACT
Department of Information Technology, Bengal Engineering and Science University, Shibpur, India
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 11.2 Routing Topologies in NoC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
11.2.1 Topologies in 2D NoCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 11.2.2 Topologies in 3D NoCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 11.2.3 Topologies in Optical or Photonic NoCs . . . . . . . . . . . . . . . . 310 11.2.4 Topologies in Wireless NoCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
11.3 Design of Router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 11.3.1 Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 11.3.2 Virtual Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 11.3.3 Buffer Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
11.4 Switching Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 11.4.1 Circuit Switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 11.4.2 Packet Switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
11.5 Routing Flow Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 11.5.1 Store-and-Forward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 11.5.2 Virtual Cut-Through . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 11.5.3 Wormhole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
11.6 Traffic Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 11.6.1 Synthetic Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 11.6.2 Realistic Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
11.7 Routing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 11.7.1 Oblivious Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 11.7.2 Adaptive Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
11.8 Problems of Routing in NoC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 11.8.1 Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 11.8.2 Livelock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 11.8.3 Starvation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
11.9 Emerging Techniques in NoC Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 11.9.1 Routing in Optical NoC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 11.9.2 Wireless NoC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
11.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
Architecture,
Chip design has four distinct primary aspects, viz., computing, communication, memory, and I/O (input/output) or interfacing. For modern high-end System-On-Chip (SoC) designs, conventional bus based interconnection architectures fail to address the problem of on-chip communication due to increased integration density and communication complexity. Networks-on-Chip (NoC) is a viable alternative as well as a reliable solution for on-chip communication among multiple cores (Rantala, Lehtonen, and Plosila 2006). A Network-onchip (NoC) is a pre-designed network fabric consisting of routers and links connected in a definite topology, used to communicate between different IP cores. An NoC can provide separation between computation and communication, it can support modularity and IP reuse via standard interfaces, handle synchronization issues, and hence increase system productivity by reducing the complexity of interconnects, consumed power, network latency, noise, and all other important metrics which are desired for a high performance system-onchip. The performance of an NoC architecture mainly depends on its topology, switching mechanism, routing algorithms, and flow control (see Figure 11.1. This chapter will review these factors in detail.