广东工业大学学报 ›› 2017, Vol. 34 ›› Issue (05): 60-64.doi: 10.12052/gdutxb.160047

• 综合研究 • 上一篇    下一篇

一种片上网络路由算法的分析与优化设计

孙锋, 刘怡俊   

  1. 广东工业大学 计算机学院, 广东 广州 510006
  • 收稿日期:2016-03-16 出版日期:2017-09-09 发布日期:2017-07-10
  • 作者简介:孙锋(1989-),男,硕士研究生,主要研究方向为片上网络.
  • 基金资助:
    广东省科技计划项目（2015B090908001，2013A090100005，2014B090901061，2015B090903080）；广州市科技计划项目（2014Y2-00211）

Analysis and Optimization Design of Network-on-Chip Routing Algorithm

Sun Feng, Liu Yi-jun   

  1. School of Computers Science, Guangdong University of Technology, Guangzhou 510006, China
  • Received:2016-03-16 Online:2017-09-09 Published:2017-07-10

HTML

PDF (PC)

2971

摘要： 针对XY-YX算法局部路径选择单一、较容易出现拥塞热点区域、不能很好适应高速的网络数据传输等问题，提出一种无死锁路由算法（dead-lock free XY-YX）.该算法通过改进XY-YX路由算法，达到了减轻局部链路负载过重导致的热点问题的目的；此外，为了适应改进的路由算法，设计了一种无死锁结构的路由，避免了死锁的出现.在本文设计的无死锁路由架构上仿真后，结果表明，改进的路由算法，相比于XY路由算法和XY-YX路由算法，其网络平均延时与吞吐量均有所提升.

关键词: 路由算法, 无死锁路由, 片上网络

Abstract: To solve XY-YX routing algorithm's problem of choosing a single key path, liable to fall into hot spot region and cannot adapt to high speed network data transmission, a modified XY-YX routing algorithm with dead-lock free XY-YX routing is set up. The modified algorithm can release the burden of link circuit. What's more, in order to adapt to the modified algorithm, a dead-lock free route is put forward to avoid the dead-lock. Simulation result shows that the modified routing algorithm, experimented on dead-lock free route, can keep lower level latency and achieve higher network throughput than XY routing algorithm and XY-YX routing algorithm.

Key words: routing algorithm, dead-lock free route, network on chip

中图分类号: 

  • TP391
[1] 李超. 异步片上网络自动生成及模拟方法的研究[D]. 广州:广东工业大学计算机学院, 2014. [2] DALLY W J. Virtual-channel flow control[J]. IEEE Transactions on Parallel & Distributed Systems, 1992, 3(2):60-68. [3] 欧阳一鸣, 董少周, 梁华国. 基于2D Mesh的NoC路由算法设计与仿真[J]. 计算机工程, 2009, 35(22):227-229, 235.OUYANG Y M, DONG S Z, LIANG H G. Design and simulation of NoC routing algorithm based on 2D Mesh[J]. Computer Engineering, 2009, 35(22):227-229, 235. [4] DEHYADGARI M, NICKRAY M. Evaluation of pseudo adaptive XY routing using an object-oriented model for NOC[C]//The 17th International Conference on Microelectronics. Islamabad:IEEE, 2005:5pp, doi:10.1109/icm.2005.1590068. [5] YANG S, LI L, XU Y, et al. A power-aware adaptive routing scheme for network on a chip[C]//IEEE 20077th International Conference on ASIC. Guilin:Curran Associates, 2007:1301-1304. [6] LOTFI-KAMRAN P, RAHMANI A M, DANESHTALAB M, et al. EDXY-A low cost congestion-aware routing algorithm for network-on-chips[J]. Journal of Systems Architecture, 2010, 56(7):256-264. [7] JIANG S Y, CHEN L, LU Z, et al. Low latency routing algorithm simulation and hardware verification of NoC[C]//Electronic Engineering and Information Science:Proceedings of the International Conference of Electronic Engineering and Information Science 2015(ICEEIS 2015). Harbin:CRC Press, 2015:251-254. [8] AHMED A B, ABDALLAH A B. LA-XYZ:low latency, high throughput look-ahead routing algorithm for 3D network-on-chip (3D-NoC) architecture[C]//The 6th IEEE international symposium on embedded multicore SoCs. Aizu-Wakamatsu:IEEE,2012:167-174. [9] 王芳丽, 杜慧敏. 片上网络路由算法综述[J]. 西安邮电学院学报, 2007, 16(1):72-77.WANG F L, DU H M. The summary of network-on-chip routing algorithm[J]. Journal of Xi'an Institute of Posts and Telecommunications, 2007, 16(1):72-77. [10] 郭林林, 李光顺, 吴俊华. 基于虚拟通道非均匀分布的路由算法[J]. 计算机科学, 2014, 41(8):164-168, 177.GUO L L, LI G S, WU J H. Routing algorithm based on non-uniform distribution of virtual channel[J]. Computer Science, 2014, 41(8):164-168, 177. [11] SHIM K S, CHO M H, KINSY M, et al. Static virtual channel allocation in oblivious routing[C]//Proceedings of the 20093rd ACM/IEEE International Symposium on Networks-on-Chip. Washington D C:IEEE Computer Society, 2009:38-43. [12] JEONG Y S, LEE S E. Deadlock-free XY-YX router for on-chip interconnection network[J]. IEICE Electronics Express, 2013, 10(20):699-704. [13] MULLINS R, WEST A, MOORE S. Low-latency virtual-channel routers for on-chip networks[C]//2014 ACM/IEEE 41st International Symposium on Computer Architecture (ISCA). Washington D C:IEEE Computer Society, 2004:188-197. [14] LI M, ZENG Q A, JONE W B. DyXY-A proximity congestion-aware deadlock-free dynamic routing method for network on chip[C]//Proceedings of the 43rd annual Design Automation Conference. New York:ACM Press, 2006:849-852. [15] NICOPOULOS C A, PARK D, KIM J, et al. ViChaR:a dynamic virtual channel regulator for network-on-chip routers[C]//IEEE/ACM International Symposium on Microarchitecture. Orlando:IEEE, 2006:333-346.
[1] 张坤, 刘怡俊. 一种提高无缓存片上网络性能的方法[J]. 广东工业大学学报, 2017, 34(04): 97-101.
[2] 邹小武, 徐杜, 蒋永平, 周燕灿. ZigBee网络路由分析与节点设计[J]. 广东工业大学学报, 2010, 27(2): 89-92.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2017 《广东工业大学学报》编辑部
地址：广州市东风东路729号广东工业大学 邮编：510090
电话：020-37626653,020-37626139,020-37626396
邮箱：xbzrb@gdut.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发