隨著半導體產業製程技術不斷的進步，晶片面積的縮小可容納更多的電晶體數目，擁有更多功能單元及效能也大幅提升，而系統晶片(system-on-chip / SoC)內封裝的矽智產(intellectual property，IP)數量也愈來愈多，在IP之間使用共享匯流排傳遞資料更加複雜，也造成雜訊與功率消耗增加的問題。因此將IP視為網路節點，以路由器(router)進行資料傳遞來增加效率，這樣的技術稱為晶片網路(network-on-chip / NoC)。
晶片網路的研究包含拓樸設計、繞徑方式、訊息交換、流量控制等，本論文將探討TRAIN (Tree-based Routing Architecture for Irregular Networks)以樹狀架構的繞徑演算法，在具不同大小矽核心的不規則網路拓樸下，以不同結構的樹狀建構方式完成網路拓樸。
C-TRAIN繞徑演算法，能減少封包傳送繞徑的距離和網路壅塞，與使用繞徑表(routing table)的演算法相比較，在傳送資訊的效率及硬體消耗更具優勢。實作使用booksim2.0模擬器，在完整的晶片網路架構下設計實驗，C-TRAIN演算法在不需要繞徑表的情況下，有相當優異的效能。

With continuous advance of semiconductor manufacturing technology, a single chip can contain more and more transistors. Hence, we can have chips with higher and higher complexity and computing capability. With the emergence of system-on-chip (SoC), we can put more silicon intellectual properties (SIP) in the chip. However, the communication interconnect on the chip, mostly shard buses, has to transmit more traffic between SIPs and eventually becomes a bottleneck for SoC. To solve the problem, network-on-chip (NoC) has been proposed to solve the problem.
There are many key research issues on NoC, including topology, routing, switching, and flow control. This thesis focuses on routing, and specifically our proposed TRAIN (Tree-based Routing Architecture for Irregular Networks) routing algorithm on 2D mesh with variable-size IP cores. We proposed and studied a particular C-TRAIN with different spanning trees on the 2D mesh with variable-size IPs and faulty components. We employed Booksim 2.0 simulator to evaluate the performance for different designs. Compared to the previously proposed lookup-table-based routing algorithms for irregular networks, our design achieve excellent performance without using the slow and costly routing tables.

第一章 概論
1.1 研究動機.............1
1.2 論文架構.............2
第二章 晶片網路
2.1 晶片網路背景.........3
2.2.1網路拓樸............6
2.2.2 繞徑方式與死結避免..9
2.2.3 訊息交換與流量控制..11
2.2.4 虛擬通道...........16
2.3 相關研究.............16
第三章 TRAIN演算法
3.1 TRAIN Routing.......19
3.2 建構拓樸與Tree ID....20
3.3 路徑距離計算.........21
3.4 死結預防.............23
3.5 C-TRAIN網路拓樸......25
3.6 樹狀繞徑影響..........31
第四章 實驗效能評估
4.1 實驗環境.............37
4.2 網路拓樸.............38
4.3 實驗結果與分析........42
4.4 虛擬通道差異..........48
4.5 Hotspot影響..........57
第五章 結論
參考文獻..................67

[1] 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.

[2] 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.

[3] 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.

[4] 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.

[5] 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.

[6] 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.

[7] L. Benini and G. DeMicheli, “Network-on-chips: A New SoC Paradigm,” IEEE Computer, vol. 35, no.1, Jan. 2002, pp. 70-78.

[8] Ville Rantala, Teijo Lehtonen, and Juha Plosila, “Network-on-Chip Routing Algorithms,” TUCS Technical Reports 779, Turku Centre for Computer Science, Aug. 2006

[9] Christopher J. Glass Lionel M. Ni, “The Turn Model for Adaptive Routing,” Proceedings of the 19th Annual International Symposium on Computer Architecture(ISCA ‘92), vol. 20, Issue 2, May. 1992, pp. 278-287

[10] P.M. Merlin and P.J. Schweitzer, “Deadlock Avoidance in Store-and-Forward Networks: Store-and-Forward Deadlock,” IEEE Transactions on Communications, Mar. 1980, pp. 345-354

[11] P. Kermani and L. Kleinrock, “Virtual Cut-Through: A New Computer Communication Switching Technique,” Computer Networks, vol.3,1979, pp. 267-286

[12] O. Lysne, “Deadlock Avoidance for Switchs Based on Wormhole Networks,” IEEE International Conference on Parallel Processing, Sep. 1999, pp. 68-74

[13] W. J. Dally, “Virtual-channel flow control”, IEEE Transactions on Parallel and Distributed Systems, vol.3, Mar. 1992, pp.194–204.

[14] 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.

[15] Jiazheng Zhou, Xuan-Yi Lin and Yeh-Ching Chung, “A Tree-Turn Model for Irregular Networks ,” Proceedings of the International Symposium on Network Computing and Applications, Jul. 2006, pp.11-18.

[16] H.C Chi and T.S Chang, “Design of a Reconfigurable Pipelined Switch for Faulty On-chip Networks,” Proceedings of International Conference on Parallel and Distributed Computing and Networks, Innsbruck, Feb. 2011, pp.51-56

[17] N. Jiang, D.U. Becker, G. Michaelogiannakis, J. Balfour, B. Towles, J. Kim and W.J. Dally, “A Detailed and Flexible Cycle-Accurate Network-on-Chip Simulator”, IEEE Performance Analysis of systems and Software (ISPASS), April 2013, pp. 86-96.

[18] N. McKeown, “The iSLIP scheduling algorithm for input-queued switches,” IEEE/ACM Transaction on Networking, vol.7, 1999, pp.188-201