多层3D芯片中硅通孔分布优化的改进算法

李德隆, 郝　聪, 吉村猛, 俞　晖

(1.上海交通大学 上海交通大学电子信息与电气工程学院,上海 200240;2.早稻田大学 IPS研究所,东京 169-8050)



多层3D芯片中硅通孔分布优化的改进算法

李德隆1, 郝聪2, 吉村猛2, 俞晖1

(1.上海交通大学 上海交通大学电子信息与电气工程学院,上海 200240;2.早稻田大学 IPS研究所,东京 169-8050)

摘要:3D芯片中硅通孔(TSV)的位置分布会对总线长造成很大影响,所以对于TSV位置分布的优化有许多算法,逐层进行TSV分配只能做到局部优化.提出用逆向重分配的方法对已有算法结果进一步优化以达到减少总线长的目的.同时提出了一种快速重分配以提高深度优化的运行时间.实验结果表明,对比逐层TSV分配方法,此逆向重分配方法可减少3.7%的总线长;此方法亦可对其他TSV分配算法(如逐网TSV分配、拉格朗日松弛算法等)所得结果作进一步线长优化;而快速重分配可将逆向重分配的运行时间降低为原来的10%.

关键词:3D芯片; 硅通孔(TSV); 逆向重分配; 线长优化

0概述

近年来,3D芯片已经成为研究者与开发者重点研究的课题.相比传统2D芯片,3D芯片可以在极大提高芯片性能的同时降低信号时延.而硅通孔(Through Silicon Via,TSV)作为3D芯片层与层之间的垂直连接,也受到了相当的关注.

全局最优化的TSV位置分配问题已经被证明是NP完全问题,而低优化度的TSV分配方法可能会导致芯片内布线总长的增加进而提高生产成本,针对TSV位置分配优化的问题已经有了很多相关研究与算法.逐层分配方法主要使用最小消费最大流模型逐层对所有TSV分配位置,此方法不考虑TSV所属不同节点网,使得每一层的TSV分配达到局部最优,却会导致同网的未分配层的TSV无法选取最优位置而引起冗余布线.逐网分配方法无视了TSV所属层而依次对每一个节点网分别进行TSV位置分配,其核心思想可等效为最短路径问题,此方法会使后期分配的TSV无法取到最优位置.

本文作者提出了逆向逐层重分配的方法对已有逐层算法所得结果进行深度优化,尽可能使总布线线长最小从而减小布线花费.实验仿真结果显示此方法可对原始逐层TSV分配方法所得结果有较好改善,同时此重分配方法亦适用于其他TSV分配方法.为了减少重分配运行时间,本文作者提出了快速重分配,通过替换最小消费最大流模型求解而使运算时间大幅度减少.

1系统模型与预操作

对于一个m层3D芯片,可将其从顶层到底层定义为layer0,layer1,…,layerm-1.如果一个节点网覆盖多于1层:layeri～layerj(i

1.1节点网分解

逐层TSV分配是对每一层上所有TSV同时分配位置,不考虑TSV所属节点网,这就要对所有节点网进行分解,使每一节点网上的节点根据所在层数分解为数个子网进而服务于TSV的分配.

如图1,节点网nt1={p1,…,p7}的7个节点分布在4层,若要连通此节点需插入3个硅通孔(TSV)pvia1、pvia2、pvia3,进而可以将nt1与插入的TSV节点根据所在不同层分解为4个子网:{p1,pvia1}、{p2,p3,pvia1,pvia2}、{p4,p5,p6,pvia2,pvia3}、{p7,pvia3}.若使布线长最短,则只需令4个子网的线长达到最优,研究中采用矩形半周长预测(HPWL)评估线长.

图1　节点网分解

1.2设定备选位置

为了计算方便,可将每一层都建立P*Q方格结构,定义每格面积为ws(g),这样对于可插入TSV的方格,其容量即可定义为ws(g)/A(v),其中A(v)为TSV所占面积.对于TSV,该层所有容量大于等于1的方格皆可成为其备选位置,为了降低时间复杂度,设定一个备选范围,其初始范围为子节点网(不含TSV节点)所有节点圈定的矩形,若其内方格总容量不大于1,则扩展此范围直到容量大于等于1.

2逆向重分配算法

2.1逐层TSV分配

逐层TSV分配是基于最小消费最大流模型的TSV位置分配算法,此算法不考虑TSV所隶属的节点网而只关注当前层所有待插入TSV的分配问题,使当前层上所有子节点网线长达到最优.原始的逐层分配算法是局部最优算法,当前所分配TSV的位置可能会造成未分配层的布线冗余.图2为原始逐层分配所引起冗余布线的说明.从顶层layer 0开始逐层布线,分配pvia2时,并没有考虑layer 2上子节点网的信息,而在选择pvia2时,所有在pvia1与p3所构成的备选范围内的方格都被判断为最优位置而随机选择其中之一.然而此位置可能导致layer 2上子节点网的线长增加,如图2中所示,虚线为插入pvia2时的更佳位置,若可以将pvia2重新分配到虚线位置,则可以达到优化布线总长的目的.

图2　原始逐层TSV分配算法缺点

2.2最小消费最大流模型

逐层分配与逆向重分配的核心就是利用最小消费最大流模型解决当前层的TSV分布.利用最小消费最大流算法解决TSV分配问题,首先要建立流图.

定义1二分图G(V,E)代表该层所有待分配TSV与所有方格.

(1)V(G)=Vv∪Vg,其中Vv={vi|i=1,…,kv}表示所有该层待分配TSV,Vg={wj|j=1,…,kg}为方格集合;

(2)E(G)={(vi,wj)|vi∈Vv,wj∈Vg},其中wj为vi的备选位置,(vi,wj)为从TSV指向其备选位置的边.

逐层分配算法即对每一层采用最小消费最大流模型对该层所有TSV同时分配位置,设Nv为该层TSV数目,Ng为该层方格数目,则可建立S-T网络流来解决最小消费最大流问题.

定义2S-T网络流N(V,E,fcap,fcost),其中V为点集,E为边集,fcap边的容量约束,fcost为边的费用.

(1)V(N)=V(G)∪{S,T};

(2)E(N)=E(G)∪ESv∪EgT,其中ESv={(S,v)|v∈Vv},EgT={(g,T)|g∈Vg};

(3)fcap为整数方程,用以表示流图中所有边的容量,

(1)

4)fcost为实数方程,用以表示流图中所有边的费用,

