利用命题逻辑最大可满足性的冗余通孔最优插入方法

Method for Optimal Redundant via Insertion with Maximum Satisfiability

在纳米尺度的集成电路设计中,冗余通孔插入是减轻通孔失效造成良率降低问题的常用技术.文中将最优冗余通孔插入问题规约到命题逻辑最大逻辑可满足性(maximum satisfiability,Max SAT)问题,并利用完备求解器求取最优解.Max SAT问题是一个NP困难问题,采用2种方法来降低求解难度;一是预选取方法,将提前确定的不与其他通孔产生冲突的冗余通孔作为部分解来降低问题的规模;二是分治法,根据连通分量将原问题划分成多个子问题分别求解,降低求解的复杂度.同时,从理论上证明这2种方法能够保证解的最优性.在2019年国际物理设计研讨会(ISPD)举办的详细布线比赛基准测试集上进行实验的结果表明,所提出的插入方法带来的时间开销不到详细布线时间的5%,算法的最优性保证了最大化解决插入冲突后的插入率,在所有可插入通孔中,冗余通孔的插入率为67%~87%.

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 re-dundant 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.