請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/62484完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 吳安宇 | |
| dc.contributor.author | Chia-An Lin | en |
| dc.contributor.author | 林家安 | zh_TW |
| dc.date.accessioned | 2021-06-16T16:03:09Z | - |
| dc.date.available | 2015-07-02 | |
| dc.date.copyright | 2013-07-25 | |
| dc.date.issued | 2013 | |
| dc.date.submitted | 2013-07-02 | |
| dc.identifier.citation | [1] D. Hodges, H. Jackson, and R. Saleh, “Analysis and design of digital integrated circuits: in deep submicron technology”, McGraw-Hill Science, July 2003.
[2] P. Magarshack and P. Paulin, “System-on-chip beyond the nanometer wall,” in Proc. Design Automation Conf., 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] L. Benini and G.D. Micheli, “Network on chip: a new paradigm for systems on chip design,” in Proc. IEEE Conf. on DATE, pp.418-419, March 2002. [7] M. Radetzki, C. Feng, X. Zhao, and A. Jantsch, “Methods for fault tolerance in network on chip,” ACM Computing Survey, vol. 44, pp. 1-36, Jan. 2013. [8] S. Furber, “Living with failure: lessons from nature?,” Journal of Educational Technology & Society, Vol. 00, pages 4-8, 2006. [9] Petersen K. and Oberg J., “Toward a scalable test methodology for 2D mesh network-on-chips.”, in Proc. Conf. on DATE, pp. 367–372, April 2007. [10] Grecu C., Pande P., Ivanov A., and Saleh R., “BIST for network-onchip interconnect infrastructures,” in Proc. IEEE VLSI test symposium, pp. 30–35, April 2006. [11] S.Y. Lin, W.C. Shen, C.C. Hsu, C.H. Chao, and A.Y. Wu, “Fault-tolerant router with built-in self-test/self-diagnosis and fault-isolation circuits for 2D-mesh based chip multiprocessor systems”. in Proc. IEEE Symposium on VLSI-DAT, pp 72–75, April 2009. [12] Raik J, Ubar R, and Govind V, “Test configuration for diagnosing faulty links in NoC switches,” in Proc. IEEE European Test Symposium, pp 29–34, May 2007. [13] Raik J, Govind V, and Ubar R, “Design-for-testability-based external test and diagnosis of mesh-like network-on-a-chips,” IET Comput Digit Tech 3, pp. 476–486, Sep. 2009. [14] Z. Zhang, A. Greiner, and S. Taktak, “A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh Network-on-Chip,” in Proc. ACM/IEEE Conf. on DAC, pp. 441-446, June 2008. [15] A. Mehranzadeh, A. Khademzadeh, and A. Mehran, “FADyAD- Fault and congestion aware routing algorithm based on DyAD algorithm,” in Proc. IEEE Conf. on IST, pp. 274-279, Dec. 2010. [16] I. Pratomo, and S. Pillement, “Gradient—An adaptive fault-tolerant routing algorithm for 2D mesh Network-on-Chips,” in Proc. DASIP, pp. 1-8, Oct. 2012 [17] S. Pasricha, and Y. Zou, “NS-FTR: A fault tolerant routing scheme for networks on chip with permanent and runtime intermittent faults,” in Proc. ASP-DAC, pp. 83–86, Jan. 2011. [18] M. Daneshtalab, and A. Sobhani, “NoC hot spot minimization using antnet dynamic routing algorithm,” in Proc. IEEE Conf. on ASAP, pp. 33-38, Sep. 2006. [19] Beckers R., Deneubourg J.L., and S. Goss. “Trails and U-turns in the selection of the shortest path by the ant Lasius niger.” Journal of Theoretical Biology, vol. 159, pp. 397–415, July 1992. [20] H.K. Hsin, E.J. Chang, C.H. Chao, and A.Y. Wu, “Regional ACO-based routing for load-balancing in NoC systems,” in Proc. IEEE Second World Congress on NaBIC, pp. 370-376, Dec. 2010. [21] K.Y. Su, H. K. Hsin, E.J. Chang, and A.Y. Wu, “ACO-based deadlock-aware fully-adaptive routing in network-on-chip systems,” in Proc. IEEE Workshop on SiPS, pp. 209-214, Oct. 2012. [22] “Noxim: the network-on-chip simulator,” http://sourceforge.net/projects/noxim, 2008. [23] G. Ascia, V. Catania, and M. Palesi, “Multi-objective mapping for mesh-based NoC architectures,” in Proc. IEEE Conf. on Hardware/Software Codesign and System Synthesis, pp. 182-187, Sep. 2004 [24] W.J. Dally and B. Towles, “Principles and practices of interconnection networks,” Morgan Kaufmann, Jan. 2004. [25] K.C. Chen, S.Y. Lin, W.C. Shen, and A.Y. Wu, “A scalable built-in self-recovery (BISR) VLSI architecture and design methodology for 2D-mesh based on-chip networks,” in Proc. Design Automation for Embedded Systems, vol.15, no.2, pp. 111-132, Jan. 2011. [26] S.Y. Lin, C.H. Huang, C.H. Chao, K.H. Huang, and A.Y. Wu, 'Traffic-balanced routing algorithm for irregular mesh-based on-chip networks,' IEEE Trans. on Computers, vol. 57, no. 9, pp. 1156-1168, Sep. 2008. [27] R. Gallager, “Low-Density Parity-Check Codes,” IRE Trans. Inf. Theory, vol. 7, pp. 21–28, Jan. 1962. [28] W.H. Hu et al., “Parallel LDPC decoding on a Network-on-Chip based multiprocessor platform,” in Proc. International Symposium Computer Architecture and High Performance Computing, pp. 35-40, Oct. 2009. [29] K.C. Chen, S.Y. Lin, H.S. Hung, A.Y. Wu, 'Topology-aware adaptive routing for non-stationary irregular mesh in throttled 3D NoC systems,' IEEE Trans. Parallel and Distributed Systems, pp. 1-11, Oct. 2012. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/62484 | - |
| dc.description.abstract | 本篇論文提出一應用於晶片上網路之錯誤感知路由演算法，用以容忍晶片上發生之錯誤，並在此環境中提升晶片上網路之吞吐量並降低整體之網路延遲，進而提高網路效能。此演算法是基於“蟻群最佳化演算法”與“蟻群錯誤容忍行為”的概念來進行設計，藉此提升網路封包傳遞效率與錯誤容忍能力。“蟻群最佳化演算法”是由真實世界中之蟻群行為所啟發的最佳化演算法，而過去文獻中基於此演算法所開發出的網路路由演算法已被證實在分散網路流量方面有較高的能力。而“蟻群錯誤容忍行為”是當蟻群遭遇突發障礙擋住行進路徑時所因應的行為，可分為三個步驟─遭遇、找尋、選擇。
本篇論文應用了“蟻群最佳化演算法”的概念，藉由費洛蒙資訊來提供時間軸上的歷史網路資訊，並且進一步結合了“蟻群錯誤容忍行為”的概念，提出三個與蟻群行為相對應的機制來增強傳統之路由演算法，使得各個路由器具有錯誤容忍之能力。根據實驗結果，本論文提出的演算法能有效地增加網路效能，以及提升網路容錯能力。除此之外，也完成了此演算法的路由器硬體架構設計及電路合成。綜合系統效能以及硬體成本進行分析，數據顯示本論文所提出之演算法在網路效能上有46.0%之改進，而在面積效率上也有最佳之表現。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T16:03:09Z (GMT). No. of bitstreams: 1 ntu-102-R00943012-1.pdf: 6105843 bytes, checksum: 1738c18e090a5c7bb35b3262e1800167 (MD5) Previous issue date: 2013 | en |
| dc.description.tableofcontents | 致謝 ………………………………………………………………………… vi
中文摘要 ………………………………………………………………………….viii ABSTRACT x CONTESTS xii LIST OF FIGURES xv Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Fault-tolerant NoC Scheme 4 1.2.1 Test and Diagnosis Mechanisms 5 1.2.2 Fault-tolerant Routing 6 1.3 Problem Description 7 1.4 Goal and Contribution 9 1.5 Thesis Organization 11 Chapter 2 Related Works 12 2.1 Turn Model Based Fault-tolerant Routing 12 2.2 Virtual Channels Based Fault-tolerant Routing 14 2.3 Ant Colony Optimization-based (ACO-based) Routing 14 2.3.1 Concept of Ant Colony Optimization 15 2.3.2 ACO-based Adaptive Routing in NoC 16 2.3.3 Regional ACO-based Adaptive Routing in NoC 17 2.3.4 ACO-based Deadlock-aware Fully-adaptive Routing in NoC 19 2.4 Summary 22 Chapter 3 Proposed ACO-based Fault-aware Routing (ACO-FAR) 23 3.1 Main Concept 23 3.2 Fault Model 24 3.3 Proposed Routing Algorithm 25 3.3.1 Notification mechanism of fault information 26 3.3.2 ACO-based fault-aware path searching mechanism 28 3.3.3 ACO-based fault-aware path selecting mechanism 30 3.4 Flowchart of Proposed Routing Algorithm 32 3.5 Summary 33 Chapter 4 Performance Evaluation 34 4.1 Environment Setting for Simulations 34 4.2 Performance Evaluation and Comparison 36 4.2.1 Evaluation and Comparison in Single-fault NoC 36 4.2.2 Evaluation and Comparison in Multiple-fault NoC 39 4.2.3 Normalized Performance Improvement 40 4.3 Fault-tolerance Ability 41 4.3.1 Unreachable Packet Ratio 41 4.3.2 Statistical Traffic Load Distribution 42 4.4 Summary 44 Chapter 5 Architecture Design 45 5.1 Introduction to Router Architecture 45 5.2 Implementation of Proposed Algorithm 46 5.2.1 Notification mechanism of fault information 46 5.2.2 ACO-based fault-aware path searching mechanism 47 5.2.3 ACO-based fault-aware path selecting mechanism 48 5.2.4 Implementation Results 49 5.3 Evaluation on Area Efficiency 51 5.4 Evaluation on Energy Consumption 52 5.5 Summary 55 Chapter 6 Conclusions and Future Work 57 6.1 Conclusions 57 6.2 Future Work 58 REFERENCE 59 | |
| dc.language.iso | en | |
| dc.subject | 晶片上網路:蟻群最佳化:錯誤容忍 | zh_TW |
| dc.subject | 錯誤感知機制 | zh_TW |
| dc.subject | 路由演算法 | zh_TW |
| dc.subject | 錯誤感知機制 | zh_TW |
| dc.subject | 路由演算法 | zh_TW |
| dc.subject | 晶片上網路:蟻群最佳化:錯誤容忍 | zh_TW |
| dc.subject | Ant colony Optimization | en |
| dc.subject | Network on Chip | en |
| dc.subject | Fault-aware mechanism | en |
| dc.subject | Routing algorithm | en |
| dc.subject | Fault-tolerant | en |
| dc.title | 適用於晶片網路系統的蟻群最佳化之錯誤感知路由演算法和架構設計 | zh_TW |
| dc.title | ACO-Based Fault-Aware Routing Algorithm and Architecture for Network-on-Chip Systems | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 101-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 盧奕璋,邱?德,呂學坤,黃穎聰 | |
| dc.subject.keyword | 晶片上網路:蟻群最佳化:錯誤容忍,路由演算法,錯誤感知機制, | zh_TW |
| dc.subject.keyword | Network on Chip,Ant colony Optimization,Fault-tolerant,Routing algorithm,Fault-aware mechanism, | en |
| dc.relation.page | 63 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2013-07-03 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-102-1.pdf 未授權公開取用 | 5.96 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。