(2)

其中wl(*)表示子节点网的半周长预测(HPWL).图3为某一包含n个带插入TSV与m个方格芯片层所对应的S-T网络流.

图3　最小消费最大流针对的某一层的S-T网络流

2.3逆向重分配算法

原始逐层TSV分配会导致布线冗余,本文作者提出了逆向重分配的算法对原始逐层分配得到的结果进一步优化.经过第一次的正向逐层TSV分配,各层TSV的位置信息已经得到,利用当前TSV位置可以对各层TSV重新分配位置.

原始TSV解决最小消费最大流问题中费用约束条件只计算了针对某一TSV其连接的两层子节点网的半周长预测(HPWL),然而wl(snt1)子节点网并不包含下一层所插入的TSV,若将当前已有的原始逐层分配位置结果考虑进去,则已分配位置此时可能不是最优解.利用原始分配结果可以对这部分TSV重新分配位置,使其达到基于当前其他层TSV位置的最优解.

在进行逆向重分配时,按照从底层到顶层的逆向顺序,对每一层所有TSV重新分配位置,这里依然采用最小消费最大流算法来解决问题,但是因为考虑所有TSV的位置信息,可以将S-T网络流中的约束条件加以更新:

(3)

其中n为芯片层数.此费用方程计算了该TSV所在节点网的所有子节点网总线长,这样最小消费问题就可以得到基于当前条件的最优线长TSV位置.而通过逆向或循环重分配,可以使节点网布线总长不断得到优化,实验显示,10次循环之后所得结果不会再有明显改善,而循环重分配平均可以将原始逐层TSV算法线长降低3.7%.同时此逆向重分配算法亦可用于优化其他TSV位置分配算法所得结果,仿真实验已验证其有效性.

2.4快速重分配算法

在逆向重分配算法中,解决最小消费最大流模型问题所消耗的时间占总运行时间60%以上,如果能够用一种快速算法代替最小消费最大流问题进行TSV分配,则可极大地降低运行时间.快速重分配算法省去了最小消费最大流中同时给该层所有TSV分配位置的步骤,改为按照一定顺序依次对TSV分配位置.理论分析可以发现,如果TSV所在节点网总线长越短,说明其所联通层数越少,而这些TSV的位置对其他节点网插入TSV的影响就越小,所以可以优先分配.这里定义了一个代价函数用来代表某一TSV的影响能力:

(4)

快速重分配算法按照该层所有TSV的I(v)递增顺序对TSV进行依次插入,在减少运行时间的同时,又不会牺牲太大的线长优化能力.

3仿真实验结果

仿真实验是基于64-bit 的IBM Linux平台,利用c++语言对MCNC(ami33,ami49)及GSRC(n50,n100,n200,n300)6种检验标准进行仿真.利用已有的3D芯片布局(包括层上空白位置信息),定义TSV大小为5 μm×5 μm,3D芯片布局层数为4层.本仿真所得数据为循环10次重分配所得结果,数据为10次运行平均值.表1为各检验标准电路参数,包含平均子节点网数、总节点数以及需插入的TSV数.

