Cited By
View all- Zhu WLin GAli M(2013)Max-k-Cut by the Discrete Dynamic Convexized MethodINFORMS Journal on Computing10.1287/ijoc.1110.049225:1(27-40)Online publication date: 1-Jan-2013
Conjugate conflict continuation graphs for multi-layer constrained via minimization
Authors: 
Rung-Bin Lin, Shu-Yu ChenAuthors Info & Claims
Pages 2436 - 2447
Abstract
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 a new graph model, called the conjugate conflict continuation graph, for multi-layer CVM with stacked vias. This graph model eases the handling of stacked via problems. An integer linear programming (ILP) formulation and a simulated annealing (SA) algorithm based on this graph model are developed to solve multi-layer CVM. The ILP model is too complicated to solve efficiently. The SA algorithm on average achieves 6.4% via reduction for layouts obtained using a commercial tool under a set of practical constraints in which the metal wires (including pins) used in cell layouts, power rails and rings, and clock routing are treated as obstacles or fixed-layer objects to a multi-layer CVM.
References
[1]
Barahona, F., On via minimization. IEEE Transactions on Circuits and Systems. v37 i4. 527-530.
[2]
Chang, C.C. and Cong, J., An efficient approach to multi-layer assignment with application to via minimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. v18 i5. 608-620.
[3]
Chang, K.C. and Du, H.C., Layer assignment problem for three-layer routing. IEEE Transactions on Computers. v37 i5. 625-632.
[4]
J.S. Cherng, S.J. Chen, C.-C. Tsai, J.M. Ho, An efficient approach for via minimization in multi-layer VLSI/PCB routing, in: Proc. IEEE Custom Integrated Circuit Conference, 1995, pp. 473-476.
[5]
Cho, J.D., Raje, S. and Sarrafzadeh, M., Fast approximation algorithms on maxcut k-coloring and k-color ordering for VLSI applications. IEEE Transactions on Computers. v47 i11. 1253-1266.
[6]
Y.C. Chou, Y.L. Lin, A graph-partitioning-based approach for multi-layer constrained via minimization, in: Proc. International Conference on Computer Aided Design, 1998, pp. 426-429.
[7]
S.C. Fang, K.E. Chang, W.S. Feng, S.J. Chen, Constrained via minimization with practical considerations for multi-layer VLSI/PCB routing problems, in: Proc. 28th ACM/IEEE Design Automation Conference, 1991, pp. 60-65.
[8]
Gan, J.R., Wang, X.G. and Lou, Z.H., A multi-layer channel routing algorithm based on via minimization. Chinese Journal of Computers. v25 i8. 830-836.
[9]
A. Hashimoto, J. Stevens, Wire routing by optimizing channel assignment with large apertures, in: Proc. 8th IEEE/ACM Design Automation Conference, 1971, pp. 155-169.
[10]
Hsu, C.P., Minimum-via topological routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. v2 i4. 235-246.
[11]
Joy, D.A. and Ciesielski, M.J., Layer assignment for printed circuit boards and integrated circuits. Proceedings of the IEEE. v80 i2. 311-331.
[12]
Y.S. Kuo, T.C. Chern, W.K. Shih, Fast algorithm for optimal layer assignment, in: Proc. 25th ACM/IEEE Design Automation Conference, 1988, pp. 554-559.
[13]
K.Y. Lee, T.C. Wang, Post-routing redundant via insertion for yield/reliability improvement, in: Proc. Asia and South Pacific Design Automation Conference, Yokohama, Japan, 2006, pp. 303-308.
[14]
F. Luo, Y. Jia, W. Dai, Yield-preferred via insertion based on novel geotopological technology, in: Proc. Asia and South Pacific Design Automation Conference, Yokohama, Japan, 2006, pp. 730-735.
[15]
Ma, Q. and Yan, X.L., Constrained via minimization with practical considerations for different-styled multi-layer routing. Acta Electronical Sinica. v29 i8. 1086-1089.
[16]
Molitor, P., A hierarchy preserving hierarchical bottom-up 2-layer wiring algorithm with respect to via minimization Integration. The VLSI Journal. v15 i1. 73-95.
[17]
Naclerio, N.J., Masuda, S. and Nakajima, K., The via minimization problem is NP-complete. IEEE Transactions on Computers. v38 i11. 1604-1608.
[18]
R. Noteboom, H.H. Ali, A new graph coloring algorithm for constrained via minimization, in: Proc. 37th Midwest Symposium on Circuits and Systems, vol. 1, 1994, pp. 363-366.
[19]
Pinter, R.Y., Optimal layer assignment for interconnect. Journal of VLSI and Computer Systems. v1 i2. 123-137.
[20]
S. Raghvendra, P. Hurat, DFM: Linking design and manufacturing, in: Proc. 18th International Conference on VLSI Design, Kolkata, India, 2005, pp. 705-708.
[21]
C.J. Shi, Solving constrained via minimization by compact linear programming, in: Proc. Asia and South Pacific Design Automation Conference, 1997, pp. 635-640.
[22]
C.J. Shi, A signed hypergraph model of constrained via minimization, in: Proc. 2nd Great Lakes Symposium on VLSI, 1992, pp. 159-166.
[23]
K.R. Stevens, W.M. Van Cleemput, Global via elimination in a generalized routing environment, in: Proc. IEEE International Symposium on Circuits and Systems, 1979, pp. 689-692.
[24]
K. Takahashi, T. Watanabe, A heuristic algorithm to solve constrained via minimization for three-layer routing problems, in: Proc. IEEE International Symposium on Circuits and Systems, vol. 6, 1998, pp. 254-257.
[25]
Tang, M., Chen, L. and Chua, H., A practical and efficient approach to the constrained via minimization problem. Computers and Electrical Engineering. v27. 201-216.
[26]
M. Tang, K. Eshraghian, H.N. Cheung, An efficient approach to constrained via minimization for two-layer VLSI routing, in: Proc. Asia and South Pacific Design Automation Conference, 1999, pp. 149-152.
[27]
M. Tang, An adaptive genetic algorithm for the minimal switching graph theorem, in: Proc. 5th European Conference on Evolutionary Computation in Combinatorial Optimization, Lausanne, Switzerland, 2005, pp. 224-233.
[28]
The, K.S., Wong, D.F. and Cong, J., A layout modification approach to via minimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. v10 i4. 536-541.
[29]
Tzeng, W.G. and King, G.H., Three-quarter approximation for the number of unused colors in graph coloring. Information Sciences. v114. 105-126.
[30]
D. Wu, J. Hu, R. Mahapatra, M. Zhao, Layer assignment for crosstalk risk minimization, in: Proc. Asia and South Pacific Design Automation Conference, Yokohama, Japan, 2004, pp. 159-162.
[31]
Wu, D., Hu, J., Mahapatra, R. and Rabi, N., Antenna avoidance in layer assignment. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. v25 i4. 734-738.
[32]
Xiong, X.M. and Kuh, E.S., A unified approach to the via minimization problem. IEEE Transactions on Circuits and Systems. v36 i2. 190-204.
Index Terms
- Conjugate conflict continuation graphs for multi-layer constrained via minimization
Recommendations
Congestion-Constrained Layer Assignment for Via Minimization in Global Routing
In this paper, we study the problem of layer assignment for via minimization, which arises during multilayer global routing. In addressing this problem, we take the total overflow and the maximum overflow as the congestion constraints from a given one-...
Delay-driven layer assignment in global routing under multi-tier interconnect structure
ISPD '13: Proceedings of the 2013 ACM International symposium on Physical DesignA multilayer routing system usually adopts multiple interconnect configuration with different wire sizes and thicknesses. Since thicker layers of metal lead to fatter wires with smaller resistance, the layer assignment of nets has a large impact on the ...
BoxRouter 2.0: A hybrid and robust global router with layer assignment for routability
In this article, we present BoxRouter 2.0, and discuss its architecture and implementation. As high-performance VLSI design becomes more interconnect-dominant, efficient congestion elimination in global routing is in greater demand. Hence, we propose a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier Inc. © 2007.
Publisher
Elsevier Science Inc.
United States
Publication History
Published: 20 June 2007
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Nov 2024
Other Metrics
Citations
Cited By
View all- Zhu WLin GAli M(2013)Max-k-Cut by the Discrete Dynamic Convexized MethodINFORMS Journal on Computing10.1287/ijoc.1110.049225:1(27-40)Online publication date: 1-Jan-2013
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in