research-article

A polynomial time exact algorithm for self-aligned double patterning layout decomposition

Authors:

Martin D.F. WongAuthors Info & Claims

ISPD '12: Proceedings of the 2012 ACM international symposium on International Symposium on Physical Design

Pages 17 - 24

https://doi.org/10.1145/2160916.2160922

Published: 25 March 2012 Publication History

Abstract

Double patterning lithography (DPL) technologies have become a must for today's sub-32nm technology nodes. There are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among these two DPL technologies, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well-studied in the literature, only few attempts have been made to address the SADP layout decomposition problem. In this paper, we present the first polynomial time exact (optimal) algorithm to determine if a given layout has an overlay-free SADP decomposition. All previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.

References

[1]

Gurobi optimizer. http://www.gurobi.com.

[2]

Nangate open cell library. http://www.si2.org/openeda.si2.org/projects/nangatelib.

[3]

B. Aspvall. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inform. Process. Lett., 8:121--123, 1979.

[4]

Y. Ban, K. Lucas, and D. Z. Pan. Flexible 2d layout decomposition framework for spacer-type double patterning lithography. In Proc. DAC, pages 789--794, Jun 2011.

Digital Library

[5]

Y. Ban, A. Miloslavsky, K. Lucas, S. Choi, C.-H. Park, and D. Z. Pan. Layout decomposition of self-aligned double patterning for 2d random logic patterning. In Proc. SPIE, Jan 2011.

[6]

C. Bencher. Sadp: The best option. Nanochip Technology Journal, 5(2):1--6, Oct 2007.

[7]

Y.-S. Chang, J.-C. Lai, C.-C. Lin, J. Sweis, and J. Yu. Full-area pattern decomposition of self-aligned double patterning for 30nm node nand flash process. Proc. SPIE, Jan 2010.

[8]

C.-H. Hsu, Y.-W. Chang, and S. R. Nassif. Simultaneous layout migration and decomposition for double patterning technology. In Proceedings of the 2009 International Conference on Computer-Aided Design, ICCAD '09, pages 595--600, New York, NY, USA, 2009. ACM.

Digital Library

[9]

A. B. Kahng, C.-H. Park, X. Xu, and H. Yao. Layout decomposition for double patterning lithography. In Proc. ICCAD, ICCAD '08, pages 465--472, Piscataway, NJ, USA, 2008. IEEE Press.

Digital Library

[10]

Y. Ma, J. Sweis, C. Bencher, H. Dai, Y. Chen, J. P. Cain, Y. Deng, J. Kye, and H. J. Levinson. Decomposition strategies for self-aligned double patterning. In Proc. SPIE, volume 7641, 76410T, Jan 2010.

[11]

M. C. Smayling, C. Bencher, H. D. Chen, H. Dai, and M. P. Duane. Apf pitch-halving for 22nm logic cells using gridded design rules. Proc. SPIE, 6925(1):69251E--69251E-8, 2008.

[12]

S. Sun, C. Bencher, Y. Chen, H. Dai, M.-P. Cai, J. Jin, P. Blanco, L. Miao, P. Xu, X. Xu, J. Yu, R. Hung, S. Oemardani, O. Chan, C.-P. Chang, and C. Ngai. Demonstration of 32nm half-pitch electrical testable nand flash patterns using self-aligned double patterning. Proc. SPIE, 7274(1):72740D--72740D-7, 2009.

[13]

Y. Wei and R. L. Brainard. Advanced Processes for 193-nm Immersion Lithography, chapter 9, pages 215--225. SPIE Press Book, 2009.

[14]

Y. Xu and C. Chu. Grema: graph reduction based efficient mask assignment for double patterning technology. In Proceedings of the 2009 International Conference on Computer-Aided Design, ICCAD '09, pages 601--606, New York, NY, USA, 2009. ACM.

Digital Library

[15]

K. Yuan, J.-S. Yang, and D. Pan. Double patterning layout decomposition for simultaneous conflict and stitch minimization. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 29(2):185--196, feb. 2010.

Digital Library

[16]

H. Zhang, Y. Du, M. Wong, R. Topaloglu, and W. Conley. Effective decomposition algorithm for self-aligned double patterning lithography. In Proceedings of SPIE, volume 7973, page 79730J, 2011.

[17]

H. Zhang, Y. Du, M. D. F. Wong, and R. O. Topaloglu. Self-aligned double-patterning decomposition for overlay minimization and hot spot detection. In Proc. DAC, 2011.

Digital Library

Cited By

