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

research-article

An Effective Chemical Mechanical Polishing Fill Insertion Approach

Authors:

Evangeline F. Y. YoungAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 21, Issue 3

Article No.: 54, Pages 1 - 21

https://doi.org/10.1145/2886097

Published: 11 May 2016 Publication History

Abstract

To reduce chip-scale topography variation, dummy fill is commonly used to improve the layout density uniformity. Previous works either sought the most uniform density distribution or sought to minimize the inserted dummy fills while satisfying certain density uniformity constraint. However, due to more stringent manufacturing challenges, more criteria, like line deviation and outlier, emerge at newer technology nodes. This article presents a joint optimization scheme to consider variation, total fill, line deviation, outlier, overlap, and running time simultaneously. More specifically, first we decompose the rectilinear polygons and partition fillable regions into rectangles for easier processing. After decomposition, we insert dummy fills into the fillable rectangular regions optimizing the fill metrics simultaneously. We propose three approaches, Fast Median approach, LP approach, and Iterative approach, which are much faster with better quality, compared with the results of the top three contestants in the ICCAD Contest 2014.

References

[1]

Yu Chen, Puneet Gupta, and Andrew B. Kahng. 2003. Performance-impact limited-area fill synthesis. In Advanced Microelectronic Manufacturing. International Society for Optics and Photonics, 75--86.

[2]

Yu Chen, Andrew B. Kahng, Gabriel Robins, and Alex Zelikovsky. 2000. Monte-Carlo algorithms for layout density control. In Proceedings of the 2000 Asia and South Pacific Design Automation Conference. ACM, 523--528.

Digital Library

[3]

Yu Chen, Andrew B. Kahng, Gabriel Robins, and Alexander Zelikovsky. 2002. Area fill synthesis for uniform layout density. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 21, 10 (2002), 1132--1147.

Digital Library

[4]

Stephane Durocher and Saeed Mehrabi. 2012. Computing partitions of rectilinear polygons with minimum stabbing number. In COCOON. Springer, 228--239.

[5]

Chunyang Feng, Hai Zhou, Changhao Yan, Jun Tao, and Xuan Zeng. 2011. Efficient approximation algorithms for chemical mechanical polishing dummy fill. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 30, 3 (2011), 402--415.

Digital Library

[6]

L. Ferrari, P. V. Sankar, and Jack Sklansky. 1984. Minimal rectangular partitions of digitized blobs. Computer Vision, Graphics, and Image Processing 28, 1 (1984), 58--71.

[7]

Kevin D. Gourley and Douglas M. Green. 1983. Polygon-to-rectangle conversion algorithm. IEEE Computer Graphics and Applications 3, 1 (1983), 31--32.

Digital Library

[8]

Warren Grobman, M. Thompson, R. Wang, C. Yuan, Ruiqi Tian, and E. Demircan. 2001. Reticle enhancement technology: Implications and challenges for physical design. In Proceedings of the 38th Annual Design Automation Conference. ACM, 73--78.

Digital Library

[9]

Andrew B. Kahng, Gabriel Robins, Anish Singh, and Alexander Zelikovsky. 1999. Filling algorithms and analyses for layout density control. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 18, 4 (1999), 445--462.

Digital Library

[10]

Andrew B. Kahng and Rasit Onur Topaloglu. 2007. Performance-aware CMP fill pattern optimization. Invited Paper, in Proc. VMIC (2007).

[11]

Bernhard Liegl, Brian Sapp, Stephen Greco, Timothy A. Brunner, Nelson Felix, Ian Stobert, Kourosh Nafisi, and Chandrasekhar Sarma. 2010. Predicting substrate-induced focus error. Journal of Micro/Nanolithography, MEMS, and MOEMS 9, 4 (2010), 041311.

[12]

Yibo Lin, Bei Yu, and David Z. Pan. 2015. High performance dummy fill insertion with coupling and uniformity constraints. In Proceedings of the 52nd Annual Design Automation Conference. ACM, 71.

Digital Library

[13]

W. T. Liou, J. J. Tan, and R. C. Lee. 1989. Minimum partitioning simple rectilinear polygons in O (n log log n)-time. In Proceedings of the 5th Annual Symposium on Computational Geometry. ACM, 344--353.

Digital Library

[14]

Chuangwen Liu, Peishan Tu, Pangbo Wu, Haomo Tang, Yande Jiang, Jian Kuang, and Evangeline F. Y. Young. 2015. An effective chemical mechanical polishing filling approach. In Proceedings of the 2015 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). IEEE, 44--49.

[15]

Surendra Nahar and Sartaj Sahni. 1988. Fast algorithm for polygon decomposition. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 7, 4 (1988), 473--483.

Digital Library

[16]

Brian E. Stine, Duane S. Boning, James E. Chung, Lawrence Camilletti, Frank Kruppa, Edward R. Equi, William Loh, Sharad Prasad, Moorthy Muthukrishnan, Daniel Towery, and others. 1998. The physical and electrical effects of metal-fill patterning practices for oxide chemical-mechanical polishing processes. IEEE Transactions on Electron Devices 45, 3 (1998), 665--679.

[17]

Tomáš Suk, Cyril Höschl, and Jan Flusser. 2012. Decomposition of binary images a survey and comparison. Pattern Recognition 45, 12 (2012), 4279--4291.

