| 利用命题逻辑最大可满足性的冗余通孔最优插入方法 |
| |
| 引用本文： | 杨成,杨骏,张亚东.利用命题逻辑最大可满足性的冗余通孔最优插入方法[J].计算机辅助设计与图形学学报,2023(7):1132-1138. |
| |
| 作者姓名： | 杨成 杨骏 张亚东 |
| |
| 作者单位： | 1. 中国科学院微电子研究所汽车电子中心;2. 中国科学院大学 |
| |
| 摘 要： | 在纳米尺度的集成电路设计中,冗余通孔插入是减轻通孔失效造成良率降低问题的常用技术.文中将最优冗余通孔插入问题规约到命题逻辑最大逻辑可满足性(maximum satisfiability, Max SAT)问题,并利用完备求解器求取最优解.MaxSAT问题是一个NP困难问题,采用2种方法来降低求解难度;一是预选取方法,将提前确定的不与其他通孔产生冲突的冗余通孔作为部分解来降低问题的规模;二是分治法,根据连通分量将原问题划分成多个子问题分别求解,降低求解的复杂度.同时,从理论上证明这2种方法能够保证解的最优性.在2019年国际物理设计研讨会(ISPD)举办的详细布线比赛基准测试集上进行实验的结果表明,所提出的插入方法带来的时间开销不到详细布线时间的5%,算法的最优性保证了最大化解决插入冲突后的插入率,在所有可插入通孔中,冗余通孔的插入率为67%～87%.
|
| 关 键 词： | 冗余通孔插入 命题逻辑最大可满足性问题 版图后优化 可制造性设计 |
|
|
