Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19940
標題: 一種以統計流量為基礎的路徑選擇策略應用於晶片網路
A Statistical Traffic Analysis for Path Selection in Networks on Chip
作者: 林逸豪
Lin, Yi-Hao
關鍵字: 晶片網路
Networks on chip
擁塞
路徑選擇
congestion
path selection
出版社: 資訊科學與工程學系所
引用: [1]. Moore, and E. Gordon, "Cramming more components onto integrated circuits," IEEE Solid-State Circuits Newsletter, vol. 11, pp. 33-35, Sept. 2006. [2]. L. Benini, “Networks on chips: a new SoC paradigm,” IEEE Computer, vol. 31, pp.70-78, Jan. 2002. [3]. D. Bertozzi, and L. Benini, “Xpipes: a network-on-chip architecture for gigascale systems-on-chip,” IEEE Circuits and Systems Magazine, vol. 4, pp. 18-31, Feb. 2004. [4]. Wang Zhang, Ligang Hou, and Jinhui Wang, “Comparison Research between XY and Odd-Even Routing Algorithm of a 2-Dimension 3X3 Mesh Topology Network-on-Chip,” Global Congress Intelligent Systems, vol. 3, pp. 329-333, May 2009. [5]. H. Gu, J. Xu, K. Wang, and M. Hung, “A new distributed congestion control mechanism for networks on chip,” Telecommunication Systems, vol. 44, pp. 321-331, August 2010. [6]. G.M. Chiu, “The Odd-even turn model for adaptive routing,” IEEE Transactions on Parallel and Distributed Systems, vol. 11, pp. 729-738, July 2000. [7]. Jingcao Hu, and R. Marculescu, “DyAD smart routing for networks on chip,” Proc. Design Automation Conference, pp. 260-263, July 2004. [8]. Po-Tsang Huang, and Wei Hwang, “An adaptive Congestion-Aware Routing Algorithm for Mesh Networks on Chip Platform,” Proc. IEEE International SOC Conference, pp. 375-378, Sept. 2009. [9]. V. Catania, M. Palesi and D. Patti, “Neighbors-on-Path: A New Selection Strategy for On-Chip Networks,” Proc. IEEE/ACM International Federation for Information Procession, pp. 79-84, Oct. 2006. [10]. Masakazu Taniguchi, Hiroki Matsutani and Nobuyuki Yamasaki, “Design and Implementation of On-Chip Adaptive Router with Predictor for Regional Congestion,” IEEE Embedded and Real-Time Computing Systems and Applications, vol. 2, pp. 22-27, Aug. 2011. [11]. P. Gratz, B. Grot and S.W. Keckler “Regional congestion awareness for load balance in networks-on-chip,” Proc. IEEE High Performance Computer Architecture, pp. 203-214, Feb. 2008. [12]. R.S. Ramanujam and Bill Lin “Destination-based adaptive routing on 2D mesh networks,” Proc. IEEE Architecture for Networking and Communications Systems, pp. 1-12, Oct. 2010. [13]. P. Lotfi-Kamran, A.M. Rahmani, M. Daneshtalab and A. Afzali-Kusha “EDXY - A low cost congestion-aware routing algorithm for network-on-chips,” Journal of Systems Architecture, vol. 56, pp. 256-264, July 2010. [14]. U.Y. Ogras and R. Marculescu “Prediction-based Flow Control for Network-on-Chip Traffic,” Proc. IEEE Design Automation Conference, pp. 839-844, June 2006. [15]. P. Mohapatra, “Wormhole routing techniue for directily connected multicomputer systems,” ACM Computing Surveys, vol. 30, pp. 374-410, Sept. 1998. [16]. C. Glass and L. Ni, “The Turn Model for Adaptive Routing,” Journal of the Association for Computing Machinery, vol. 41, pp. 874-902, Sep. 1994. [17]. W. J. Dally, “Virtual-channel flow control,” IEEE Transaction on Parallel and Distributed Systems, vol. 3, pp. 194–205, Mar 1992. [18]. Minghua Tang, “A Novel Performance Metric of Routing Algorithm,” Proc. International Conference on Computer Science and Electronics Engineering, pp. 2859-2862, Jan. 2013. [19]. Sourceforge.net, Noxim: Network-on-chip simulator, 2008. [Online]. Available: http://noxim.sourceforge.net [20]. MPPA Manycore processor URL: http://www.kalray.eu/products/mppa-manycore/ [21]. An Efficient Network on Chip (NoC) for a Low-Power, Low-Area Homogeneous Many-Core DSP Platform URL: http://www.csee.umbc.edu/2012/04/ms-defense-chandler-on-efficient-network-on-chip-for-a-low-power-low-area-homogeneous-many-core-dsp-platform/ [22]. R.S. Ramanujam and Bill Lin “Destination-based adaptive routing on 2D mesh networks,” Proc. IEEE Architecture for Networking and Communications Systems, pp. 1-12, Oct. 2010. [23]. A.E. Kiasari, Zhonghai Lu and A. Jantsch, “An Analytical Latency Model for Networks-on-Chip, ” IEEE Transactions on Very Large Scale Integration Systems, vol. 21, pp. 113-123, Jan. 2013.
摘要: 隨著半導體科技的進步,越來越多的矽智財核心可整合在晶片內。這種現象將導致晶片內的流量將越來越大量,所以傳統系統晶片(System on Chip,SoC)的匯流排架構(Bus architecture)將無法負荷此龐大的資料量。於是晶片網路 (Networks on Chip,NoC)的概念被視為解決未來系統晶片溝通量大量增加的方法。 影響NoC效能的關鍵在於使用沒有死結的路由演算法以及有效率的路徑選擇策略。而路徑選擇策略的效能決定在於正確評估網路的擁塞狀況。傳統評估網路擁塞的方法是監控路由器內暫存器的使用率,但有兩種情況可能造成網路擁塞的誤判。 本論文提出一個路徑選擇策略,藉由結合路由器內暫存器的使用率以及分析路由器內暫存器的封包流量,可以更準確的評估網路擁塞情況以避開擁塞的節點。此策略的目標在於選擇適當的通道使封包以較短的等待時間傳送到的目的端。我們並且使用數學模型去分析未達到飽和封包注入率的狀況下,評估我們所提出的選擇策略它的平均封包傳送延遲。 實驗結果顯示在不同的流量型式下,我們提出的策略不只改善了odd-even路由演算法,也勝過其他路徑選擇策略在於傳送封包的平均延遲。
Recently, following the development of semiconductor technology, there are more and more intellectual property(IP) cores that are integrated together in a chip. Hence, chip creates more communication traffic, so the traditional bus architecture of system-on-chip(SoC) cannot support the huge traffic. Networks on chip(NoC) has become one of the promising candidates to solve the large communication demands of SoC systems. Deadlock-free routing and efficient path selection strategy are critical factors for the performance of NoC. If we accurately estimate congestion of the network, the performance of path selection strategy is increased. The traditional method is to monitor the buffer utilization of router to determine the congestion situation, but there are two cases which cannot determine the congestion situation of NoC. In this paper, we present a path selection strategy that can more precisely estimate the network situation to avoid congestion nodes by using buffer utilization and analyzing the packet direction from the buffer of the router. The proposed selection strategy aims to choose the suitable channel that transmits the packet to the destination and considers transmission delay as less as possible. We also proposed a mathematical analysis to obtain the average transmission packet delay in non-saturated packet injection rate . Simulation results show the proposed strategy that improves odd-even routing and outperforms the average transmission packet delay of other path selection strategies on different traffic scenarios.
URI: http://hdl.handle.net/11455/19940
其他識別: U0005-2208201319441800
文章連結: http://www.airitilibrary.com/Publication/alDetailedMesh1?DocID=U0005-2208201319441800
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.