分层立方体网络在NoC线性阵列中的最优嵌入_过汝燕.pdf

h t t p:/ww w.j s j k x.c o mD O I:1 0.1 1 8 9 6/j s j k x.2 2 0 1 0 0 0 1 9到稿日期:2 0 2 2-0 1-0 4 返修日期:2 0 2 2-0 5-1 6基金项目:国家自然科学基金联合基金(U 1 9 0 5 2 1 1);江苏高校优势学科建设工程资助项目T h i sw o r kw a ss u p p o r t e db yt h eJ o i n tF u n do f t h eN a t i o n a lN a t u r a l S c i e n c eF o u n d a t i o no fC h i n a(U 1 9 0 5 2 1 1)a n dP r o j e c tF u n d e db y t h eP r i o r i t yA c a d e m i cP r o g r a mD e v e l o p m e n to f J i a n g s uH i g h e rE d u c a t i o nI n s t i t u t i o n s.通信作者:王岩(w a n g y a n m e s u d a.e d u.c n)分层立方体网络在N o C线性阵列中的最优嵌入过汝燕1王 岩1樊建席1樊卫北21苏州大学计算机科学与技术学院 江苏 苏州2 1 5 0 0 62南京邮电大学计算机学院 南京2 1 0 0 0 3(2 0 2 0 5 2 2 7 0 1 5s t u.s u d a.e d u.c n)摘 要 随着大数据时代的到来,大规模计算的需求使得人们对芯片性能的要求日益提高,片上网络(N e t w o r k-o n-C h i p,N o C)作为芯片内部以网络通信为中心的互连结构,在通信的各个方面实现了良好的平衡。N o C组件的物理布局及互连方式对芯片的总体性能(如信号延迟、电路成本等)有着很大的影响,因芯片面积有限,最小化连接组件的导线总长度,即最小化线长,被作为芯片设计的重点。分层立方体网络(H i e r a r c h i c a lC u b i cN e t w o r k,HC N)具有通信延迟低、可靠性和扩展性高等优点,而线性阵列是N o C常用的拓扑结构之一,将分层立方体网络移植到线性阵列上,就可以在线性阵列上模拟分层立方体网络的结构和算法。图嵌入是实现网络移植的关键技术。在图嵌入中,最小化导线总长度的目标可以通过求解具有最小线长的最优嵌入来达成。文中主要研究了分层立方体网络在线性阵列中的最优嵌入问题。首先,通过研究分层立方体网络的最优集,提出了分层立方体网络在线性阵列中的一种嵌入方案h e l,并证明在嵌入方案h e l下的线长相比其他嵌入方案下的线长是最小的,即h e l为最优嵌入;然后给出了嵌入h e l下线长的精确值以及一个时间复杂度为O(N)的嵌入算法,其中N为n维分层立方体网络的顶点数且N=22n;其次,还给出了分层立方体网络在N o C上的线性物理布局算法;最后,通过对比实验评估了嵌入h e l的性能。关键词:片上网络;图嵌入;线长;分层立方体网络;线性阵列中图法分类号 T P 3 9 3 O p t i m a lE m b e d d i n go fH i e r a r c h i c a lC u b i cN e t w o r k s i n t oL i n e a rA r r a y so fN o CGUOR u y a n1,WANGY a n1,F ANJ i a n x i1a n dF AN W e i b e i21S c h o o l o fC o m p u t e rS c i e n c ea n dT e c h n o l o g y,S o o c h o wU n i v e r s i t y,S u z h o u,J i a n g s u2 1 5 0 0 6,C h i n a2S c h o o l o fC o m p u t e r,N a n j i n gU n i v e r s i t yo fP o s t sa n dT e l e c o mm u n i c a t i o n s,N a n j i n g2 1 0 0 0 3,C h i n a A b s t r a c t W i t ht h ea d v e n t o f t h e e r ao f b i gd a t a,t h ed e m a n do f l a r g e-s c a l e c o m p u t i n gm a k e s t h e r e q u i r e m e n t s o n t h ep e r f o r m a n c eo f c h i p sc o n s t a n t l y i n c r e a s i n g.N e t w o r k-o n-C h i p(N o C),a san e t w o r k-c o mm u n i c a t i o n-c e n t e r e d i n t e r c o n n e c t i o ns t r u c t u r eo nc h i p s,h a sa c h i e v e dag o o dt r a d e o f f i na l l a s p e c t so fc o mm u n i c a t i o n.T h ep h y s i c a l l a y o u ta n di n t e r c o n n e c t i o nm o d eo fN o Cc o m p o n e n t sh a v eas i g n i f i c a n t i m p a c to nt h eo v e r a l l p e r f o r m a n c eo f t h ec h i p(s u c ha ss i g n a l d e l a y,c i r c u i t c o s t).D u e t ot h e l i m i t e da r e ao f t h ec h i p,m i n i m i z i n gt h e t o t a l l e n g t ho fw i r e sc o n n e c t i n gc o m p o n e n t s,i no t h e rw o r d s,m i n i m i z i n gw i r e l e n g t h,i sc o n s i d e r e da s t h ek e yo f c h i pd e s i g n.T h eh i e r a r c h i c a l c u b i cn e t w o r k i s a ne x c e l l e n t i n t e r c o n n e c t i o nn e t w o r kw h i c hh a s l e s s c o mm u n i c a t i o nd e l a y,b e t t e rr e l i a b i l i t ya n dg r e a t e rs c a l a b i l i t yw h i l e t h e l i n e a ra r r a y i so n eo f t h ec o mm o nt o p o l o g i e so fN o C.W h e nt h eh i e r a r c h i c a l c u b i cn e t-w o r k i sp o r t e dt ot h e l i n e a r a r r a y,t h es t r u c t u r ea n da l g o r i t h mo fh i e r a r c h i c a l c u b i cn e t w o r kc a nb es i m u l a t e do nt h e l i n e a r a r r a y.G r a p he m b e d d i n g i s ak e y t e c h n o l o g y t or e a l i z en e t w o r kp o r t i n g.I ng r a p he m b e d d i n g,t h eg o a l o fm i n i m i z i n gt h e t o t a lw i r e l e n g t hc a nb ea c h i e v e db yf i n d i n gt h eo p t i m a le m b e d d i n gw i t hm i n i m u m w i r e l e n g t h.T h i sp a p e rm a i n l ys t u d i e st h eo p t i m a le m b e d d i n gp r o b l e mo fh i e r a r c h i c a l c u b i cn e t w o r k si n t ol i n e a ra r r a y sw i t hm i n i m u m w i r e l e n g t h.F i r s t l y,b ys t u d y i n gt h eo p t i m a ls e to ft h eh i e r a r c h i c a l c u b i cn e t w o r k,a ne m b e d d i n gs c h e m eh e lo f h i e r a r c h i c a l c u b i cn e t w o r k s i n t o l i n e a r a r r a y s i sp r o p o s e d,a n d i t i sp r o v e dt h a t t h ew i r e l e n g t hu n d e rh e li sm i n i m u mc o m p a r e dw i t ho t h e re m b e d d i n gs c h e m e s,t h a t i s,h e li sa no p t i m a l e m b e d d i n g.T h e n,t h ee x a c tv a l u eo f t h ew i r e l e n g t hu n d e rh e la n da ne m b e d d i n ga l g o r i t h m w i t hO(N)t i m ec o m p l e x i t ya r eg i v e n,w h e r eN=22ni st h en u m b e ro fv e r t i c e so f t h en-d i m e n s i o n a l h i e r a r c h i c a l c u b en e t w o r k.F u r t h e r m o r e,a na l g o r i t h mo f p h y s i c a l l i n e a r l a y o u t i nN o Cf o rh i e r a r c h i c a l c u b i cn e t w o r k s i sp r o p o s e d.F i n a l l y,c o m p a r i s o ne x p e r i m e n t s a r e c o n d u c t e d t oe v a l u a t e t