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

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

MOS晶体管最佳二维共质心结构生成算法
我们的算法分为以下五个子步骤。 算法的输入是晶体管单元电路原理图和设计规则。 输出是晶体管单元电路的最佳公共质感布局。 在介绍整个算法之前，我们会给出一些必要的定义。
定义3:堆栈是一串晶体管指链，没有任何间隔，构建了正确的电子布局，共享源极和漏极。 在堆栈中，每个手指具有相同的通道宽度。
定义4：公共质心阵列是一种特殊的堆栈，必须满足定义1和条件1。
定义5：公共质心矩阵由多行堆栈组成，必须满足定义1和条件1。晶体管手指不共享源极和漏极。

如果有一个MOS晶体管单元电路对应的完全公共质心阵列或矩阵的紧凑布局，每个晶体管的指数必须是偶数或最多只有一个奇数 数字。 证明：如果晶体管A存在于阵列或矩阵中ai，且指ai如果不是质地，A的另一个手指aj与ai中心对称。 因此，晶体管A的指数必须是偶数。 但如果手指 ai 就质地而言 A 指数必须是奇数。

共享源漏区多，虚拟手指少。MOS晶体管的手指序列应根据原电路原理图构建扩散图。 将CMOS电路中的每个节点映射到图的顶部，并将晶体管的每个源泄漏连接到多边，得到与晶体管指数相同的电路扩散图 . 图2(a)扩散图如图2所示(b)所示。

对于集合${\sum }_{lega{l}_W}$中的每个w，我们可以得到一个手指向量W/w，它描述了所有晶体管的手指数。 每个向量 W/w 对应一个扩散图。 我们的算法是在所有这些扩散图中找到最优解。

为了构造公共质心数组或矩阵，我们首先构造一个仅由一半手指组成的堆栈，然后邻接其余的镜像副本。
定义6：半扩散图G=是任意两个顶点之间的边数为原扩散图一半的扩散图。
定理 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. 定义 1 足以构建电阻器和电容器的公共质心结构，但对于晶体管，定义 1 和条件 1 一起就足够了，因为具有不相等手性的晶体管将经历与方向相关的失配 [6]。
3. 失配被定义为导致过程引起的、与时间无关的相同设计设备的物理质量随机变化的过程[4]。
4. 还有其他布局样式，其不匹配已在 [5] 中进行了测量和比较。 发现使模拟设备不匹配最小化的最佳布局样式是通用质心布局。
5. 具有不相等手性的晶体管将经历与方向相关的失配 [6]。【大致实现，让我开始写论文的时候，具体的工程需求，从而立足一下文章的意义怎么写，请教一下工程师。做这个算法 为什么这么做的出发点 为什么要匹配 对什么性能有影响，左旋和右旋的影响，工程上是不是有需求，工程上倾向于怎样的设计】
6. 最大行数以及每行的finger数具体计算不清晰