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

Optimal Embedding of Hierarchical Cubic Networks into Linear Arrays of NoC

作　　者：过汝燕 王岩[1] 樊建席[1] 樊卫北 GUO Ruyan;WANG Yan;FAN Jianxi;FAN Weibei(School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China;School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006 [2]南京邮电大学计算机学院,南京210003

出　　处：《计算机科学》2023年第4期249-256,共8页Computer Science

基　　金：国家自然科学基金联合基金(U1905211);江苏高校优势学科建设工程资助项目。

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]