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

research-article

Layout Decomposition for Quadruple Patterning Lithography and Beyond

Authors:

David Z. PanAuthors Info & Claims

DAC '14: Proceedings of the 51st Annual Design Automation Conference

Pages 1 - 6

https://doi.org/10.1145/2593069.2593152

Published: 01 June 2014 Publication History

Abstract

For next-generation technology nodes, multiple patterning lithography (MPL) has emerged as a key solution, e.g., triple patterning lithography (TPL) for 14/11nm, and quadruple patterning lithography (QPL) for sub-10nm. In this paper, we propose a generic and robust layout decomposition framework for QPL, which can be further extended to handle any general K-patterning lithography (K>4). Our framework is based on the semidefinite programming (SDP) formulation with novel coloring encoding. Meanwhile, we propose fast yet effective coloring assignment and achieve significant speedup. To our best knowledge, this is the first work on the general multiple patterning lithography layout decomposition.

References

[1]

D. Z. Pan, B. Yu, and J.-R. Gao, "Design for manufacturing with emerging nanolithography," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 32, no. 10, pp. 1453--1472, 2013.

Digital Library

[2]

B. Yu, J.-R. Gao, D. Ding, Y. Ban, J.-S. Yang, K. Yuan, M. Cho, and D. Z. Pan, "Dealing with IC manufacturability in extreme scaling," in Proc. ICCAD, 2012, pp. 240--242.

Digital Library

[3]

A. B. Kahng, C.-H. Park, X. Xu, and H. Yao, "Layout decomposition for double patterning lithography," in Proc. ICCAD, 2008, pp. 465--472.

Digital Library

[4]

B. Yu, K. Yuan, B. Zhang, D. Ding, and D. Z. Pan, "Layout decomposition for triple patterning lithography," in Proc. ICCAD, 2011, pp. 1--8.

Digital Library

[5]

K. Yuan, J.-S. Yang, and D. Z. Pan, "Double patterning layout decomposition for simultaneous conflict and stitch minimization," in Proc. ISPD, 2009, pp. 107--114.

Digital Library

[6]

Y. Xu and C. Chu, "A matching based decomposer for double patterning lithography," in Proc. ISPD, 2010, pp. 121--126.

Digital Library

[7]

X. Tang and M. Cho, "Optimal layout decomposition for double patterning technology," in Proc. ICCAD, 2011, pp. 9--13.

Digital Library

[8]

S.-Y. Fang, W.-Y. Chen, and Y.-W. Chang, "A novel layout decomposition algorithm for triple patterning lithography," in Proc. DAC, 2012, pp. 1185--1190.

Digital Library

[9]

J. Kuang and E. F. Young, "An efficient layout decomposition approach for triple patterning lithography," in Proc. DAC, 2013, pp. 69:1--69:6.

Digital Library

[10]

B. Yu, Y.-H. Lin, G. Luk-Pat, D. Ding, K. Lucas, and D. Z. Pan, "A high-performance triple patterning layout decomposer with balanced density," in Proc. ICCAD, 2013, pp. 163--169.

Digital Library

[11]

Y. Zhang, W.-S. Luk, H. Zhou, C. Yan, and X. Zeng, "Layout decomposition with pairwise coloring for multiple patterning lithography," in Proc. ICCAD, 2013, pp. 170--177.

Digital Library

[12]

B. Yu, J.-R. Gao, and D. Z. Pan, "Triple patterning lithography (TPL) layout decomposition using end-cutting," in Proc. of SPIE, vol. 8684, 2013.

[13]

H. Tian, H. Zhang, Q. Ma, Z. Xiao, and M. Wong, "A polynomial time triple patterning algorithm for cell based row-structure layout," in Proc. ICCAD, 2012, pp. 57--64.

Digital Library

[14]

B. Yu, X. Xu, J.-R. Gao, and D. Z. Pan, "Methodology for standard cell compliance and detailed placement for triple patterning lithography," in Proc. ICCAD, 2013, pp. 349--356.

Digital Library

[15]

H. Tian, Y. Du, H. Zhang, Z. Xiao, and M. Wong, "Constrained pattern assignment for standard cell based triple patterning lithography," in Proc. ICCAD, 2013, pp. 57--64.

Digital Library

[16]

D. Karger, R. Motwani, and M. Sudan, "Approximate graph coloring by semidefinite programming," J. ACM, vol. 45, pp. 246--265, March 1998.

Digital Library

[17]

K. Appel and W. Haken, "Every planar map is four colorable. part i: Discharging," Illinois Journal of Mathematics, vol. 21, no. 3, pp. 429--490, 1977.

[18]

C. Kuratowski, "Sur le probleme des courbes gauches en topologie," Fundamenta mathematicae, vol. 15, no. 1, pp. 271--283, 1930.

[19]

N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas, "Efficiently four-coloring planar graphs," in ACM Symposium on Theory of computing, 1996, pp. 571--575.

Digital Library

[20]

R. E. Gomory and T. C. Hu, "Multi-terminal network flows," Journal of the Society for Industrial & Applied Mathematics, vol. 9, no. 4, pp. 551--570, 1961.

[21]

D. Gusfield, "Very simple methods for all pairs network flow analysis," SIAM Journal on Computing, vol. 19, no. 1, pp. 143--155, 1990.

Digital Library

[22]