表1　检验标准参数

图4为循环重分配1至5周所得总线长趋势,循环次数越多,线长优化度越高,但优化趋势逐渐趋于平缓,循环运行时间越长.

图4　1～5次循环重分配所得线长

表2为仿真实验结果,基于最小消费最大流的逆向TSV重分配算法经过10周循环重分配对总布线长度进行优化.10次运行平均结果为:对比原始逐层TSV分配,总线长减少了3.7%,运行时间为原始逐层分配的12.93倍.此实验结果说明逆向重分配方法通过循环对TSV已分配位置进一步优化减少了总布线长度,降低了生产成本,代价为增加了运算时间.快速重分配方法经过10次10周循环所得运行结果为:对比原始逐层分配方法,总线长降低2.2%,运行时间为原始方法的1.84倍.可以发现快速重分配方法虽然无法达到基于最小消费最大流的逆向重分配方法的高优化程度,但是可以显著减少逆向重分配的运行时间,10周重分配所占时间小于原始逐层分配所消耗时间.

表2　逆向重分配算法

`

4结论

本文作者提出了逆向重分配的方法对原始逐层TSV分配方法进一步优化,实验结果表明,在原始方法基础上可以减少平均3.7%的总线长以达到降低生产成本的目的.此方法运行时间为原始逐层分配方法的12.93倍.而快速重分配方法则可以显著降低重分配所需时间,代价为无法达到基于最小消费最大流算法的重分配优化度.

参考文献:

[1]Banerjee K,Souri S J,Kapur P,et al.3-D ICs:A novel chip design for improving deep-submicrometer interconnect performance and systems-on-chip integration [J].Proceedings of the IEEE,2001,89(5):602-633.

[2]Joyner J W,Zarkesh-Ha P 0,Meindl J D.A global interconnect design window for a three-dimensional system-on-a-chip [C]//IEEE:Interconnect Technology Conference 2001 Proceedings of the IEEE 2001 International.Burlingame:IEEE,2001.

[3]Goplen B,Spatnekar S.Placement of 3D ICs with thermal and interlayer via considerations [C]//ACM.Proceedings of the 44th annual Design Automation Conference.San Diego:ACM,2007.

[4]Cong B J,Zhang Y.Thermal-driven multilevel routing for 3-D ICs [C]//ACM.Proceedings of the 2005 Asia and South Pacific Design Automation Conference.New York:ACM,2005.

[5]Zhou L,Wakayama C,Shi C J R.Cascade:A standard supercell design methodology with congestion-driven placement for three-dimensional interconnect-heavy very large-scale integrated circuits [J].Computer-Aided Design of Integrated Circuits and Systems IEEE Transactions on,2007,26(7):1270-1282.

[6]Chen S,Ge L W,Chiang M F,et al.Lagrangian Relaxation Based Inter-Layer Signal Via Assignment for 3-D ICs [J].IEICE TRANSACTIONS on Fundamentals of Electronics Communications and Computer Sciences,2009,E92-A(4):1080-1087.

(责任编辑：顾浩然)

An improved layer by layer TSV assignmentoptimization for multi-layer 3-D ICs

LI Delong1, HAO Cong2, YOSHIMURA Takesi2, YU Hui1

(1.School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240 China;2.Graduate School of Information,Production and Systems LSI,WASEDA University,Tokyo 169-8050,Japan)

Abstract:Poor TSV assignment algorithm leads to a large detour of wire-length.Some of the previous works deal with TSV assignment problem using layer-by-layer methods(LBL) only gets local optimal results.In this research work,a backward layer-by-layer reassignment(BRLBL) is developed to do further optimization.This reassignment algorithm takes global information into consideration and optimizes the outcome of layer-by-layer TSV assignment methods.Also a fast layer-by-layer reassignment(FLBL) method is proposed to shorten the runtime.Experimental results show that BRLBL achieves an average reduction over 3.7% of wire-length,while the FLBL improves the execution time of BRLBL by 10 times.

Key words:3-D IC; Through-silicon via(TSV);wire-length optimization; backward reassignment

中图分类号:TN 47

文献标志码:A

文章编号:1000-5137(2016)02-0180-06

通信作者:俞辉,中国上海市闵行区东川路800号,上海交通大学电子信息与电气工程学院,邮编:200240,E-mail:yuhui@sjtu.edu.cn.

基金项目:国家科技重大专项“TD-LTE/FDD-LTE/TD-SCDMA/WCDMA/GSM多模型基带商用芯片研发”(2013 ZX03001007-004)

收稿日期:2015-12-15