More Web Proxy on the site http://driver.im/

research-article

Simultaneous antenna avoidance and via optimization in layer assignment of multi-layer global routing

Authors:

Tsung-Hsien Lee,

Ting-Chi WangAuthors Info & Claims

ICCAD '10: Proceedings of the International Conference on Computer-Aided Design

Pages 312 - 318

Published: 07 November 2010 Publication History

Abstract

Antenna effect is an important issue that needs to be considered in the routing stage for modern design. In this paper, we study a layer assignment problem that arises during multi-layer global routing and takes antenna avoidance into account. The problem asks to transform a given 2-dimensional global routing result into a 3-dimensional one (i.e., a multi-layer one) and to minimize the amount of antenna violations and the via count subject to given wire congestion constraints. We present an algorithm that tackles the addressed layer assignment problem in a net-by-net manner. An existing dynamic-programming-based single-net layer assignment method that can only consider the via count is judiciously modified and adopted by our algorithm to handle both antenna avoidance and via count minimization for each net. To further reduce the via count but without increasing the amount of antenna violations, a refinement procedure based on min-cost max-flow is developed and added to our algorithm. The experiment results show that when compared with the layer assignment approach adopted by a state-of-the-art academic global router, our algorithm not only can improve the via count slightly but also can significantly reduce the amount of antenna violations.

References

[1]

T.-H. Lee and T.-C. Wang, "Congestion-constrained Layer Assignment for Via Minimization in Global Routing," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, No. 9, pp. 1643--1656, 2008.

Digital Library

[2]

ISPD 2007 Global Routing Contest. {Online}. Available: http://www.sigda.org/ispd2007/contest.html

[3]

ISPD 2008 Global Routing Contest. {Online}. Available: http://www.ispd.cc/contests/ispd08rc.html

[4]

M. M. Ozdal and M. D. F. Wong, "Archer: A History-based Global Routing Algorithm," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 28, No. 4, pp. 528--540, 2009.

Digital Library

[5]

J. A. Roy and I. L. Markov, "High-Performance Routing at the Nanometer Scale," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, No. 6, pp. 1066--1077, 2008.

Digital Library

[6]

M. Cho, K. Lu, K. Yuan, and D. Z. Pan, "BoxRouter 2.0: A Hybrid and Robust Global Router with Layer Assignment for Routability," ACM Transactions on Design Automation of Electronic Systems, Vol. 14, No. 2, pp. 1--21, 2009.

Digital Library

[7]

M. D. Moffitt, "MaizeRouter: Engineering an Effective Global Router," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, No. 11, pp. 2017--2026, 2008.

Digital Library

[8]

Y.-J. Chang, Y.-T. Lee, and T.-C. Wang, "NTHU-Route 2.0: A Fast and Stable Global Router," Proceedings of International Conference on Computer-Aided Design, pp. 338--343, 2008.

Digital Library

[9]

Y. Xu, Y. Zhang, and C. Chu, "FastRoute 4.0: Global Router with Efficient Via Minimization," Proceedings of Asia and South Pacific Design Automation Conference, pp. 576--581, 2009.

Digital Library

[10]

H.-Y. Chen, C.-H. Hsu, and Y.-W. Chang, "High-Performance Global Routing with Fast Overflow Reduction," Proceedings of Asia and South Pacific Design Automation Conference, pp. 582--587, 2009.

Digital Library

[11]

K.-R. Dai, W.-H. Liu, and Y.-L. Li, "Efficient Simulated Evolution based Rerouting and Congestion-relaxed Layer Assignment on 3D Global Routing," Proceedings of Asia and South Pacific Design Automation Conference, pp. 570--575, 2009.

Digital Library

[12]

H. Shin, C.-C. King, and C. Hu, "Thin Oxide Damage by Plasma Etching and Ashing Process," Proceedsings of International Reliability Physics Symposium, pp. 37--41, 1992.

[13]

H. Watanabe, J. Komori, K. Higashitani, M. Sekine, and H. Koyama, "A Wafer Level Monitoring Method for Plasma-charging Damage Using Antenna PMOSFET Test Structure," IEEE Transactions on Semiconductor Manufacturing, Vol. 10, No. 2, pp. 228--232, 1997.

[14]

D. Wu, J. Hu, and R. Mahapatra, "Antenna Avoidance in Layer Assignment," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 25, No. 4, pp. 1643--1656, 2006.

Digital Library

[15]

C. J. Alpert, "The ISPD98 Circuit Benchmark Suite," Proceedings of International Symposium on Physical Design, pp. 80--85, 1998.

Digital Library

[16]

T.-Y. Ho, Y.-W. Chang, and S.-J. Chen, "Multilevel routing with antenna avoidance," Proceedings of International Symposium on Physical Design, pp. 34--40, 2004.

Digital Library

[17]

C.-H. Hsu, H.-Y. Chen, and Y.-W. Chang, "Multi-layer Global Routing Considering Via and Wire Capacities," Proceedings of International Conference on Computer-Aided Design, pp. 350--355, 2008.

Digital Library

[18]

T.-H. Lee and T.-C. Wang, "Robust Layer Assignment for Via Optimization in Multi-layer Global Routing," Proceedings of International Symposium on Physical Design, pp. 159--166, 2009.

Digital Library

Cited By

Liu DYu BChowdhury SPan D(2016)Incremental layer assignment for critical path timingProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2898033(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2898033
Yu BLiu DChowdhury SPan DMarculescu DLiu F(2015)TILAProceedings of the IEEE/ACM International Conference on Computer-Aided Design10.5555/2840819.2840835(110-117)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.5555/2840819.2840835
Fang SLiu IChang Y(2013)Stitch-aware routing for multiple e-beam lithographyProceedings of the 50th Annual Design Automation Conference10.1145/2463209.2488765(1-6)Online publication date: 29-May-2013
https://dl.acm.org/doi/10.1145/2463209.2488765
Show More Cited By

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 the antenna area and separators in layer assignment of multi-layer global routing
ISPD '12: Proceedings of the 2012 ACM international symposium on International Symposium on Physical Design

Traditional solutions to antenna effect, such as jumper insertion and diode insertion peformed at post-route stage may produce extra vias and degrade circuit performance. The work in [1] suggests combining layer assignment, jumper insertion and diode ...
Coupling aware timing optimization and antenna avoidance in layer assignment
ISPD '05: Proceedings of the 2005 international symposium on Physical design

The sustained progress of VLSI technology has altered the landscape of routing which is a major physical design stage. For timing driven routings, traditional approaches which consider only wire self capacitance become inadequate since the wire delay is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '10: Proceedings of the International Conference on Computer-Aided Design

November 2010

863 pages

ISBN:9781424481927

General Chair:
Louis Scheffer
Howard Hughes Medical Institute, Ashburn, VA
,
Program Chairs:
Joel Phillips
Cadence Research Labs, Berkeley, CA
,
Alan J. Hu
Univ. of British Columbia, Vancouver, BC V6T 1Z4 Canada

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE CEDA

Publisher

IEEE Press

Publication History

Published: 07 November 2010

Check for updates

Qualifiers

Research-article

Conference

ICCAD '10

Sponsor:

SIGDA

ICCAD '10: The International Conference on Computer-Aided Design

November 7 - 11, 2010

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
55
Total Downloads

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

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu DYu BChowdhury SPan D(2016)Incremental layer assignment for critical path timingProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2898033(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2898033
Yu BLiu DChowdhury SPan DMarculescu DLiu F(2015)TILAProceedings of the IEEE/ACM International Conference on Computer-Aided Design10.5555/2840819.2840835(110-117)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.5555/2840819.2840835
Fang SLiu IChang Y(2013)Stitch-aware routing for multiple e-beam lithographyProceedings of the 50th Annual Design Automation Conference10.1145/2463209.2488765(1-6)Online publication date: 29-May-2013
https://dl.acm.org/doi/10.1145/2463209.2488765
Ao JDong SChen SGoto SKoh CSze C(2013)Delay-driven layer assignment in global routing under multi-tier interconnect structureProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451942(101-107)Online publication date: 24-Mar-2013
https://dl.acm.org/doi/10.1145/2451916.2451942
Liu WLi YHu JKoh C(2012)Optimizing the antenna area and separators in layer assignment of multi-layer global routingProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160946(137-144)Online publication date: 25-Mar-2012
https://dl.acm.org/doi/10.1145/2160916.2160946
Gao XMacchiarulo LPhillips JHu AGraeb H(2011)A jumper insertion algorithm under antenna ratio and timing constraintsProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132399(290-297)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132399

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents