大规模集成电路原图图形的最小划分

D01:10.13374/i.issn1001053x.1981.04.014 大规模集成电路原图图形的最小划分 工程图学教研室陈仁宽 摘 要 本文给出LSI原图图形划分成最小矩形数的公式，并为这样 的划分提出改进的算法。， 集成电路掩膜原图上的图形，都是由水平和垂直的直线所围成，其内部包括中空部分。 感光板靠透过图形发生器的矩形小窗的光照来曝光。适当地变换矩形小窗的尺寸、形状进行 曝光可在感光板上描绘出所需的图形，因此希望图形用最少的单元矩形之和来表示，而且要 求矩形不互相重迭，以保证原图的精度。发生器工作由计算机控制。 平面上有限个矩形单元的集合称为矩形单元组合体。集成电路原图上所呈现的图形，对 应为矩形单元组合体结构的一个平面图形。具有上述特征的图形，以下称图形P。集合所包 含的矩形单元的个数M称为划分数，本文将论述这样一个计算几何问题一一给出任何一个图 形P的最小划分数和完成这种刘分的算法。 设图形P的顶点数为N,构成闭合的边界数为B,即P没有中空部分时B=1,K个中空 部分时B=K+1。内角为直角的顶点称为凸点，设其个数为N1,内角是三个直角的顶点 (图1中用小圆圈表示)，称为凹点，设其个数为N2。 定理一：对于任何图形P有下列关系 N1=N+4-2B (1.1) 2 N2=N-4+2B 2 (1.2) N=12 B=2 =6 N=6 图1 图2 证：作辅助线，把P划分为若干三角形（图2）。设三角形的个数为R,辅助线的条数 为E。根据图论里欧拉公式（参阅参考文献2） n(頂点数)+r(区域数)-e(边数)=2 144

大规模集成电路原图图形的最小划分 工 程 图学教研 室 陈仁 宽 摘 要 本文给 出 原 图 图形 划分成最小矩形傲 的公 式 ， 并为这样 的划分提 出改进的 算法 。 、 集成 电路掩膜原 图上 的 图形 ， 都是 由水 平和垂直 的直线所 围成 ， 其 内部包 括 中空部分 。 感光板靠透过图 形发生器的 矩形小窗 的光照 来 曝光 。 适 当地 变换矩形小窗的尺寸 、 形状进 行 曝光可在 感光板上描绘 出所 需的 图形 ， 因此希望 图形用 最少 的单元 矩形 之和 来表 示 ， 而且要 求矩形 不 互 相重 迭 ， 以 保证原图的精度 。 发生 器工 作 由计算机控 制 。 平面 上 有限 个矩形单 元 的集合称为矩 形单元组 合 体 。 集成 电路原 图上所 呈现的图形 ， 对 应 为矩形单元组 合体结 构 的一 个平面 图 形 。 具有上 述特征 的图形 ， 以 下称 图形 。 集合所包 含的 矩形单元 的个数 称为划分数 ， 本文将论述这样一个计算几何 问题— 给出任何一个图 形 的最小划 分数和完成这种 划 分 的算法 。 设 图形 的 顶点数为 ， 构成 闭合 的边界数为 ， 即 没 有中空 部分时 一 ， 个 中空 部分 时 。 内角为直 角的顶点 称为凸点 ， 设 其个数 为 ， 内角是 三 个直 角的顶点 图 中用 小 圆圈 表示 ， 称为凹点 ， 设其 个数为 。 定理 一 对于 任何图 形 有下列关 系 · · 夸 一 斗 一 。 二 二 户 广 ‘ 习 图 图 证 作辅助线 ， 把 划 分为若干三 角形 图 。 设 三 角形的个数为 ， 辅 助线 的 条数 为 。 根 据图 论里 欧拉公 式 参阅参考文献 顶点数 区域数 一 边数 科 DOI ：10．13374／j ．issn1001—053x．1981．04．014

