The routing algorithm and flow control allocate network resources, including buffers and channels, to packets. They directly determine the network-on-chip (NoC) performance. Owing to the limited parallelism of a single application, multiple applications will run concurrently on a many-core platform. This workload consolidation scenario requires routing algorithms not only to provide high performance, but also to maintain the application isolation. In addition, the resource allocation must avoid network deadlock. There are several deadlock avoidance theories for routing and flow control designs. Yet, most theories were originally presented for off-chip networks, whose traffic characteristics are quite different from those of on-chip networks. These theories have been used for about one or two decades, and it is now the right time to re-examine them, and propose more efficient deadlock-free routing and flow control for NoCs. On the basis of these insights, this part delves into NoC routing and flow control designs in three chapters.

In Chapter 5 a holistic approach is applied to design efficient routing for workload consolidation scenarios. Existing locally adaptive algorithms do not consider enough status information to avoid network congestion. Globally adaptive routing algorithms attack this issue by utilizing network status beyond neighboring nodes. However, they may suffer from interference, coupling the otherwise independent applications. To address these issues, we propose a novel selection strategy, the destination-based selection strategy (DBSS), for many-core systems running consolidation workloads. The key aspects of routing design include adaptivity, path selection strategy, virtual channel (VC) allocation, isolation, and hardware implementation cost; these aspects are not independent. We holistically consider all aspects to ensure an efficient design. DBSS leverages both local and nonlocal network status to provide more effective adaptivity. More importantly, by integrating the destination into the selection procedure, DBSS mitigates interference and offers dynamic isolation among applications.

Fully adaptive routing algorithms provide high routing flexibility. Yet, their performance may be limited by flow control mechanisms. Chapter 6 focuses mainly on efficient flow control designs for deadlock-free fully adaptive routing. Existing fully adaptive routing algorithms apply conservative VC reallocation: only empty VCs can be reallocated, which limits performance. In this chapter we propose two novel flow control designs. First, whole packet forwarding reallocates a nonempty VC if the VC has enough free buffers for an entire packet. Whole packet forwarding does not induce deadlock if the routing algorithm is deadlock-free using conservative VC reallocation. It is an important extension to several deadlock avoidance theories. Second, we extend Duato's theory to apply aggressive VC reallocation on escape VCs without deadlock. Finally, we propose a design which maintains maximal routing flexibility with low hardware cost.

The torus NoC needs additional effort to avoid deadlock. Chapter 7 delves into the design of high-performance, low-cost, and deadlock-free flow control for torus NoCs. Existing designs for torus networks cannot efficiently handle variable-size packets existing in cache-coherent NoCs. For deadlock-free operations, one design uses two VCs, which increases the router complexity and negatively affects the router frequency. Some optimizations use one VC. Yet, they must regard all packets as maximum-length packets, inefficiently utilizing the precious NoC buffers. We propose the flit bubble flow control theory, which maintains one free flit-size buffer slot to avoid deadlock. Flit bubble flow control uses one VC, and does not treat short packets as long ones. On the basis of this theory, we present two implementations. Both implementations achieve high frequencies and efficient buffer utilization. They are suitable for the torus NoCs.