隨著目前的科技和半導體製程不斷的進步，使單位面積內能夠容納的電晶體數量越來越多，並將許多功能融合在系統晶片(system-on-chip)來完成更多的工作。但隨著矽智產(intellectual property / IP)的數量越來越多，使匯流排架構沒辦法在提供有效的頻寬和效能，因此可能造成矽智產溝通變得困難。於是有學者將電腦網路的概念導入系統晶片的設計中，將IP視為網路上的節點(node)，以封包(packet)的概念使用繞徑器(router)來傳送資料，這種技術我們就叫晶片網路(network-on-chip)。
晶片網路的研究有諸多領域，有拓樸、流量控制、繞徑演算法等，許多演算法仍需要使用到路由表(routing table)，而拓樸的研究幾乎都是以相同大小的IP為主。在本論文中，我們改變一般TRAIN拓樸長樹方式，變更為中心長樹C-TRAIN，並不需要使用繞徑表，使TRAIN能夠在樹狀結構繞徑時，使用捷徑(shortcut)的優勢更為明顯。我們使用二維格狀網路，並加入大矽核心，並與其他演算法做比較，根據實驗的結果分析出格狀網路拓樸上的大矽核心的最佳擺放位置，使繞徑樹能夠提升在晶片網路上的整體效能。

With the rapid development of semiconductor technology, it has become feasible to integrate tens or even hundreds of intellectual properties (IP) cores on a single chip. Such highly integrated system-on-chip (SoC) can implement very complex functions on a single chip and achieve very high performance. However, as the number of on-chip IP cores increases, the conventional shared bus has suffered from the poor performance due to its inherent limited bandwidth. Recently, some researchers have introduced the concept of computer network into the design of SoC, treating IP cores as the nodes in the network. In such chips, data are interchanged between IP cores using packet switched network on the chip. Such design is called network-on-chip (NoC).
There are many research fields in Noc, such as topology, flow control, and routing algorithms. In this thesis, we focus on the routing for 2D mesh with variable-size IP cores. Many previously proposed algorithms assume the topology is based on the same size of IP, or use routing tables in the switch for irregular networks. This thesis focuses on the 2D mesh network with over-size IP cores. We employ our proposed algorithms TRAIN and C-TRAIN that do not require routing tables in our design. Based on the results of our simulations, we demonstrate the strategies for placing the over-size IP cores in the mesh to improve the overall performance of the NoC.

致謝 I
摘要 II
Abstract III
目錄 IV
圖目錄 VI
表目錄 XI
第一章 序論 1
1.1 研究動機與目的 1
1.2 論文架構 2
第二章 晶片網路 5
2.1 晶片網路概述 5
2.2 晶片網路架構 7
2.2.1 晶片網路拓樸 8
2.2.2 繞徑演算法與機制 11
2.2.3 死結避免 12
2.2.4 資料交換技術 14
2.2.5 虛擬通道 16
2.3 相關研究 18
2.3.2 Tree routing 18
2.3.3 Tree-Turn routing 20
2.3.4 L-Turn routing 21
第三章 TRAIN演算法 23
3.1 TRAIN演算法 23
3.1.1 建構網路拓樸 24
3.1.2 距離計算方式 25
3.1.3 路徑選擇 26
3.1.4 死結預防 27
3.2 C-TRAIN 28
3.2.1 建構網路拓樸 28
3.2.2 死結預防 33
第四章 實驗與數據評估 35
4.1 實驗環境 35
4.2 實驗分析 40
4.2.1 TRAIN與C-TRAIN 40
4.2.3 虛擬通道 49
4.2.3 效能分析 58
4.2.3 hotspot模擬分析 63
第五章 結論 77
參考文獻 79

[1] M. Ali, M. Welzl and M. Zwicknagl, “Networks on Chips: Scalable Interconnects for Future Systems on Chips,” Proceedings of European Conference on Circuits and Systems for Communications, Bucharest, Jul. 2008, pp. 240-245.
[2] A. Baghdadi, D. Lyonnard, N.E. Zergainoh and A.A. Jerraya, “An Efficient Architecture Model for Systematic Design of Application-Specific Multiprocessor SoC,” Proceedings of Conference on Design, Automation and Test in Europe, Munich, Mar. 2001, pp. 55-62.
[3] L. Benini and G. De Micheli, “Networks on Chips: A New SoC Paradigm,” IEEE Computer, vol. 35, Jan. 2002, pp. 70-78.
[4] D. Geist, G. Biran, T. Arons, M. Slavkin, Y. Nustov, M. Farkas, K. Holtz, A. Long, D. King and S. Barret, “A Methodology for the Verification of a System on Chip, ” Proceedings of the Design Automation Conference, Los Angeles, Jun. 1999, pp.574-579.
[5] S. Kumar, A. Jantsch, J.P. Soininen, M. Forsell, M. Millberg, J. Oberg, K. Tiensyrja and A. Hemani, “A Network on Chip Architecture and Design Methodology,” Proceedings of IEEE Computer Society Annual Symposium on Very Large Scale Integration, Pittsburgh, Apr. 2002, pp. 105-112.
[6] T. Schonwald, J. Zimmermann, O. Bringmann and W. Rosenstiel, “Network-on-Chip Architecture Exploration Framework,” Proceedings of Euromicro Conference on Digital System Design, Architectures, Methods and Tools, Patras, Aug. 2009, pp. 375-382.
[7] W.J Dally and B.Towles, “Route Packets, Not Wires: On-Chip Interconnection Networks,” Proceedings of the Design Automation Conference, Las Vegas, Jun. 2001, pp.684-689.
[8] A. A. Chien. “A cost and speed model for k-ary n-cube wormhole routers, ” IEEE Transactions on Parallel and Distributed Systems, vol.9, Feb. 1998, pp.150–162.
[9] L.M. Ni and P.K. McKinley, “A Survey of Wormhole Routing Techniques in Direct Networks,” IEEE on Computers, vol. 26, Feb. 1993, pp. 62-76.
[10] W. J. Dally, “Virtual-channel flow control”, IEEE Transactions on Parallel and Distributed Systems, vol.3, Mar. 1992, pp.194–204.
[11] J. Zhou, X.Y. Lin and Y.C. Chung, “A Tree-Turn Model for Irregular Networks ,” Proceedings of the International Symposium on Network Computing and Applications, Jul. 2006, pp.11-18.
[12] M. Koibuchi, A. Funahashi, A. Jouraku and H. Amano, “L-turn Routing: An Adaptive Routing in Irregular Networks,” Proceedings of IEEE International Conference on Parallel Processing, Sep. 2001, pp. 383-392.
[13] H.C. Chi and C.T. Tang, “A Deadlock-Free Routing Scheme for Interconnection Networks with Irregular Topologies,” Proceedings of International Conference on Parallel and Distributed Systems, Seoul, Dec. 1997, pp. 88-95.
[14] H.C. Chi and W.J. Wu, “Routing Tree Construction for Interconnection Networks with Irregular Topologies,” Proceedings of Euromicro Conference on Parallel, Distributed and Network-Based Processing, Genova, Italy, Feb. 2003, pp. 157-164.
[15] H.C. Chi and T.S. Chang, “Design of a Reconfigurable Pipelined Switch for Faulty On-Chip Networks,” Proc. International Conference on Parallel and Distributed Computing and Networks, Innsbruck, Feb. 2011, pp.51-56.