欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2022105718978
申请人: 南通大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于牛顿迭代法的混合尺寸单元电路布局设计方法,其特征在于:包括如下步骤:S1:对标准单元进行预处理,将多倍行高标准单元分割为多个单倍行高标准子单元;

S2:基于网络流算法对标准单元进行扩散;

S3:将混合尺寸标准单元合法化问题表示为二次规划数学模型;

S4:将二次规划模型转换成线性互补问题;

S5:将线性互补问题转化成广义绝对值方程;

S6:利用牛顿迭代法求解广义绝对值方程;

S7:将多倍行高标准单元分割成的子单元的x坐标进行统一,并对齐到行中的可放置位上;

S8:对剩余的非法单元进行合法化处理。

2.根据权利要求1所述的一种基于牛顿迭代法的混合尺寸单元电路布局设计方法,其特征在于:步骤S1的具体实现方式包括:给定一个芯片的矩形布局区域,用(0,0)和(W,H)分别表示其左下角坐标和右上角坐标;W表示布局区域的宽度,H表示布局区域的高度;待布局的可移动标准单元集为C=(c1,c2,…cn),其中单元ci从全局阶段获得的初始左下角坐标为单元宽度及高度分别为wi,hi,所求的合法化阶段后的坐标用(xi,yi)表示;对于多倍行高标准单元,将其表示成多个子单元,用(ci1,ci2,…cit)表示,其中,t表示标准单元的高度是行高的t倍。

3.根据权利要求2所述的一种基于牛顿迭代法的混合尺寸单元电路布局设计方法,其特征在于:所有单元的高度都是行高的整数倍;然后将所有标准单元对齐到最近的与其电源线匹配的行上去;电源线和接地线在行中交错排布;对于奇数倍行高单元,其两端的电源类型是不同的,因此只要不超出布局区域,便可以放置在任意的行上面,通过翻转来实现电源类型的匹配;对于偶数倍行高单元,其两端的电源类型是相同的,因此需要放置到与其电源类型匹配的行上。

4.根据权利要求2所述的一种基于牛顿迭代法的混合尺寸单元电路布局设计方法,其特征在于:步骤S2的具体实现方式包括:为避免后续处理中标准单元过于拥挤,利用网络流算法对单元进行扩散,确保每行中的单元宽度之后不超过该行的宽度;对布局区域在水平方向和垂直方向进行均匀地划分成网格,每一个网格构成网络流图中的一个节点;此外,再额外创建两个节点,即超级源节点(NB)和超级汇节点(NE);计算每个网格中所属单元的面积之和sC,将其与网格面积sG进行比较;如果sC>sG,则该网格称为溢出网格并记录溢出的面积so;如果sC≤sG,则该网格称为空闲网格并记录剩余的空闲面积sf;对于溢出网格,将其设置成网络流中的源节点Ns,并建立一条从NB到Ns的弧,弧上的容量和成本分别设置为so和零;对于空闲网格,将其设置为目标节点Nt,并建立一条从Nt到NE的弧,弧上的容量和成本分别设置为sf和0;并且对溢出网格,寻找与它相邻的空闲网格,建立从Ns到Nt的弧,弧上的容量和成本分别设置为无穷大和单元在两个网格之间移动的位移;对于建立好的网络流图进行求解,可得到单元在网格中移动的策略,按照该策略移动单元,移动后的单元ci的坐标为

5.根据权利要求4所述的一种基于牛顿迭代法的混合尺寸单元电路布局设计方法,其特征在于:步骤S3的具体实现方式包括:合法化过程是消除单元之间的重叠,并以最小化标准单元总位移为优化目标,并且在前述步骤中单元已经进行垂直方向上的最小移动,即与匹配的电源轨对齐,因此可忽略垂直方向上的位移,将合法化问题描述为下述模型(1):s.t.xj‑xi≥wi,若xi,xj在同一行且xj‑xi≥0;   (1)xi≥0.

将上述模型改写为凸二次规划问题的标准形式,即:

其中, 是一个单位矩阵, 是一个列向量,其分量由标

准单元的初始横坐标构成;任意相邻的一对标准单元应该满足不等式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如下所示:R=(0 ‑1 1 0),d=(w1 w2);

利用拉格朗日乘子法,将二次规划中的等式约束加入到目标函数中,则(2)可表示为:其中,λ为拉格朗日乘子。

6.根据权利要求5所示的一种基于牛顿迭代法的混合尺寸单元电路布局设计方法,其特征在于:所述步骤S4的具体实施方式为:利用Karush‑Kuhn‑Tucker(KKT)条件,可将模型(3)写成如下条件的KKT方程组:将方程组(4)改下为如下形式:

令 该问题则演变为寻求一对非负且正交的解向量

满足如下条件:

T

w=Az+q≥0,z≥0 and wz≥0.          (6)问题(6)则为线性互补问题,其中

7.根据权利要求6所示的一种基于牛顿迭代法的混合尺寸单元电路布局设计方法,其特征在于:所述步骤S5的具体实施方式为:由于线性互补问题中的系统矩阵A的(2,2)块为

0,因此是半正定矩阵;将该矩阵的(2,2)块加上一个扰动,即εIm,则矩阵A的分块为:其中 是单位矩阵,令z=(|v|‑v),w=(|v|+v),则(6)可转换成下列等价的广义绝对值方程:(A+I)v‑(A‑I)|v|=q.                (7)令C=A+I,B=A‑I,则(7)可重新表述为如下形式:Cv‑B|v|=q.              (8)。

8.根据权利要求7所示的一种基于牛顿迭代法的混合尺寸单元电路布局设计方法,其特征在于:所述步骤S6的具体实施方式为:令F(v)=Cv‑B|v|‑q,并令F(v)=0;由于F(v)是一个分段线性向量函数,是不可微的,不能直接应用牛顿迭代方法来求解此方程,因此,基于|v|的分量的次梯度,使用|v|的广义雅可比 来获得广义绝对值方程(8)的近似解; 可用对角矩阵D(v)表示,其中 且

牛顿迭代法定义如下:

k+1 k k ‑1 k

v =v‑F′(v) F(v),k=0,1,2,…,           (10)k k

只要F(v)的雅可比矩阵F’(v)存在且可逆,可以利用(10)求解F(v),即k+1 k k ‑1 k k

v =v‑(C‑BD(v)) (Cv‑B|v|‑q).           (11)k

将上式(11)两边同时乘以(C‑BD(v))可得

k k+1 k k k k

(C‑BD(v))v =(C‑BD(v))v‑(Cv‑B|v|‑q).          (12)k k k

由于D(v)v=|v|,将式(12)整理后可得

k k+1

(C‑BD(v))v =q.            (13)由于C=A+I,B=A‑I,因此与合法化问题等价的线性互补问题可转化为如下迭代格式进行求解:k+1 k ‑1

v =((A+I)‑(A‑I)D(v)) q.            (14)k+1

给定一个任意的初始向量 通过迭代地求解线性系统来计算v 的值,直到绝(k) (k+1) (k)

对残差向量的二范数RES(v ):=||z ‑z ||2小于等于给定的一个常数,此时可认为迭(k) (k) (k)代序列 收敛,且z =(|v |‑v ),k=0,1,2,…。

9.根据权利要求8所示的一种基于牛顿迭代法的混合尺寸单元电路布局设计方法,其特征在于:所述步骤S7的具体实施方式为:将所求得的每个多倍行高标准单元的所有子单元的x坐标按照升序排序,中位数即为所求的该多倍行高单元的x坐标,接着将单元放置到离所求得的x坐标最近的可放置位上。

10.根据权利要求9所示的一种基于牛顿迭代法的混合尺寸单元电路布局设计方法,其特征在于:所述步骤S8的具体实施方式为:针对少许仍然重叠或超出布局区域右边界的标准单元,从布局区域右上角开始,按照从右到左,从上到下的顺序对标准单元进行遍历,若单元ci超过右边界,则把其坐标置为W‑wi,若单元ci与ci‑1重叠,则将ci‑1坐标置为xi‑wi‑1;由于多倍行高单元的移动可能会引起相邻行的单元重叠,因此,对于在上一行中已经移动过的多倍行高单元,在下一行则不再移动它们;接着,按照相同的规则从左到右,从下到上的顺序遍历再次遍历标准单元,经过该步骤处理后,所有单元重叠均可消除。