請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/62484
標題: | 適用於晶片網路系統的蟻群最佳化之錯誤感知路由演算法和架構設計 ACO-Based Fault-Aware Routing Algorithm and Architecture for Network-on-Chip Systems |
作者: | Chia-An Lin 林家安 |
指導教授: | 吳安宇 |
關鍵字: | 晶片上網路:蟻群最佳化:錯誤容忍,路由演算法,錯誤感知機制, Network on Chip,Ant colony Optimization,Fault-tolerant,Routing algorithm,Fault-aware mechanism, |
出版年 : | 2013 |
學位: | 碩士 |
摘要: | 本篇論文提出一應用於晶片上網路之錯誤感知路由演算法,用以容忍晶片上發生之錯誤,並在此環境中提升晶片上網路之吞吐量並降低整體之網路延遲,進而提高網路效能。此演算法是基於“蟻群最佳化演算法”與“蟻群錯誤容忍行為”的概念來進行設計,藉此提升網路封包傳遞效率與錯誤容忍能力。“蟻群最佳化演算法”是由真實世界中之蟻群行為所啟發的最佳化演算法,而過去文獻中基於此演算法所開發出的網路路由演算法已被證實在分散網路流量方面有較高的能力。而“蟻群錯誤容忍行為”是當蟻群遭遇突發障礙擋住行進路徑時所因應的行為,可分為三個步驟─遭遇、找尋、選擇。
本篇論文應用了“蟻群最佳化演算法”的概念,藉由費洛蒙資訊來提供時間軸上的歷史網路資訊,並且進一步結合了“蟻群錯誤容忍行為”的概念,提出三個與蟻群行為相對應的機制來增強傳統之路由演算法,使得各個路由器具有錯誤容忍之能力。根據實驗結果,本論文提出的演算法能有效地增加網路效能,以及提升網路容錯能力。除此之外,也完成了此演算法的路由器硬體架構設計及電路合成。綜合系統效能以及硬體成本進行分析,數據顯示本論文所提出之演算法在網路效能上有46.0%之改進,而在面積效率上也有最佳之表現。 This thesis proposes a fault-tolerant routing algorithm for Network-on-Chip (NoC) systems to tolerate on-chip failures, increase network throughput, and decrease total latency of network. With the algorithm which adopts the Ant Colony Optimization (ACO) algorithm and fault-tolerant behavior of ant colony, the network performance and the fault-tolerance ability are improved. ACO is a problem-solving technique inspired by the behavior of real-world ant colony. ACO-based routing also has high potential on balancing the traffic load in the domain of NoC, where the performance is generally dominated by the traffic distribution and routing. Fault-tolerant behavior of ant colony is the behavior that ants react when an obstacle appears and blocks the trail, consisting of three steps, 1) encounter, 2) search, and 3) select. The algorithm proposed utilizes the pheromone information in the ACO algorithm, which provides the temporal network information. Moreover, it further adopts the concept of Fault-tolerant behavior of ant colony, which proposes three corresponding mechanisms to the behavior for enhancing conventional routing algorithms. As a result, it achieve the fault-tolerance of each router. According to the experimental results, the proposed routing scheme can significantly improve the network performance and fault-tolerance ability. Moreover, the hardware design of the corresponding router architecture is also implemented and analyzed. The results show an improvement of 46.0% on network performance and the highest area efficiency achieved by the algorithm proposed. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/62484 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-102-1.pdf 目前未授權公開取用 | 5.96 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。