《基于sakurai模型的时延驱动steiner树算法3》由会员分享，可在线阅读，更多相关《基于sakurai模型的时延驱动steiner树算法3（6页珍藏版）》请在金锄头文库上搜索。
1、 第20卷第1期 半 导 体 学 报 Vol . 20,No. 1 1999年1月 CH I N ESE JOURNAL OF SEM ICONDUCTORS Jan. , 1999 3 国家 “九五” 科技攻关(项目编号: 962738201208203)和高等学校博士学科点专项科研基金资助项目(项目编号: 96000330) 鲍海云 男, 1972年出生,博士研究生,从事大规模集成电路自动布线算法的研究 洪先龙 男, 1940年出生,教授,目前从事计算机设计自动化的教学和科研工作 蔡懿慈 女, 1960年出生,副教授,目前从事大规模集成电路计算机辅助设计的教学和科研工作 199721022
2、5收到, 1998202223定稿基于Sakura i模型的时延 驱动Steiner树算法3鲍海云 洪先龙 蔡懿慈 乔长阁(清华大学计算机科学与技术系 北京 100084 )摘要 时延驱动的Steiner树构造算法是时延驱动总体布线的基础.本文首先简介了求解最佳Steiner树的D reyfus2W agner算法.随后通过引入Sakurai时延模型,提出了直接基于Sakurai模型的提高线网时延性能的时延驱动DW算法.当集成电路工艺的特征宽度较小时,该算法求得的Steiner树中关键点的时延值,明显小于I DW和CFD算法的结果.EEACC:7410D, 51201 引言随着集成电路工艺的飞
3、速发展,芯片面积正在不断增大,线条尺寸不断减小,布线的层数增多,连线造成的延迟已不能忽略1.在深亚微米工艺下设计芯片时,连线造成的延迟已逐渐在总延迟中占了很大的比例,甚至超过了门延迟2.传统的总体布线算法仅以总的线长为优化目标,而对于多端线网来说,总的线长最短并不意味着时延最短3.因此如果希望优 化整个芯片的电性能,就必须在布局和总体布线时考虑电性能的优化.求解Steiner树的算法是多数总体布线算法的核心算法4, 5,它是一个多端网络最基本的布线问题到图论问题的直接转化.总体布线算法是从整体上控制所有总体布线树(Steiner 树)的性质,而每个总体布线树的求解就必须利用求解Steiner树
4、的算法.因此要构造时延驱动的总体布线算法,就必须首先构造以时延为优化目标的Steiner树构造算法.为此清华大学的洪先龙教授在文献6中提出了基于D reyfus2W agner的时延驱动Steiner树迭代构造 算法(简称I DW算法),在文献7中提出了构造性力指向的Steiner树构造算法(简称CFD 算法). CFD算法与I DW算法相比,大大加快了求解速度,同时线网时延性能有所降低.I DW算法中使用的时延模型是简化的Elmore时延模型8.该模型计算便捷,但有一定的局限性,对形状较复杂线网的时延估计会有较大的误差.另外当线网中的节点数较多(大于6)时, I DW算法的求解时间将变得相当
5、长.本文将Sakurai时延模型用于D reyfus2W agn2er算法中,并针对Sakurai时延模型的特点,避免了重复求解,实现了速度、 性能均优于I DW 和CFD算法的时延驱动Steiner树的构造算法.2 应用Sakurai时延模型的时延驱动Dreyfus-Wagner算法2. 1 Dreyfus-Wagner算法D reyfus2W agner算法(简称DW算法)9应用动态规划技术求解Steiner树,它反复使 用两个递推公式,从所有可能的Steiner树中,找出连通给定顶点集Z的最小(长度最短)Steiner树.若用p(v,w)表示图G中点v到w的最短距离, K表示G对应点集的
6、子集,Sv(K (v)表示G中Kv的最小Steiner树的长度,Pv(Kv)表示G中Kv的v度大于1的最小Steiner树的长度,则这两个递推公式分别为:Pv(Kv) = m inSv(K v) +Sv(K -K v)K K且K 5(1)Sv(Kv) = m inm inp(v,w) +Sw(K)wK,m inp(v,w)+Pw(Kw)w|K(2)用DW算法求解最短Steiner树的整个过程如下:(1)初始化:计算G中所有顶点之间的最短路径p(v,w);(2)递推:下面的过程从k= 1, 2, 3, . . .Z- 1,依次处理KZ,K=k,vZ?K,依照公式(1),寻找Pv(Kv).KZ,K
7、=k,vZ?K,依照公式(2),寻找Sv(Kv).2. 2 Sakura i时延模型要设计以时延为优化目标的Steiner树构造算法,就必须对不同Steiner树的时延进行估计,也就不可避免地要用到时延模型.对于总体布线来说,时延模型的主要任务是确定如何连线可以使时延短,而不是必须得到准确的时延值.因此对时延模型的要求中,精确是相对次要的;而与实际时延长短的对应关系,或说一致性则是比较重要的;计算简单、 快捷也是比较重要的因素.因此我们选用了Sakurai时延模型10.在Sakurai时延模型中,一条连线被看作具有分布电阻re和电容ce的传输线.该传输线的输入是内阻为Rs的单位电压源,电容负载
8、为Cz.这种模型与布线问题中的实际情况基本相同.文献11导出了该模型下,经过连线后的输出Vo从0增加到019VDD的时延TD:TD=Rs(Ce+Cz) +rece+reCz,其中 = 1. 02,= 2. 21如果规定TDZ为Vo从0增加到017VDD的时延12,则 = 0159,= 1121.如果规定TDZ为Vo从0增加到0162VDD的时延13,则 = 015,= 110.对于树型多端连线结构,从源到各结点的时延可根据其前驱结点时延确定:TD(s) =RsCsTD(w) =TD(v) +rcL2 vw+rL vwCw其中 s为线网的源;Rs为源的输出电阻;Cs为整个线网的负载电容;v为w的
9、前驱结点;Lvw为v到w的连线长度;Cw为结点w之后的总电容;r为单位线长的电阻值;c为单位线长的电容值. Sakurai时延模型比Elmore时延模型更精确,能够较正确地反映Steiner树的形24 半 导 体 学 报 20卷状对时延的影响,适用面更广,而计算复杂度增加不大,所以用于时延驱动的总体布线中是 较为合适的.2. 3 分解Sakura i时延公式 分解Sakurai时延公式,是为了分离出Steiner树各部分对某个结点的时延贡献,以确 定每一步的优化目标,即用Sakurai时延模型的时延最小值,代替DW算法中的线长最小值公式.可将Sakurai时延变形如下:TD(t) =TD(s)
10、 +rc xypath (s,t)L2 xy+r xypath (s,t)LxyCy=RsCs+rc xypath (s,t)L2 xy+r xypath (s,t)LxyCy=RsCs-w+rc xypath (s,w)L2 xy+r xypath (s,w)LxyCy-w+(Rs+r xypath (s,w)Lxy)Cw+rc xypath (w,t)L2 xy+r xypath (w,t)LxyCy其中 x为y的前驱结点;xy表示连接x和y的边,path(s,t)表示s到t的路径,即连接点s 和t的边的集合;Cv-w表示v点以下w点以上部分的电容值,可以看出用方括号分隔出的 前一部分与w
11、以下的Steiner树没有任何关系;而后一部分中只有Cw的系数与非w以下的部分有关.若令Rsw=Rs+r xypath (s,w)Lxy,设t为关键点(要控制时延的结点),若wpath(s,t)则求解w以下Steiner树时,只需以下式表示的TD(t)后半部分为优化目标即可:Td(w,t) =RswCw+rc xypath (w,t)L2 xy+r xypath(w,t)LxyCy(3)从该式中可以看出,可将w看作是其下树的假想源,其驱动电阻为Rsw. 而对v|path(s,t),则由TD(t)计算式的前一部分知:v以下的Steiner树对TD(t)的 影响仅仅表现在两个电容项Cs-w和Cy-
12、w上,因此在求解v以下的Steiner树时,只需使其总 电容最小,即总线长最小即可. 扩展到多个关键点的情况,可以用向量t= (t1,t2,tn)表示所有关键点;用Sv(Kv,Rsv)表示对应电阻值Rsv的G中Kv的时延最小Steiner树,其中v是该树中距源s 最近的点;以Pv(Kv,Rsv)表示再附加上条件 “v的度大于1” 后的时延最小Steiner树; 用Td(Sv,ti)表示Steiner树Sv中v到ti的时延(若ti不在Sv中则该值为0),其中v是该树 中距源s最近的点(假想源),并令时延向量(黑体字母表示向量):Td(Sv,t) =(Td(Sv,t1),Td(Sv,t2),Td(
13、Sv,tn)则对应DW算法的(1)、(2)两式,Td(Sv,t)分别有如下传递关系:Td(Pv(Kv,Rsv),t)= m inTd(Sv(K v,Rsv),t)+RsvCK- K- vIK- K+Td(Sv(K- K v,Rsv),t)+RsvCK- vIK (4)对应(1)式Td(Sv(Kv,Rsv),t)= m in m inTd(Sw(K),Rsv)+rLvw),t)+ (rLvw)Cw+rcL2 vw)IKwKm inTd(Pw(Kw),Rsv)+rLvw),t)+ (rLvw)Cw+rcL2 vw)IKw|K (5)对应(2)式其中 IK= (i1K,i2K,inK),若tjK则i
14、jK= 1,否则ijK= 0.请注意用于向量的m in函数可341期 鲍海云等: 基于Sakurai模型的时延驱动Steiner树算法 以根据实际需要赋予不同的含义.2. 4 利用已求得的部分解加快求解过程 将DW算法的迭代公式中的线长对应地替换为Sakurai时延公式,就能够求得使关键 节点时延最短的Steiner树,但与以线长为优化目标的DW算法有所不同.在原先的算法 中,Pv(K)和Sv(K)对应的最小Steiner树的形状只与K和v有关,且最小值具有传递性,所以可以通过自下而上求解,达到避免重复构造子Steiner树的目的.而由(35)式知,考虑时 延后Pv(K)和Sv(K)对应的St
15、einer树的形状与Rsv有关,分别记为Pv(K,Rsv)和Sv(K,Rsv).并且时延的最小值不再具有传递性,不能简单地利用已求解过的Steiner树.这样当结点数较多时,运算量将远远大于原DW算法.为加快求解过程,要尽可能地利用已求得的部 分解.可以证明若Rsv1Rsv2,且Sv(K,Rsv1)=Sv(K,Rsv2),则对RsvRsv1,Rsv2可以有Sv (K,Rsv) =Sv(K,Rsv1).对Pv(K,Rsv)也有类似的特性.利用这一特性可以加快Steiner树 的求解过程.具体做法是:定义一个栈数据结构保存K,v,Rsv1,Rsv2以及对应的Sv(K,Rsv1) 的降级分解方法,该结构按K和v分层保存构成结果栈,同层的数据按Rsv1顺序保存.加速 后的整个求解过程自上而下递归进行,在求解Sv(K,Rsv)之前先在栈中查找已有的解,如果 有合适的解则将其返回,否则遍历其所有的降级分解方式求解得到Sv(K,Rsv),更新结果栈 中的数据,并返回.2. 5 实验结果 理论上可以证明当线网中仅有一个关键点时,用基于Sakurai模型的时延驱动Steiner 算法必能取得使关键点时延最短的解.我
