基于最小宽度约束的6T&6TPPNN单元布局方法

摘要

一种基于最小宽度约束的6T&6TPPNN单元布局方法，其包括以下步骤：考虑Vdd/Vss轨道对齐约束的单元对齐；基于最小宽度约束的单元聚类；6TPPNN单元转化；基于片段效应的单元移动；二次规划问题模型及基于模迭代法求解，本发明的方法，在不增加任何芯片设计面积的前提下，可在减少所有最小宽度约束的基础上引起的线长增长，同时降低了片段效应达，提高了电路性能。

权利要求

1.一种基于最小宽度约束的6T&6TPPNN单元布局方法，包括以下步骤：

1）考虑Vdd/Vss轨道对齐约束的单元对齐；

2）基于最小宽度约束的单元聚类；

3）6TPPNN单元转化；

4）基于片段效应的单元移动；

5）二次规划问题模型及基于模迭代法求解；

所述步骤4）进一步包括以下具体步骤：a）在片段效应热点区域进行基于片段效应的单元移动，所述片段效应热点区域，为芯片布局区域的一个窗口，其满足： ，其中 是一个给定的常数， 是该窗口的总面积， 是该窗口中所有6TPPNN单元的面积和；

b）在每个片段热点区域，对每一个6TPPNN单元，构造一个赋权表，任意两个单元之间的权值等于他们之间的曼哈顿距离；

c）找到最小权值的两个聚类单元，通过单元移动将6TPPNN单元移动到一起组成新的聚类；

d）为每一个聚类找一个最优区进行放置。

2.根据权利要求1所述的基于最小宽度约束的6T&6TPPNN单元布局方法，其特征在于，所述步骤1）进一步包括以下步骤：a）给定一个有多个标准单元和多条线网的混合高度单元全局布局；

b）设定一个矩形框作为布局区域，设定矩形框左下角、右上角的顶点坐标；设定单元的左下角坐标及其宽度和高度；

设定每个单元的Vdd/Vss引脚，其宽度为给定的常数；设定高、低阈值电压单元和标准阈值电压单元的集合；最小宽度约束为给定的常数；

将每个单元放置到其左下角坐标上，并满足以下 约束条件：（1）单元间互不重叠；（2）单元放置于布局区域内部；（3）单元放在布局行相应的位点上；（4）单元匹配到正确的Vdd/Vss轨道；（5）6TPPNN单元均满足最小宽度约束；

c）将所有6T&6TPPNN单元对齐到最靠近正确的电源轨道布局行上。

3.根据权利要求1所述的基于最小宽度约束的6T&6TPPNN单元布局方法，其特征在于，所述步骤2）进一步包括以下步骤：a）给定一个初始半径r，对一个最小宽度冲突单元，以其为中心，r为半径构造一个局部搜索圆形区域；

b）在此局部搜索圆形区域中，搜索所有与冲突单元具有相同电压的单元，构造成同时在此冲突单元与每一个搜索单元之间设置的权重；

c）遍历所有权重，找到权重最小的单元序对，然后将单元进行聚类；

d）为每一个聚类找一线长增量最优区；

e）分别计算每条线网中除了聚类包含的单元外其它所有单元的边界盒。

4.根据权利要求3所述的基于最小宽度约束的6T&6TPPNN单元布局方法，其特征在于，所述权重公式为：其中，

是单元 的左下角坐标， 是单元 宽度和高度， 是单元 的左下角坐标， 是单元 宽度和高度，

若单元 和 均违反最小宽度约束，则 ，否则， 是单元 和 之间的曼哈顿距离。

5.根据权利要求3所述的基于最小宽度约束的6T&6TPPNN单元布局方法，其特征在于，所述最优区的寻找公式为：设聚类 ，其中 表示聚类 所包含的单元个数，最优区通过求解下列问题的最优解得出：

其中 表示与单元 相连的单元个数。

6.根据权利要求1所述的基于最小宽度约束的6T&6TPPNN单元布局方法，其特征在于：所述步骤3）中，进一步包括以下具体步骤：将6TPPNN单元转化为三倍行高的单元，便于后续阶段对单元进行合法化。

7.根据权利要求1所述的基于最小宽度约束的6T&6TPPNN单元布局方法，其特征在于：所述找到最小权值的两个聚类单元，通过单元移动将6TPPNN单元移动到一起组成新的聚类的步骤，进一步包括，在单元移动过程中，计算每一个聚类中6TPPNN单元的宽度和；

