摘要

在本文中，提出了一种在二维公共质心 MOS 晶体管矩阵中拟合任意沟道宽度晶体管的通用算法。 所提出的算法保证了晶体管单元电路的布局不仅是完整的公共质心，而且在所有公共质心结构中都是最优的。 论文还提出了一种新的信道路由算法来实现公共质心路由。 该算法的可行性由实际的模拟晶体管单元电路证明。

背景

布局引起的失配和寄生会大大降低模拟电路的性能。 众所周知，常见的质心布局样式可以使匹配要求严格的模拟器件达到更好的匹配，并且对工艺变化不太敏感。 但是两个以上的匹配设备手动生成完全最优的公共质心布局是非常困难的。 在有关模拟设备的常见质心布局生成的文献中几乎找不到任何线索，这是一个容易出错且手动费力的过程。 在[1]中，该算法可以为具有任意电容比的电容器生成公共质心布局，但不适用于晶体管。 在[2]中，通过特殊的优化算法考虑了公共质心放置、对称布线和寄生平衡，但仅限于设备对。 在[3]中，该算法只能为MOS晶体管构建一维共质心布局，但一维共质心布局有时又细又长，在布局布线时是不可取的。 更重要的是，二维公共质心布局通常比一维质心布局提供更好的梯度消除。 在本文中，我们提出了一种通用算法，用于在二维公共质心 MOS 晶体管矩阵中拟合任意沟道宽度的晶体管。

失配被定义为导致过程引起的、与时间无关的相同设计设备的物理质量随机变化的过程[4]。 如今，由于大多数模拟电路的功能是基于模拟设备的相对特性参数而不是这些参数的绝对值，因此失配对特定技术工艺中可实现的电路性能产生了根本性的限制。【意思是失配在各个工艺节点下都是要解决的问题】

我们可以用公式 (1) 来表示参数P的失配，其中$A_P$和$S_P$是参数P的技术相关面积和距离比例常数；变量D表示两个晶体管之间的间距；W和L分别表示晶体管沟道的宽度和长度。

根据失配模型，我们可以通过减小共质心器件的距离与扩散区域面积之间的距离来减少上述两种失配。 常见的质心布局可以将质心之间的距离减少到零，并消除长距离变化的影响，只要这些距离的线性函数。 即使变化包含非线性分量，它们在短距离内仍保持近似线性。 可以使公共质心布局越紧凑，它就越不容易受到非线性梯度的影响。 因此，常见的质心布局可以减少公式（1）中的两项，并且适用于所有匹配的模拟设备。 还有其他布局样式，其不匹配已在 [5] 中进行了测量和比较。 发现使模拟设备不匹配最小化的最佳布局样式是通用质心布局。
定义1：公共质心结构是由设备指组成的序列或矩阵，并满足以下条件：

1. 重合：不同匹配设备的质心至少应近似重合。 理想情况下，质心应该完全重合，称为完全共质质心结构。
2. 对称：结构应围绕 X 轴和 Y 轴对称。
3. 分散：每个设备的手指应尽可能均匀地分布在整个结构中。
4. 紧凑：结构应尽可能紧凑。 理想情况下，它应该几乎是一个正方形。
   定义2：晶体管的手性是由它包含的向右手指的分数减去它包含的向左手指的分数获得的值。
   在图1中，很明显M1的手性为1，M2的手性为-1/3，M3的手性为0。
   

条件一：晶体管共质心结构的手性条件是每个匹配的器件都应具有相等的手性。 定义 1 足以构建电阻器和电容器的公共质心结构，但对于晶体管，定义 1 和条件 1 一起就足够了，因为具有不相等手性的晶体管将经历与方向相关的失配 [6]。

调研 【太老 不重要 但是可看到发展流程】

数据集

自己构造 ，三个实际电路 和 版图构造， 没有真实的性能对比之类的参数。

实验指标

