請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56911
標題: | 晶片內網路之蟻群最佳化可適性路由演算法與架構設計 Ant-Colony Optimization-based Adaptive Routing Algorithms and Architectures in Network-on-Chips Systems |
作者: | Hsien-Kai Hsin 辛賢楷 |
指導教授: | 吳安宇(An-Yeu Wu) |
關鍵字: | 晶片網路系統,路由演算法,蟻群最佳化, Network-on-Chip,routing algorithm,Ant Colony Optimization, |
出版年 : | 2014 |
學位: | 博士 |
摘要: | 隨著半導體製程的演進,不斷提升的系統複雜度及資料傳輸延遲成為設計單晶片系統 (System-on-Chip, SoC)所面臨的重要挑戰。對於多核心處理器(Chip Multiprocessor, CMP)系統來說,為了在多核心的系統需求下提高資料傳輸效率,晶片內網路(Network-on-Chip, NoC)系統被提出為一個具備高度設計彈性、系統規模化及設計可重複使用的解決方案。
為了可以提高系統吞吐量,晶片內網路採用封包多工傳輸來充分使用網路資源,然而交換器內的封包競爭問題導致難以預測的延遲。另一方面,隨著網路系統的變大,交通負載也隨著不同的的應用而變得相當地不平衡,進而導致交換器及傳輸通道產生嚴重的壅塞。交通壅塞不僅會讓路由路徑的延遲上升,也相對地消耗額外的功率,嚴重地造成整體網路效能下降。對於一個高效能的晶片內網路而言,如何設計有效的路由演算法來紓緩交通壅塞問題,將成為關鍵的設計挑戰。 一個有效的可適性路由演算法可以幫助改善交通壅塞問題。然而傳統的可適性路由演算法缺少考量網路之歷史資訊,單憑著目前的通道資訊來評估全域的壅塞狀況,而把封包送往遠方或是即將壅塞的區域,因此導致在時變(time-variant)的真實交通下效能大幅低下。 為了可以預測時間上的壅塞變化,本論文應用了蟻群最佳化仿生演算法,憑藉著網路歷史資訊來預測下一個時間點的壅塞程度。分散式的螞蟻封包在路由器之間移動,並分泌費洛蒙物質來更新路由表上的資訊。但一般的蟻群最佳化可適性路由演算法並未考慮透過時間與空間資訊的變化和結合來達到更準確的估測、也未考慮如網路死結以及網路錯誤導致的整體系統影響。 本論文提出三個主題以解決上述問題:首先,本論文提出時空間增強之蟻群路由演算法,透過額外的時間與空間資訊來提供對於全域網路狀態更佳的近似。在空間上,透過二級外的路由以取得更精準的壅塞資訊;在時間上,透過股票市場的指數移動平均來開發多費洛蒙機制以預測未來的壅塞狀況變化。第二部分,本論文提出蟻群費洛蒙擴散性路由演算法,並建立一個統一的網路資訊分析架構。所提出的架構可調為子集的網路資訊與對應的路由演算法。基於此架構,透過擴散性的費洛蒙來達到時空間網路資訊的整合。第三部分,本論文提出蟻群錯誤感知路由演算法,將壅塞感知、死結感知與錯誤感知之網路資訊進行整合,透過蟻群之1)遭遇, 2)找尋, 3)選擇之啟發來開發有效的繞徑機制。可提升整體的系統效能以及錯誤容忍度。 總結本論文所提出之設計方法,可以有效地紓緩空間及時間上的交通壅塞問題,並且達到一個效能與成本的設計平衡點。 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 congestion problem in channels results in unpredictable delays for each packet flow. As the system size increases, the network traffic load tends to become unbalanced with various applications. The congestion in channels increases queuing delays in the routing path, which not only causes network congestion but also dissipates additional energy. Congestion problem cause severely degradation on 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 historical network information, channel-based information has difficulty showing the real congestion status under time-variant traffic patterns. 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. Distributed artificial ant agents migrate from node to node and emulate laying of pheromone by updating the corresponding entries in the routing (or pheromone) tables in different nodes which record. However, conventional ACO-based adaptive routing have not consider the integration of spatial/temporal information and multiple congestion factors includes deadlock and faulty nodes. There are three main topics in this work. First, we use additional temporal and spatial information provides better approximation of network status for global load-balancing. In spatial domain, to acquire the spatial range of congestion information, we record historical buffer information from routers within two-hop of distances, which helps to extend spatial pheromone coverage. In temporal domain, we adopt the concept of Exponential Moving Average (EMA) from stock market to use multiple pheromone for capturing hidden-state dependencies of upcoming congestion status In the second part of this dissertation, we establish a framework on analyzing the network information and showed how to integrate the spatial and temporal network information. The proposed framework can indicate arbitrary combinations of network information and corresponding routing algorithms. Based on this framework, we use the concept of diffusive pheromone to integration the information and show that we can reconfigure the ACO-PhD algorithm to each routing algorithm in its subsets by adjusting the parameter settings. In the third part of this dissertation, we integrate the congestion-awareness, deadlock-awareness, and fault-awareness information in channel evaluation function to avoid the hotspot around the faulty router. The three steps behavior of an ant colony while facing an obstacle (failure in NoC) as 1) encounter, 2) search, and 3) select is transformed into effective detouring mechanisms to increase the system throughput and faulty tolerance under faulty network. In summary, the proposed routing schemes can effectively mitigate the spatial and temporal traffic congestion in NoC and achieve good performance with feasible cost. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56911 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf 目前未授權公開取用 | 8.28 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。