将宽度和小的6TPPNN聚类移动到宽度和大的6TPPNN聚类，并组合成新的聚类。

8.根据权利要求1所述的基于最小宽度约束的6T&6TPPNN单元布局方法，其特征在于：所述步骤5），进一步包括以下具体步骤：a）将6T&6TPPNN单元合法化问题转化为二次规划问题，其相应数学模型如下：使得：

（1）对相同行的所有相邻单元 和 ，若 ，有： ；

（2）对所有单元 ，有 .

其中 和 是单元 和 在合法化之前的 坐标；

b）应用基于模迭代法(MMSIM)求解器对此合法化问题进行高效求解。

说明书

基于最小宽度约束的6T&6TPPNN单元布局方法

技术领域

[0001] 本发明涉及超大规模集成电路(VLSI)物理设计自动化技术领域，特别是涉及一种单元布局方法。

背景技术

[0002] 在传统电路设计中，具有相同高度的标准单元更易于设计和优化。然后随着设计复杂性的提升，具有混合高度的一般的6T&6TPPNN单元结构相对于单倍高标准单元，可以实现面积和可绕线性更好的平衡。具体而言，更小的单元高度可以实现更小的面积和更低的功耗，但是其电源驱动力较低。相反，更高的单元高度可以实现更大的电源驱动力和更好的可绕线性，但是其也需花费更大的面积和更高的功耗。由于单元结构的异质性，使得这种混合高度单元的电路设计更富于挑战性。而且，在这种布局设计时，需要额外考虑多倍行高单元对齐到正确的电源线(Vdd)和接地线(Vss)轨道上。Vdd/Vss轨道线在布局单元行中交叉排列，每个单元必须对齐到正确的电源轨道，使得Vdd/Vss的引脚与相应的轨道匹配。对于一般的6T单元，其Vdd/Vss引脚位于单元两侧。因此，对于一般的偶数倍行高的6T单元，其两端的Vdd/Vss引脚相同，所以其只能对应到特定的电源轨道行上；而对于一般的奇数倍行高的6T单元，其两端的Vdd/Vss引脚不同，则其可直接或经竖直翻转后对齐到任意行布局上。对于一般的6TPPNN单元，首先其均为两倍高单元，而且其 Vdd/Vss引脚位于单元内部。因此，6TPPNN单元需对应到特定的布局半行上。

[0003] 如图1所示，6T单元在集成电路内部布局行上面会占据一行或者多行，其布局的上下边界和行的上下边界重合；6TPPNN单元高度为两倍行高，但其在集成电路内部布局行上会跨越三行，其布局的上下边界和行的中间水平线重合。

[0004] 此外，应用多阈值电压的方法被广泛用于平衡时延和功耗，其可以在保持良好的电路性能的同时减少电源的泄露。在6T&6TPPNN多阈值电压电路设计中，有三种电压，分别为高阈值电压，低阈值电压及标准阈值电压。在本发明专利中，我们将高/低阈值电压单元集合记为ULVT，将标准阈值电压单元集合记为SVT。

[0005] 然而随着单元特征尺寸的减少，且由于光刻技术的限制，多阈值电压单元在布局时可能会违反复杂的最小宽度约束。最小宽度约束是指在每一轨道半行上，对相同电压单元的宽度和指定了一个宽度下界。若一个单元所在半行其相邻相同电压的宽度和小于给定的最小宽度下界，则此单元引发最小宽度约束。此外，由于6TPPNN 单元是双倍高，且其只能放在半行上，因此每个6TPPNN单元其上下两边均会产生半行的片段效应，该效应对电路布局性能具有显著影响。

发明内容

[0006] 为了解决现有技术存在的不足，本发明的目的在于提供一种基于最小宽度约束的6T&6TPPNN单元布局方法，在不增加任何芯片设计面积的前提下，减少最小宽度约束的引起的线长增长，降低片段效应。

[0007] 为实现上述目的，本发明提供的基于最小宽度约束的6T&6TPPNN单元布局方法，包括以下步骤：

[0008] 1)考虑Vdd/Vss轨道对齐约束的单元对齐；

[0009] 2)基于最小宽度约束的单元聚类；

[0010] 3)6TPPNN单元转化；

[0011] 4)基于片段效应的单元移动；

[0012] 5)二次规划问题模型及基于模迭代法求解。

[0013] 进一步地，所述步骤1)进一步包括以下步骤：

