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

research-article

A new graph-theoretic, multi-objective layout decomposition framework for double patterning lithography

Authors:

David Z. PanAuthors Info & Claims

ASPDAC '10: Proceedings of the 2010 Asia and South Pacific Design Automation Conference

Pages 637 - 644

Published: 18 January 2010 Publication History

Abstract

As Double Patterning Lithography(DPL) becomes the leading candidate for sub-30nm lithography process, we need a fast and lithography friendly decomposition framework. In this paper, we propose a multi-objective min-cut based decomposition framework for stitch minimization, balanced density, and overlay compensation, simultaneously. The key challenge of DPL is to accomplish high quality decomposition for large-scale layouts under reasonable runtime with the following objectives: a) the number of stitches is minimized, b) the balance between two decomposed layers is maximized for further enhanced patterning, c) the impact of overlay on coupling capacitance is reduced for less timing variation. We use a graph theoretic algorithm for minimum stitch insertion and balanced density. An additional decomposition constraints for self-overlay compensation are obtained by integer linear programming(ILP). With the constraints, global decomposition is executed by our modified FM graph partitioning algorithm. Experimental results show that the proposed framework is highly scalable and fast: we can decompose all 15 benchmark circuits in five minutes in a density balanced fashion, while an ILP-based approach can finish only the smallest five circuits. In addition, we can remove more than 95% of the timing variation induced by overlay for tested structures.

References

[1]

D. Laidler, P. Leray, K. D'have, and S. Cheng. Sources of Overlay Error in Double Patterning Integration Schemes. In Proc. SPIE 6922, 2008.

[2]

G. Bailey, A. Tritchkov, J.-W. Park, L. Hong, V. Wiaux, E. Hendrickx, S. Verhaegen, P. Xie, and J. Versluijs. Double pattern EDA solutions for 32nm HP and beyond. In Proc. SPIE 6521, 2007.

[3]

David Z. Pan, Jae-Seok Yang, Kun Yuan, Minsik Cho, and Yongchan Ban. Layout Optimizations for Double Patterning Lithography. In IEEE 8th International Conference on ASIC (ASICON), Oct 2009.

[4]

T.-B. Chiou, R. Socha, H. Chen, L. Chen, S. Hsu, P. Nikolsky, A. van Oosten, and A. C. Chen. Development of layout split algorithms and printability evaluation for double patterning technology. In Proc. SPIE 6924, 2008.

[5]

M. Cho, Y. Ban, and D. Z. Pan. Double Patterning Technology Friendly Detailed Routing. In Proc. Int. Conf. on Computer Aided Design, Nov 2008.

Digital Library

[6]

A. B. Kahng, C.-H. Park, and H. Yao. Layout Decomposition for Double Patterning Lithography. In Proc. Int. Conf. on Computer Aided Design, Nov 2008.

Digital Library

[7]

K. Yuan, J.-S. Yang, and D. Z. Pan. Double Patterning Layout Decomposition for Simultaneous Conflict and Stitch Minimization. In Proc. Int. Symp. on Physical Design, March 2009.

Digital Library

[8]

C. M. Fiduccia and R. M. Mattheyses. A Linear-Time Heuristic for Improving Network Partitions. In Proc. Design Automation Conf., June 1982.

Digital Library

[9]

Alfred K. Wong. Resolution Enhancement Techniques in Optical Lithography. SPIE Publications, 2001.

[10]

J.-S. Yang and D. Z. Pan. Overlay Aware Interconnect and Timing Variation Modeling for Double Patterning Technology. In Proc. Int. Conf. on Computer Aided Design, Nov 2008.

Digital Library

[11]

R. S. Ghaida and P. Gupta. Design-Overlay Interactions in Metal Double Patterning. In Proc. SPIE 7275, 2009.

[12]

E. Y. Chin and A. R. Neureuther. Variability aware interconnect timing models for double patterning. In Proc. SPIE 7275, 2009.

[13]

J. Rubinstein and A. Neureuther. Post-decomposition assessment of double patterning layout. In Proc. SPIE 6924, 2008.

[14]

P. Chen, D. A. Kirkpatrick, and K. Keutzer. Miller Factor for Gate-Level Coupling Delay Calculation. In Proc. Int. Conf. on Computer Aided Design, Nov 2000.

Digital Library

[15]

A. B. Kahng, S. Muddu, and E. Sarto. On Switch Factor Based Analysis of Coupled RC Interconnects. In Proc. Design Automation Conf., June 2000.

