臺灣博碩士論文加值系統

　　單晶片系統(SoC)為釵h應用提供整合的解決方法，例如電腦系統、通訊、多媒體與消費電子產品等。在設計單晶片系統時最重要的是如何使工作在不同頻率、具有不同特性的異質元件間能相互通訊。大部份現今的單晶片系統所使用的通訊架構是匯流排。當系統隨製程的進步到達一定的複雜度之後，晶片上的通訊將對系統效能、必v消耗、系統可靠度造成重要的影響。然而，使用匯流排的設計方式，將會受到限制並且沒有辦法達到這些需求。對於下一代單晶片系統，提出了一個以封包傳輸訊息來通訊各個元件的方式。這種將單晶片系統的內部架構視為由元件或模組所組成的網路，稱為晶片網路(network-on-chip, NoC)或微型網路(micronetwork)。
　　晶片網路系統提供設計者一個傳輸架構來將大量的異質IP區塊整合在一起。而為保障傳送的延遲時間和整體的生產率，電路交換之網路是較適合的晶片網路架構。但是，電路交換之網路需要一個排程演算法來建立傳送路徑並配置適當的頻寬給各個傳送路徑。
　　在這篇論文中，我們設計一個有效的排程演算法來使用在電路交換之網路架構．我們的設計提供一個新穎的解決方法。藉由我們設計的排程演算法，可以降低在電路交換之網路上交換器的成本及延遲時間。我們的演算法分為三個步驟。第一步驟中，我們先將已建立好的電路傳輸路徑對應到各個交換器上的輸入埠表格，再將這些輸入埠表格轉換成頻寬需求表。第二步驟是將頻寬需求表配置適當的輸出Time slot並計算其等候時間，之後再建立輸出時槽表。最後一個步驟是依需求將輸出時槽表做最佳化，將整體的等待時間降低。在實驗結果中，我們儘可能將數據表現出來以作未來改進之用。

　　System-on-chip (SoC) design provides integrated solutions to many applications such as computer systems, telecommunications, multimedia, consumer electronics, etc. One of the major challenges of designing a SoC chip is the communication architecture between heterogeneous components running different frequencies and possessing different characteristics. Most of the current communication architectures in SoC are based on dedicated wires and buses. As systems grow in complexity, the on-chip communication is expected to become critical for performance, power consumption, reliability, etc. However, the dedicated wiring and bus architectures have their limitation and do not meet these requirements. For next-generation SoC design, circuit-switched and packet-switched networks delivering messages between communicating components have been proposed. Such architecture is called network-on-chip (NoC) or micronetwork.
　　In this thesis, we propose a scheduling scheme that efficiently schedules the connections in the switches in circuit-switched NoC architectures. The cost and latency of the switch in the circuit-switched network can be lowered down with our scheduler. Our algorithm uses three steps to solve these scheduling problems in circuit-switched networks. We translate the connection requirement table of a switch to the bandwidth requirement table with contention freedom in the first step. The second step is to assign the bandwidth requirement table with proper time slots and also calculate the waiting time in the output time slot table. And the last step is to optimize the output time slot table depend on the requirements to lower down the total waiting time in the NoC architecture. For having even more improvement in the future, we show the simulation results of the proposed algorithm to validate our ideas.

第一章 導論.........................................................................1
1.1研究動機與目的.............................................................1
1.2論文組識.........................................................................2
第二章 晶片網路.................................................................3
2.1背景.................................................................................3
2.1.1晶片網路架構簡介......................................................4
2.1.2專用連線與晶片網路之比較......................................5
2.2晶片網路設計.................................................................6
2.2.1網路拓樸......................................................................8
2.2.2路徑安排....................................................................12
2.2.3交換技術....................................................................20
2.2.4晶片網路架構上的距離計算....................................24
2.3相關研究.......................................................................25
第三章 晶片網路排程演算法...........................................27
3.1排程演算法簡介...........................................................27
3.2區域性的問題與解決方法...........................................29
3.2.1 Bandwidth_Allocation( )............................................30
3.2.2 Pseudo Code of Bandwidth_Allocation( )..................39
3.3總體性的問題與解決方法...........................................41
3.3.1 Time_Slot_Allocation( ).............................................43
3.3.2 Pseudo Code of Time_Slot_Allocation( )...................44
3.4交換器上延遲時間的最小化.......................................46
3.4.1 Latency_Minimization( )............................................46
3.4.2 Pseudo Code of Latency_Minimization( )..................49
第四章 演算法實做與結果...............................................52
4.1採用架構簡述...............................................................52
4.1.1繞徑法則....................................................................53
4.2線路的建置...................................................................54
4.3頻寬配置程序...............................................................56
4.4時槽配置程序...............................................................59
4.5延遲時間最小化...........................................................63
4.6實做結果比較...............................................................67
第五章 結論與未來研究...................................................73
參考文獻............................................................................74

