壅塞感知之高效率晶片內網路可適性路由演算法與架構設計

Congestion-Aware High-Efficiency Adaptive Routing Algorithms and Architectures in Network-on-Chips Systems

張恩瑞(En-Jui Chang)

指導教授 ： 吳安宇

國立臺灣大學/電機資訊學院/電子工程學研究所/博士(2014年)

https://doi.org/10.6342/NTU.2014.00177

摘要

隨著半導體製程的演進，越來越高的系統複雜度及資料傳輸延遲成為設計單晶片系統 (System-on-Chip, SoC)所要面對的重要挑戰。對於一個多核心處理器(Chip Multiprocessor, CMP)系統，為了提高資料傳輸的效率且符合系統需求，晶片內網路(Network-on-Chip, NoC)系統已被提出為一個具備設計彈性、系統可尺度化及設計可重複使用的解決方案。為了可以提高系統吞吐量，晶片內網路採用封包多工傳輸來充分使用網路資源，然而交換器內的封包競爭問題將會導致不預測的延遲。另一方面，隨著網路系統的變大，交通負載也隨著不同的的應用而變得相當地不平衡，因而導致交換器及傳輸通道產生嚴重的壅塞。交通壅塞不僅會讓路由路徑的延遲上升，也相對地消耗額外的功率，嚴重地造成整體網路效能下降。對於一個高效能的晶片內網路而言，如何設計路由演算法來紓緩交通壅塞問題，將成為一個關鍵的設計挑戰。
一個有效的可適性路由演算法可以幫助改善交通壅塞問題。然而傳統的可適性路由演算法缺少考量路徑壅塞模型及網路歷史資訊，單憑著有限的通道資訊來評估全域的壅塞狀況，而把封包送往遠方或是即將壅塞的區域，因此導致效能低下。為了可以有效地紓緩壅塞及預測交通變化趨勢於一個資源受限的的晶片內網路系統中，本論文分別提出基於預測模型及仿生物最佳化演算法，來改善路由演算法的選擇效率及成本效率。
首先為了解決空間上的壅塞問題，本論文提出一路由器模型並分析其封包延遲。基於此模型進一步提出路徑壅塞感知路由演算法，透過同時偵測交換器及通道資訊來得到更精確的交通狀況，因而改善其選擇效率。除此之外，本論文亦針對交通分布不均問題，提出一路徑多樣性感知路由演算法來平均地分散交通負載到不同的通道上。
另一方面，為了可以預測時間上的壅塞變化，本論文應用了一基於學習強化的仿生物演算法，也就是蟻群最佳化演算法，憑藉著網路歷史資訊來預測下一個時間點的壅塞程度。然而直接實現蟻群最佳化演算法於晶片內網路中是要付出相當大的成本了，因此本論文將考量晶片內網路拓樸、路由器相依性及費洛蒙特性，提出一區域化蟻群路由演算法，藉由降低路由表的記憶體成本來提升其成本效率。此外為了可以進一步地改善其路徑選擇效率，本論文亦提出一及早反向螞蟻機制來提供額外的回饋交通資訊來加速學習過程收斂，提高系統效能。
總結本論文所提出之設計方法，可以有效地紓緩空間及時間上的交通壅塞問題，並且達到一個效能與成本的設計平衡點。

關鍵字

晶片內網路 ； 可適性路由演算法 ； 壅塞感知演算法 ； 仿生物演算法 ； 路由器架構

並列摘要

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.

並列關鍵字

Network-on-Chips ； Adaptive Routing Algorithms ； Congestion-Aware Algorithms ； Bio-Inspired Algorithms ； Router Architectures

參考文獻

[1] ITRS, International Technology Roadmap for Semiconductors, http://public.itrs.net.

[2] J. A. Davis et al., “Interconnect Limits on Gigascale Integration (GSI) in the 21st Century,” Proc. IEEE, vol. 89, pp. 305-324, Mar. 2001.

[4] D. Sylvester and K. Keutzer, “A Global Wiring Paradigm for Deep Submicron Design,” IEEE Trans. CAD/ICAS, vol. 19, pp. 242-252, Feb. 2000.

[7] S. Kumar et al., “A Network on Chip Architecture and Design Methodology,” in Proc.IEEE Int’l Symp. VLSI, pp. 105-112, 2002.

[8] P. Magarshack and P. G. Paulin, “System-on-Chip beyond the Nanometer Wall,” in Proc. IEEE Design Automation Conf (DAC), Anaheim, pp. 419-424, 2003.