这里由于不计外区域和中空区域，原图形P的边界为环路，其边数等于頂点数，因此有 N+R-(N+E)=2-B (1) 又因P的边界线只是一个三角形的边，而辅助线是两个三角形的公共边，则有3R±N+ 2E,'根据式(1)和上式，则有 R=N-4+2B (2) 因各三角形内角总和与P的各顶点的内角之和相等，故 (N-4+2B)×2∠R=N,×∠R+N:×3∠R (3) 又N,+N2=N,代入上式整理即得 N,=N+4-2B 2 N:=义-4+2B 证华。 从分析图形可知，凸点总是图形P里某矩形单元的顶点，划分P的线（称划分线）总是 从凹点引出。在P点任取一凹点，向X或Y方向作划分线时，必然是下列的情况之一：1)刘 分线与边界线（或和已划出的划分线）相交，交点称划分点，图3(b)里用△记号表示，2) 划分线恰好通过另一个凹，点，如图3()，称这种联结情况为并联 型。给出图形P,对于并联型的凹点显然应连接这些凹点。对于 第一种情况的凹点则向X或Y任取一方向作划分线，与P的边界 相交，且只相交一点，以后再取另一个凹点作划分线，对所有凹 煮都进行这样划分，就可完成一次划分。这种划分称为合理划 图3， 分。· 是理二：对于一个无并联型凹点的图形P,作合理划分，其划分数M和划分，方式无关 其划分数为 M=N+B-2 2 (4) ·证：由于没有并联型凹点，且作合理划分，无论凹点向X还是向Y引刘分线，和它对应的 划分点只有一个，所以划分点个数N分=N:。又图形经刘分后，边数比原图增加了2N:条线 (除分线外，对应边也被划分点分为两个线段)。经划分后，图形是连通的，由欧拉公式 n+r-e=2 以n=N+N:,e=N+N,r=M+B代入，整理即得 M=N:+2-B =(N-4+2B)+2-B 2 =N+B-2 2 证毕： 对于有并联型凹点的图形P,显然划分数M和划分方式有关，划分点数N分<N:,因 此有 定重三：对于图形P作合理划分，其划分数 145

这里 由于不计外 区域 和 中空 区域 ， 原 图 形 的 边界为环路 ， 其边数等于填 点数 ， 因此有 一 一 ’ 又 因 的边界线只 是一个三 角形的边 ， 而辅助线是 两个三 角形 的公共边 ， 则 有 ” 瓦 ， 根据式 和 上 式 ， 则有 一 · 因各三 角形 内角 总和 与 的 各顶点 的 内角之和 相 等 ， 故 ‘ 一 ” ‘ 、 、 一 乙 艺 匕 又 ， 代入 上 式 整理 即得 “ 一 粤 一 十 一 ” 攫一 十 ” 证单 从分析图形可 知 ， 凸点 总是 图形 里 某 矩形单 元的 顶点 ， 划 分 的线 称 划 分线 总是 ‘ 从 画点引出 。 在 点任取 一 凹 点 ， 向 或 方 向 作划 分线 时 ， 必 然是 下列 的情 况 之一 划 夯线与边界线 或和 巳划 出的划 分线 相交 ， 交 点称划 分点 ， 图 里用八记 号表示 ， 一 喧 划 分线恰好通 过 另一个凹 点 ， 如 图 ， 称 这种 联结情况 为并联 型 。 给 出图形 ， 对于并联 型 的 凹点显然应 连 接这些 凹 点 。 对于 第“ 种情况的 凹点则向 或 任取一方 向作划 分线 ， 与 的边界 相交 ， 且只 相交一点 ， 以 后再取 另一个凹 点作划 分线 ， 对所有凹 照都进行这样 划 分 ， 就可完 成一 次划 分 。 这种 划 分称 为合 理划 分 。 凸 凸 图 定理二 对 于一 个无 并联 型 凹点 的 图形 ， 作 合理划 分 ， 其划 分数 和划 分 ， 方式 无 关 其划 分数 为 。 」且 — 十 一 乙 一 证 由于没有并联型 凹点 ， 且 作合 理 划 分 ， 无 论 凹 点向 还是 向 引划 分线 ， 和 它对应的 划 分点只 有一个 ， 所 以划 分点 个数 分 二 。 又 图形经划 分后 ， 边数 比原 图 增加 了 条线 对应 边也被划分点分 为两个线 段 。 经划分后 ， 图形是连通 的 ， 由欧拉公式 一 片 ， 代入 ， 整 理 即得 一 今 一 ‘ “ ， 一 ” 答 一 证毕 对于有并联 型 凹 点 的 图形 ， 显 然 划 分数 和 划 分方 式 有关 ， 划 分点 数 分 ， 因 此有 定翔三 对于 图形 作 合理 划 分 ， 其 划 分数

