WiNoC中交叉开关仲裁及路由算法设计

doi:10.12263/DZXB.20191304

电子学报 ›› 2021, Vol. 49 ›› Issue (3): 518-526.DOI: 10.12263/DZXB.20191304

WiNoC中交叉开关仲裁及路由算法设计

欧阳一鸣¹, 张鹏¹, 王奇², 安鑫¹, 梁华国²

1. 合肥工业大学计算机与信息学院, 安徽合肥 230009;
2. 合肥工业大学电子科学与应用物理学院, 安徽合肥 230009

收稿日期:2019-11-12 修回日期:2020-06-24 出版日期:2021-03-25 发布日期:2021-03-25
作者简介:欧阳一鸣 男,1963年生,博士,教授,中国计算机学会高级会员,研究方向:片上网络(NoC)与片上系统(SoC),嵌入式系统的综合与测试,数字系统设计自动化.E-mail:oyymbox@163.com;张鹏男,1997年生,硕士研究生,研究方向:片上网络(NoC)与片上系统(SoC),无线片上网络.E-mail:917292287@qq.com
基金资助:
国家自然科学基金项目（No.61874157）

Switch Arbitration and Routing Algorithm Design in WiNoC

OUYANG Yi-ming¹, ZHANG Peng¹, WANG Qi², AN Xin¹, LIANG Hua-guo²

1. School of Computer and Information, Hefei University of Technology, Hefei, Anhui 230009, China;
2. School of Electronic Science & Applied Physics, Hefei University of Technology, Hefei, Anhui 230009, China

Received:2019-11-12 Revised:2020-06-24 Online:2021-03-25 Published:2021-03-25
Supported by:

摘要/Abstract

摘要： WiNoC （Wireless Network-on-Chip）中的无线路由器面临着比传统片上路由器更加严峻的拥塞问题，平衡有线/无线链路负载是当前无线片上网络的研究热点之一.为此本文提出并设计了一种基于优先级的交叉开关仲裁方案PbSA （Priority based Switch allocator），其将优先级更高的无线数据包优先路由至无线路由器；结合PbSA提出了拥塞感知的路由算法CARA （Congestion-aware Routing Algorithm），该算法有效平衡有线/无线链路负载且避免死锁，提高了数据包在网络中的路由效率.此外，本文还提出了新颖的虚通道划分方法，它不仅减少了实现PbSA的硬件复杂度，而且缓解了无线路由器发生拥塞时对整个网络的影响.实验表明，虽然本文的方案引入了较小的面积和功耗开销，但是具有良好的流量自适应特性，从而在低注入率或高注入率的情况下较好的提升了网络性能.

关键词: 无线片上网络, 拥塞避免, 交叉开关仲裁, 路由算法, 虚通道

Abstract: Wireless routers in Wireless Network on Chip confronts more severe congestion problem,so balancing wired/wireless loading has become research focus in WiNoC recently.We propose a priority-based switch arbitration scheme,in which data packets more suitable for transmission through wireless channels are routed to wireless routers; We propose a CARA(congestion-aware routing algorithm) combined with PbSA,which efficiently balance wired/wireless loading and simultaneously avoid deadlock,improving data routing efficiency.Besides,we propose a new virtual channel partition method,which decreases hardware complex for implementing PbSA,and mitigates the adverse effect caused by wireless router congestion.Evaluation shows that the scheme we proposed achieve fine data flow adaptivity with small area and energy overhead,so to improve network performance and routing efficiency under low or high injection rate.

Key words: WiNoC, congestion avoidance, switch arbitration, routing algorithm, virtual channel

中图分类号:

TP302

欧阳一鸣, 张鹏, 王奇, 安鑫, 梁华国. WiNoC中交叉开关仲裁及路由算法设计[J]. 电子学报, 2021, 49(3): 518-526.

OUYANG Yi-ming, ZHANG Peng, WANG Qi, AN Xin, LIANG Hua-guo. Switch Arbitration and Routing Algorithm Design in WiNoC[J]. Acta Electronica Sinica, 2021, 49(3): 518-526.

参考文献

