臺灣大學: 電子工程學研究所吳安宇蘇冠羽Su, Kuan-YuKuan-YuSu2013-04-102018-07-102013-04-102018-07-102012http://ntur.lib.ntu.edu.tw//handle/246246/256687本篇論文提出一應用於晶片上網路之可適性路由演算法，用以提升晶片上網路之吞吐量並降低整體之網路延遲，進而提高網路效能。此演算法結合了“蟻群最佳化演算法”並應用“費洛蒙擴散”的概念來擴大能取得的網路資訊範圍，藉此提升網路封包傳遞的效率。“蟻群最佳化演算法”是由真實世界中之蟻群行為所啟發的最佳化演算法，而過去文獻中基於此演算法所開發出的網路路由演算法已被證實在分散網路流量方面有較高的能力。 本篇論文應用了“蟻群最佳化演算法”的概念，藉由費洛蒙資訊來提供時間軸上的歷史網路資訊，並且進一步結合了“費洛蒙擴散”的概念，透過費洛蒙的向外傳遞來交換空間軸上的網路資訊。有了空間軸以及時間軸上的網路資訊，各個路由器皆能擴大其網路資訊範圍，而此資訊範圍可透過演算法中各個參數的調整來改變其大小及形狀。根據分析，過去的相關研究諸如OBL、RCA以及ACO等技術所使用之網路資訊皆落在此範圍中。換言之，本篇論文所提出之演算法不僅能取得最大之網路資訊範圍，更可以藉由網路資訊範圍的調整來達到與過去各篇相關研究相同之網路效能。除此之外，本篇論文對演算法中各個參數所代表之物理意義以及效能影響進行探討，並完成了此演算法的路由器硬體架構設計及合成。綜合系統效能以及硬體成本進行分析，數據顯示所提之演算法在網路效能上有10.04%之改進，而在面積效率上也有最佳之表現。This thesis proposes an adaptive routing algorithm for Network-on-Chip (NoC) systems. With the algorithm which adopts the Ant Colony Optimization (ACO) algorithm and applies the concept of Pheromone Diffusion, the network throughput is increased and the latency is decreased, improving the network performance. 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. The algorithm proposed utilizes the pheromone information in the ACO algorithm, which provides the temporal network information. Moreover, it further adopts the concept of Pheromone Diffusion, which diffuses the pheromone outward and the spatial network information is thus exchanged. With the acquirement of both spatial and temporal network information, each router is able to expand an information region in the shape of a pyramid. The size and shape of this information region are controllable by setting the parameters in this algorithm. According to our analysis, the information used in the related works such as OBL, RCA, and ACO are all within this region. In other words, the algorithm proposed in this thesis can not only attain the largest information region, but also perform the same performance as other related works with the corresponding settings. Moreover, this thesis discusses the physical meaning and the influence on network performance of each design parameter. Finally, the hardware design of the corresponding router architecture is also implemented and analyzed. The results show an improvement of 10.04% on network performance and the highest area efficiency achieved by the algorithm proposed.3636219 bytesapplication/pdfen-US晶片上網路可適性路由演算法蟻群最佳化演算法Network-on-Chip (NoC)Adaptive Routing AlgorithmAnt Colony Optimization (ACO)thesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/256687/1/ntu-101-R99943047-1.pdf