基于贪心算法的3D-Mesh片上网络层间互联结构

doi:10.3969/j.issn.1000-3428.2016.09.010

计算机工程

基于贪心算法的3D-Mesh片上网络层间互联结构

吕天航,刘勤让,赵博

(国家数字交换系统工程技术研究中心,郑州 450002)

收稿日期:2015-09-08 出版日期:2016-09-15 发布日期:2016-09-15
作者简介:吕天航(1990-),男,硕士研究生,主研方向为片上网络路由算法;刘勤让,研究员;赵博,助理研究员、博士。
基金项目:
国家“863”计划基金资助项目(2014AA01A704);国家自然科学基金资助项目(61572520)。

Network on Chip Inter-layer Connection Structure for 3D-Mesh Based on Greedy Algorithm

Lü Tianhang,LIU Qinrang,ZHAO Bo

(China National Digital Switching System Engineering and Technological R & D Center,Zhengzhou 450002,China)

Received:2015-09-08 Online:2016-09-15 Published:2016-09-15

摘要/Abstract

摘要： 为改善3D-Mesh拓扑结构层间互联结构固定,难以应对网络流量变化的现状,提出一种基于贪心算法的自适应3D-Mesh层间互联结构。通过对网络参数进行实时测量,动态改变网络中硅通孔(TSV)的工作状态,使其自适应转变为最适合当前网络通信的路由器-TSV映射关系。实验结果表明,与全连接和部分连接3D-Mesh结构相比,该结构的网络资源分配更合理,且具有较高的网络吞吐量及较低的延时。

关键词: 三维片上网络, 层间互联, 贪心算法, 硅通孔, 实时测量

Abstract: To improve the 3D-Mesh topology inter-layer structure which is hard to deal with network traffic changing,an adaptive inter-layer structure for 3D-Mesh based on greedy algorithm is proposed.It measures network parameters in real-time,dynamically changes Through Silicon Via(TSV) working conditions,and adaptively transforms the most appropriate router-TSV mappings for current network.Experimental results show that compared with full accessed and partially accessed 3D-Mesh,this inter-layer structure is more reasonable in allocation of network resources,and it improves throughput and reduces latency.

Key words: 3D Network on Chip(3D-NoC), inter-layer connection, greedy algorithm, Through Silicon Vias(TSV), real-time measurement

中图分类号:

TP302