[0014] a)给定一个有多个标准单元和多条线网的混合高度单元全局布局；

[0015] b)设定一个矩形框作为布局区域，设定矩形框左下角、右上角的顶点坐标；设定单元的左下角坐标及其宽度和高度；

[0016] 设定每个单元的Vdd/Vss引脚，其宽度为给定的常数；设定高、低阈值电压单元和标准阈值电压单元的集合；最小宽度约束为给定的常数；

[0017] 将每个单元放置到其左下角坐标上，并满足一下约束条件：(1)单元间互不重叠；(2)单元放置于布局区域内部；(3)单元放在布局行相应的位点上；(4) 单元匹配到正确的Vdd/Vss轨道；(5)6TPPNN单元均满足最小宽度约束；

[0018] c)将所有6T&6TPPNN单元对齐到最靠近正确的电源轨道布局行上。

[0019] 进一步地，所述步骤2)进一步包括以下步骤：

[0020] a)给定一个初始半径r，对一个最小宽度冲突单元，以其为中心，r为半径构造一个局部搜索圆形区域；

[0021] b)在此局部搜索圆形区域中，搜索所有与冲突单元具有相同电压的单元，构造成同时在此冲突单元与每一个搜索单元之间设置的权重；

[0022] c)遍历所有权重，找到权重最小的单元序对，然后将单元进行聚类；

[0023] d)为每一个聚类找一线长增量最优区；

[0024] e)分别计算每条线网中除了聚类包含的单元外其它所有单元的边界盒。

[0025] 更进一步地，所述权重公式为：

[0026]

[0027] 其中，

[0028] (xi,yi)是单元ci的左下角坐标，(wi,hi)是单元ci宽度和高度，(xj,yj)是单元cj的左下角坐标，(wj,hj)是单元cj宽度和高度，

[0029] 若单元ci和cj均违反最小宽度约束，则θij＝1，否则，θij＝2；|xi-xj|+|yi-yj| 是单元ci和cj之间的曼哈顿距离。

[0030] 更进一步地，所述最优区的寻找公式为：

[0031] 设聚类 其中 表示聚类u1所包含的单元个数，最优区通过求解下列问题的最优解得出：

[0032]

[0033] 其中mi表示与单元uci相连的单元个数。

[0034] 进一步地，所述步骤3)中，进一步包括以下具体步骤：将6TPPNN单元转化为三倍行高的单元，便于后续阶段对单元进行合法化。

[0035] 进一步地，所述步骤4)进一步包括以下具体步骤：

[0036] a)在片段效应热点区域进行基于片段效应的单元移动，所述片段效应热点区域，为芯片布局区域的一个窗口，其满足：Afrag/Awind≥τ，其中τ是一个给定的常数，Awind是该窗口的总面积，Afrag是该窗口中所有6TPPNN单元的面积和；

[0037] b)在每个片段热点区域，对每一个6TPPNN单元，构造一个赋权表，任意两个单元之间的权值等于他们之间的曼哈顿距离；

[0038] c)找到最小权值的两个聚类单元，通过单元移动将6TPPNN单元移动到一起组成新的聚类；

[0039] d)为每一个聚类找一个最优区进行放置。

[0040] 更进一步地，所述找到最小权值的两个聚类单元，通过单元移动将6TPPNN单元移动到一起组成新的聚类的步骤，进一步包括，

[0041] 在单元移动过程中，计算每一个聚类中6TPPNN单元的宽度和；

[0042] 将宽度和小的6TPPNN聚类移动到宽度和大的6TPPNN聚类，并组合成新的聚类。

[0043] 更进一步地，所述步骤5)，进一步包括以下具体步骤：

[0044] a)将6T&6TPPNN单元合法化问题转化为二次规划问题，其相应数学模型如下：

[0045]

[0046] 使得：

[0047] (1)对相同行的所有相邻单元ci和cj，若x′i≥x′j，有：xi-xj≥wj；

[0048] (2)对所有单元ci，有xi≥0.

[0049] 其中x′i和x′j是单元ci和cj在合法化之前的x坐标；

[0050] b)应用基于模迭代法(MMSIM)求解器对此合法化问题进行高效求解。

[0051] 为实现上述目的，本发明还提供一种计算机可读存储介质，其上存储有计算机指令，所述计算机指令运行时执行如上文所述的基于最小宽度约束的6T&6TPPNN 单元布局方法的步骤。

