請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64690完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 吳安宇(An-Yeu Wu) | |
| dc.contributor.author | Kuan-Yu Su | en |
| dc.contributor.author | 蘇冠羽 | zh_TW |
| dc.date.accessioned | 2021-06-16T22:57:28Z | - |
| dc.date.available | 2015-08-10 | |
| dc.date.copyright | 2012-08-10 | |
| dc.date.issued | 2012 | |
| dc.date.submitted | 2012-08-09 | |
| dc.identifier.citation | [1] D. Hodges, H. Jackson, and R. Saleh, Analysis and Design of Digital Integrated Circuits: In Deep Submicron Technology, 2004.
[2] P. Magarshack and P. Paulin, “System-on-chip beyond the nanometer wall,” Proc. Design Automation Conf. (DAC), pp. 419-424, Jun. 2003. [3] J. Howard, et al., “A 48-Core IA-32 Processor in 45 nm CMOS Using On-Die Message-Passing and DVFS for Performance and Power Scaling,” IEEE Journal of Solid-State Circuits, vol. 46, no. 1, pp. 173-183, Jan. 2011. [4] Cloud Computing, Intel Labs, “Single Chip Cloud Computer: Project,” http://www.intel.com/content/www/us/en/research/intel-labs-single-chip-cloud-computer.html, Dec. 2009. [5] R. Marculescu, U.Y. Ogras, L.-S. Peh, N.E. Jerger, and Y. Hoskote, “Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives,” IEEE Trans. on Computer Aided Design of Integrated Circuits and Systems, vol. 28, no. 1, pp. 3-21, Jan. 2009. [6] W.J. Dally and B. Towles, “Route packets, not wires: on-chip interconnection networks,” Proc. ACM/IEEE Design Automation Conf., pp. 684-689, 2001. [7] L. Benini and G. D. Micheli, “Network on chip: a new SoC paradigm for systems on chip design,” IEEE Proc. Conf. on Design, Automation and Test in Europe Conference and Exhibition, pp. 418-419, 2002. [8] W. J. Dally and B. Towles, Principles and practices of interconnection networks, Morgan Kaufmann, 2004. [9] T.M. Pinkston and S. Warnakulasuriya, “On Deadlocks in Interconnection Networks,” Proc. of International Symposium on Computer Architecture, pp. 38-49, Jun 1997. [10] C.J. Glass and L.M. Ni, “The turn model for adaptive routing,” Proc. of International Symposium on Computer Architecture, pp.278-287, May 1992. [11] G. M. Chiu, “The odd-even turn model for adaptive routing,” IEEE Trans. on Parallel and Distributed Systems, vol. 11, no. 7, pp. 729-738, July 2000. [12] J.C. Martı'nez, F. Silla, P. Lo'pez, and J. Duato, “On the influence of the selection function on the performance of networks of workstations,” Proc. International Symp. High Performance Computing, pp. 292-299, 2000. [13] L. Schwiebert and R. Bell, “Performance tuning of adaptive wormhole routing through selection function choice,” Journal of Parallel and Distributed Computing, vol. 62, no. 7, pp. 1121-1141, July 2002. [14] U.Y. Ogras, J. Hu, and R. Marculescu “Key research problems in NoC design: a holistic perspective,” IEEE/ACM/IFIP International Conf. on Hardware/Software Codesign and System Synthesis, pp.69-74, 2005. [15] G. Ascia, V. Catania, M. Palesi, and D. Patti, “Neighbors-on-Path: A New Selection Strategy for On-Chip Networks,” Proc. Embedded Systems for Real Time Multimedia, pp. 79-84, 2006. [16] G. Ascia, V. Catania, M. Palesi, and D. Patti, “Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip,” IEEE Trans. on Computer, vol. 57, no. 6, Jun. 2008. [17] P. Gratz, B. Grot, and S.W. Keckler, “Regional congestion awareness for load balance in networks-on-chip,” International Symposium on High-Performance Computer Architecture, pp. 203-214, Feb. 2008. [18] M. Daneshtalab and A. Sobhani, “NoC hot spot minimization using antnet dynamic routing algorithm,” IEEE Int. Conf. on Application Specific Systems, Architectures and Processors, pp. 33-38, 2006. [19] H.-K. Hsin, E.-J. Chang, C.-H. Chao, and A.-Y. Wu, “Regional ACO-based routing for load-balancing in NoC systems,” IEEE Second World Congress on Nature and Biologically Inspired Computing, pp. 370-376, Dec. 2010. [20] M. Dorigo, M. Birattari, and T. Stutzle, “Ant Colony Optimization,” Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, 2006. [21] M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: optimization by a colony of cooperating agents,” IEEE Trans. on Systems, Man, Cybernetics B, vol. 26, no. 2, pp. 29-41, 1996. [22] M. Dorigo and L.M. Gambardella, “Ant colony system: a cooperative learning approach to the Travelling Salesman Problem,” IEEE Trans. on Evolutionary Computation, pp. 53-66, 1997. [23] K.M. Sim and W.H. Sun, “Ant colony optimization for routing and load-balancing: survey and new directions,” IEEE Trans. on Systems, Man and Cybernetics, vol. 33, no. 5, pp. 560-572, 2003. [24] “Noxim: network-on-chip simulator,” http://sourceforge.net/projects/noxim, 2008. [25] L. Shang, L.-S. Peh, and N.-K. Jha, “Powerherd: a distributed scheme for dynamically satisfying peak-power constraints in interconnection networks,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 1, Jan. 2006. [26] E. Shin, V. Mooney, and G. Riley, “Round-robin arbiter design and generation, ” Proc. IEEE International Symposium on System Synthesis, pp. 243-248, Oct. 2002. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64690 | - |
| dc.description.abstract | 本篇論文提出一應用於晶片上網路之可適性路由演算法，用以提升晶片上網路之吞吐量並降低整體之網路延遲，進而提高網路效能。此演算法結合了“蟻群最佳化演算法”並應用“費洛蒙擴散”的概念來擴大能取得的網路資訊範圍，藉此提升網路封包傳遞的效率。“蟻群最佳化演算法”是由真實世界中之蟻群行為所啟發的最佳化演算法，而過去文獻中基於此演算法所開發出的網路路由演算法已被證實在分散網路流量方面有較高的能力。
本篇論文應用了“蟻群最佳化演算法”的概念，藉由費洛蒙資訊來提供時間軸上的歷史網路資訊，並且進一步結合了“費洛蒙擴散”的概念，透過費洛蒙的向外傳遞來交換空間軸上的網路資訊。有了空間軸以及時間軸上的網路資訊，各個路由器皆能擴大其網路資訊範圍，而此資訊範圍可透過演算法中各個參數的調整來改變其大小及形狀。根據分析，過去的相關研究諸如OBL、RCA以及ACO等技術所使用之網路資訊皆落在此範圍中。換言之，本篇論文所提出之演算法不僅能取得最大之網路資訊範圍，更可以藉由網路資訊範圍的調整來達到與過去各篇相關研究相同之網路效能。除此之外，本篇論文對演算法中各個參數所代表之物理意義以及效能影響進行探討，並完成了此演算法的路由器硬體架構設計及合成。綜合系統效能以及硬體成本進行分析，數據顯示所提之演算法在網路效能上有10.04%之改進，而在面積效率上也有最佳之表現。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T22:57:28Z (GMT). No. of bitstreams: 1 ntu-101-R99943047-1.pdf: 3636219 bytes, checksum: 8fed33bfa830e358768ff23a62201871 (MD5) Previous issue date: 2012 | en |
| dc.description.tableofcontents | CONTENTS
中文摘要 vii ABSTRACT viii CONTENTS ix LIST OF FIGURES xii LIST OF TABLES xiv Chapter 1 Introduction 1 1.1 Motivation and Goal 1 1.2 Routing on NoC 2 1.2.1 Adaptive Routing 4 1.2.2 Ant Colony Optimization-based Adaptive Routing 4 1.3 Problem Description 6 1.3.1 Problem of Information Acquirement 6 1.3.2 Information Region 6 1.4 Thesis Organization 7 Chapter 2 Related Works 9 2.1 Output Buffer Level (OBL) Selection 9 2.2 Neighbors-on-Path (NoP) Selection [15], [16] 10 2.3 Regional Congestion Awareness (RCA) Selection [17] 12 2.4 Ant Colony Optimization-based (ACO-based) Selection 14 2.4.1 Concept of Ant Colony Optimization 15 2.4.2 Original ACO-based Adaptive Routing in NoC [18] 16 2.4.3 Regional ACO-based Adaptive Routing [19] 17 2.4.4 Signal Wiring and Information Region of ACO 18 2.5 Summary 19 Chapter 3 ACO with Pheromone Diffusion 20 3.1 Main Concept 20 3.2 Comparison on Information Region 21 3.3 Proposed Algorithm 22 3.3.1 Modified State Transition Rule 23 3.3.2 Formation of Diffusive Pheromone 24 3.4 Design Parameters 26 3.4.1 ACO Weighting — 26 3.4.2 PhD Weighting — 27 3.5 Wordlengths of Design Parameters 28 3.5.1 Wordlength of — 28 3.5.2 Wordlength of — 28 3.6 Parameter Setting in ACO-PhD 29 3.7 Summary 31 Chapter 4 Performance Evaluation 32 4.1 Environment Setting for Simulations 32 4.2 Performance Evaluation and Comparison 32 4.2.1 Performances of Different Parameter Settings 33 4.2.2 Performance Comparison 34 4.3 Summary 38 Chapter 5 Architecture Design 39 5.1 Introduction to Router Architecture 39 5.2 Implementation of Proposed Algorithm 40 5.2.1 Fixed-Point Analysis on 40 5.2.2 Fixed-Point Analysis on 42 5.2.3 Fixed-Point Analysis on both and 43 5.2.4 Hardware Implementation of ACO-PhD 44 5.2.5 Analysis on Hardware Cost 46 5.3 Evaluation on Area Efficiency 47 5.4 Summary 49 Chapter 6 Conclusion and Future Work 50 6.1 Conclusion 50 6.2 Future Work 50 REFERENCE 52 | |
| dc.language.iso | en | |
| dc.subject | 可適性路由演算法 | zh_TW |
| dc.subject | 晶片上網路 | zh_TW |
| dc.subject | 蟻群最佳化演算法 | zh_TW |
| dc.subject | Network-on-Chip (NoC) | en |
| dc.subject | Adaptive Routing Algorithm | en |
| dc.subject | Ant Colony Optimization (ACO) | en |
| dc.title | 適用於晶片上網路系統的基於蟻群最佳化與費洛蒙擴散之可適性路由演算法 | zh_TW |
| dc.title | ACO-based Adaptive Routing with Pheromone Diffusion for Network-on-Chip Systems | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 100-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 盧奕璋(Yi-Chang Lu),李建模(Chien-Mo Li),呂學坤(Shyue-Kung Lu) | |
| dc.subject.keyword | 晶片上網路,可適性路由演算法,蟻群最佳化演算法, | zh_TW |
| dc.subject.keyword | Network-on-Chip (NoC),Adaptive Routing Algorithm,Ant Colony Optimization (ACO), | en |
| dc.relation.page | 54 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2012-08-09 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-101-1.pdf 未授權公開取用 | 3.55 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。