| 主权项 |
一种用于积体电路布局之绕线后阶段冗余介层洞插入之方法，包含：自一绕线后阶段设计同时建构一互斥关系图之连接线及顶点集合，其中每一顶点对应于一可行双介层洞，且若两个顶点为一连接线之端点，则该绕线后阶段设计中之相应两个双介层洞的存在将违反设计规则，或该等相应两个双介层洞来自相同单介层洞；获得该互斥关系图之一最大独立集合(MIS)解，其中该MIS中之该顶点在每一对的该顶点之间不具有连接线；及用对应于该MIS中之该顶点的该双介层洞替代单介层洞；其中该互斥关系图之建构包含以下步骤：(a)建立一包含可行双介层洞之延伸边界框(DVE)的顶点比较集合(VCS)，其中该VCS起初为空集合；(b)藉由所有该单介层洞之x座标以非递减次序对所有单介层洞进行排序；(c)依序处理经排序之该单介层洞，若处理中之该单介层洞与该DVE之间的距离超过一临限值，则自该VCS删除该DVE；(d)识别每一单介层洞之可行双介层洞，且将对应于该可行双介层洞之顶点添加至该互斥关系图中；(e)在对应于一可行双介层洞之该顶点与对应于一与该可行双介层洞冲突的该VCS之元素的该顶点之间添加一连接线；(f)对于步骤(d)中所识别之每一可行双介层洞将DVE添加至该VCS中；及(g)在对应于步骤(d)中所识别之该可行双介层洞之每一对该顶点之间添加一连接线；其中，重复该等步骤(c)至(g)直至处理了所有该等单介层洞，若验证中之该单介层洞与一已验证之单介层洞座标相同，则跳过该步骤(c)。 |
