Fast and Optimal Redundant Via Insertion
Fast and Optimal Redundant Via Insertion
复制标题
DOI：
10.1109/tcad.2008.2006151
复制
发表时间：
2008-12
影响因子：
2.9
通讯作者：
Kuang‐Yao Lee;Cheng-Kok Koh;Ting-Chi Wang;Kai-Yuan Chao
中科院分区：
文献类型：
--
作者：
Kuang‐Yao Lee;Cheng-Kok Koh;Ting-Chi Wang;Kai-Yuan Chao
冗余通孔插入在提高芯片成品率和可靠性方面非常有效。本文研究了布线后阶段的双割通孔插入问题，其中单个通孔最多只能插入一个冗余通孔，目标是插入尽可能多的冗余通孔。DVI问题可以自然地表示为0-1整数线性规划(0-1ILP)。我们的主要贡献是减少问题大小和约束数量的加速方法。此外，我们扩展了0-1 ILP公式以处理通过密度约束。实验结果表明，我们的0-1 ILP算法在计算最优DVI解方面非常有效，与现有的启发式算法相比，加速比高达73.98倍。
Redundant via insertion is highly effective in improving chip yield and reliability. In this paper, we study the problem of double-cut via insertion (DVI) in a post-routing stage, where a single via can have, at most, one redundant via inserted next to it and the goal is to insert as many redundant vias as possible. The DVI problem can be naturally formulated as a zero-one integer linear program (0-1 ILP). Our main contributions are acceleration methods for reducing the problem size and the number of constraints. Moreover, we extend the 0-1 ILP formulation to handle via density constraints. Experimental results show that our 0-1 ILP is very efficient in computing an optimal DVI solution, with up to 73.98 times speedup over existing heuristic algorithms.