E. A. Dinic, "Algorithm for solution of a problem of maximum flow in networks with power estimation," in Soviet Math. Dokl, vol. 11, no. 5, 1970, pp. 1277--1280.

[23]

"GUROBI," http://www.gurobi.com/html/academic.html.

[24]

B. Borchers, "CSDP, a C library for semidefinite programming," Optimization Methods and Software, vol. 11, pp. 613--623, 1999.

Cited By

Zhong WHu SMa YYang HMa XYu B(2022)Deep Learning-Driven Simultaneous Layout Decomposition and Mask OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.306149441:3(709-722)Online publication date: Mar-2022
https://doi.org/10.1109/TCAD.2021.3061494
Zhong WHu SMa YYang HMa XYu B(2020)Deep Learning-Driven Simultaneous Layout Decomposition and Mask Optimization2020 57th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18072.2020.9218530(1-6)Online publication date: Jul-2020
https://doi.org/10.1109/DAC18072.2020.9218530
Chang HJiang IBustany ISwartz W(2019)Multiple Patterning Layout Compliance with Minimizing Topology Disturbance and Polygon DisplacementProceedings of the 2019 International Symposium on Physical Design10.1145/3299902.3309755(93-100)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3299902.3309755
Show More Cited By

Index Terms

Layout Decomposition for Quadruple Patterning Lithography and Beyond
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Multiple patterning layout decomposition considering complex coloring rules
DAC '16: Proceedings of the 53rd Annual Design Automation Conference

Multiple patterning lithography has been recognized as one of the most promising solutions, in addition to extreme ultraviolet lithography, directed self-assembly, nanoimprint lithography, and electron beam lithography, for advancing the resolution ...
Pushing multiple patterning in sub-10nm: are we ready?
DAC '15: Proceedings of the 52nd Annual Design Automation Conference

Due to elongated delay of extreme ultraviolet lithography (EUVL), the semiconductor industry has been pushing the 193nm immersion lithopgrahy using multiple patterning to print critical features in 22nm/14nm technology nodes and beyond. Multiple ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

DAC '14: Proceedings of the 51st Annual Design Automation Conference

June 2014

1249 pages

ISBN:9781450327305

DOI:10.1145/2593069

Copyright © 2014 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 the author(s) 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].

In-Cooperation

EDAC: Electronic Design Automation Consortium
SIGBED: ACM Special Interest Group on Embedded Systems
SIGDA: ACM Special Interest Group on Design Automation
IEEE-CEDA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

DAC '14

DAC '14: The 51st Annual Design Automation Conference 2014

June 1 - 5, 2014

CA, San Francisco, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
200
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)2

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhong WHu SMa YYang HMa XYu B(2022)Deep Learning-Driven Simultaneous Layout Decomposition and Mask OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.306149441:3(709-722)Online publication date: Mar-2022
https://doi.org/10.1109/TCAD.2021.3061494
Zhong WHu SMa YYang HMa XYu B(2020)Deep Learning-Driven Simultaneous Layout Decomposition and Mask Optimization2020 57th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18072.2020.9218530(1-6)Online publication date: Jul-2020
https://doi.org/10.1109/DAC18072.2020.9218530
Chang HJiang IBustany ISwartz W(2019)Multiple Patterning Layout Compliance with Minimizing Topology Disturbance and Polygon DisplacementProceedings of the 2019 International Symposium on Physical Design10.1145/3299902.3309755(93-100)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3299902.3309755
Lvov ATellez GNam GChu CBustany I(2018)On Coloring and Colorability Analysis of Integrated Circuits with Triple and Quadruple Patterning TechniquesProceedings of the 2018 International Symposium on Physical Design10.1145/3177540.3178241(152-159)Online publication date: 25-Mar-2018
https://dl.acm.org/doi/10.1145/3177540.3178241
Ma YGao JKuang JMiao JYu BParameswaran S(2017)A unified framework for simultaneous layout decomposition and mask optimizationProceedings of the 36th International Conference on Computer-Aided Design10.5555/3199700.3199711(81-88)Online publication date: 13-Nov-2017
https://dl.acm.org/doi/10.5555/3199700.3199711
Lin YXu XYu BBaldick RPan D(2017)Triple/quadruple patterning layout decomposition via linear programming and iterative roundingJournal of Micro/Nanolithography, MEMS, and MOEMS10.1117/1.JMM.16.2.02350716:2(023507)Online publication date: 14-Jun-2017
https://doi.org/10.1117/1.JMM.16.2.023507
Chang HJiang I(2016)Multiple patterning layout decomposition considering complex coloring rulesProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2898048(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2898048
Yu BYuan KGao JHu SPan D(2016)EBL Overlapping Aware Stencil Planning for MCC SystemACM Transactions on Design Automation of Electronic Systems10.1145/288839421:3(1-24)Online publication date: 16-May-2016
https://dl.acm.org/doi/10.1145/2888394
Yu BPan DYu BPan D(2016)Design for Manufacturability with E-Beam LithographyDesign for Manufacturability with Advanced Lithography10.1007/978-3-319-20385-0_5(111-157)Online publication date: 2016
https://doi.org/10.1007/978-3-319-20385-0_5
Yu BPan DYu BPan D(2016)Layout Decomposition for Other Patterning TechniquesDesign for Manufacturability with Advanced Lithography10.1007/978-3-319-20385-0_3(53-82)Online publication date: 2016
https://doi.org/10.1007/978-3-319-20385-0_3
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