Digital Library

Cited By

Lu YChang YChang Y(2018)WB-treesProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196137(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196137
Kuang JYoung E(2017)Fixed-Parameter Tractable Algorithms for Optimal Layout Decomposition and BeyondProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062250(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062250
Zhang YLuk WYang YZhou HYan CPan DZeng X(2015)Layout Decomposition with Pairwise Coloring and Adaptive Multi-Start for Triple Patterning LithographyACM Transactions on Design Automation of Electronic Systems10.1145/276490421:1(1-25)Online publication date: 2-Dec-2015
https://dl.acm.org/doi/10.1145/2764904
Show More Cited By

Recommendations

Layout decomposition for triple patterning lithography
ICCAD '11: Proceedings of the International Conference on Computer-Aided Design

As minimum feature size and pitch spacing further decrease, triple patterning lithography (TPL) is a possible 193nm extension along the paradigm of double patterning lithography (DPL). However, there is very little study on TPL layout decomposition. In ...
Optical lithography extension with double patterning
ISPD '13: Proceedings of the 2013 ACM International symposium on Physical Design

Design shrinking beyond the resolution limits of 193 nm optical lithography requires the introduction of double patterning technology (DPT) for the semiconductor industry. Two consecutive lithography and etching process (LELE; Litho-Etch-Litho-Etch) and ...
Layout decomposition approaches for double patterning lithography
Special issue on the 2009 ACM/IEEE international symposium on networks-on-chip

In double patterning lithography (DPL) layout decomposition for 45 nm and below process nodes, two features must be assigned opposite colors (corresponding to different exposures) if their spacing is less than the minimum coloring spacing. However, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPDAC '10: Proceedings of the 2010 Asia and South Pacific Design Automation Conference

January 2010

920 pages

ISBN:9781605588377

General Chair:
Youn-Long Lin
National Tsing Hua University

Sponsors

TICD: TICD
SIGDA: ACM Special Interest Group on Design Automation
IEEE CAS

Publisher

IEEE Press

Publication History

Published: 18 January 2010

Check for updates

Qualifiers

Research-article

Conference

ASPDAC '10

Sponsor:

TICD
SIGDA

ASPDAC '10: Asia and South Pacific Design Automation Conference

January 18 - 21, 2010

Taipei, Taiwan

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
116
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lu YChang YChang Y(2018)WB-treesProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196137(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196137
Kuang JYoung E(2017)Fixed-Parameter Tractable Algorithms for Optimal Layout Decomposition and BeyondProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062250(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062250
Zhang YLuk WYang YZhou HYan CPan DZeng X(2015)Layout Decomposition with Pairwise Coloring and Adaptive Multi-Start for Triple Patterning LithographyACM Transactions on Design Automation of Electronic Systems10.1145/276490421:1(1-25)Online publication date: 2-Dec-2015
https://dl.acm.org/doi/10.1145/2764904
Pan DLiebmann LYu BXu XLin Y(2015)Pushing multiple patterning in sub-10nmProceedings of the 52nd Annual Design Automation Conference10.1145/2744769.2747940(1-6)Online publication date: 7-Jun-2015
https://dl.acm.org/doi/10.1145/2744769.2747940
Zhang YLuk WZhou HYan CZeng XHenkel J(2013)Layout decomposition with pairwise coloring for multiple patterning lithographyProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561864(170-177)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561864
Yu BLin YLuk-Pat GDing DLucas KPan DHenkel J(2013)A high-performance triple patterning layout decomposer with balanced densityProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561863(163-169)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561863
Ghaida RGupta PMacii E(2013)Role of design in multiple patterningProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485366(314-319)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.5555/2485288.2485366
Kuang JYoung E(2013)An efficient layout decomposition approach for triple patterning lithographyProceedings of the 50th Annual Design Automation Conference10.1145/2463209.2488818(1-6)Online publication date: 29-May-2013
https://dl.acm.org/doi/10.1145/2463209.2488818
Abed IWassal ARosenstiel WMacii E(2012)Double-patterning friendly grid-based detailed routing with online conflict resolutionProceedings of the Conference on Design, Automation and Test in Europe10.5555/2492708.2493069(1475-1478)Online publication date: 12-Mar-2012
https://dl.acm.org/doi/10.5555/2492708.2493069
Yu BGao JDing DBan YYang JYuan KCho MPan DHu A(2012)Dealing with IC manufacturability in extreme scalingProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429430(240-242)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429430
Show More Cited By

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