Article

Free access

An optimum layer assignment for routing in ICs and PCBs.

Authors:

M. J. Ciesielski,

E. KinnenAuthors Info & Claims

DAC '81: Proceedings of the 18th Design Automation Conference

Pages 733 - 737

Published: 29 June 1981 Publication History

PDF eReader

Abstract

An optimum layer assignment of interconnections in IC and two-layer PCB is derived. The assignment is optimal in the sense that it is achieved through a global minimization of contacts or vias. The problem is formulated as a 0,1 integer program and solved using a branch and bound technique. There are no constraints on contact location or on the number of wires that can be connected at each contact. Applications of this procedure to VLSI circuits are discussed.

References

[1]

Hashimoto, A. and J. Stevens, Wire routing by optimizing channel assignment within large apertures, Proc. 8th Design Automation Workshop, 1971, pp. 155-169.

Digital Library

Google Scholar

[2]

Stevens, K.R., and W.M. van Cleemput, Global via elimination in a generalized routing environment, Proc. ISCAS, 1979, pp. 689-692.

Google Scholar

[3]

Kajitani, Y., On via hole minimization of routings on a 2-layer board, Proc. ICCC, 1980, pp. 295-298.

Google Scholar

[4]

Hu, T.C., Integer programming and network flows, Addison-Wesley Publishing Co., Reading, MA., 1970.

Google Scholar

[5]

Hachtel, G.D., On the sparse tableau approach to optimal layout, Proc. ICCC, 1980, pp. 1019-1022.

Google Scholar

[6]

Land, A.H., and S. Powell, Fortran codes for mathematical programming: linear, quadratic and discrete, J. Wiley and Sons, London, 1973.

Digital Library

Google Scholar

Cited By

View all

Cho MLu KYuan KPan D(2009)BoxRouter 2.0ACM Transactions on Design Automation of Electronic Systems10.1145/1497561.149757514:2(1-21)Online publication date: 7-Apr-2009
https://dl.acm.org/doi/10.1145/1497561.1497575
Chou YLin YYasuura H(1998)A graph-partitioning-based approach for multi-layer constrained via minimizationProceedings of the 1998 IEEE/ACM international conference on Computer-aided design10.1145/288548.289065(426-429)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1145/288548.289065
Shi CVannelli AVlach J(1997)Performance-Driven Layer Assignment by Integer Linear Programming and Path-Constrained Hypergraph PartitioningJournal of Heuristics10.1023/A:10096831100273:3(225-243)Online publication date: 1-Nov-1997
https://dl.acm.org/doi/10.1023/A%3A1009683110027
Show More Cited By

Index Terms

An optimum layer assignment for routing in ICs and PCBs.

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-...
Optimizing Pin Assignment and Escape Routing for Blind-via-Based PCBs
Pin assignment and escape routing are two closely related problems and it is desired to consider routability during pin assignment for package-board co-design. During pin assignment and escape routing, differential pairs and blind-via usage are two major ...
LAYER ASSIGNMENT FOR RUBBER BAND ROUTING

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '81: Proceedings of the 18th Design Automation Conference

June 1981

899 pages

Publisher

IEEE Press

Publication History

Published: 29 June 1981

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
185
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cho MLu KYuan KPan D(2009)BoxRouter 2.0ACM Transactions on Design Automation of Electronic Systems10.1145/1497561.149757514:2(1-21)Online publication date: 7-Apr-2009
https://dl.acm.org/doi/10.1145/1497561.1497575
Chou YLin YYasuura H(1998)A graph-partitioning-based approach for multi-layer constrained via minimizationProceedings of the 1998 IEEE/ACM international conference on Computer-aided design10.1145/288548.289065(426-429)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1145/288548.289065
Shi CVannelli AVlach J(1997)Performance-Driven Layer Assignment by Integer Linear Programming and Path-Constrained Hypergraph PartitioningJournal of Heuristics10.1023/A:10096831100273:3(225-243)Online publication date: 1-Nov-1997
https://dl.acm.org/doi/10.1023/A%3A1009683110027
Fang SChang KFeng WChen SNewton A(1991)Constrained via minimization with practical considerations for multi-layer VLSI/PCB routing problemsProceedings of the 28th ACM/IEEE Design Automation Conference10.1145/127601.127629(60-65)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/127601.127629
Naclerio NMasuda SNakajima K(1989)The Via Minimization Problem is NP-CompleteIEEE Transactions on Computers10.1109/12.4213538:11(1604-1608)Online publication date: 1-Nov-1989
https://dl.acm.org/doi/10.1109/12.42135
Xiong XKuh EShaklee DNewton A(1988)The constrained via minimization problem for PCB and VLSI designProceedings of the 25th ACM/IEEE Design Automation Conference10.5555/285730.285823(573-578)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.5555/285730.285823
Kuo YChern TShih WShaklee DNewton A(1988)Fast algorithm for optimal layer assignmentProceedings of the 25th ACM/IEEE Design Automation Conference10.5555/285730.285820(554-559)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.5555/285730.285820
Chang KDu H(1988)Layer Assignment Problem for Three-Layer RoutingIEEE Transactions on Computers10.1109/12.461637:5(625-632)Online publication date: 1-May-1988
https://dl.acm.org/doi/10.1109/12.4616
Chang KDu HThomas D(1986)A preprocessor for the via minimization problemProceedings of the 23rd ACM/IEEE Design Automation Conference10.5555/318013.318144(702-707)Online publication date: 2-Jul-1986
https://dl.acm.org/doi/10.5555/318013.318144
Ciesielski MKinnen ECrabbe JRadke COfek H(1982)An analytical method for compacting routing area in integrated circuitsProceedings of the 19th Design Automation Conference10.5555/800263.809182(30-37)Online publication date: 1-Jan-1982
https://dl.acm.org/doi/10.5555/800263.809182

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Congestion-Constrained Layer Assignment for Via Minimization in Global Routing

Optimizing Pin Assignment and Escape Routing for Blind-via-Based PCBs

LAYER ASSIGNMENT FOR RUBBER BAND ROUTING