分层立方体网络在NoC线性阵列中的最优嵌入

doi:10.11896/jsjkx.220100019

计算机科学 ›› 2023, Vol. 50 ›› Issue (4): 249-256.doi: 10.11896/jsjkx.220100019

分层立方体网络在NoC线性阵列中的最优嵌入

过汝燕¹, 王岩¹, 樊建席¹, 樊卫北²

1 苏州大学计算机科学与技术学院江苏苏州 215006
2 南京邮电大学计算机学院南京 210003

收稿日期:2022-01-04 修回日期:2022-05-16 出版日期:2023-04-15 发布日期:2023-04-06
通讯作者: 王岩(wangyanme@suda.edu.cn)
作者简介:(20205227015@stu.suda.edu.cn)
基金资助:
国家自然科学基金联合基金(U1905211);江苏高校优势学科建设工程资助项目

Optimal Embedding of Hierarchical Cubic Networks into Linear Arrays of NoC

GUO Ruyan¹, WANG Yan¹, FAN Jianxi¹, FAN Weibei²

1 School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
2 School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China

Received:2022-01-04 Revised:2022-05-16 Online:2023-04-15 Published:2023-04-06
About author:GUO Ruyan,born in 1998,postgra-duate.Her main research interests include parallel and distributed systems and graph embedding.
WANG Yan,born in 1977,Ph.D,asso-ciate professor.Her main research interests include parallel and distributed systems,interconnection architectures,social networks,algorithms and graph theory.
Supported by:
Joint Fund of the National Natural Science Foundation of China(U1905211) and Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.

摘要/Abstract

摘要： 随着大数据时代的到来,大规模计算的需求使得人们对芯片性能的要求日益提高,片上网络(Network-on-Chip,NoC)作为芯片内部以网络通信为中心的互连结构,在通信的各个方面实现了良好的平衡。NoC组件的物理布局及互连方式对芯片的总体性能(如信号延迟、电路成本等)有着很大的影响,因芯片面积有限,最小化连接组件的导线总长度,即最小化线长,被作为芯片设计的重点。分层立方体网络(Hierarchical Cubic Network,HCN)具有通信延迟低、可靠性和扩展性高等优点,而线性阵列是NoC常用的拓扑结构之一,将分层立方体网络移植到线性阵列上,就可以在线性阵列上模拟分层立方体网络的结构和算法。图嵌入是实现网络移植的关键技术。在图嵌入中,最小化导线总长度的目标可以通过求解具有最小线长的最优嵌入来达成。文中主要研究了分层立方体网络在线性阵列中的最优嵌入问题。首先,通过研究分层立方体网络的最优集,提出了分层立方体网络在线性阵列中的一种嵌入方案hel,并证明在嵌入方案hel下的线长相比其他嵌入方案下的线长是最小的,即hel为最优嵌入;然后给出了嵌入hel下线长的精确值以及一个时间复杂度为O(N)的嵌入算法,其中N为n维分层立方体网络的顶点数且N=2²ⁿ;其次,还给出了分层立方体网络在NoC上的线性物理布局算法;最后,通过对比实验评估了嵌入hel的性能。

关键词: 片上网络, 图嵌入, 线长, 分层立方体网络, 线性阵列

Abstract: With the advent of the era of big data,the demand of large-scale computing makes the requirements on the performance of chips constantly increasing.Network-on-Chip(NoC),as a network-communication-centered interconnection structure on chips,has achieved a good tradeoff in all aspects of communication.The physical layout and interconnection mode of NoC components have a significant impact on the overall performance of the chip(such as signal delay,circuit cost).Due to the limited area of the chip,minimizing the total length of wires connecting components,in other words,minimizing wirelength,is considered as the key of chip design.The hierarchical cubic network is an excellent interconnection network which has less communication delay,better reliability and greater scalability while the linear array is one of the common topologies of NoC.When the hierarchical cubic network is ported to the linear array,the structure and algorithm of hierarchical cubic network can be simulated on the linear array.Graph embedding is a key technology to realize network porting.In graph embedding,the goal of minimizing the total wire length can be achieved by finding the optimal embedding with minimum wirelength.This paper mainly studies the optimal embedding problem of hierarchical cubic networks into linear arrays with minimum wirelength.Firstly,by studying the optimal set of the hierarchical cubic network,an embedding scheme hel of hierarchical cubic networks into linear arrays is proposed,and it is proved that the wirelength under hel is minimum compared with other embedding schemes,that is, hel is an optimal embedding.Then,the exact value of the wirelength under hel and an embedding algorithm with O(N) time complexity are given,where N=2²ⁿ is the number of vertices of the n-dimensional hierarchical cube network.Furthermore,an algorithm of physical linear layout in NoC for hierarchical cubic networks is proposed.Finally,comparison experiments are conducted to evaluate the performance of embed-ding hel.