吕天航,刘勤让,赵博. 基于贪心算法的3D-Mesh片上网络层间互联结构[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2016.09.010.

Lü Tianhang,LIU Qinrang,ZHAO Bo. Network on Chip Inter-layer Connection Structure for 3D-Mesh Based on Greedy Algorithm [J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2016.09.010.

参考文献

参考文献［1］Viswanathan N,Paramasivam K,Somasundaram K.Exploring Hierarchical,Cluster Based 3D Topologies for 3D NoC［J］.Procedia Engineering,2012,30(9):606-615. ［2］Chen Y,Hu Jianhao,Ling Xiang.A Novel 3D NoC Architecture Based on De Bruijn Graph［J］.Computers & Electrical Engineering,2012,38(3):801-810. ［3］Cong J,Wei Jie,Zhang Yan.A Thermal-driven Floorplanning Algorithm for 3D ICs［C］//Proceedings of IEEE/ACM International Conference on Computer-aided Design.Washington D.C.,USA:IEEE Press,2004:306-313. ［4］Cong J,Zhang Yan.Thermal via Planning for 3-D ICs［C］//Proceedings of IEEE/ACM International Conference on Computer-aided Design.Washington D.C.,USA:IEEE Press,2005:745-752. ［5］Goplen B,Sapatnekar S.Thermal via Placement in 3D ICs［C］//Proceedings of 2005 International Symposium on Physical Design.New York,USA:ACM Press,2005:167-174. ［6］Kagami T,Matsutani H,Koibuchi M,et al.Headfirst Sliding Routing:A Time-based Routing Scheme for Bus-NoC Hybrid 3-D Architecture［C］//Proceedings of the 7th IEEE/ACM International Symposium on Networks on Chip.Washington D.C.,USA:IEEE Press,2013:1-8. ［7］Rahmani A M,Liljeberg P,Plosila J,et al.Developing a Power-efficient and Low-cost 3D NoC Using Smart GALS-based Vertical Channels［J］.Journal of Computer and System Sciences,2013,79(4):440-456. ［8］Miller F,Wild T,Herkersdorf A.Virtualized and Fault-tolerant Inter-layer-links for 3D-ICs［J］.Microprocessors and Microsystems,2013,37(8):823-835. ［9］谭海,何月顺,靳文兵,等.V-Mesh:面向三维堆叠芯片的低延时低功耗片上网络结构［J］.计算机学报,2014,37(10):2139-2152. ［10］Miyakawa N.A 3D Prototyping Chip Based on a Wafer-level Stacking Technology［C］//Proceedings of 2009 Asia and South Pacific Design Automation Conference.Washington D.C.,USA:IEEE Press,2009:416-420. ［11］Katti G,Stucchi M,de Meyer K,et al.Electrical Modeling and Characterization of Through Silicon via for Three-dimensional ICs［J］.IEEE Transactions on Electron Devices,2010,57(1):256-262. ［12］Yin A W,Xu T C,Yang B,et al.Change Function of 2D/3D Network-on-chip［C］//Proceedings of the 11th International Conference on Computer and Information Technology.Washington D.C.,USA:IEEE Press,2011:181-188. ［13］Xu T C,Liljeberg P,Tenhunen H.Optimal Number and Placement of Through Silicon Vias in 3D Network-on-chip［C］//Proceedings of the 14th International Sym-posium on Design and Diagnostics of Electronic Circuits & Systems.Washington D.C.,USA:IEEE Press,2011:105-110. ［14］Mohapatra P.Wormhole Routing Techniques for Directly Connected Multi-computer Systems［J］.ACM Computing Surveys,1998,30(3):374-410. ［15］Dally W J,Towles B P.Principles andPractices of Inter-connection Networks［M］.Amsterdam,the Netherlands:Elsevier,2004. ［16］Ebrahimi M,Chang X,Daneshtalab M,et al.DyXYZ:Fully Adaptive Routing Algorithm for 3D NoCs［C］//Proceedings of the 21st Euromicro International Conference on Parallel,Distributed,and Network-based Processing.Washington D.C.,USA:IEEE Computer Society,2013:499-503. 编辑陆燕菲

[1]	杨奔, 王炜晔, 赵婉婷, 谢瑾奎. 基于DQN的动态深度多分支搜索自动配载算法[J]. 计算机工程, 2020, 46(8): 313-320.
[2]	陈俞娴, 桂良启, 任利明, 周自成, 占美娟, 杨杰波, 郎量, 陈柯, 田加胜, 郭伟. 基于ARM与FPGA的气象微波辐射计测控系统设计[J]. 计算机工程, 2019, 45(8): 86-91.
[3]	孙美东, 刘勤让, 刘崇阳. 基于区域划分的非全互连3D NoC多播路由算法[J]. 计算机工程, 2019, 45(10): 57-63.
[4]	郑金金,罗志年. LTE-A系统载波聚合下基于贪心算法的资源管理[J]. 计算机工程, 2017, 43(11): 50-54.
[5]	魏浩,陈华锋,陈军. 基于路径覆盖的城市监控摄像网络优化部署方法[J]. 计算机工程, 2016, 42(5): 269-274.
[6]	张翔,朱明,孙吟龙,方雪峰. 网络电视直播中的虚拟频道生成算法[J]. 计算机工程, 2015, 41(12): 236-240.
[7]	凌权,李枚毅. 无线Mesh网络中骨干节点部署算法研究[J]. 计算机工程, 2015, 41(11): 147-152.
[8]	谢林，潘红兵，张宇昂，韩峰，李丽，何书专. 3D NoC网络架构设计[J]. 计算机工程, 2013, 39(9): 150-152.
[9]	程权, 廖名学, 胡晓惠, 何晓新. 超短波无线网络规划方法研究[J]. 计算机工程, 2013, 39(2): 61-66.
[10]	张佩云，宫秀文. 基于概率转移矩阵的社会网络影响最大化算法[J]. 计算机工程, 2013, 39(11): 41-45,51.
[11]	徐云峰, Rudolf Fleischer. 求解区间图K-连接最短路径问题的在线算法[J]. 计算机工程, 2012, 38(11): 51-52,55.
[12]	陈光平. 传感器网络节点选择的分布式在线算法[J]. 计算机工程, 2012, 38(10): 95-98.
[13]	翁鸣, 王吴静. 基于报童模型和贪心算法的订货管理系统[J]. 计算机工程, 2012, 38(01): 261-263,267.
[14]	孙泽宇, 邢萧飞, 魏巍. 无线传感器网络中的目标关联覆盖算法[J]. 计算机工程, 2011, 37(9): 138-140,143.
[15]	张志远, 徐涛, 冯霞. 航班信息抽取规则的自动生成技术[J]. 计算机工程, 2011, 37(6): 65-67.

基于贪心算法的3D-Mesh片上网络层间互联结构

Network on Chip Inter-layer Connection Structure for 3D-Mesh Based on Greedy Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10