四。 实验结果和结论 我们已经用 C++ 实现了整个算法。 图6、图7和图8的所有结果都是在Sun-V880的Solaris 5.2平台上得到的。 本文提出了一种在二维公共质心 MOS 晶体管矩阵中拟合任意沟道宽度晶体管的通用算法，我们可以保证它是最优的。 实际的单元电路证明了该算法的可行性。

具体方法【现有方法和它对比 有一定参考意义】

MOS晶体管最优二维共质心结构的生成算法
我们的算法分为以下五个子步骤。 算法的输入是晶体管单元电路原理图和设计规则。 输出是晶体管单元电路的最佳公共质心布局。 在介绍整个算法之前，我们将给出一些必要的定义。
定义3：堆栈是一串没有任何间隔的晶体管指链，它部分构建了电子正确的布局并共享源极和漏极。 在堆栈中，每个手指具有相同的通道宽度。
定义4：公共质心阵列是一种特殊的堆栈，必须满足定义1和条件1。
定义5：公共质心矩阵由多行堆栈组成，必须满足定义1和条件1。在不同的行中晶体管手指不共享源极和漏极。
A. 确定MOS晶体管指的宽度定理1：
如果有一个MOS晶体管单元电路对应的完全公共质心阵列或矩阵的紧凑布局，则每个晶体管的指数必须是偶数或最多只有一个奇数 数字。 证明：如果阵列或矩阵中存在晶体管A的指ai，且指ai不在质心处，则A的另一指aj与ai中心对称。 所以晶体管A的指数必须是偶数。 但是如果手指 ai 位于质心，则 A 的手指数必须是奇数。
B. 将电路原理图转换为扩散图
要生成共享源漏区较多、虚拟手指较少的MOS晶体管的手指序列，首先要根据原电路原理图构建扩散图。 将CMOS电路中的每个节点映射到图的顶点，并将晶体管的每个源漏连接映射到多边，得到电路的扩散图，其个数与晶体管的指数相同 . 图2(a)的扩散图如图2(b)所示。

对于集合${\sum }_{lega{l}_W}$中的每个w，我们可以得到一个手指向量W/w，它描述了所有晶体管的手指数。 每个向量 W/w 对应一个扩散图。 我们的算法是在所有这些扩散图中找到最优解。
C. 生成半欧拉轨迹
为了构造公共质心数组或矩阵，我们首先构造一个仅由一半手指组成的堆栈，然后邻接其余的镜像副本。
定义6：半扩散图G=<EV,>是任意两个顶点之间的边数为原扩散图一半的扩散图。
定理 2：当且仅当扩散图中至少存在欧拉轨迹时，晶体管单元电路可以构造为堆栈样式。

证明： ⇐ 我们可以用对应的手指代替所有的边，用欧拉轨迹中的网络代替所有的顶点。 连接所有相同的门和源/漏网，我们将获得布局。⇒我们用边代替所有的手指，用顶点代替所有的网络。 因此，通过上述方法得到的顶点和边的交错序列是一个欧拉轨迹。

如果 G 不是欧拉图，我们必须添加额外的边以将其转换为欧拉图。 根据奇度顶点数必须为偶数的图解定理，我们将所有顶点两两分组，并在每组两个顶点之间添加一条虚拟边。 问题1：对分组问题是如果甚至有不同的对象，则生成所有分组解，并将它们两个两个分组。 定理 3：问题 1 的算法复杂度为 n！ 2 n / 2 × (n / 2 )！ ，其中 n 表示不同对象的数量。

尽管算法复杂度随着 n 的增加而明显增加，但我们放弃了具有许多虚拟变量的解，这些虚拟变量对应于虚拟边缘。 因此，n 的值通常很小。
我们使用集合 ∑add_edge来表示添加的边集，它是将非欧拉图转换为欧拉图的最小边集。 式(3)中，Spg代表问题1的整个解空间。G’代表半欧拉图。 我们将每条欧拉轨迹命名为 G′ Half-Euler 轨迹。

