請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/51610完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 吳安宇 | |
| dc.contributor.author | Yu-Yin Chen | en |
| dc.contributor.author | 陳毓茵 | zh_TW |
| dc.date.accessioned | 2021-06-15T13:41:05Z | - |
| dc.date.available | 2017-02-24 | |
| dc.date.copyright | 2016-02-24 | |
| dc.date.issued | 2015 | |
| dc.date.submitted | 2016-01-07 | |
| dc.identifier.citation | [1] ITRS, International Technology Roadmap for Semiconductors, http://public.itrs.net.
[2] J. A. Davis et al., “Interconnect Limits on Gigascale Integration (GSI) in the 21st Century,” Proc. IEEE, vol. 89, pp. 305-324, Mar. 2001. [3] R. Ho, K. W. Mai, and M. A. Horowitz, “The Future of Wires,” Proc. IEEE, vol. 89, pp. 490-504, Apr. 2001. [4] BONE, Basic On-Chip Network, http://ssl.kaist.ac.kr/ocn/. [5] W. J. Dally and B. Towles, “Route Packets, not Wires: On-Chip Interconnection Networks,” Proc. ACM/IEEE Design Automation Conf., pp. 684-689, 2001. [6] L. Benini and G. DeMicheli, “Networks on Chip: A New SoC Paradigm,” IEEE Computer, vol. 35, issue 1, pp. 70-78, Jan. 2002. [7] Y. Hoskote, S. Vangal, A. Singh, N. Borkar, and S. Borkar, “A 5-GHz Mesh Interconnect for A Teraflops Processor,” IEEE Micro, vol. 27, pp. 51-61, 2007. [8] J. Howard, S. Dighe, Y. Hoskote, S. Vangal et al., “A 48-Core IA-32 Message- passing Processor With DVFS in 45nm CMOS,” in Proc. International. Solid-State Circuits Conf., pp. 108-109, Feb. 2010. [9] Tilera TILE Processor, http://www.tilera.com/products/processors [10] E. Painkras, L.A. Plana, J. Garside, S. Temple, F. Galluppi, “SpiNNaker: A 1-W 18-Core System-on-Chip for Massively-Parallel Neural Network Simulation,” IEEE Journal of Solid-State Circuits, vol. 48, no. 8, pp. 1943-1953, Aug. 2013. [11] G. Chen et al., “A 340mV-to-0.9V 20.2 Tb/s Source-Synchronous Hybrid Packet/Circuit-Switched 16x16 Network-on-Chip in 22nm Tri-Gate CMOS,” in Proc. International. Solid-State Circuits Conf., pp. 276-278, 2014. 12] J.D.Owensetal.,“ResearchChallengesforOn-ChipInterconnectionNetworks,” IEEE Micro, vol. 27, issue 5, pp. 96-108, Sept.-Oct. 2007. [13] S. Furber, “Living with Failure: Lessons from Nature?,” in Proc. European Test Symposium (ETS), pp. 4-8, May 2006. [14] M. Radetzki, C. Feng, X. Zhao, and A. Jantsch, “Methods for Fault Tolerance in Networks-on-Chip,” ACM Computing Surveys, vol. 46, no. 1, pp. 8:1-8:38, Oct. 2013. [15] L.-T. Wang, C.-W. Wu, and X. Wen, “VLSI Test Principles and Architectures: Design for Testability,” San Francisco, 2006. [16] A.Singh,M.Shafique,A.Kumar,andJ.Henkel,“MappingonMulti/Many-core Systems: Survey of Current and Emerging Trends,” Proc. ACM/IEEE Design Automation Conf. (DAC), pp. 1-10, May 2013. [17] T. Dumitras, S. Kerner, and R. Marculescu, “Towards On-Chip Fault-Tolerant Communication,” in Proc. Asia and South Pacific Design Automation Conference, pp. 21-24, Jan. 2003. [18] M.Pirrettietal.,“FaultTolerantAlgorithmsforNetwork-on-ChipInterconnect,” in Proc. IEEE Symposium on VLSI, pp. 46-51, Feb. 2004. [19] Z.Zhang,A.Greiner,andS.Taktak,“AReconfigurableRoutingAlgorithmfora Fault-tolerant 2D-mesh Network-on-Chip,” in Proc. ACM/IEEE Design Automation Conf. (DAC), pp. 441-446, Jun. 2008. [20] I. Pratomo, and S. Pillement, “Gradient - An Adaptive Fault-tolerant Routing Algorithm for 2D Mesh Network-on-Chips,” in Proc. Design and Architectures for Signal and Image Processing (DASIP), pp. 1-8, Oct. 2012. [21] M.Ebrahimi,M.Daneshtalab,J.Plosila,F.Mehdipour,“MD:MinimalPath-based Fault-Tolerant Routing in On-chip Networks,” in Proc. ASP Design Automation Conf., pp. 35-40, Jan. 2013. [22] S.Pasricha,andY.Zou,“NS-FTR:AFaultTolerantRoutingSchemeforNetworks on Chip with Permanent and Runtime Intermittent Faults,” in Proc. ASP Design Automaton Conf., pp. 443-448, Jan. 2011. [23] A.Zinzuwadia,P.Parandkar,R.Verma,andS.Katiyal,“AnEfficientDeadlock- free NARCO Based Fault Tolerant Routing Algorithm in NoC Architecture,” International Journal of Emerging Technology and Advanced Engineering, vol. 2, issue 2, pp. 227-234, Feb. 2012. [24] Y.-H. Kuo et al., “Path-Diversity-Aware Adaptive Routing in Network-on Chip Systems,” IEEE International Symposium on Embedded Multicore SoCs (MCSoC), pp. 175-182, Sept. 2012. [25] G.-M.Chiu,“TheOdd-EvenTurnModelforAdaptiveRouting,”IEEETrans.on Parallel and Distributed Systems, vol. 11, no. 7, pp. 729-738, Jul. 2000. [26] E. Nilsson, M. Millberg, J. Oberg, and A. Jantsch, “Load Distribution with the Proximity Congestion Awareness in a Network on Chip,” in Proc. Design, Automation and Test in Europe, pp. 1126-1127, Mar. 2003. [27] G. Ascia, V. Catania and M. Palesi, “Implementation and Analysis of a New Selection Strategy for Adaptive Routing in Networks-on-Chip,” IEEE Transactions on Computer, vol. 57, no. 6, pp. 809-920, Jun. 2008. [28] W.-C. Tsai, K.-C. Chu, Y.-H. Hu, and S.-J. Chen, “Non-minimal, Turn-model Based NoC Routing,” Microprocessors and Microsystems, vol. 37, issue 8, pp. 899- 914, Nov. 2013. [29] K. V. Anjan, T. M. Pinkston, “An Efficient, Fully Adaptive Deadlock Recovery Scheme: DISHA,” International Symposium on Computer Architecture (ISCA), pp. 201-210, 1995. [30] SourceForge. (2008) Noxim: Network-on-Chip Simulator [Online]. Avaliable: http://sourceforge.net/projects/noxim [31] J. Hu and R. Marculescu, “Energy-Aware Mapping for Tile-Based NoC Architectures under Performance Constraints,” in Proc. ASP Design Automation Conf., pp. 233-239, Jan. 2003. [32] W.J.DallyandB.Towles,PrinciplesandPracticesofInterconnectionNetworks, Burlington, MA, USA: Morgan Kaufmann, 2004. [33] 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 Design Automation for Embedded System, vol. 15, no. 2, pp. 111-132, Jan. 2011. [34] S.Y.Lin,C.H.Huang,C.H.Chao,K.H.Huang,andA.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. [35] S.Y.Lin,W.C.Shen,C.C.Hsu,andA.Y.Wu,“Fault-tolerantRouterwithBuilt- in Self-test/Self-diagnosis and Fault-isolation Circuits for 2D-mesh Based Chip Multiprocessor,” International Journal of Electrical Engineering (IJEE), vol. 16, no. 3, pp. 213-222, Jun. 2009. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/51610 | - |
| dc.description.abstract | 在多核心處理器(Chip Multiprocessor, CMP)系統,為了提高資料傳輸的效率且 符合系統需求,晶片內網路(Network-on-Chip, NoC)系統已被提出為一個具備設計 彈性、系統可尺度化及設計可重複使用的解決方案。但隨著半導體製程的演進,晶 片內網路系統易遭受到製造缺陷,使其良率隨之降低。當晶片中含有這些缺陷的路 由器或連結,封包可使用的傳送路徑將會減少;進而導致系統壅塞、效能下降。因 此,由容錯路由演算法來保持系統功能的正確性變得不可或缺。
傳統容錯路由演算法使用區域性的錯誤位置資訊與緩衝器剩餘空間來處理錯 誤的問題。然而,這些區域性資訊只在短距離傳輸上有顯著性;為了達到容錯傳輸 與交通負載均衡,本篇論文提出路徑多樣性感知之路由演算法(PDA-FTR)。此演算 法透過路徑數量資訊中加入錯誤位置的資訊,使得路由器可察覺到遠距離的錯誤。 另外,為了同時探討錯誤與交通狀況的影響,PDA-FTR 將同時參考路徑數量與緩 衝器剩餘空間的資訊,選取具有高彈性與高傳輸能力之路徑。本篇論文提出之技術 相較於其他容錯路由演算法,可提升 29.0% - 132.9%的平均飽和吞吐量,並且只需 10.8%額外的硬體成本。 總結本論文所提出之設計方法,可以有效分散交通負載到不同的通道上,在一 個良好的效能與成本的設計平衡點上,完成容錯封包傳輸。 | zh_TW |
| dc.description.abstract | 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. With the increasing number of cores and the scaling of network in deep submicron (DSM) technology, the NoC systems become subject to manufacturing defects and have low production yield. Due to the fault issues, the reduction in the number of available packet routing paths may cause severe traffic congestion and performance degradation. Therefore, a fault-tolerant routing algorithm is required to maintain the correctness of system functionality and enhance effective yield.
To overcome fault problems, the conventional fault-tolerant routing algorithms employ fault information and buffer occupancy (BO) information of the local regions. However, the local information only provides a limited view of network status, thus, results in heavy traffic congestion. To achieve fault-resilient packet delivery and traffic balancing, this thesis proposes a Path-Diversity-Aware Fault-Tolerant Routing (PDA-FTR) algorithm which adopts Path Diversity (PD) in path selection. In PDA-FTR, fault information is integrated into PD, therefore, routers are aware of distant faults. To jointly evaluate the effect of faults and traffic status, PDA-FTR simultaneously considers PD and BO such that packets are routed on path with high adaptiveness and great transfer capability. Compared with other fault-tolerant routing algorithms, the proposed algorithm improves the average saturation throughput by 29.0% - 132.9% compared to the existing fault-tolerant routing schemes with only 10.8% hardware overhead. In summary, the proposed routing scheme can effectively balance traffic load and accomplish fault-resilient packet transmission. Moreover, PDA-FTR achieves a good trade-off between cost and performance. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T13:41:05Z (GMT). No. of bitstreams: 1 ntu-104-R02943029-1.pdf: 4784694 bytes, checksum: 983155d06569d79f43f7932cf97f7a4e (MD5) Previous issue date: 2015 | en |
| dc.description.tableofcontents | 致謝 vi
中文摘要 viii ABSTRACT ix CONTENTS x LIST OF FIGURES xiii LIST OF TABLES xvii Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Fault-Tolerant NoC Scheme 4 1.2.1 Test and Diagnosis Mechanism 5 1.2.2 Fault-Aware Task Re-Mapping 6 1.2.3 Fault-Tolerant Routing Algorithm 7 1.3 Goals and Contributions 8 1.4 Thesis Organization 9 Chapter 2 Related Works on Fault-Tolerant Routing Algorithm 10 2.1 Flooding-Based Fault-Tolerant Routing Algorithms 10 2.2 Turn-Restricted-Based Fault-Tolerant Routing Algorithms 12 2.3 Problems of Conventional Fault-Tolerant Routing Algorithms 15 2.4 Summary 17 Chapter 3 Proposed Path-Diversity-Aware Fault-Tolerant Routing (PDA-FTR) Algorithm 18 3.1 Fault Model 18 3.2 The Concept of Path Diversity 19 3.2.1 Definition of Path Diversity (PD) 19 3.2.2 Normalization of Path Diversity (NPD) 23 3.2.3 Analysis of Path Diversity with Router Delay Model 25 3.3 Proposed Routing Algorithm 30 3.3.1 Fault-Location-Based PD (FPD) 31 3.3.2 PDA-FTR Routing Function Using FPD 34 3.3.3 PDA-FTR Selection Function Using Effective Buffer Length (EBL) 37 3.4 Flowchart of Proposed Routing Algorithm 41 3.5 Summary 42 Chapter 4 Performance Evaluation 43 4.1 Simulation Environment and Setup 43 4.2 Performance Evaluation 45 4.2.1 Performance of PDA-FTR on Single-Fault NoC 45 4.2.2 Performance of PDA-FTR on Multiple-Fault NoC 50 4.2.3 Unreachable Packet Ratio 54 4.2.4 Statistical Traffic Load Distribution (STLD) 54 4.2.5 Performance Scalability 56 4.3 Summary 57 Chapter 5 Architecture Design 58 5.1 Introduction to Router Architecture 58 5.2 Implementation of Proposed Routing Algorithm 59 5.2.1 PDA-FTR Router Architecture 59 5.2.2 Cost Reduction on PDA-FTR Table 62 5.3 Evaluation on Area Efficiency 67 5.4 Summary 69 Chapter 6 Conclusions and Future Works 71 6.1 Conclusions 71 6.2 Future Works 72 REFERENCE 75 | |
| dc.language.iso | en | |
| dc.subject | 路徑多樣性 | zh_TW |
| dc.subject | 容錯路由演算法 | zh_TW |
| dc.subject | 晶片網路系統 | zh_TW |
| dc.subject | Path-Diversity | en |
| dc.subject | Fault-Tolerant Routing Algorithm | en |
| dc.subject | Network-on-Chip | en |
| dc.title | 適用於晶片網路系統的路徑多樣性感知之容錯路由演算法和架構設計 | zh_TW |
| dc.title | Path-Diversity-Aware Fault-Tolerant Routing Algorithm and Architecture for Network-on-Chip Systems | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 楊佳玲,呂學坤,盧奕璋 | |
| dc.subject.keyword | 容錯路由演算法,晶片網路系統,路徑多樣性, | zh_TW |
| dc.subject.keyword | Fault-Tolerant Routing Algorithm,Network-on-Chip,Path-Diversity, | en |
| dc.relation.page | 96 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-01-07 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-104-1.pdf 未授權公開取用 | 4.67 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。