Congestion-Aware High-Efficiency Adaptive Routing Algorithms and Architectures in Network-on-Chips Systems
Date Issued
2014
Date
2014
Author(s)
Chang, En-Jui
Abstract
As semiconductor technology continues to advance, increasing complexity and interconnection delay are becoming limiting factors in system-on-chip (SoC) designs. To increase the efficiency of interconnections and meet data transfer requirements, network-on-chip (NoC) systems have proven to be a flexible, scalable, and reusable solution for chip multiprocessor (CMP) systems. To achieve a high system throughput rate, the packet-switched NoC multiplexes packets on channels and shares network resources among these packet flows. However, the packet contention problem in switches results in unpredictable delays for each packet flow. As the system size increases, the network traffic load tends to become unbalanced with various applications. Switches and channels are prone to congestion, which increases queuing delays in the routing path. It not only causes network congestion but also dissipates additional energy. Congestion problem severely degrades the overall system performance, especially in real-time applications with strict latency requirements. Therefore, to overcome the problem of traffic congestion, packet routing is a critical design challenge for high-performance NoC.
An effective adaptive routing algorithm can help minimize network congestion through load balancing. However, conventional adaptive routing schemes only use current channel-based information to detect the congestion status. Because of the lack of fine-grained path-congestion model and historical network information, channel-based information has difficulty showing the real congestion status under non-uniform and time-variant traffic patterns. To effectively relieve spatial traffic congestion and predict traffic-flow trends, we propose model-based and bio-inspired routing schemes. In this dissertation, our goal is to both improve the selection efficiency and cost efficiency of adaptive routing algorithms in the resource-limited NoC system.
There are two main topics in this work. First, to figure out hidden spatial congestion information, we analyze the router latency and propose a model-based approach to improve the selection efficiency of adaptive routing algorithms. Namely, it simultaneously considers two congestion situations, switch congestion and channel congestion. Moreover, to overcome imbalance traffic problem, we propose a path-diversity-aware adaptive routing scheme to evenly distribute traffic load on the available channels.
In the second part of this dissertation, to predict temporal network congestion, we apply a bio-inspired approach, Ant Colony Optimization (ACO), to identify the near-future non-congested path to a desired target according to historical network information. However, the cost of ACO-based adaptive routing is too high for implementation in resource-limited NoCs.
Therefore, in considering the NoC topology, router dependency, and pheromone characteristics, we propose a cost-efficient ACO-based adaptive routing with a regional routing table, which has potential to reduce routing table cost. Moreover, to further improve the selection efficiency of ACO-based routing, we propose the early backward-ant mechanism to provide extra feedback congestion to enhance the learning process, which improves the system performance.
In summary, the proposed routing schemes can effectively mitigate the spatial and temporal traffic congestion in NoC and achieve a good trade-off between cost and performance.
Subjects
晶片內網路
可適性路由演算法
壅塞感知演算法
仿生物演算法
路由器架構
SDGs
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-103-F97943013-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):95655b6fd53139cdf8d67b5e87339255