臺灣博碩士論文加值系統

單晶片系統(System-on-a-Chip, SOC)為許多應用提供了整合的解決方案。然而，如何使工作在不同頻率、具有不同特性的異質元件相互通訊是設計時的主要挑戰之一。現在的單晶片系統在連接各矽智財模組及信號傳遞的方式，大都是使用匯流排方式，但傳輸線的延遲、電路的同步、雜訊與功率消耗等問題，將隨著製程演進而日益嚴重。未來單晶片系統內元件連線方式可能會借用目前電腦網路所使用的封包(packet)傳送的觀念。這種將單晶片系統的內部架構視為由元件或模組所組成的網路，稱為晶片網路(network-on-chip, NoC)。
在本篇論文中，我們提出階層式網格樹架構，乃模仿交通運輸之架構。例如我們在一個城市地區可以搭公共汽車，不同城市之間可以搭國內班機，國際間就需要使用國際班機。因此在長距離運輸上，將可大幅提昇其速度。在最底層為傳統之單層網格架構，而要往遠地傳輸時，就用第二層的星狀網格(Star-mesh)，來縮短移動距離，並在這層中在不增加硬體成本的考量下，採用調適性演算法，以增加通道使用效率。

In this paper, a new architecture for network on chip (NOC) called Mesh-Tree is presented first. Then, a deterministic routing algorithm and a nondeterministic routing algorithm are designed and simulated via a CAD tool written in C++ programming language. A Mesh-Tree is a multilayered, three dimensional, pyramidal architecture. Each layer is a mesh and trees are used to connect adjacent layers. This architecture is good for broadcasting and high speed communications. The simulation results show that this architecture for NOC can make the transportation much faster than the 2-D mesh architecture while the performance/cost ratio is relatively higher.
We use west-first algorithm in Mesh-Tree. We try to approach the flexibility of fully adaptive routing at the expense of a moderate increase in complexity with respect to deterministic routing. Most partially adaptive algorithms proposed up to now rely upon the absence of cyclic dependencies between channels to avoid deadlock.
Our proposals aim at maximizing adaptive without increasing the resources required to avoid deadlocks.

CONTENTS
CHINESE ABSTRACT i
ABSTRACT ii
ACKNOWLEDGEMENT vi
LIST OF TABLES vii
LIST OF FIGURES viii
1. Introduction 1
1.1 What is SOC1
1.2 Basic Switching Techniques 3
1.2.1 Circuit Switching 3
1.2.2 Packet Switching 3
1.2.3 Virtual Cut-Through (VCT) Switching 3
1.2.4 Wormhole Switching 5
1.2.5 Mad Postman Switching 7
1.2.6 Comparison of Switching Techniques 9
1.3 The layered approach of OSI Model 10
1.4 Deadlock, Livelock, and Starvation 13
1.4.1 Definition of Deadlock, Livelock and Starvation 13
1.4.2 Reasons for occurrence of Deadlock, Livelock and Starvation 15
1.4.3 Techniques to Solve Deadlock, Livelock, and Starvation----15
1.4.3.1 Solution to Deadlock 16
1.4.3.2 Solution to Livelock 17
1.4.3.3 Solution to Starvation18
1.5 Organization 19
2. Related Work 20
2.1 Network Design Considerations 20
2.2 Classification of networks 22
2.2.1 Share-Medium network 22
2.2.2 Direct network 25
2.2.3 Indirect network 28
2.2.4 Hybrid network 30
2.3 NOC System Design 32
2.4 Network on Chip Architecture 33
2.4.1 The NOC network 33
2.4.2 NOC resources 35
2.5 Generic router model 37
2.6 Advanced Microcontroller Bus Architecture 40
2.6.1 AMBA Buses 40
2.6.2 Arbitration 42
2.6.3 Bus Transfer 42
2.6.4 Bus Reset44
2.6.5 Test Interface 45
2.6.6 Advanced Peripheral Bus45
2.6.7 Advanced High-Performance Bus 47
2.7 Existing Proposals 49
2.7.1 Scalable, Programmable, Integrated Network (SPIN) 49
2.7.2 Fat-tree Architecture 50
2.7.3 A Binary Tree Based on Huffman Coding for NOC 53
3. Maximal-Profit Spanning Tree Architecture for NoC 57
3.1 Packet-Switching Technique 59
3.2 Switch Implementation 60
4. Mesh-Tree Architecture for Network-on-a-Chip Design 63
4.1 The New Architecture 64
4.2 The XY Routing Algorithm of the Mesh-Tree Topology 65
4.2.1 Performance Analysis 69
4.2.2 Cost Analysis 71
4.3 An Adaptive Router Design Based on Mesh-tree Architecture for Network-on-a-chip 72
4.3.1 Turn Model 72
4.3.2 XY Algorithm and West-First Algorithm 74
4.3.3 West-First Routing Algorithm for local router 75
4.3.4 Nonminimal West-First Algorithm for airport router 77
4.3.5 Case of possible routing channel 78
4.4 Switch Implementation 83
5. Results and Discussion 85
5.1 A CAD simulation tool 85
5.1.1 The platform and programming language 86
5.1.2 Operational step 86
5.1.3 The Output Files 89
5.2 Experiment Results 91
6. Conclusion 95
Reference 96
Publication List 100

