Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (5): 1470-1475.DOI: 10.11772/j.issn.1001-9081.2017102411

Previous Articles     Next Articles

Adaptive unicast routing algorithm for vertically partially connected 3D NoC

SUN Meidong, LIU Qinrang, LIU Dongpei, YAN Binghao   

  1. National Digital Switching System Engineering & Technological R & D Center, Zhengzhou Henan 450002, China
  • Received:2017-10-11 Revised:2017-12-20 Online:2018-05-10 Published:2018-05-24
  • Contact: 孙美东
  • Supported by:
    This work is partially supported by the National Science and Technology Major Project of the Ministry of Science and Technology of China (2016ZX01012101), the National Natural Science Foundation of China (61572520, 61521003).

面向非全互连3D NoC的自适应单播路由算法

孙美东, 刘勤让, 刘冬培, 燕昺昊   

  1. 国家数字交换系统工程技术研究中心, 郑州 450002
  • 通讯作者: 孙美东
  • 作者简介:孙美东(1993-),男,黑龙江哈尔滨人,硕士研究生,主要研究方向:三维片上网络路由算法;刘勤让(1975-),男,河南商丘人,研究员,博士,主要研究方向:宽带信息网络、片上网络设计;刘冬培(1985-),男,湖南永州人,博士,主要研究方向:芯片验证与测试;燕昺昊(1994-),男,山西吕梁人,硕士研究生,主要研究方向:流量识别、入侵检测。
  • 基金资助:
    国家科技重大专项(2016ZX01012101);国家自然科学基金资助项目(61572520,61521003)。

Abstract: Traditional TSV (Through Silicon Via) table in vertically partially connected three-Dimensional Network-on-Chip (3D NoC) only stores TSV address information, which easily causes network congestion. In order to solve this problem, a record table architecture was proposed. The record table stored not only the nearest four TSV addresses to the router, but also the input-buffer occupancy and fault information of the corresponding router. Based on the record table, a novel adaptive unicast routing algorithm for the shortest transmission path was proposed. Firstly, the coordinates of current node and destination node were calculated to determine the transmission mode of packets. Secondly, by using the proposed algorithm, whether the transmission path was faulty and got information of buffer occupancy was obtained simultaneously. Finally, the optimal transmission port was determined and the packets were transmitted to the neighboring router. The experimental results under two network sizes show that the proposed algorithm has obvious advantages in average delay and throughput compared with Elevator-First algorithm. Additionally, the rates of losing packet under Random model and Shuffle traffic model are 25.5% and 29.5% respectively when the network fault rate is 50%.

Key words: vertically partially connected three-Dimension Network-on-Chip (3D NoC), record table, adaptive unicast, average delay, throughput

摘要: 针对在非全互连三维片上网络(3D NoC)架构中的硅通孔(TSV)表只存储TSV地址信息,导致网络拥塞的问题,提出了记录表结构。该表不仅可以存储距离路由器最近的4个TSV地址,也可存储相应路由器输入缓存的占用和故障信息。在此基础上,又提出最短传输路径的自适应单播路由算法。首先,计算当前节点与目的节点的坐标确定数据包的传输方式;其次,检测传输路径是否故障,同时获取端口缓存占用信息;最后,确定最佳的传输端口,传输数据包到邻近路由器。两种网络规模下的实验结果表明,与Elevator-First算法相比,所提算法在平均延时和吞吐率性能指标上有明显的优势,且在网络故障率为50%时,Random和Shuffle流量模型下的丢包率分别为25.5%和29.5%。

关键词: 非全互连三维片上网络, 记录表, 自适应单播, 平均延时, 吞吐率

CLC Number: