Conjugate conflict continuation graphs for multi-layer constrained via minimization
作者： Rung-Bin Lin , Shu-Yu Chen
DOI: 10.1016/J.INS.2007.01.013
关键词: Strength of a graph 、 Moral graph 、 Algorithm 、 Mathematical optimization 、 Constrained optimization 、 Graph theory 、 Simulated annealing 、 Integer programming 、 Graph bandwidth 、 Graph coloring 、 Mathematics
摘要: A graph model for describing the relationships among wire segments is crucial to constrained via minimization (CVM) in a VLSI design. In this paper we present new model, called conjugate conflict continuation graph, multi-layer CVM with stacked vias. This eases handling of problems. An integer linear programming (ILP) formulation and simulated annealing (SA) algorithm based on are developed solve CVM. The ILP too complicated efficiently. SA average achieves 6.4% reduction layouts obtained using commercial tool under set practical constraints which metal wires (including pins) used cell layouts, power rails rings, clock routing treated as obstacles or fixed-layer objects
yzu.edu.tw
elsevier.com参考文章(32)
Maolin Tang, An Adaptive Genetic Algorithm for the Minimal Switching Graph Problem Evolutionary Computation in Combinatorial Optimization. pp. 224- 233 ,(2005) , 10.1007/978-3-540-31996-2_21
Ron Y. Pinter, Optimal layer assignment for interconnect Advances in VLSI and Computer Systems archive. ,vol. 1, pp. 123- 137 ,(1984) , 10.5555/2334.2335
C.J.-R. Shi, A signed hypergraph model of constrained via minimization great lakes symposium on vlsi. pp. 159- 166 ,(1992) , 10.1109/GLSV.1992.218350
Chi-Ping Hsu, Minimum-Via Topological Routing IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 2, pp. 235- 246 ,(1983) , 10.1109/TCAD.1983.1270041
Yih-Chih Chou, Youn-Long Lin, A graph-partitioning-based approach for multi-layer constrained via minimization international conference on computer aided design. pp. 426- 429 ,(1998) , 10.1145/288548.289065
Jiang Hu, Di Wu, Min Zhao, Rabi Mahapatra, Layer assignment for crosstalk risk minimization asia and south pacific design automation conference. pp. 159- 162 ,(2004) , 10.5555/1015090.1015128
F. Barahona, On via minimization IEEE Transactions on Circuits and Systems. ,vol. 37, pp. 527- 530 ,(1990) , 10.1109/31.52754
Wen-Guey Tzeng, Gow-Hsing King, Three-quarter approximation for the number of unused colors in graph coloring Information Sciences. ,vol. 114, pp. 105- 126 ,(1999) , 10.1016/S0020-0255(98)10058-0
Mao-Lin Tang, Li-Hui Chen, Hock-Chuan Chua, A practical and efficient approach to the constrained via minimization problem Computers & Electrical Engineering. ,vol. 27, pp. 201- 216 ,(2001) , 10.1016/S0045-7906(00)00015-X
Kuang-Yao Lee, Ting-Chi Wang, Post-routing redundant via insertion for yield/reliability improvement Proceedings of the 2006 conference on Asia South Pacific design automation - ASP-DAC '06. pp. 303- 308 ,(2006) , 10.1145/1118299.1118376