一种基于牛顿迭代法的混合尺寸单元电路布局设计方法

摘要

本发明提供了一种基于牛顿迭代法的混合尺寸单元电路布局设计方法，首先对多倍行高单元预处理成单倍行高子单元，并放置到最近的与电源线匹配的行上，然后对所有单元建立网络流模型，对其进行扩散，避免局部拥挤，接着将合法化问题表述为一个凸二次规划问题，并将二次规划问题等价地转换成线性互补问题，然后将线性互补问题等价地表示成广义绝对值方程，利用牛顿迭代法求解，最后将多倍行高标准单元进行复原并放置到行中的可放置位上，并对余下的非法单元进行处理。与现有技术相比，本发明通过牛顿迭代法对与合法化问题等价的广义绝对值方程进行求解，无需考虑参数的设置，避免了因参数选取不当而无法有效求解的局限，本发明能够有效加快迭代过程的收敛速度，并快速得到合法化问题的高质量邻域解。

说明书

技术领域

本发明涉及超大规模集成电路物理设计自动化领域，具体涉及一种基于牛顿迭代法的混合尺寸单元电路布局设计方法。

背景技术

超大规模集成电路(VLSI)电路的物理设计对于半导体芯片的制造至关重要。随着超大规模集成电路先进节点技术的发展，设计具有多种高度的标准单元库的电路成为主流。多倍行高的标准单元具有更好的引脚可达性以及更短的延迟，但是，它们的出现也为布局阶段带来更大的挑战。不同于单倍行高标准单元移动时仅需考虑该行的单元重叠即可，多倍行高单元的移动过程中，还需额外考虑相邻行单元的重叠问题。除此之外，混合尺寸单元的布局还需遵循电源轨匹配的限制。电路设计中标准单元的数量巨大，使得解空间组合爆炸，具有极高的计算复杂度，因此布局问题是一个NP-难问题。对于该类问题，通常采用迭代求解的方法来获得近似解，如何快速、高效地逼近最优解是当前亟待解决的一个问题。

现有的合法化算法分为启发式算法和解析式算法。启发式算法具有求解速度快的优点，然而容易陷入局部最优解；解析式方法通常对合法化问题建立一个数学模型，从而对该模型进行求解；陈建利等(CN 106971042 A)提出了将合法化问题中的二次规划问题等价地表示为线性互补问题，并应用模系矩阵分裂迭代法对线性互补问题进行求解。

发明内容

发明目的：本发明的目的是超大规模集成电路设计合法化过程中，产生的线性互补问题重新表示为等价的广义绝对值方程，因此，提供一种基于牛顿迭代法的混合尺寸单元电路布局设计方法，主要涉及布局过程中合法化阶段的一种求解方法，通过将与合法化问题等价的线性互补问题转化成一个广义绝对值方程，然后利用一种牛顿迭代法进行求解；与现有方法相比，该方法无需确定参数，避免了参数选择不当而造成难以收敛或者收敛速度过慢的问题；该发明能大大减少迭代求解过程中的迭代次数以及运行时间，进一步提升布局阶段的设计效率。

为了实现以上目的，本发明提供一种基于牛顿迭代法的混合尺寸单元电路布局设计方法，包括如下步骤：

S1：对标准单元进行预处理，将多倍行高标准单元分割为多个单倍行高标准子单元；

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

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

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

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

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

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

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