[1]L. Benini, G. De Micheli, “Networks on Chips: A New SoC Paradigm,” IEEE Computer, vol. 35, pp. 70 -78, Jan. 2002.
[2] W. J. Dally and B. Towels, "Route packets, not wires: On-Chip Interconnection Networks," Proceedings of 38th Design Automation Conference, June 2001, pp 684-689.
[3]S. Kumar, A. Jantsch, J.-P. Soininen, M. Forsell, M. Millberg, J. Oberg, K. Tiensyrja, A. Hemani, “A Network on Chip Architecture and Design Methodology,” Proceedings of the IEEE Computer Society Annual Symposium on VLSI, 2002 (ISVLSI.02), April 2002, pp 105-112.
[4]A. Hemani, A. Jantsch, S. Kumar, A. Postula, J. Oberg, M. Millberg, and D. Lindqvist, “Network on Chip: An Architecture for Billion Transistor Era,” Proceedings of IEEE NorChip Conference, Nov. 2000, pp. 166-173.
[5]J. Hu and R. Marculescu,”Exploiting the Routing Flexibility for Energy/Performance Aware Mapping of Regular NoC Architectures,” Proceedings of Design Automation and Test in Europe Conference and Exhibition, March 2003, pp. 688-693.
[6]T. Lei and S. Kumar, “A Two-step Genetic Algorithm for Mapping Task Graphs to a Network on Chip Architecture,” Proceedings of Euromicro Symposium on Digital System Design: Architectures, Methods and Tools, Turkey, Sept. 2003.
[7]J. Liu, L.-R. Zheng and H. Tenhunen, “A Guaranteed-Throughput Switch for Network-on-Chip,” Proceedings of International Symposium on System-on-Chip, 2003, Nov. 2003.
[8]S. Murali and G. D. Micheli, “Bandwidth-Constrained Mapping of Cores onto NoC Architectures,” Proceedings of Design Automation and Test in Europe Conference and Exhibition, pp. 869-901, Feb. 2004.
[9]J. Nurmi, I. Saastamoinen, and D. Siguenza-Tortosa, “Interconnect IP Node for Future System-on-Chip Designs,” Proceedings of 1st IEEE International Workshop on Electronic Design, Test and Applications (DELTA '02), Jan. 2002.
[10]P. P. Pande, C. Grecu, A. Ivanov, R. Saleh,” Design of a Switch for Network on Chip Applications,” Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS), Jan. 2003.
[11]E. Rijpkema, K. G. W. Goossens, A. Radulescu, J. Dielissen, J. Van Meerbergen, P. Wielage, and E. Waterlander, “Trade Offs in the Design of a Router with Both Guaranteed and Best-Effort Services for Networks on Chip,” Proceedings of Design Automation and Test in Europe Conference and Exhibition, March 2003.
[12]M. Sgroi, M. Sheets, A. Mihal, K. Keutzer, S. Malik, and J. Rabaey, and A. Sangiovanni-Vencentelli, “Addressing the System-on-a-Chip Interconnect Woes through Communication-Based Design,” Proceedings of 38th Conference on Design automation, June 2001.
[13]S. Sathe, D. Wiklund, D. Liu, “Design of a Switching Node (router) for on-chip networks,” Proceedings of the 6th International Conference on ASIC (ASICON 2003), Oct. 2003.
[14]Semiconductor Industry Association, International Technology Roadmap for Semiconductors, World Semiconductor Council, Edition 1999, 1999.
[15]D. Wiklund and D. Liu, “SoCBUS: Switched Network on Chip for Hard Real Time Embedded Systems,” Proceedings of International Parallel and Distributed Processing Symposium, April 2003.
[16]D. Wingard, “MicroNetwork-Based Integration for SOCs,” Proceedings of 38th Design Automation Conference, June, 2001.