跳到主要內容

臺灣博碩士論文加值系統

(35.173.42.124) 您好!臺灣時間:2021/07/26 14:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:黃群翔
研究生(外文):Chun-Hsiang Huang
論文名稱:適用於晶片內非規律網狀網路之交通均衡負載路由演算法
論文名稱(外文):Traffic-Balanced Routing Algorithm for Irregular Mesh-Based On-Chip Networks
指導教授:吳安宇吳安宇引用關係
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電子工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:55
中文關鍵詞:晶片內網路路由演算法非規則網狀網路
外文關鍵詞:On-chip networksrouting algorithmirregular mesh
相關次數:
  • 被引用被引用:0
  • 點閱點閱:77
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在未來奈米製程下,快速成長的電晶體數目與積體電路設計的複雜度上升將會是嚴重的問題,因此晶片內網路 (On-chip network) 被發表來解決這些問題。在晶片內網路中,實際上矽智產的面積大小並不會一樣,所以可以提供擺放不同大小矽智產的非規律網狀網路 (Irregular mesh) 是一個相當重要的概念。然而,適用於原本網狀網路的路由演算法 (Routing algorithm) 並不能直接套用在有尺寸過大之矽智產 (Oversized IP, OIP) 的非規律網狀網路上。為了能夠在傳送資料時能順利繞過OIP ,原本的路由演算法必須被修正。在多電腦(multicomputer) 系統裡,故障的網狀網路 (Faulty mesh) 在拓撲學上與非規律網狀網路是很相似的,而其容錯路由演算法 (Fault-tolerant routing algorithm) 已經被討論很多年了。然而,直接套用容錯路由演算法在非規律網狀網路上會造成下列兩大問題: 1) 在OIP 附近會有嚴重的交通負載以致於網路上的負載並不平均, 2) 有些封包的路徑過長。在這篇論文中,我們提出了一個避開OIP 預先路由演算法 (OIP avoidance pre-routing algorithm, OAPR) 以解決上述問題。OAPR可將交通負載平均分散到整個網路上,並且減少不必要的繞路行為,以縮短封包的路徑。所以,使用OAPR 的網路與傳統的容錯路由演算法相比有較低的延遲 (Latency) 以及較高的通量 (Throughput)。在我們的實驗中,有三個不同的例子證明OAPR 相較於其他兩種容錯路由演算法,增進了55.6% ~ 100%的通量。引用的兩個演算法分別為Chen and Chiu’s algorithm[15] 以及Extended XY routing algorithm [17]。最後,我們將演算法實現在硬體上,與整個晶片內的路由器 [24]比較起來,只佔不到1%的面積。因此,對於晶片內非網狀網路,OAPR 是一個既有優良效果並且易於實現的路由演算法。
On-chip networks (OCNs) have been proposed to solve increasing scale and complexity of the designs in nano-scale VLSI designs. In OCNs, the concept of irregular mesh is an important issue because IPs with different sizes can be supported. In order to solve routing on irregular mesh, modified routing algorithms to detour oversized IPs (OIPs) are needed. Fault-tolerant routing algorithms have been thought as solutions for irregular mesh because of the similar topology, faulty mesh, in multicomputer system. However, directly applying fault-tolerant routing algorithms may cause two serious problems: 1) heavy traffic loads around OIPs and unbalanced traffic loads on irregular meshes, 2) some paths of packets much longer than minimal path. In this thesis, we propose an OIP avoidance pre-routing (OAPR) algorithm to solve the aforementioned problems. OAPR can make traffic loads even spread on the networks, and shorten some paths of packets. Therefore, the networks using OAPR have lower latency and higher throughput than those using fault-tolerant routing algorithms. In our experiments, three different cases are simulated to demonstrate that proposed OAPR improve 55.6% ~ 100% sustainable throughputs than two cited fault-tolerant routing algorithm, Chen and Chiu’s algorithm [15] and extended XY routing algorithm [17]. Finally, we implement OAPR into hardware. The area overhead of OAPR is less than 1% compared to a whole router [24]. OAPR algorithm has good performance and is practical for irregular mesh-based OCNs.
Chapter 1 Introduction 1
1.1 Motivation and Goal 1
1.1.1 On-Chip Communication Trend 1
1.1.2 Network Performance vs. Routing Algorithm 3
1.1.3 Irregular Mesh 3
1.1.4 A Similar Topology – Faulty Mesh 4
1.1.5 Goal 6
1.2 Thesis Organization 6
Chapter 2 Previous Works 9
2.1 2-D Mesh 9
2.2 Odd-Even Turn Model [21] 10
2.3 Extended XY Routing [17] 11
2.4 Chen and Chiu’s Algorithm [15] 14
2.5 Faulty Mesh vs. Irregular Mesh 15
Chapter 3 Proposed OAPR Algorithm for Irregular Mesh 17
3.1 Overview 17
3.2 Default Routing 18
3.3 Single OIP 19
3.3.1 Blocked in Y Direction 19
3.3.2 Blocked in X Direction 20
3.4 Multiple OIPs 22
3.4.1 OIPs Placed Vertically 22
3.4.2 OIPs Placed Horizontally 23
3.5 F-chain 24
3.5.1 N-chain and S-chain 24
3.5.2 W-chain 26
3.6 Placement Restriction 28
3.7 Summary 30
Chapter 4 Performance Evaluation 31
4.1 Performance Evaluation Method 31
4.1.1 Static Analysis – Statistical Traffic Load Distribution 31
4.1.2 Dynamic Evaluation – SystemC Simulation 32
4.2 Case Studies 33
4.2.1 Case I: Single OIP 34
4.2.2 Case II: Multiple OIPs 36
4.2.3 Case III: F-ring and F-chains 38
4.3 OIP Placement Guidelines 40
4.3.1 One 3 × 3 OIP on 12 × 12 Mesh 40
4.3.2 One 4-Unit OIP on 12 × 12 Mesh 42
Chapter 5 Hardware Implementation 45
5.1 Hardware Implementation Issue 45
5.2 Table Reduction 48
5.3 Synthesis Results 49
Chapter 6 Conclusions and Future Works 51
6.1 Conclusions 51
6.2 Future Works 51
References 53
[1]ITRS, International Technology Roadmap for Semiconductors, http://public.itrs.net.
[2]J. A. Davis et al. “Interconnect Limits on Gigascale Integration (GSI) in the 21st Century,” Proc. IEEE, vol. 89, pp. 305-324, Mar. 2001.
[3]R. Ho, K. W. Mai, and M. A. Horowitz, “The Future of Wires,” Proc. IEEE, vol. 89, pp. 490-504, April. 2001.
[4]D. Sylvester and K. Keutzer, “A Global Wiring Paradigm for Deep Submicron Design,” IEEE Trans. CAD/ICAS, vol. 19, pp. 242-252, Feb. 2000.
[5]L. Benini and G. De Micheli, “Networks on Chips: A New SoC Paradigm,” IEEE Computer, vol. 35, pp. 70-78, Jan. 2002.
[6]P. Magarshack and P. G. Paulin, “System-on-Chip beyond the Nanometer Wall,” in Proc. DAC, Anaheim, 2003, pp. 419-424.
[7]S. Kumar et al., “A Network on Chip Architecture and Design Methodology,” in Proc. Int’l Symp. VLSI, 2002, pp. 105-112
[8]P. Guerrier and A. Greiner, “A Generic Architecture for On-Chip Packet-Switched Interconnections,” in Proc. DATE, Piscataway, N.J., 2000, pp. 250-256.
[9]K. Goossens, J. Dielissen, and A. Radulescu, “AEthereal Network on Chip: Concepts, Architectures, and Implementations,” IEEE Design and Test of Computers, vol. 22, pp. 414-421, Oct. 2005.
[10]S. G. Pestana et al. “Cost-Performance Trade-Offs in Networks on Chip: A Simulation-Based Approach,” in Proc. DATE, CNIT La Defese, Paris, France, 2004, pp. 764-769.
[11]BONE, Basic On-Chip Network, http://ssl.kaist.ac.kr/ocn/.
[12]D. Bertozzi and L. Benini, “Xpipes: A Network-on-Chip Architecture for Gigascale Systems-on-Chip,” IEEE Circuits Syst. Magazine, vol. 4, pp. 18-31, 2004.
[13]E. Bolotin, I. Cidon, R. Ginosar, and A. Kolodny, “QNoC: QoS Architecture and Design Process for Network on Chip,” Journal of Systems Architecture, vol. 50, pp. 105-128, Feb. 2004.
[14]M.K.F Schafer, T. Hollstein, H. Zimmer, M. Glesner, “Deadlock-Free Routing and Component Placement for Irregular Mesh-Based Networks-on-Chip,” in ICCAD, 2005, pp. 238-245
[15]K-H. Chen and G-M. Chiu, “Fault-Tolerant Routing Algorithm for Meshes without Using Virtual Channels,” Journal of Information Science and Engineering, vol.14, pp.765-783, Dec. 1998.
[16]R. V. Boppana and S. Chalasani, “Fault-Tolerant Wormhole Routing Algorithms for Mesh Networks,” IEEE Trans. Computer, vol. 44, pp. 848-864, 1995.
[17]Jie Wu, “A Fault-Tolerant and Deadlock-Free Routing Protocol in 2D Meshes Based on Odd-Even Turn Model,” IEEE Trans. Computers, vol. 52, pp. 1154-1169, Sept. 2003.
[18]R. Holsmark and S. Kumar, “Design Issues and Performance Evaluation of Mesh NoC with Regions,” in NORCHIP, Oulu, Finland, 2005, pp. 40-43.
[19]W.J. Dally, “Virtual-Channel Flow Control,” IEEE Trans. Parallel and Distributed Systems, vol. 3, pp. 194-205, Mar. 1992.
[20]G.J. Glass and L.M. Ni, “The Turn Model for Adaptive Routing,” J. ACM, vol. 40, pp. 874-902, Sept. 1994.
[21]G.M. Chiu, “The Odd-Even Turn Model for Adaptive Routing,” IEEE Trans. Parallel and Distributed Systems, vol. 11, pp. 729-737, July 2000.
[22]E. Bolotin, I. Cidon, R. Ginosar and A. Kolodny, “Routing Table Minimization for Irregular Mesh NoCs,” in DATE, Acropolis, Nice, France, 2007.
[23]J. Hu and R. Marculescu, “DyAD - Smart Routing for Networks-on-Chip,” in DAC, San Diego, Ca, 2004, pp. 260-263.
[24]J. Hu and R. Marculescu, “Smart Routing for Networks-on-Chip.” Technical report, ECE Department, Carnegie Mellon University, March 2004. Available at http://www.ece.cmu.edu/~sld/pubs.
[25]J. Hu and R. Marculescu, “Energy- and Performance-Aware Mapping for Regular NoC Architecture,” IEEE Trans. Computer-Aided Design of Integrated and Systems, vol. 24, pp. 551-562, Apr. 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top