Digital Library

[18]

Rasit O. Topaloglu. 2014. ICCAD-2014 CAD contest in design for manufacturability flow for advanced semiconductor nodes and benchmark suite. In Proceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design. IEEE Press, 367--368.

Digital Library

[19]

I.-Lun Tseng and Adam Postula. 2006. An efficient algorithm for partitioning parameterized polygons into rectangles. In Proceedings of the 16th ACM Great Lakes Symposium on VLSI. ACM, 366--371.

Digital Library

[20]

Ye Zhang, Wai-Shing Luk, Hai Zhou, Changhao Yan, and Xuan Zeng. 2013. Layout decomposition with pairwise coloring for multiple patterning lithography. In Proceedings of the International Conference on Computer-Aided Design. IEEE Press, 170--177.

Digital Library

[21]

Jinming Zhao, Hailong Yao, Yici Cai, and Qiang Zhou. 2013. A new splitting graph construction algorithm for SIAR router. In Proceedings of the 2013 IEEE 10th International Conference on ASIC (ASICON). IEEE, 1--4.

Cited By

Zhang QHuang HLi JZhang YLi Y(2023)CmpCNN: CMP Modeling with Transfer Learning CNN ArchitectureACM Transactions on Design Automation of Electronic Systems10.1145/356994128:4(1-18)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3569941
Kim HLee JAhn H(2023)Rectangular partitions of a rectilinear polygonComputational Geometry10.1016/j.comgeo.2022.101965110(101965)Online publication date: Mar-2023
https://doi.org/10.1016/j.comgeo.2022.101965
Maity ADutt MBiswas A(2022)Rectangularization of Digital Objects and Its Relation with Straight SkeletonsCombinatorial Image Analysis10.1007/978-3-031-23612-9_2(31-45)Online publication date: 13-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-23612-9_2
Show More Cited By

Index Terms

An Effective Chemical Mechanical Polishing Fill Insertion Approach
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Physical synthesis

Recommendations

On partitioning rectilinear polygons into star-shaped polygons
Abstract
We present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. ...
An efficient algorithm for partitioning parameterized polygons into rectangles
GLSVLSI '06: Proceedings of the 16th ACM Great Lakes symposium on VLSI

In this paper, we propose an algorithm for partitioning parameterized orthogonal polygons into rectangles. The algorithm is based on the plane-sweep technique and can be used for partitioning polygons which contain holes. The input to the algorithm ...
A parallel dual-scanline algorithm for partitioning parameterized 45-degree polygons
Special Section on Networks on Chip: Architecture, Tools, and Methodologies

In order to use rectangular corner stitching data structures in storing parameterized orthogonal layouts, parameterized polygons in the layouts must be partitioned into rectangles. Likewise, in order to use trapezoidal corner stitching data structures ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 21, Issue 3

Special Section on New Physical Design Techniques for the Next Generation Integration Technology and Regular Papers

July 2016

434 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/2926747

Editor:
Naehyuck Chang
Korea Advanced Institute of Science and Technology, Korea

Issue’s Table of Contents

Copyright © 2016 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 11 May 2016

Accepted: 01 January 2016

Revised: 01 January 2016

Received: 01 August 2015

Published in TODAES Volume 21, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Research Grants Council of the Hong Kong Special Administrative Region, China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
171
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang QHuang HLi JZhang YLi Y(2023)CmpCNN: CMP Modeling with Transfer Learning CNN ArchitectureACM Transactions on Design Automation of Electronic Systems10.1145/356994128:4(1-18)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3569941
Kim HLee JAhn H(2023)Rectangular partitions of a rectilinear polygonComputational Geometry10.1016/j.comgeo.2022.101965110(101965)Online publication date: Mar-2023
https://doi.org/10.1016/j.comgeo.2022.101965
Maity ADutt MBiswas A(2022)Rectangularization of Digital Objects and Its Relation with Straight SkeletonsCombinatorial Image Analysis10.1007/978-3-031-23612-9_2(31-45)Online publication date: 13-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-23612-9_2
Yu SKao CHuang CJiang ICheng KYang H(2020)Equivalent Capacitance Guided Dummy Fill Insertion for Timing and ManufacturabilityProceedings of the 25th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC47756.2020.9045668(133-138)Online publication date: 17-Jan-2020
https://dl.acm.org/doi/10.1109/ASP-DAC47756.2020.9045668
Shomalnasab GZhang L(2019)Density-Uniformity-Aware Analog Layout RetargetingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.278972837:10(1999-2012)Online publication date: 14-Nov-2019
https://dl.acm.org/doi/10.1109/TCAD.2018.2789728
Lin YYu BPan D(2017)High Performance Dummy Fill Insertion With Coupling and Uniformity ConstraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.263845236:9(1532-1544)Online publication date: Sep-2017
https://doi.org/10.1109/TCAD.2016.2638452
Durocher SMehrabi S(2017)Computing conforming partitions of orthogonal polygons with minimum stabbing numberTheoretical Computer Science10.1016/j.tcs.2017.05.035689(157-168)Online publication date: Aug-2017
https://doi.org/10.1016/j.tcs.2017.05.035

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents