現今計算機系統已越來越發達，將多項功能整合在體積更小、高效能且低功耗的晶片上，因此在物聯網技術上的發展也越來越蓬勃。但在二維(2D)積體電路(integrated circuit/IC)架構已無法讓摩爾定律有效的向上發展，因此三維(3D) IC已是目前研究發展和矽穿孔(TSV)生產技術的重要課題。透過三維晶片的堆疊整合異質IC取得更好的效能。
而在內部鏈結網路(interconnection network)設計的優劣，將也會直接的影響效能，故連接網路的設計必須具低的傳輸延遲(low latency)、高輸出(high throughput)能力、以及容錯能力(fault tolerance)。
本輪文中將探討對於不同大小矽核心以及鏈結損毀之三維格狀(mesh)樹狀網路拓樸的繞徑情形，而目前已有相當多的研究演算法被提出。而本論文將以TRAIN (Tree-based Routing Algorithm for Irregular Networks)為基礎建立一個有容錯功能的擴展樹演算法C-TRAIN。
C-TRAIN (Center-rooted Tree-based Routing Algorithm for Irregular Networks)是將網路拓樸中心的節點設為root，並給定每個節點tree ID。當網路中有出現損毀的鏈結或節點時，可以容易的把它建立成新樹狀架構，並使用相關算法來做尋徑工作。

Nowadays, the advanced semiconductor technology allows us to integrate many complex functions into small efficient chips and achieve very high performance. With the advance of many areas such as Internet of things, the requirement of the functionality and performance for the chips is even higher. With traditional two-dimensional (2D) integrated circuits (IC) unable to keep Moore's law within ten years or so, three-dimensional (3D) IC has been proposed to overcome the problem.
The current research and development of through silicon via (TSV) technology provide and feasible approach to facilitate 3D implementation. In order to achieve low latency, high throughput, scalability and fault tolerance, the interconnection network of such 3D chips requires efficient routing algorithms and high-performance router design.
This thesis presents the design of the network-on-chip (NoC) fault-tolerant tree-based algorithms and architectures for future 3D VLSI chips. We focus on 3D mesh network routing with over-size IP cores and faulty links in the NoC. In such a network, the network topology is no longer a conventional mesh. This research realizes a fault-tolerant extended tree routing algorithm based on our previously proposed TRAIN (Tree-based Routing Algorithm for Irregular Networks), which is called C-TRAIN。
We study the strategies for placing our tree root and construct the spanning tree in the network with C-TRAIN. When there are faulty links or nodes in the network, a new embedded tree can be easily developed in the network. We demonstrate how to construct the trees in various networks, and compare them with some previously proposed routing algorithms. Our C-TRAIN shows that it can achieve good performance without using routing tables in the router.

第一章:概述 1
第一節:研究動機與目的 1
第二節:論文架構 2
第二章:晶片網路 3
第一節:晶片網路概述 3
第二節:相關研究 17
第三章:TRAIN 演算法與架構 23
第一節:TRAIN 繞徑演算法 23
第二節:C-TRAIN 擴展樹演算法 33
第四章:實驗與數據分析 55
第一節:實驗環境 55
第二節:實驗分析 57
第五章:結論與未來研究方向 125

[1] A. Sheibanyrad, F. Pe´trot, and A. Jantsch, 3D-Integration for NoC-Based SoC Architectures: Springer, 2011.

[2] B. S. Feero and P. P. Pande, "Networks-on-Chip in a Three-Dimensional Environment: A Performance Evaluation," IEEE Transactions on Computers , vol. 58, pp. 32-45, 2009.

[3] V. F. Pavlidis and E. G. Friedman, "3-D Topologies for Networks-on-Chip," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 15, pp. 1081-1090, 2007.

[4] H. C. Chi and W. E. Chiang, "Design of Tree-Based Routing for 3D Mesh On-Chip Networks," 2012.

[5] H. C. Chi and C. W. Shu , "Design and Evaluation of Fault-Tolerant Routing for Network-on-Chip Architectures," 2009.

[6] H. C. Chi and T. C. Tsung, "A Deadlock-Free Routing Scheme for Interconnection Networks with Irregular Topologies," 1997.

[7] H. C. Chi and L. F. Bin, "Design of an Algorithmic Router for 3D On-Chip Networks with Irregular Topologies," 2015.

[8] W. Dally and B. Towles, "Principles and Practices of Interconnection Networks," Morgan Kaufmann Publishers Inc. San Francisco, CA, USA ©2003.

[9] H. C. Chi and C. T. Yi, "Design of Tree-Based Shortcut Routing for 3D On-Chip Networks with Over-Size IP Cores," 2015.

[10] L. M. Ni and P. K. McKinley, "A survey of wormhole routing techniques in direct networks," Computer, vol. 26,pp. 62-76, 1993.

[11] W. J. Dally, "Virtual-channel flow control," Proceedings of 17th Annual International Symposium on Computer Architecture, 1990. pp. 60-68.

[12] N. Dahir, T. Mak, R. Al-Dujaily, and A. Yakovlev, "Highly adaptive and deadlock-free routing for three-dimensional networks-on-chip," Computers & Digital Techniques, IET, vol. 7, pp. 255-263, 2013.

[13] A. B. Ahmed and A. B. Abdallah, "LA-XYZ: Low Latency, High Throughput Look-Ahead Routing Algorithm for 3D Network-on-Chip (3D-NoC) Architecture," 2012 IEEE 6th International Symposium on Embedded Multicore Socs (MCSoC), pp. 167-174.

[14] A. Bartzas, N. Skalis, K. Siozios, and D. Soudris, "Exploration of Alternative Topologies for Application-Specific 3d Networks-on-Chip," Proceedings of Workshop Application Specific Processors (WASP), 2007.

[15] M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, T. L. Rodeheffer, et al., "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE Journal on Selected Areas in Communications, , vol. 9, pp. 1318-1335, 1991.

[16] F. Dubois, A. Sheibanyrad, Pe, x, F. trot, and M. Bahmani, "Elevator-First: A Deadlock-Free Distributed Routing Algorithm for Vertically Partially Connected 3D-NoCs," IEEE Transactions on Computers, vol. 62, pp. 609-615, 2013.

[17] H. C. Chi, Y. H. Jhang, and W. S. Chen, "Tree-Based Routing for Faulty On-Chip Networks with Mesh Topology," IEEE Computer Society Annual Symposium on in VLSI (ISVLSI), 2010 , pp. 321-326.

[18] H. C. Chi and W. J. Wu, "Routing tree construction for interconnection networks with irregular topologies," Processing of Eleventh Euromicro Conference on in Parallel, Distributed and Network-Based, 2003., pp. 157-164.
[19] J. Nan, D. U. Becker, G. Michelogiannakis, J. Balfour, B. Towles, D. E. Shaw, et al., "A detailed and flexible cycle-accurate Network-on-Chip simulator," in 2013 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), 2013, pp. 86-96.

[20] N. McKeown, "The iSLIP scheduling algorithm for input-queued routeres," IEEE/ACM Transactions on Networking , vol. 7, pp. 188-201, 1999.