臺灣博碩士論文加值系統

隨著晶片製程技術的進步，現今一個晶片上已可以容納超過一億個邏輯閘，因此晶片系統(system-on-a-chip)的設計將容許涵蓋數量龐大的IP核心，然而各個IP之間的訊息交換將會形成一項新的挑戰，因此近年晶片網路(Network-on-chip)架構被提出，它提供一個具良好延伸性並且可靠的晶片通訊方式。2D網格(mesh)拓墣架構在過去的NoC設計中被普遍的使用，因為它能使用簡單的路由演算法，並且具有好的網路延展性。但是由於2D網格拓墣有相對較大的網路半徑，造成有些長距離的封包傳送有較大的傳輸延遲。因此在這篇論文中我們針對傳統2D網格拓墣提出一個簡單的設計方法，概念是讓長距離封包傳送在額外的另一層網格拓墣。實驗實作一個大小為12 x12的雙層網格拓墣NoC，在分別以3x3和4x4個節點為群組的架構下，使用Uniformly Distributed 流量測試且和一般的網格拓墣比較，結果顯示最小的平均傳輸延遲分別降低32%和25%，而付出的面積成本為21.2%和11.9%。

With the development of deep submicron chip technology, a chip can pack more than a billion transistors nowadays. This capacity will allow the System-on-Chip (SoC) designs with a large amount of IP cores on a single chip. However, the inter-communication between IP cores becomes a new challenge. In recent years, Network-on-Chip (NoC) has been proposed to provide an on-chip communication infrastructure with better scalability and reliability. The 2D mesh is a very popular topology of previous NoC designs, because of the simplicity with designing its routing algorithm and network scalability. However, mesh has a relatively large average distance between any two nodes; hence some long distance traffic suffers from high transmission latency. In this thesis, we proposed an easy design method for 2D mesh NoC, the concept is letting the long distance traffic traverse on an additional Level-2 mesh. Simulation results demonstrate that it can reduce the transmission latency of long distance traffic. The 2-level 12x12 mesh with 3x3 sub-meshes and 4x4 sub-meshes can reduce the minimum latency of Uniformly Distributed traffic by 32%, and 25% compared to normal mesh architectures, the area overhead of routers are 21.2%, and 11.9%, respectively.

口試委員會審定書 #
誌謝 i
中文摘要 ii
ABSTRACT iii
CONTENTS iv
LIST OF FIGURES vi
LIST OF TABLES viii
Chapter 1 Introduction 1
1.1 Why Network on Chip 1
1.2 Basic Network on Chip Architecture 3
1.3 Thesis organization 4
Chapter 2 Related Work and Background 5
2.1 NoC topology 5
2.1.1 Meshes and Torus type topologies 5
2.1.2 Tree type topologies 7
2.1.3 Ring type topologies 8
2.2 Switching techniques 9
2.2.1 Communication unit 9
2.2.2 Circuit switching 10
2.2.3 Packet switching 11
2.2.4 Store-and-forward 11
2.2.5 Cut-through 12
2.3 Routing Basics 13
2.4 Virtual Channels 15
2.5 Router Structure 16
2.6 Related work 19
Chapter 3 The Proposed Method for Reducing the Latency in Mesh 20
3.1 Motivation 20
3.2 Network topology 21
3.3 Routing algorithm 24
3.3.1 Who route the long distance packets to Level-2 mesh 25
3.3.2 Route Packets on Level-2 Mesh 26
3.3.3 Packets classification 26
3.3.4 Routing alternatives 27
3.3.5 Deadlock avoidance 30
Chapter 4 Experimental results 33
4.1 Simulation infrastructure 33
4.2 Experimental results 36
Chapter 5 Conclusion 41
REFERENCE 42

[1]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," in VLSI, 2002. Proceedings. IEEE Computer Society Annual Symposium on, 2002, pp. 105-112.
[2]W. J. Dally and B. Towles, "Route packets, not wires: on-chip interconnection networks," in Design Automation Conference, 2001. Proceedings, 2001, pp. 684-689.
[3]L. Benini and G. De Micheli, "Networks on chips: a new SoC paradigm," Computer, vol. 35, pp. 70-78, 2002.
[4]M. Saneei, A. Afzali-Kusha, and Z. Navabi, "Low-latency Multi-Level Mesh Topology for NoCs," in Microelectronics, 2006. ICM ''06. International Conference on, 2006, pp. 36-39.
[5]L. Benini, and G.D. Micheli eds., Networks on Chips: Technology and Tools, Morgan Kaufmann, 2006.
[6]A. Mello, L. Tedesco, N. Calazans, and F. Moraes, "Virtual Channels in Networks on Chip: Implementation and Evaluation on Hermes NoC," in Integrated Circuits and Systems Design, 18th Symposium on, 2005, pp. 178-183.
[7]P. Guerrier and A. Greiner, "A generic architecture for on-chip packet-switched interconnections," in Design, Automation and Test in Europe Conference and Exhibition 2000. Proceedings, 2000, pp. 250-256.
[8]F. Karim, A. Nguyen, and S. Dey, "An interconnect architecture for networking systems on chips," Micro, IEEE, vol. 22, pp. 36-45, 2002.

[9]M. Coppola, R. Locatelli, G. Maruccia, L. Pieralisi, and A. Scandurra, "Spidergon: a novel on-chip communication network," in System-on-Chip, 2004. Proceedings. 2004 International Symposium on, 2004, p. 15.
[10]K. Goossens, J. Dielissen, and A. Radulescu, "AEthereal network on chip: concepts, architectures, and implementations," Design & Test of Computers, IEEE, vol. 22, pp. 414-421, 2005.
[11]W. J. Dally and B. Towles. Principles and Practices of Interconnection Networks, Morgan Kaufmann, 2004.
[12]Aline Vieira de Mello, Luciano Copello Ost, Fernando Gehm Moraes, and Ney Laert Vilar Calazans, "Evaluation of Routing Algorithms on Mesh Based NoCs," Technical Report Series, PUCRS, Brazil, May, 2004.
[13]R. Mullins, A. West, and S. Moore, "Low-latency virtual-channel routers for on-chip networks," in Computer Architecture, 2004. Proceedings. 31st Annual International Symposium on, 2004, pp. 188-197.
[14]L. S. Peh and W. J. Dally, "A delay model and speculative architecture for pipelined routers," in High-Performance Computer Architecture, 2001. HPCA. The Seventh International Symposium on, 2001, pp. 255-266.
[15]M. Saneei, A. Afzali-Kusha, and Z. Navabi, "Low-latency Multi-Level Mesh Topology for NoCs," in Microelectronics, 2006. ICM ''06. International Conference on, 2006, pp. 36-39.
[16]S. Bourduas and Z. Zilic, "A Hybrid Ring/Mesh Interconnect for Network-on-Chip Using Hierarchical Rings for Global Routing," in Networks-on-Chip, 2007. NOCS 2007. First International Symposium on, 2007, pp. 195-204.
[17]W. Dajin and C. Jiannong, "On optimal hierarchical configuration of distributed systems on mesh and hypercube," in Parallel and Distributed Processing Symposium, 2003. Proceedings. International, 2003, p. 8 pp.
[18]K. Amit, P. Li-Shiuan, K. Partha, and K. J. Niraj, "Express virtual channels: towards the ideal interconnection fabric," in Proceedings of the 34th annual international symposium on Computer architecture San Diego, California, USA: ACM, 2007.