[1] L. M. Ni and P. K. McKinley, “A survey of Wormhole Routing Techniques in Direct Networks”, IEEE on Computers, vol. 26, pp.62-76, February 1993
[2] J. Leijten et al., "Stream Communication between Real-Time Tasks in a High-Performance Multiprocessor", Proceedings of the 1998 DATE Conference, Paris, France, March 1998.
[3] A. Hemani, A. Jantsch, S. Kumar, A. Postula, J. Oberg, M. Millberg, and D. Lindqvist, “Network on Chip: An architecture for billion transistor era”, Proc. of the IEEE NorChip Conference, Nov. 2000.
[4] Pierre Guerrier and Alain Greiner, ”A Generic Architecture for On-Chip Packet-Switched interconnections”, Proceedings of the Conference on Design, Automation and Test in Europe, pp.250-256, March 27-30, 2000.
[5] Jian Liang, Sriram Swaminathan, and Russell Tessier, “a SOC: A Scalable, Single-Chip Communications Architecture”, 2000 International Conference on Parallel Architectures and Compilation Techniques (PACT'00), October 15 - 19, 2001, Philadelphia, Pennsylvania.
[6] Drew Wingard, "MicroNetwork-Based Integration for SOCs", Proceedings of IEEE Design Automation Conference, pp673—677, 2001.
[7] W. J. Dally and B. Towels, "Route, Packets, Not Wires: On-Chip Interconnection Networks," Proceedings of IEEE Design Automation Conference, pp. 684--689, 2001.
[8] “Virtual Component Interface Standard Version 2 On-Chip Bus DWG,” VSI, April 2001.
[9] Forsell, M.; Hemani, A.; Jantsch, A.; Kumar, S.; Millberg, M.; Oberg, J.; Soininen, J-P.; Tiensyrja, K., “A network on chip architecture and design methodology”, VLSI on Annual Symposium, IEEE Computer Society ISVLSI 2002, pp.105 –112, 2002.
[10] Benini, L.; De Micheli, G.; “Networks on chips: a new SoC paradigm”, IEEE Computer, Volume: 35 Issue: 1, pp. 70 -78, Jan 2002.
[11] Kumar, S.et al, ”A Network on Chip Architecture and Design Methodology.” Proceedings of ISVLSI 2002, pp. 117-124.
[12] W. Cesário et al., “Component-Based Design Approach for Multicore SoCs,” Proc. 39th Design Automation Conf. (DAC 02), ACM Press, pp. 789-794,New York, 2002,.
[13] Pande, P.P.; Grecu, C.; Ivanov, A.; Saleh, R., “Design of a switch for network on chip applications,” Circuits and Systems, 2003. ISCAS'03. pp.217 -220 vol.5, 25-28 May 2003.
[14] Wiklund, D.; Dake Liu; “SoCBUS: switched network on chip for hard real time embedded systems” Parallel and Distributed Processing Symposium, 2003. Proceedings. pp. 78 -85, April 22-26, 2003.
[15] K. keutzer, “Chip Level Assembly (and not Integration of Synthesis and Physical) is the Key to DSM Design”, Proceedings of the ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems (Tau’99), Monterey, CA, USA, March 1999.
[16] W.J.Dally and C.L. Seitz, “Deadlock-Free Message Routing in Multiprocessor Interconnection Networks”, IEEE Trans. on Computers, vol.36, no.5, pp.547-553, May 1987.
[17] ARM, AMBA Specification, available from www.arm.com
[18] W. Peterson. Design Philosophy of the Wishbone SoC Architecture. In Silicore Corporation, 1999. http://www.silicore.net/wishbone.htm.
[19] Axel Jantsch, Hannu Tenhumen, “Networks on Chip”, Kluwer Academic Publishers. Netherlands.2003.
[20] Duato, Yalamanchili, Ni, “Interconnection Networks: An Engineering Approach”, Morgan Kaufmann, 2002.
[21] Soininen, Jantsch, Forsell, Pelkonen, Kreku, Kumar, “Extending Platform-Based Design to Network on Chip Systems”. proceedings of the 16th international Conference on VLSI Design (VLSI’03), IEEE, 2003.
[22] Edwin Rijpkema, Kees Goossens, and Paul Wielage, “A router Architecture for Network on Silicon”, Proceedings of Progress 2001, 2nd Workshop on Embedded Systems.
[23] Yuan-Long Jeang, Jer-Min Jou, Win-Hsien Huang, “A Binary Tree Based Methodology for Designing an Application Specific Network-on-Chip (ASNOC)”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E88-A, No.12, Dec. 2005.
[24] ELLis Horowitz, Sartaj Sahni, and Dinesh Mehta”Fundamentals of Data Structures IN C++”

[25] H. Sullivan and T.R. Bashkow, “A large scale, homogeneous, fully distributed parallel machine,” Proceedings of the 4th International Synposium on Computer Architecture, March 1977
[26] Shih-Hsun Hsu, Jer-Min Jou, Yuan-Chin Wu, “New Routing Algorithms and Router Architecture Design for NOC,” The 15th VLSI Design/CAD Symposium, Taiwan, August 2004.
[27] C.J. Glass and L. M. Ni, “The turn model for adaptive routing,” Proceedings of the 19th International Symposium on Computer Architecture, pp. 278-287, May 1992.