进一步优选的，步骤S1的具体实现方式包括：给定一个芯片的矩形布局区域，用(0，0)和(W，H)分别表示其左下角坐标和右上角坐标；W表示布局区域的宽度，H表示布局区域的高度；待布局的可移动标准单元集为C＝(c

进一步优选的，所有单元的高度都是行高的整数倍；然后将所有标准单元对齐到最近的与其电源线匹配的行上去；电源线和接地线在行中交错排布；对于奇数倍行高单元，其两端的电源类型是不同的，因此只要不超出布局区域，便可以放置在任意的行上面，通过翻转来实现电源类型的匹配；对于偶数倍行高单元，其两端的电源类型是相同的，因此需要放置到与其电源类型匹配的行上。

进一步优选的，步骤S2的具体实现方式包括：为避免后续处理中标准单元过于拥挤，利用网络流算法对单元进行扩散，确保每行中的单元宽度之后不超过该行的宽度；对布局区域在水平方向和垂直方向进行均匀地划分成网格，每一个网格构成网络流图中的一个节点；此外，再额外创建两个节点，即超级源节点(N

进一步优选的，步骤S3的具体实现方式包括：合法化过程是消除单元之间的重叠，并以最小化标准单元总位移为优化目标，并且在前述步骤中单元已经进行垂直方向上的最小移动，即与匹配的电源轨对齐，因此可忽略垂直方向上的位移，将合法化问题描述为下述模型(1)：

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

其中，

利用拉格朗日乘子法，将二次规划中的等式约束加入到目标函数中，则(3)可表示为：

其中，λ为拉格朗日乘子。

进一步优选的，所述步骤S4的具体实施方式为：利用Karush-Kuhn-Tucker(KKT)条件，可将模型(3)写成如下条件的KKT方程组：

将方程组(4)改下为如下形式：

令

w＝Az+q≥0，z≥0and w

问题(6)则为线性互补问题，其中

进一步优选的，所述步骤S5的具体实施方式为：由于线性互补问题中的系统矩阵A的(2，2)块为0，因此是半正定矩阵；将该矩阵的(2，2)块加上一个扰动，即εI

其中

(A+I)v-(A-I)|v|＝q. (7)

令C＝A+I，B＝A-I，则(7)可重新表述为如下形式：

Cv-B|v|＝q. (8)。

进一步优选的，所述步骤S6的具体实施方式为：令F(v)＝Cv-B|v|-q，并令F(v)＝0；由于F(v)是一个分段线性向量函数，是不可微的，不能直接应用牛顿迭代方法来求解此方程，因此，基于|v|的分量的次梯度，使用|v|的广义雅可比

牛顿迭代法定义如下：

v

只要F(v

v

将上式(11)两边同时乘以(C-BD(v

(C-BD(v

由于D(v

(C-BD(v

由于C＝A+I，B＝A-I，因此与合法化问题等价的线性互补问题可转化为如下迭代格式进行求解：

v

给定一个任意的初始向量

进一步优选的，所述步骤S7的具体实施方式为：将所求得的每个多倍行高标准单元的所有子单元的x坐标按照升序排序，中位数即为所求的该多倍行高单元的x坐标，接着将单元放置到离所求得的x坐标最近的可放置位上。

进一步优选的，所述步骤S8的具体实施方式为：针对少许仍然重叠或超出布局区域右边界的标准单元，从布局区域右上角开始，按照从右到左，从上到下的顺序对标准单元进行遍历，若单元ci超过右边界，则把其坐标置为W-w

本发明的上述技术方案相比现有技术具有以下优点：一种基于牛顿迭代法的混合尺寸单元电路布局设计方法，首先对多倍行高单元预处理成单倍行高子单元，并放置到最近的与电源线匹配的行上，然后对所有单元建立网络流模型，对其进行扩散，避免局部拥挤，接着将合法化问题表述为一个凸二次规划问题，并将二次规划问题等价地转换成线性互补问题，然后将线性互补问题等价地表示成广义绝对值方程，利用牛顿迭代法求解，最后将多倍行高标准单元进行复原并放置到行中的可放置位上，并对余下的非法单元进行处理。与现有技术相比，本发明通过牛顿迭代法对与合法化问题等价的广义绝对值方程进行求解，无需考虑参数的设置，避免了因参数选取不当而无法有效求解的局限，本发明能够有效加快迭代过程的收敛速度，并快速得到合法化问题的高质量邻域解。

附图说明

图1是混合尺寸标准单元电路合法化流程图；

图2是考虑电源轨约束的布局说明图；

图3是混合尺寸标准单元的布局示例图

图4是牛顿迭代法求解步骤图；

图5是牛顿迭代法求解由合法化问题导出的广义绝对值方程的一个实施例迭代图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明一部分实施例，而不是全部的实施例，基于本发明中的实施例，本领域技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

如图1所示，一种基于牛顿迭代法的混合尺寸单元电路布局设计方法，包括如下步骤：

S1：对标准单元进行预处理，将多倍行高标准单元分割为多个单倍行高标准子单元；

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

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

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

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

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

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

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

步骤S1的具体实现方式包括：给定一个芯片的矩形布局区域，用(0，0)和(W，H)分别表示其左下角坐标和右上角坐标；W表示布局区域的宽度，H表示布局区域的高度；待布局的可移动标准单元集为C＝(c

步骤S2的具体实现方式包括：为避免后续处理中标准单元过于拥挤，利用网络流算法对单元进行扩散，确保每行中的单元宽度之后不超过该行的宽度；我们对布局区域在水平方向和垂直方向进行均匀地划分成网格，每一个网格构成网络流图中的一个节点；此外，再额外创建两个节点，即超级源节点(N

步骤S3的具体实现方式包括：合法化过程是消除单元之间的重叠，并以最小化标准单元总位移为优化目标，并且在前述步骤中单元已经进行垂直方向上的最小移动，即与匹配的电源轨对齐，因此可忽略垂直方向上的位移，将合法化问题描述为下述模型(1)：

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

其中，

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

其中，λ为拉格朗日乘子；

所述步骤S4的具体实施方式为：利用Karush-Kuhn-Tucker(KKT)条件，可将模型(3)写成如下条件的KKT方程组：

将方程组(4)改下为如下形式：

令

w＝Az+q≥0，z≥0and w

问题(6)则为线性互补问题，其中

所述步骤S5的具体实施方式为：由于线性互补问题中的系统矩阵A的(2，2)块为0，因此是半正定矩阵；将该矩阵的(2，2)块加上一个扰动，即εI

其中

(A+I)v-(A-I)|v|＝q. (7)

令C＝A+I，B＝A-I，则(7)可重新表述为如下形式：

Cv-B|v|＝q. (8)

所述步骤S6的具体实施方式为：令F(v)＝Cv-B|v|-q，并令F(v)＝0；由于F(v)是一个分段线性向量函数，是不可微的，不能直接应用牛顿迭代方法来求解此方程；因此，基于|v|的分量的次梯度，使用|v|的广义雅可比

(8)的近似解；

牛顿迭代法定义如下：

v

只要F(v

v

将上式(11)两边同时乘以(C-BD(v

(C-BD(v

由于D(v

(C-BD(v

由于C＝A+I，B＝A-I，因此与合法化问题等价的线性互补问题可转化为如下迭代格式进行求解：

v

给定一个任意的初始向量

所述步骤S7的具体实施方式为：将所求得的每个多倍行高标准单元的所有子单元的x坐标按照升序排序，中位数即为所求的该多倍行高单元的x坐标，接着将单元放置到离所求得的x坐标最近的可放置位上；

所述步骤S8的具体实施方式为：针对少许仍然重叠或超出布局区域右边界的标准单元，从布局区域右上角开始，按照从右到左，从上到下的顺序对标准单元进行遍历，若单元c

以上所述仅为本发明的示例性实施例，并非因此限制本发明专利保护范围，凡是利用本发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。