M丹+B-2 定理二和三的内容及证明虽然和参考文献【】里稍有区别，但对算法却提供了有力的依 据。它使我们从形形色色的图形，各种可能的刘分方式中解放出来，在考虑算法时，只要对 并联型的凹点先以直线连接，其它凹点按合理划分进行，就能获得最优划分。 在参考文献【！里给出一种刘分的算法，其基本想法转述如下： (1)在P的水平边中，设y坐标最大的边为AB=(x1,x',y)。其中x1为A点的x 坐标，x'为B点的x坐标，y:为AB的y坐标。 (2)在沿X轴向，投影与AB重迭的边中，设y坐标最大的边为CD,且 CD=(x2,x',y:),(x1,x)∩(x2,x'2)丰中 (3)设矩形L为由AB和从A、B点向下作的垂线以及CD所围成，即 L={(x,y)∈R2|x≤x≤x'1,y2≤y≤y} (4)如L=P,则计算完毕，如果不是，就把从P中减去L后的图形，重新作为P(数据 结构要更新)，再从头开始计算。 这个算法对定理二指出的情况能给最小划分，出对有并联型凹点的图形则不能求得最优 解答。此外文中只给出想法而没有写明采用什么样的数据结构表示图形P。下面就这些方面 进一步作一些探讨和改进。 1.败据结构 图形P的内外边界都是简单回路，它的每个頂点的内向积和外向积均为1。为了算法中 经常要存取、插入和删除，考忠用双向链表来表示图形P。每条闭合的边界线用一条环形链 来表示。链表的每个结点，其数据城存放图形頂点的编号、坐标和凹点标记：另外有两个指 针，向前指针存放先导结点的地址和编号，向后指针存放后继结点的地址。以Y坐标最大中 最右的一点为链头。以链头所在的水平向量为首向量。以逆时针作为外边界的链表指向，以 顺时针作为内边界的链表指向（图4），图中A、B各为相应的链头。 2.算法 (1)设有首向量AB=(x1,x'1,y1),取其先导向量EF(x2,x',y:)和后继向量 CD(x,x',y)检查C、D、E、F四点中有无凹点，有则执行下一步，否则，置状态变 量0=3，转第4步。 (2)如果(x1,x')∩(x2,x'2)∩(x3,x') =中，且y:=ys,则令yz为y,置变量o=0(如 图5)，否则，令y=max{y2,y}(两数中取 大值)，置变量o=1(如图6) (3)取各内边界的首向量（x1,x‘:1)i=1 2…m。如果(x1,x)∩(x1,x')牛中且y: 图4 图5 >y则令y=yi,置①=2。 (4)按状态变量⊙，作下列处理，输出矩形L和更新数据结构。 对@=0，作并联处理事 ⊙=1，作单凹点处理影 0=2,作中空处理 ①=3，作无凹点处理。（见下面说明）。 146

、 ， ， ’ 州 二生 — 十 艺 — 定理二和三 的内容及证 明 虽然和 参考文 献 ‘ 里 稍有区别 ， 但 对算法却提供 了有力的依 据 。 它使我 们从形形 色色的图形 ， 各种可 能 的划 分方 式 中解放 出来 ， 在考虑算法时 ， 只 要对 并联 型 的 凹点 先 以 直线连 接 ， 其 它 凹点按 合 理划 分进 行 ， 就 能获 得最优划 分 。 在 参考文 献 ‘ 里给 出一种 划分 的 算法 ， 其基 本 想法 转述如 下 一一 寸 在 的 水 平边 中 ， 设 坐标最大的边为 ， ， ， 。 其 中 为 点的 且 一 州 坐标， 尹 为 点的 坐标， 为 的 坐标 。 在 沿 轴 向 ， 一 ， 投影 与 重 迭的 边 中 ， 设 坐标 最大的 边为 ， 产 ， ， ， ， 尹， ， 斗 小 设 矩形 为由 和 从 、 点向下 作的垂 线 以 及 所 围成 ， 即 ， 〔 三 三 尹 ， 三 三了 “ 如 ， 则计 算完毕 ， 如 果不 是 ， 就 把 从 中减去 后 的 图 形 ， 重新 作为 数据 结 构要 更新 ， 再 从头开 始计 算 。 这 个算法对定 理二 指 出的 情况 能 给 最小 划分 ， 出对 有并联 型 凹点的 图 形则不 能 求得最优 解答 。 此外文 中只 给出 想法而没有写 明采用 什 么样 的 数据结 构表示 图形 。 下面就这些 方面 进 一 步作一些 探讨 和 改 进 。 胜 结构 图 形 的 内外边界都是 简单 回路 ， 它的每个顶 点的 内向积和 外向 积均为 。 为 了算法中 经 常要 存取 、 插 入 和 删除 ， 考虑 用 双 向链 表 来表示 图 形 。 每 条 闭合的 边界线用一 条环形链 来表示 。 链表的 每个结 点 ， 其数据域 存放图形顶点的 编号 、 坐标和 凹点标记， 另外有两个指 针 ， 向前指 针存放先导结 点的 地址 和 编 号 ， 向后 指针存放后继结 点的 地址 。 以 坐标最大 中 最右的 一 点为链头 。 以链 头所在 的水 平向量为首 向量 。 以 逆时针作为外 边界的链 表指 向 ， 以 顺时针作为内边界的 链 表指 向 图 ， 图 中 、 各为 相应 的链 头 。 算 法 门 一 寸 设有首向量 ， 产 ， ， ， 取 其 先导 向量 ， 了 ， 和 后 继 向量 。 ， 尹 ， 检 查 、 、 、 四 点 中有无 凹点， 有则执 行下一 步， 否则 ， 置状态 变 。 ， 转 第 步 。 如 果 ， 矛 门 ， ， 门 。 ， 尹 小 ， 且 。 ， 则令 为 ， 置 变量 。 如 图 ， 否则 ， 令 ， 两数 中取 大值 ， 置 变最 。 如图 取 各内边界 的 首 向量 ‘ ， 矛‘ … … 。 如 果 ， 尹 门 ‘ ， ， 尹‘ 今 小且 ‘ ， 图 图 则令 ‘ ， 置 。 。 按状态 变最 。 ， 作下 列 处 理 ， 输 出矩 形 和 更新 数据结 构 。 对 。 二 ， 作 并联处 理， 。 ， 作单 凹 点处理， 。 ， 作 中空处理， ① ， 作无 凹 点处理 。 见 下面说 明 。 母

(5)如首向量的先导向量就是后继向量（即结点数等于4），则输出最后一个矩形、计 算完毕，否则，按更新后的数据从头开始计算。 上述算法中根据状态变量进行四种不同的处理，每种处理可写成公用程序块。现对这四 种处理略加说明。 ①①=0，称并联处理（图5）。输出矩形L,L由首向量AB和y:一y确定。在链表 上酬余和矩形頂点相对应的四个结点，改CD,EF中保留下米的两个结点E、D的指针， 如图5令E指向D。按y坐标大小重新确定新链头。 字原西 图6 图7 图8 ②o=1,称单凹点处理，它有图6所示子种情况：a)(x1,x')∩(x2,x':)∩(xs x')=中，b)(x1,x')门(x2,x'2)中4，（x1,x')∩(x3,x'3)+中，c)(x1,x∩ (x,x)=,(×,x')∩(x,x')≠中。处理时，首先输出矩形L,L由首向量 AB和y1一y确定，然后在链表中删余AB并在(x:,y)和(x':,y)两点中删去与纵坐 标为y的向量里相重合的那个结点（即在链表结点C,D中删去C),其中剩下的一点为划 分点，插入链表。 ③⊙=2、称中空部分处理（图7）。输出矩形L。在链表中删除首向量AB,插入划 分点M(x1,y)和N(x',y),插入内边界链的各结点，修改相应指针，建立一个新的链 表以表示外边界（如图7为MGHIJNC…)。 ④⊙=3，称无凹点处理（图8）。输出两个矩形，由坐标x2、,x':、y2、y:和坐 标x、x',、y,y:确定。然后从链表中删余向量AB、CD和EF上各结点，插入划分 点M(x',y1)和N(x,y)。 最后，这个算法比文献【山的算法估计在查找、计算上会节省些，并且也作了并联处 理。但是，这个算法对X坐标相同的并联型凹点没有进行处理，因此还不能对所有的图形都 求得最优解答。 参芳文献 〔1)小山田： “LSIブ”一卜夕一夕R夕)刀最小分割”《情报处理》VoL.16. No.7. (2)J.A.Bondy and U.S.R.Murty:"Graph Thery with A pplications" .,1976. 147