Ding YChu CMak W(2018)Self-Aligned Double Patterning-Aware Detailed Routing With Double Via Insertion and Via Manufacturability ConsiderationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.271266037:3(657-668)Online publication date: Mar-2018
https://doi.org/10.1109/TCAD.2017.2712660
Chen YWang SWang T(2017)On refining standard cell placement for self-aligned double patterningProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130729(1496-1501)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130729
Chen YWang SWang T(2017)On refining standard cell placement for self-aligned double patterningDesign, Automation & Test in Europe Conference & Exhibition (DATE), 201710.23919/DATE.2017.7927227(1492-1497)Online publication date: Mar-2017
https://doi.org/10.23919/DATE.2017.7927227
Show More Cited By

Index Terms

A polynomial time exact algorithm for self-aligned double patterning layout decomposition
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Partitioning and floorplanning

Recommendations

A Polynomial Time Exact Algorithm for Overlay-Resistant Self-Aligned Double Patterning (SADP) Layout Decomposition

Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has ...
A novel layout decomposition algorithm for triple patterning lithography
DAC '12: Proceedings of the 49th Annual Design Automation Conference

While double patterning lithography (DPL) has been widely recognized as one of the most promising solutions for the sub-22nm technology node to enhance pattern printability, triple patterning lithography (TPL) will be required for gate, contact, and ...
Fast and scalable parallel layout decomposition in double patterning lithography

For 32/22nm technology nodes and below, double patterning (DP) lithography has become the most promising interim solutions due to the delay in the deployment of next generation lithography (e.g., EUV). DP requires the partitioning of the layout patterns ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISPD '12: Proceedings of the 2012 ACM international symposium on International Symposium on Physical Design

March 2012

220 pages

ISBN:9781450311670

DOI:10.1145/2160916

General Chair:
Jiang Hu
Texas A&M University
,
Program Chair:
Cheng-Kok Koh
Purdue University

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 March 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISPD'12

Sponsor:

SIGDA

ISPD'12: International Symposium on Physical Design

March 25 - 28, 2012

California, Napa, USA

Acceptance Rates

Overall Acceptance Rate 62 of 172 submissions, 36%

Upcoming Conference

ISPD '25

Sponsor:
sigda

International Symposium on Physical Design

March 16 - 19, 2025

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
259
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ding YChu CMak W(2018)Self-Aligned Double Patterning-Aware Detailed Routing With Double Via Insertion and Via Manufacturability ConsiderationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.271266037:3(657-668)Online publication date: Mar-2018
https://doi.org/10.1109/TCAD.2017.2712660
Chen YWang SWang T(2017)On refining standard cell placement for self-aligned double patterningProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130729(1496-1501)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130729
Chen YWang SWang T(2017)On refining standard cell placement for self-aligned double patterningDesign, Automation & Test in Europe Conference & Exhibition (DATE), 201710.23919/DATE.2017.7927227(1492-1497)Online publication date: Mar-2017
https://doi.org/10.23919/DATE.2017.7927227
Ma YZeng XYu B(2017)Methodologies for layout decomposition and mask optimization: A systematic review2017 IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC)10.1109/VLSI-SoC.2017.8203477(1-6)Online publication date: Oct-2017
https://doi.org/10.1109/VLSI-SoC.2017.8203477
Ding YChu CMak W(2017)Self-Aligned Double Patterning Lithography Aware Detailed Routing With Color PreassignmentIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.262262536:8(1381-1394)Online publication date: Aug-2017
https://doi.org/10.1109/TCAD.2016.2622625
Huang CFang S(2016)Overlay-aware layout legalization for self-aligned double patterning lithography2016 International Symposium on VLSI Design, Automation and Test (VLSI-DAT)10.1109/VLSI-DAT.2016.7482574(1-4)Online publication date: Apr-2016
https://doi.org/10.1109/VLSI-DAT.2016.7482574
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
Xu XCline BYeric GYu BPan D(2015)Self-Aligned Double Patterning Aware Pin Access and Standard Cell Layout Co-OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.239943934:5(699-712)Online publication date: May-2015
https://doi.org/10.1109/TCAD.2015.2399439
Fang SYi-Shu Tai Yao-Wen Chang (2015)Layout decomposition for Spacer-is-Metal (SIM) self-aligned double patterningThe 20th Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2015.7059085(671-676)Online publication date: Jan-2015
https://doi.org/10.1109/ASPDAC.2015.7059085
Xu XCline BYeric GYu BPan DSze CDavoodi A(2014)Self-aligned double patterning aware pin access and standard cell layout co-optimizationProceedings of the 2014 on International symposium on physical design10.1145/2560519.2560530(101-108)Online publication date: 30-Mar-2014
https://dl.acm.org/doi/10.1145/2560519.2560530
Show More Cited By

View Options

Get Access

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