[1] Borkar S.Thousand core chips:a technology perspective[A].Proceedings of the 44th annual Design Automation Conference[C].San Diego:ACM,2007.746-749.
[2] Dally W J.Route packets,notwires:on-chip inteconnection networks[A].Proceedings of the 38th Annual Design Automation Conference[C].Las Vegas:IEEE,2001.684-689.
[3] Benini L,De Micheli G.Networks on chips:A new SoC paradigm[J].Computer,2002,35(1):70-78.
[4] Chao C H,Jheng K Y,Wang H Y,et al.Traffic and thermalaware runtime thermal management scheme for 3D NoC systems[A].IEEE International Symposium on Nocs[C].Grenoble:IEEE,2010.223-230.
[5] Joshi A,Batten C,Kwon Y J,et al.Silicon-photonic clos networks for global on-chip communication[A].2009 3rd ACM/IEEE International Symposium on Networks-on-Chip[C].La Jolla:IEEE,2009.124-133.
[6] Chang M F,Cong J,Kaplan A,et al.CMP network-on-chip overlaid with multi-band RF-interconnect[A].International Symposium on High Performance Computer Architecture[C].Salt Lake City:IEEE,2008.191-202.
[7] Mansoor N,Ganguly A.Reconfigurable wireless network-on-chip with a dynamic medium access mechanism[A].Proceedings of the 9th International Symposium on Networks-on-Chip[C].Vancouver:ACM,2015.1-8.
[8] Deb S,Ganguly A,Pande P P,et al.Wireless NoC as interconnection backbone for multicore chips:Promises and challenges[J].IEEE Journal on Emerging and Selected Topics in Circuits and Systems,2012,2(2):228-239.
[9] Rayess W,Matolak D W,Kaya S,et al.Antennas and channel characteristics for wireless networks on chips[J].Wireless Personal Communications,2017,95(4):5039-5056.
[10] Mamaghani S M,Jamali M A J.A load-balanced congestion-aware routing algorithm based on time interval in wireless network-on-chip[J].Journal of Ambient Intelligence and Humanized Computing,2019,10(7):2869-2882.
[11] Ganguly A,Chang K,Deb S,et al.Scalable hybrid wireless network-on-chip architectures for multicore systems[J].IEEE Transactions on Computers,2010,60(10):1485-1502.
[12] Kim R G,Choi W,Liu G,et al.Wireless NoC for VFI-enabled multicore chip design:performance evaluation and design trade-offs[J].IEEE Transactions on Computers,2016,65(4):1323-1336.
[13] Deb S,Chang K,Ganguly A,et al.Design of an efficient NoC architecture using millimeter-wave wireless links[A].Thirteenth International Symposium on Quality Electronic Design[C].Santa Clara:IEEE,2012.165-172.
[14] Hu W H,Wang C,Bagherzadeh N.Design and analysis of a mesh-based wireless network-on-chip[J].Journal of Supercomputing,2015,71(8):2830-2846.
[15] Rezaei A,Daneshtalab M,Palesi M,et al.Efficient congestion-aware scheme for wireless on-chip networks[A].Parallel,Distributed and Network-Based Processing[C].Heraklion:IEEE,2016.742-749.
[16] Rohbani N,Shirmohammadi Z,Zare M,et al.LAXY:A location-based aging-resilient Xy-Yx routing algorithm for network on chip[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2017,36(10):1725-1738.
[17] 黎建华,吴宁,胡永良,等.一种自适应的混合型无线NoC拓扑结构[J].电子学报,2016,44(6):1420-1428. LI Jian-hua,WU Ning,HU Yong-liang,et al.An adaptive hybrid wireiess NoC topoiogy structure[J].Acta Electronica Sinica,2016,44(6):1420-1428.(in Chinese)
[18] Liu S,Chen T,Li L,et al.FreeRider:Non-local adaptive network-on-chip routing with packet-carried propagation of congestion information[J].IEEE Transactions on Parallel and Distributed Systems,2014,26(8):2272-2285.
[19] 欧阳一鸣,何鑫城,梁华国,等.针对路径故障与局部拥塞的NoC容错路由算法[J].电子学报,2016,44(4):920-925. OUYANG Yi-ming,HE Xin-cheng,LIANG Hua-guo,et al.A fault tolerant routing algorithm aiming at a path fault and local congestion in NoC[J].Acta Electronica Sinica,2016,44(4):920-925.(in Chinese)
[20] 欧阳一鸣,陈静雯,梁华国,等.NoC中负载均衡的AVOQ路由器设计[J].电子测量与仪器学报,2017,31(1):92-98. OUYANG Yi-ming,CHEN Jing-wen,LIANG Hua-guo,et al.Design of load-balancing AVOQ router in network-on-chip[J].Journal of Electronic Measurement and Instrumentation,2017,31(1):92-98.(in Chinese)
[21] Catania V,Mineo A,Monteleone S,et al.Cycle-accurate network on chip simulation with noxim[J].ACM Transactions on Modeling and Computer Simulation,2016,27(1):1-25.
[22] 欧阳一鸣,钱昌,杜高明,黄正峰,李建华,梁华国.WiNoC中EF-ACK容错无线接口设计[J].电子学报,2018,46(11):2561-2570. OUYANG Yi-ming,QIAN Chang,DU Gao-ming,HUANG Zheng-feng,LI Jian-hua,LIANG Hua-guo,et al.Design of an EF-ACK fault-tolerate wireless interface in WiNoC[J].Acta Electronica Sinica,2018,46(11):2561-2570.(in Chinese)

WiNoC中交叉开关仲裁及路由算法设计

Switch Arbitration and Routing Algorithm Design in WiNoC

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	欧阳一鸣, 贾博远, 李建华, 黄正峰, 梁华国. WiNoC中无线通信拥塞与故障感知的容错路由算法[J]. 电子学报, 2020, 48(4): 662-669.
[2]	魏松杰, 王佳贺, 刘沛龙, 程浩. LEO星座中基于不完全信息的路由联盟博弈策略[J]. 电子学报, 2020, 48(10): 1923-1927.
[3]	欧阳一鸣, 李胜, 黄正峰, 梁华国, 安鑫. WiNoC中无线节点和无线链路级拥塞避免的高效路由器设计[J]. 电子学报, 2018, 46(4): 775-782.
[4]	马学彬, 王应彪, 高瑞超, 张晓娟. 具有传输成功率保证的概率路由算法的TTL预测模型[J]. 电子学报, 2018, 46(11): 2679-2687.
[5]	欧阳一鸣, 钱昌, 杜高明, 黄正峰, 李建华, 梁华国. WiNoC中EF-ACK容错无线接口设计[J]. 电子学报, 2018, 46(11): 2561-2570.
[6]	黎建华, 吴宁, 胡永良, 张肖强. 一种自适应的混合型无线NoC拓扑结构[J]. 电子学报, 2016, 44(6): 1420-1428.
[7]	欧阳一鸣, 何鑫城, 梁华国, 易茂祥, 杜高明, 安鑫. 针对路径故障与局部拥塞的NoC容错路由算法[J]. 电子学报, 2016, 44(4): 920-925.
[8]	刘春蕊, 张书奎, 贾俊铖, 林政宽. 机会网络中基于摆渡节点与簇节点相互协作的路由机制[J]. 电子学报, 2016, 44(11): 2607-2617.
[9]	何林波, 蒋定德, 仲维佳. 一种基于能效与频效的路由优化算法[J]. 电子学报, 2016, 44(10): 2314-2322.
[10]	马学彬, 白婧, 郑田玉. 机会网络中基于有权社团结构图的路由协议研究[J]. 电子学报, 2016, 44(10): 2449-2458.
[11]	邵星, 王翠香, 饶元. 基于跨层网络编码感知的无线传感器网络节能路由算法研究[J]. 电子学报, 2015, 43(12): 2484-2490.
[12]	罗成, 谢维信. 传感器网络拥塞避免与控制的模糊AQM算法[J]. 电子学报, 2014, 42(4): 679-684.
[13]	虞潇, 李丽, 张宇昂, 潘红兵, 王佳文, 韩平. 一种面向功耗免死锁三维全动态3DNoC路由算法[J]. 电子学报, 2013, 41(2): 329-334.
[14]	虞志刚, 向东, 王新玉. Torus网络中基于中心距离的完全自适应路由算法[J]. 电子学报, 2013, 41(11): 2113-2119.
[15]	姚磊;蔡觉平;李赞;张海林;王韶力. 基于内建自测技术的Mesh结构NoC无虚通道容错路由算法[J]. 电子学报, 2012, 40(5): 983-989.