[0052] 与现有技术相比，本发明的基于最小宽度约束的6T&6TPPNN单元布局方法，具有如下技术效果：

[0053] (1)通过基于图的聚类算法，使具有同种电压的6T&6TPPNN单元聚类成一个紧密的结构来实现对引起最小宽度约束冲突单元的处理。为聚类过程中极小化线长增长，我们运用中值公式对每一个聚类寻找一个最优区作为单元聚类后的最优放置位置；

[0054] (2)使用基于片段效应的单元移动方法在片段效应热点区域对6TPPNN单元进行移动，实现片段效应的降低；

[0055] (3)将6TPPNN单元转化为三倍高单元后，我们将6T&6TPPNN单元合法化问题转化为二次规划(QP)问题，并使用基于模迭代法(MMSIM)对其进行求解；

[0056] 实验结果表明，本发明的方法，在不增加任何芯片设计面积的前提下，可在完全解决所有最小宽度约束的基础上仅引起3.6％的线长增长，同时平均降低片段效应达40900nm，其显著提高了电路性能。

[0057] 本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。

附图说明

[0058] 附图用来提供对本发明的进一步理解，并且构成说明书的一部分，并与本发明的实施例一起，用于解释本发明，并不构成对本发明的限制。在附图中：

[0059] 图1为6T单元和6TPPNN单元在集成电路内部布局行上的分布，以及片段效应的产生和减少的示意图；

[0060] 图2为根据本发明的基于最小宽度约束的6T&6TPPNN单元布局方法流程图。

具体实施方式

[0061] 以下结合附图对本发明的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本发明，并不用于限定本发明。

[0062] 图2为根据本发明的基于最小宽度约束的6T&6TPPNN单元布局方法流程图，下面将参考图2，对本发明的基于最小宽度约束的6T&6TPPNN单元布局方法进行详细描述。

[0063] 本发明的基于最小宽度约束的6T&6TPPNN单元布局方法的数学模型描述如下：

[0064] 首先给定一个含有n个标准单元C＝{c1,c2,…,cn}和m条线E＝{e1,e2,…,em}的 6T&6TPPNN单元全局布局。布局区域为一矩形框，其(0,0)和(W,H)分别是矩形框左下角和右上角的顶点坐标。设(xi,yi)是单元ci的左下角坐标，(wi,hi)是其宽度和高度。每个位点的宽度为sitew。每个单元具有相应的Vdd/Vss引脚。设CUL和CS分别是高/低阈值电压单元(ULVT)和标准阈值电压单元(LVT)的集合。最小宽度ω是一个给定的常数。

[0065] 基于最小宽度约束的6T&6TPPNN单元布局目标是将每个单元ci放置到坐标 (xi,yi)上，使得单元总位移量最小、不产生面积溢出，并且满足以下5个约束条件： (1)单元间互不重叠；(2)单元放置于布局区域内部；(3)单元放在布局行相应的位点上；(4)单元匹配到正确的Vdd/Vss轨道；(5)6TPPNN单元均满足最小宽度约束。其数学模型为：

[0066]

[0067] 并满足下列约束条件：

[0068] 1)

[0069] 2)

[0070]

[0071] 3)

[0072] 4) 其中，单元 在同一半行且两两相邻。

[0073] 首先，在步骤201，将考虑Vdd/Vss轨道对齐约束的单元对齐。具体实现方法详细叙述如下：

[0074] 为实现高质量的合法化结果，保持初始的全局布局十分重要。因此我们首先将所有单元对齐到最近的布局行上。由于6TPPNN单元的Vdd/Vss引脚在单元内部，且其内部两个引脚分别Vdd引脚和Vss引脚，因此，在考虑Vdd/Vss轨道对齐约束时，我们可以将6TPPNN单元视为奇数倍高单元。因此，对奇数倍高单元(6TPPNN) 单元，最近的行(半行)即是最接近其纵坐标的行；对偶倍高单元，最近的行即是最靠近其纵坐标的正确的电源轨道的布局行。通过更新单元的纵坐标，我们可以实现将所有6T&6TPPNN单元对齐到最近过的正确的电源轨道布局行(半行)上。

[0075] 在步骤202，基于最小宽度约束的单元聚类。具体实现方法详细叙述如下：

[0076] 基于最小宽度约束的单元聚类算法在一个动态的局部区域中进行，给定一个初始半径r。对一个最小宽度冲突单元，我们首先以其为中心，r为半径构造一个局部搜索圆形区域。然后，我们在此区域中搜索所有与该冲突单元具有相同电压的单元，同时在此冲突单元与每一个搜索单元之间设置一个合适的权重。权重公式给出如下：