Key words: Network-on-Chip, Graph embedding, Wirelength, Hierarchical cubic networks, Linear arrays

中图分类号:

TP393

过汝燕, 王岩, 樊建席, 樊卫北. 分层立方体网络在NoC线性阵列中的最优嵌入[J]. 计算机科学, 2023, 50(4): 249-256. https://doi.org/10.11896/jsjkx.220100019

GUO Ruyan, WANG Yan, FAN Jianxi, FAN Weibei. Optimal Embedding of Hierarchical Cubic Networks into Linear Arrays of NoC[J]. Computer Science, 2023, 50(4): 249-256. https://doi.org/10.11896/jsjkx.220100019

参考文献

[1]WANG X J,SHI F,ZHANG H.KLSAT:An application mapping algorithm based on Kernighan-Lin partition and simulated annealing for a specific WK-recursive NoC architecture[C]//International Conference on Network and Parallel Computing.Springer International Publishing,2019:31-42.
[2]MOSTAFA A,TURKI F A.Topological properties of hierarchi-cal interconnection networks:a review and comparison[J].Journal of Electrical and Computer Engineering,2011,2011:1-12.
[3]GHOSE K,DESAI K R.Hierarchical cubic networks[J].IEEE Transactions on Parallel and Distributed Systems,1995,6(4):427-435.
[4]ZHOU S M,SONG S L,YANG X Y,et al.On conditional fault tolerance and diagnosability of hierarchical cubic networks[J].Theoretical Computer Science,2016,609:421-433.
[5]LIU Z,FAN J X,ZHOU J Y,et al.Fault-tolerant embedding of complete binary trees in locally twisted cubes[J].Journal of Parallel and Distributed Computing,2017,101:69-78.
[6]BOSSARD A,KANEKO K.Node-to-set disjoint-path routing in hierarchical cubic networks[J].Computer Journal,2012,55(12):1440-1446.
[7]LIU H Q,ZHANG S Z,LI D.On g-extra conditional diagno-sability of hierarchical cubic networks[J].Theoretical Computer Science,2019,790:66-79.
[8]LI X J,LIU M,YAN Z,et al.On conditional fault tolerance of hierarchical cubic networks[J].Theoretical Computer Science,2019,761:1-6.
[9]ZHAO S L,HAO R X,WU J.The generalized 4-connectivity of hierarchical cubic networks[J].Discrete Applied Mathematics,2021,289:194-206.
[10]FAN W B,FAN J X,LIN C K,et al.Embedding exchanged hypercubes into rings and ladders[C]//International Conference on Algorithms and Architectures for Parallel Processing.Sprin-ger International Publishing,2018:3-17.
[11]WANG W,QIAO L,TANG Z Z.Survey on the Networks-on-Chip interconnection topologies[J].Computer Science,2011,38(10):1-5.
[12]MANUEL P,RAJASINGH I,RAJAN B,et al.Exact wirelength of hypercubes on a grid[J].Discrete Applied Mathematics,2009,157(7):1486-1495.
[13]AROCKIARAJ M,ABRAHAM J,QUADRAS J,et al.Linear layout of locally twisted cubes[J].International Journal of Computer Mathematics,2017,94(1):56-65.
[14]SHALINI A J,ABRAHAM J,AROCKIARAJ M.A linear time algorithm for embedding locally twisted cube into grid network to optimize the layout[J].Discrete Applied Mathematics,2020,286:10-18.
[15]FAN W B,FAN J X,LIN C K,et al.Optimally embedding 3-ary n-cubes into grids[J].Journal of Computer Science and Techno-logy,2019,34(2):372-387.
[16]FAN W B,FAN J X,LIN C K,et al.An efficient algorithm for embedding exchanged hypercubes into grids[J].Journal of Supercomputing,2019,75(2):783-807.
[17]XIA J J,WANG Y,FAN J X,et al.Embedding augmented cubes into grid networks for minimum wirelength[C]//International Conference on Algorithms and Architectures for Parallel Processing.Springer International Publishing,2020:47-61.
[18]BEZRUKOV S L,CHAVEZ J D,HARPER L H,et al.Embedding of hypercubes into grids[C]//International Symposium on Mathematical Foundations of Computer Science.Springer,1998:693-701.
[19]STALIN MARY R,RAJASINGH I.Embedding of completegraphs and cycles into grids with holes[J].Procedia Computer Science,2020,172:115-121.
[20]PATEL A,KUSALIK A J,MCCROSKY C.Area-efficient VLSI layouts for binary hypercubes[J].IEEE Transactions on Computers,2000,49(2):160-169.

