利用命题逻辑最大可满足性的冗余通孔最优插入方法
Method for Optimal Redundant Via Insertion withMaximum Satisfiability
-
摘要: 在纳米尺度的集成电路设计中, 冗余通孔插入是减轻通孔失效造成良率降低问题的常用技术. 文章通过将最优冗余通孔插入问题规约到命题逻辑最大逻辑可满足性(maximum satisfiability, Max SAT)问题, 并利用完备求解器求取最优解. 由于Max SAT问题是NP困难的, 文章中使用两种方法来降低求解难度, 一是预选择方法, 通过提前确定不与其它通孔产生冲突的冗余通孔作为部分解来降低问题的规模, 二是分治法, 根据连通分量将原问题划分成多个子问题分别求解, 降低求解的复杂度, 同时, 文章也从理论上证明了这两种方法能够保证解的最优性. 最后, 算法在2019年国际物理设计研讨会(International Symposium on Physical Design, ISPD)举办的详细布线比赛的基准测试集上进行实验, 实验结果显示算法带来的时间开销不到详细布线时间的5%, 算法的最优性保证了最大化解决插入冲突后的插入率, 在所有可插入通孔中, 冗余通孔的插入率为67%-87%.Abstract: In nanoscale integrated circuit design, redundant via insertion is a common technique to alleviate the yield loss caused by via failure. In this paper, the optimal redundant via insertion problem is converted to a maximum satisfiability (Max SAT) problem, and the optimal solution is obtained by using a complete solver. Since the Max SAT problem is NP-hard, two techniques are used in this paper to reduce the difficulty of finding solutions. One is the pre-selection, which reduces the size of the problem by identifying the redundant vias that do not conflict with other vias as partial solutions. The other is problem partitioning, which divides the original problem into several sub-problems with respect to the connected components to reduce the solution complexity. The paper also proves that these two methods can guarantee the optimality of the solution. Finally, the algorithm experiments on the benchmarks of the detailed routing competition of the International Symposium on Physical Design (ISPD) 2019. The optimality of the algorithm ensures that the insertion rate is maximized while resolving insertion conflicts, and the insertion rate of redundant vias is 67%-87% of all insertable vias.