1.一种加速的牛顿分裂迭代法应用于混合尺寸单元电路布局方法,其特征在于:包括如下步骤:S1:对标准单元进行预处理,将多倍行高标准单元分割为多个单倍行高标准子单元,并放置到最近的与电源线匹配的行上;
步骤S1的具体实现方式包括:给定一个芯片的矩形布局区域,用(0,0)和(W,H)分别表示其左下角坐标和右上角坐标;W表示布局区域的宽度,H表示布局区域的高度;待布局的可移动标准单元集为C=(c1,c2,…cn),其中单元ci从全局阶段获得的初始左下角坐标为单元宽度及高度分别为wi,hi,所求的合法化阶段后的坐标用(xi,yi)表示;对于多倍行高标准单元,将其表示成多个子单元,用(ci1,ci2,…cit)表示,其中,t表示标准单元的高度是行高的t倍;
S2:对所有单元建立网络流模型,对其进行扩散;
S3:将合法化问题表述为一个凸二次规划问题;
S4:将二次规划问题等价地转换成线性互补问题;
步骤S4的具体实施方式为:利用Karush-Kuhn-Tucker(KKT)条件,可将模型写成如下条件的KKT方程组:将方程组(4)改下为如下形式:
令该问题则演变为寻求一对非负且正交的解向量满足如下条件:
w=Az+q≥0,z≥0and wTz≥0; (6)
问题(6)则为线性互补问题,其中
S5:将线性互补问题等价地表示成广义绝对值方程;
所述步骤S5的具体实施方式为:令z=(|v|-v),w=(|v|+v),则(6)可转换成下列等价的广义绝对值方程:(A+I)v-(A-I)|v|=q;(7)
令C=A+I,E=A-I,其中I为单位矩阵,则(7)可重新表述为如下形式:
Cv-E|v|=q;(8)
S6:利用加速的牛顿迭代法求解广义绝对值方程;
所述步骤S6的具体实施方式为:令F(v)=Cv-E|v|-q,并令F(v)=0;由于F(v)是一个分段线性向量函数,是不可微的,不能直接应用牛顿迭代方法来求解此方程;因此,基于|v|的分量的次梯度,使用|v|的广义雅可比来获得广义绝对值方程(8)的近似解;可用对角矩阵D(v)表示,其中且对于非线性等式系统F(v),将其分解为可微函数H(v)与Lipschitz连续函数G(v)之和,即F(v)=H(v)+G(v),因此可以利用一种修正的牛顿迭代法求解F(v),即vk+1=vk-H'(vk)-1(H(vk)+G(vk)),k=0,1,2,…, (10)取H(v)=C(v)+Ω(v),G(v)=-Ω(v)-E|v|-q,其中Ω为半正定矩阵,利用(10)求解F(v)可得到如下迭代格式:vk+1=vk-(C+Ω)-1(Cvk-E|vk|-q); (11)
将(11)两边同时乘以(C+Ω)可得
(C+Ω)vk+1=Ωvk+E|vk|+q; (12)
由于C=A+I,E=A-I,因此矩阵C和E是两个正定矩阵,令C=M1-N1为矩阵C的分裂,E=M2-N2为矩阵E的分裂,并将最新的估计值vk+1替换等式右侧的vk,可得到如下迭代格式:(M1+Ω)vk+1=(N1+Ω)vk+M2|vk|-N2|vk+1|+q; (13)其中,要求N2是一个下三角矩阵;具体地,根据式(5)中矩阵A的结构,将M1,N1,M2,N2取值如下:其中,为单位矩阵;取Ω=ωI,ω为正常数,令B1=B+λRTR,因此,利用式(13)求解合法化问题的过程如下所示:给定一个任意的初始向量通过迭代地求解线性系统来计算vk+1的值,直到绝对残差向量的二范数RES(vk):=||zk-zk-1||2小于等于给定的一个常数,此时可认为迭代序列收敛,且zk=(|vk|-vk),k=0,1,2,…;
S7:将多倍行高标准单元进行复原并放置到行中的可放置位上;
S8:对剩余的非法单元进行合法化处理。
2.根据权利要求1所述的一种加速的牛顿分裂迭代法应用于混合尺寸单元电路布局方法,其特征在于:所有单元的高度都是行高的整数倍;然后将所有标准单元对齐到最近的与其电源线匹配的行上去;电源线和接地线在行中交错排布,对于奇数倍行高单元,其两端的电源类型是不同的,因此只要不超出布局区域,便可以放置在任意的行上面,通过翻转来实现电源类型的匹配;对于偶数倍行高单元,其两端的电源类型是相同的,因此需要放置到与其电源类型匹配的行上。
3.根据权利要求2所述的一种加速的牛顿分裂迭代法应用于混合尺寸单元电路布局方法,其特征在于:步骤S2的具体实现方式包括:为避免后续处理中标准单元过于拥挤,利用网络流算法对单元进行扩散,确保每行中的单元宽度之和不超过该行的宽度,对布局区域在水平方向和垂直方向进行均匀地划分成网格,每一个网格构成网络流图中的一个节点,此外,再额外创建两个节点,即超级源节点(NB)和超级汇节点(NE),计算每个网格中所属单元的面积之和sC,将其与网格面积sG进行比较,如果sC>sG,则该网格称为溢出网格并记录溢出的面积so,如果sC≤sG,则该网格称为空闲网格并记录剩余的空闲面积sf,对于溢出网格,将其设置成网络流中的源节点Ns,并建立一条从NB到Ns的弧,弧上的容量和成本分别设置为so和零,对于空闲网格,将其设置为目标节点Nt,并建立一条从Nt到NE的弧,弧上的容量和成本分别设置为sf和0,并且对溢出网格,寻找与它相邻的空闲网格,建立从Ns到Nt的弧,弧上的容量和成本分别设置为无穷大和单元在两个网格之间移动的位移,对于建立好的网络流图进行求解,可得到单元在网格中移动的策略,按照该策略移动单元,移动后的单元ci的坐标为
4.根据权利要求3所述的一种加速的牛顿分裂迭代法应用于混合尺寸单元电路布局方法,其特征在于:步骤S3的具体实现方式包括:合法化过程是消除单元之间的重叠,并以最小化标准单元总位移为优化目标,并且在前述步骤中单元已经进行垂直方向上的最小移动,即与匹配的电源轨对齐,因此可忽略垂直方向上的位移,将合法化问题描述为下述模型(1):将上述模型改写为凸二次规划问题的标准形式,即:
其中,是一个单位矩阵,是一个列向量,其分量由标准单元的初始横坐标构成;任意相邻的一对标准单元应该满足不等式xj-xi≥wi(xj≥xi),对所有相邻单元之间建立该不等式,则可以写成矩阵形式Wx≥d,W为每行仅包含-1和1这两个元素的矩阵,分别表示单元ci和cj的横坐标xj,xi,d为一个列向量,其中对应的分量表示左侧单元ci的宽度wi;那么W和d的行数为约束的个数,W的列数为标准单元的总个数,即单倍行高单元的数量与多倍行高单元拆分成的子单元数量之和,则R同样为每行由-1和1组成的矩阵,-1表示多倍行高单元ci的子单元ci1,1表示ci的子单元ci2,依次推类;xi2-xi1=0保证ci的子单元横坐标相等,由此可得到约束矩阵Rx=0,其中根据该位置构造的矩阵W、R和向量d如下所示:利用拉格朗日乘子法,将二次规划中的等式约束加入到目标函数中,则(2)可表示为:
其中,λ为拉格朗日乘子。
5.根据权利要求4所示的一种加速的牛顿分裂迭代法应用于混合尺寸单元电路布局方法,其特征在于:所述步骤S7的具体实施方式为:将所求得的每个多倍行高标准单元的所有子单元的坐标按照升序排序,中位数即为所求的该多倍行高单元的坐标,接着将单元放置到离所求得的坐标最近的可放置位上。
6.根据权利要求5所示的一种加速的牛顿分裂迭代法应用于混合尺寸单元电路布局方法,其特征在于:所述步骤S8的具体实施方式为:针对少许仍然重叠或超出布局区域右边界的标准单元,从布局区域右上角开始,按照从右到左,从上到下的顺序对标准单元进行遍历,若单元ci超过右边界,则把其坐标置为W-wi,若单元ci与ci-1重叠,则将ci-1坐标置为xi-wi-1;由于多倍行高单元的移动可能会引起相邻行的单元重叠,因此,对于在上一行中已经移动过的多倍行高单元,在下一行则不再移动它们;接着,按照相同的规则从左到右,从下到上的顺序遍历再次遍历标准单元,经过该步骤处理后,所有单元重叠均可消除。