[0077]

[0078] 若单元ci和cj均违反最小宽度约束，则θij＝1，否则，θij＝2.|xi-xj|+|yi-yj|是单元ci和cj之间的曼哈顿距离。显然，我们的权重公式具有以下两个特点：单元距离越近，越可能被聚类；单元高度相同，越可能被聚类，因为单元高度越接近，其所需插入的填料越少。

[0079] 通过遍历所有权重，我们找到权重最小的单元序对(单元ci和cj)，然后我们将单元ci和cj进行聚类。此基于最小宽度约束的单元聚类算法终止，当且仅当没有最小宽度冲突单元存在时。然后，我们为每一个聚类找一线长增量最小的区域(最优区)，其具体寻找最优区方式如下：设聚类 (其中 表示聚类ul所包含的单元个数)，则求解其相应最优区可通过求解下列问题的最优解得出：

[0080]

[0081] 其中mi表示与单元uci相连的单元个数。

[0082] 求解过程为分别计算每条线网neti中除了单元uci外包含其它所有单元的边界盒。对每个边界盒，分别对所有边界盒的横坐标和纵坐标按由小到大进行排序，然后计算排序后横坐标及纵坐标的中值。显然，边界盒坐标中值所构成的区域，即是上述问题的最优解，其即为单元线长增量最小的区域(最优区)。

[0083] 在步骤203，6TPPNN单元转化。在6TPPNN单元转化阶段，本发明将6TPPNN 聚类(单元)转化为三倍高单元，以便于后续阶段对单元进行合法化。

[0084] 在步骤204，基于片段效应的单元移动。具体实现方法详细叙述如下：

[0085] 在此阶段，为了避免过多的单元位移，本发明的基于片段效应的单元移动过程仅在片段效应热点区域中进行。

[0086] 首先给出片段效应热点区域定义如下：

[0087] 片段效应热点区域：片段效应热点区域是芯片布局区域的一个窗口，其满足： Afrag/Awind≥τ，其中τ是一个给定的常数，Awind是该窗口的总面积，Afrag是该窗口中所有6TPPNN单元的面积和。

[0088] 在每个片段热点区域，对每一个6TPPNN单元(聚类)，构造一个赋权表。任意两个单元之间的权值等于他们之间的曼哈顿距离。一旦我们找到最小权值的两个单元(聚类)，我们便通过单元移动将6TPPNN单元移动到一起组成新的聚类来降低片段效应。在单元移动过程中，我们计算每一个聚类中6TPPNN单元的宽度和，然后将宽度和较小的6TPPNN聚类移动到宽度和较大的6TPPNN聚类，并组合成新的聚类，如此，可避免造成在降低片段效应的过程中引起单元内部重叠。那之后，我们依然运用中值公式为每一个聚类找一个最优区进行放置。由于异质性的单元结构，一旦两个聚类被用于聚类来减少片段效应，那么这两个单元将不会再被卷入后续过程。

[0089] 在步骤205，二次规划问题模型及基于模迭代法求解，具体实现方法详细叙述如下：

[0090] 经过上述处理过程，所有的最小宽度约束冲突单元已经全部得到处理，片段效应得到降低。在此阶段我们将一般的6T&6TPPNN单元合法化问题转化为二次规划 (QP)问题，其数学模型如下：

[0091]

[0092] 使得：

[0093] (1)对相同行的所有相邻单元ci和cj，若x′i≥x′j，有：xi-xj≥wj；

[0094] (2)对所有单元ci，有xi≥0.

[0095] 其中x′i和x′j是单元ci和cj在合法化之前的x坐标。

[0096] 由于经过我们的6TPPNN单元转化阶段，我们已经将6TPPNN单元转化为三倍高单元，因此，我们可以直接应用基于模迭代法(MMSIM)对此合法化问题进行高效求解。且我们可以得到以下定理。

[0097] 定理1：MMSIM可在O(n)的时间复杂度下求得问题(3)的最优解，其中n为单元变量的个数。

[0098] 本发明还提供一种计算机可读存储介质，其上存储有计算机指令，所述计算机指令运行时执行如上文所述的基于最小宽度约束的6T&6TPPNN单元布局方法的步骤。

[0099] 本领域普通技术人员可以理解：以上所述仅为本发明的优选实施例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。