如首 向最的 先导 向量就是后继 向量 即结 点数等于 ， 则输 出最后一个矩形 、 计 算完毕 ， 否 则 ， 按 更新后 的 数据 从头 开 始计 算 。 上述算法中根 据状态 变 量进行 四 种不 同的 处理 ， 种处理略加说 明 。 每种 处理可 写 成公 用程序块 。 现对这 四 ① 。 ， 称 并 联 处 理 图 。 输 出矩 形 ， 由首 向量 和 一 确定 。 在 链表 上姗 杂和 矩 形厦 点 相 对应 的 四 个结 点 ， 改 ， 中保 留下来的 两个结 点 、 的 指针 ， 如图 令 指 向 。 按 坐标大 小重 新 确定 新链 头 。 月 、产 ﹄ 、 尹 图 人 ‘ 、 习 ， 薛习 ， 匕 己 目 ‘ 图 图 ② 。 ， 称 单 凹 点 处 理 ， 它有 图 所 示 冬种 清况 ，， 尹， 门 ， ‘ 门 产 小 ， 工 ， ， ’ 卜 一一夕 尹， 门 ， ‘ 子 译， ， 产， 门 ， 尹 斗 小 ， ， 尸 门 · ， 尹 门 ， 尸 笋 中 。 处 理时 ， 首 先输 出矩 形 ， 由首 向 里 和 一 确定 ， 然 后在 链 表 中删 余 并在 ， ， 和 产 ， 两点中删去 与纵坐 标为 的 向量 里 相 重 合 的 那 个结 点 即在 链 表结 点 ， 中删 去 ， 其 中剩下的 一 点为划 分 点 ， 插 入 链表 。 一 一寸 ③ 。 、 称 中空 部分处理 图 。 输 出矩 形 。 在 链 表 中删 除首 向量 ， 插入 划 分点 ， 和 产， ， 插 入 内边界链 的 各结 点 ， 修改 相应指 针 ， 建立一个新 的链 表 以 表示外 边界 如 图 为 … … 。 ④ 。 二 ， 称 无 凹点处理 图 。 输 出两个矩 形 ， 由坐 标 、 了 、 、 和坐 一 于 ， 一 ‘ 一今 标 ’ ‘ 、 ， 确定 。 然后 从链 表 中 删 余向量 、 和 上 各结点 ， 插 入划 分 点 尹 ， 和 ， ， 。 最后 ， 这个算法 比文 林川 的算法估 计 在 查 找 、 计 算上 会节 省些 ， 并且 也作 了并 联处 理 。 但是 ， 这个算法对 坐 标 相同的 并联 型 凹点 没 有进 行处理 ， 因此 还 不 能对所 有的图形都 求得最优解答 。 参 考 一 泛 献 〔 〕 小 山 田 “ 了 ” 一 卜 夕 一 夕 川 夕 ， 刀 最 小 分割 ” 《 情 报 处 理 》 〔 〕 “