相关文章 15

[1]	李勇, 吴京鹏, 张钟颖, 张强. 融合快速注意力机制的节点无特征网络链路预测算法 Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism 计算机科学, 2022, 49(4): 43-48. https://doi.org/10.11896/jsjkx.210800276
[2]	杨辉, 陶力宏, 朱建勇, 聂飞平. 基于锚点的快速无监督图嵌入 Fast Unsupervised Graph Embedding Based on Anchors 计算机科学, 2022, 49(4): 116-123. https://doi.org/10.11896/jsjkx.210200098
[3]	梁瑶, 谢春丽, 王文捷. 基于图嵌入的代码相似性度量 Code Similarity Measurement Based on Graph Embedding 计算机科学, 2022, 49(11A): 211000186-6. https://doi.org/10.11896/jsjkx.211000186
[4]	宋立国, 胡承秀, 王亮. 众核处理器研究技术综述和分析 Summary and Analysis of Research on ManyCore Processor Technologies 计算机科学, 2022, 49(11A): 211000012-7. https://doi.org/10.11896/jsjkx.211000012
[5]	富坤, 郭云朋, 禚佳明, 李佳宁, 刘琪. 语义增强的完全不平衡标签网络表示学习算法 Semantic Information Enhanced Network Embedding with Completely Imbalanced Labels 计算机科学, 2022, 49(11): 109-116. https://doi.org/10.11896/jsjkx.210900101
[6]	邢长征, 朱金侠, 孟祥福, 齐雪月, 朱尧, 张峰, 杨一鸣. 兴趣点推荐方法研究综述 Point-of-interest Recommendation:A Survey 计算机科学, 2021, 48(11A): 176-183. https://doi.org/10.11896/jsjkx.201100021
[7]	范星冉, 宋国治, 李加正. 基于混合混沌大爆炸算法的三维片上网络低功耗映射 Low-power Mapping Method for Three-dimensional Network on Chip Based on Hybrid Chaotic Big Bang-big Crunch 计算机科学, 2019, 46(8): 100-105. https://doi.org/10.11896/j.issn.1002-137X.2019.08.016
[8]	李璐璐,裘雪红,周端,张剑贤. 片上网络容错技术研究 Research on Fault Tolerant Technology for Networks-on-Chip 计算机科学, 2018, 45(3): 305-310. https://doi.org/10.11896/j.issn.1002-137X.2018.03.050
[9]	方娟,刘士建,刘思彤. 一种异构片上网络路由算法的研究 Routing Algorithm Research on Heterogeneous Network on Chip 计算机科学, 2017, 44(3): 70-72. https://doi.org/10.11896/j.issn.1002-137X.2017.03.017
[10]	宋国治张大坤涂遥黄翠王莲莲. 一种改进的基于粒子群的三维片上网络优化布局算法 Improved Algorithm for 3D NoC Floorplan Based on Particle Swarm Optimization 计算机科学, 2015, 42(7): 114-117. https://doi.org/10.11896/j.issn.1002-137X.2015.07.024
[11]	侯睿武继刚. 有向无环图的高效归约算法 Efficient Reduction Algorithms for Directed Acyclic Graph 计算机科学, 2015, 42(7): 78-84. https://doi.org/10.11896/j.issn.1002-137X.2015.07.017
[12]	官铮,钱文华,杜长青. 具有服务质量保障的片上网络路由仲裁控制 On-chip Network Router Arbitration Control with QoS Support 计算机科学, 2015, 42(2): 55-59. https://doi.org/10.11896/j.issn.1002-137X.2015.02.012
[13]	王娟,杜海顺,侯彦东,金勇. 图嵌入投影非负矩阵分解图像特征提取方法 Graph Embedding Projective Non-negative Matrix Factorization Method for Image Feature Extraction 计算机科学, 2014, 41(8): 311-315. https://doi.org/10.11896/j.issn.1002-137X.2014.08.066
[14]	郭林林,李光顺,吴俊华. 基于虚拟通道非均匀分布的路由算法 Routing Algorithm Based on Non-uniform Distribution of Virtual Channel 计算机科学, 2014, 41(8): 164-168. https://doi.org/10.11896/j.issn.1002-137X.2014.08.036
[15]	陈亦欧,胡剑浩,凌翔. 片上网络业务量的自相似性分析及模型研究 Self-similarity Analysis and Modeling for On-chip Traffic 计算机科学, 2014, 41(12): 13-18. https://doi.org/10.11896/j.issn.1002-137X.2014.12.004

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

分层立方体网络在NoC线性阵列中的最优嵌入

Optimal Embedding of Hierarchical Cubic Networks into Linear Arrays of NoC

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0