问题2：搜索所有欧拉轨迹问题。
问题 2 的算法复杂度是非多项式的。 考虑到同一晶体管的指越集中，源漏区和栅极的布线越简单，我们应该使表示同一晶体管的指的边缘尽可能集中。 我们使用以下规则来获得简化的半欧拉图 Gs： 对于图 G’ 中的任意两个顶点，如果属于 G 的边数是偶数，我们使用两条边代替这些边； 如果是奇数，我们使用一条边来代替那些边。

定理 4：Gs 也是欧拉图。 替换大大减少了边的数量，这将降低问题2的算法复杂度。对于Gs中的每条Half-Euler轨迹，我们使用与上述相反的方法来获得完整的Half-Euler轨迹G’。

D. 将Half-Euler轨迹转换为公共质心结构
D. 将Half-Euler 轨迹转换为公共质心结构 对于一维结构，我们可以直接将另一条Half-Euler 轨迹与原始的Half-Euler 轨迹以相反的顺序邻接。 在图 3 中，大写字符代表扩散图的边 ，数字表示顶点

对于二维结构，我们列出了获得公共质心矩阵的算法如下，将其应用于每个半欧拉轨迹：
1、不同的行数对应不同的二维公共质心结构，所以我们用公式（4）计算最大行数；

2. 对于给定的 RowNum，使用公式 (5) 计算每行的手指数。

3. 将半欧拉轨迹和反向欧拉轨迹分别除以EveryRowMOSNum，就会有几个完整的行，也可能有两行，其指数小于EveryRowMOSNum。 我们将完整的行从上到下一一放置，并紧靠两行半熟的行。 如果两个半生不熟的行不能组成完整的行，我们可以在间隔之间添加更多的虚拟对象，以使结构轮廓成为矩形。 在图 4 中，字符“X”代表 dummy，字符“v”代表虚拟网络，它与任何其他网络都没有连接。

定理5：我们算法得到的所有一维和二维结构都必须对应正确的电路，满足定义1和条件1。

E. 评估解决方案 我们使用成本函数 (6) 来评估每个常见的质心结构。

Cdiff 使所有扩散区域的寄生效应最小化；Carea最小化整个布局的面积； Cratio使普通质心结构的轮廓近似正方形； Cdummy 最小化假人的数量； Cconnect 将所有互连的寄生效应降至最低。

定理6：公共质心结构中的所有Nets的质心也重合。 路由规则可以表示如下：

1. 在上半矩阵中，连接同一行的网络的金属在该行的顶部通道中布线，在下半矩阵中，在底部通道中布线；
2. 在矩阵的上半部分，连接行间奇数网的金属在矩阵的左通道中，在矩阵的下半部分，在右通道中。
3. 在矩阵的上半部分，连接行间偶数网的金属在矩阵的右通道中，在矩阵的下半部分，在左通道中。
   
   在图 5 中，我们只使用不同颜色的线来代表不同的网络。 在实际布局中，我们使用 metal-1 进行水平布线，使用 metal-2 进行垂直布线。

值得跟进

1. 如何保证在所有公共质心结构是最优的？
2. 失配被定义为导致过程引起的、与时间无关的相同设计设备的物理质量随机变化的过程[4]。
3. 还有其他布局样式，其不匹配已在 [5] 中进行了测量和比较。 发现使模拟设备不匹配最小化的最佳布局样式是通用质心布局。
4. 具有不相等手性的晶体管将经历与方向相关的失配 [6]。【大致实现，让我开始写论文的时候，具体的工程需求，从而立足一下文章的意义怎么写，请教一下工程师。做这个算法 为什么这么做的出发点 为什么要匹配 对什么性能有影响，左旋和右旋的影响，工程上是不是有需求，工程上倾向于怎样的设计】
5. 最大行数以及每行的finger数具体计算不清晰