skip to main content
research-article

PARR: Pin-Access Planning and Regular Routing for Self-Aligned Double Patterning

Authors Info & Claims
Published:16 May 2016Publication History
Skip Abstract Section

Abstract

Pin access has become one of the most difficult challenges for detailed routing in advanced technology nodes, for example, in 14nm and below, for which double-patterning lithography has to be used for manufacturing lower metal routing layers with tight pitches, such as M2 and M3. Self-aligned double patterning (SADP) provides better control on line edge roughness and overlay, but it has very restrictive design constraints and prefers regular layout patterns. This article presents a comprehensive pin-access planning and regular routing framework (PARR) for SADP friendliness. Our key techniques include precomputation of both intracell and intercell pin accessibility, as well as local and global pin-access planning to enable handshaking between standard cell-level pin access and detailed routing under SADP constraints. A pin access–driven rip-up and reroute scheme is proposed to improve the ultimate routability. Our experimental results demonstrate that PARR can achieve much better routability and overlay control compared with previous approaches.

References

  1. C. J. Alpert, Z. Li, C. N. Sze, and Y. Wei. 2013. Consideration of local routing and pin access during VLSI global routing. Retrieved April 2, 2016 from http://www.google.com/patents/US20130086544 US Patent App. 13/252,067.Google ScholarGoogle Scholar
  2. Cadence. 2009. LEF/DEF Language Reference. Retrieved April 2, 2016 from ftp://ftp.sitsemi.ru/pub/Cadence/lefdefref.pdf.Google ScholarGoogle Scholar
  3. Cadence. 2012. Cadence SOC Encounter. Retrieved April 2, 2016 from http://www.cadence.com/.Google ScholarGoogle Scholar
  4. William A. Dees Jr and Patrick G. Karger. 1982. Automated rip-up and reroute techniques. In ACM/IEEE Design Automation Conference (DAC’82). 432--439. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. William A. Dees Jr and Robert J. Smith II. 1981. Performance of interconnection rip-up and reroute strategies. In ACM/IEEE Design Automation Conference (DAC’81). 382--390. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Yixiao Ding, Chris Chu, and Wai-Kei Mak. 2015. Detailed routing for spacer-is-metal type self-aligned double/quadruple patterning lithography. In ACM/IEEE Design Automation Conference (DAC’15). 69:1--69:6. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Yuelin Du, Qiang Ma, Hua Song, James Shiely, Gerard Luk-Pat, Alexander Miloslavsky, and Martin D. F. Wong. 2013. Spacer-is-dielectric-compliant detailed routing for self-aligned double patterning lithography. In ACM/IEEE Design Automation Conference (DAC’13). 93:1--93:6. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Jhih-Rong Gao and David Z. Pan. 2012. Flexible self-aligned double patterning aware detailed routing with prescribed layout planning. In ACM International Symposium on Physical Design (ISPD’12). 25--32. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Gurobi. 2014. GUROBI. Retrieved April 2, 2016 from http://www.gurobi.com/html/academic.html.Google ScholarGoogle Scholar
  10. Antonin Guttman. 1984. R-Trees: A Dynamic Index Structure for Spatial Searching. Vol. 14. ACM, New York, NY.Google ScholarGoogle Scholar
  11. Meng-Kai Hsu, Nitesh Katta, Homer Yen-Hung Lin, Keny Tzu-Hen Lin, King Ho Tam, and Ken Chung-Hsing Wang. 2014. Design and manufacturing process co-optimization in nano-technology. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD’14). 574--581. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Chikaaki Kodama, Hirotaka Ichikawa, Koichi Nakayama, Toshiya Kotani, Shigeki Nojima, Shoji Mimotogi, Shinji Miyamoto, and Atsushi Takahashi. 2013. Self-aligned double and quadruple patterning-aware grid routing with hotspots control. In IEEE/ACM Asia and South Pacific Design Automation Conference (ASPDAC’13). 267--272.Google ScholarGoogle ScholarCross RefCross Ref
  13. Iou-Jen Liu, Shao-Yun Fang, and Yao-Wen Chang. 2014. Overlay-aware detailed routing for self-aligned double patterning lithography using the cut process. In ACM/IEEE Design Automation Conference (DAC’14). 50:1--50:6. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Gerard Luk-Pat, Alex Miloslavsky, Ben Painter, Li Lin, Peter De Bisschop, and Kevin Lucas. 2012. Design compliance for spacer is dielectric (SID) patterning. In Proceedings of SPIE. 83260D--83260D.Google ScholarGoogle ScholarCross RefCross Ref
  15. Gerard Luk-Pat, Ben Painter, Alex Miloslavsky, Peter De Bisschop, Adam Beacham, and Kevin Lucas. 2013. Avoiding wafer-print artifacts in spacer is dielectric (SID) patterning. In Proceedings of SPIE. 868312--868312.Google ScholarGoogle ScholarCross RefCross Ref
  16. Yuangsheng Ma, Jason Sweis, Hidekazu Yoshida, Yan Wang, Jongwook Kye, and Harry J. Levinson. 2012. Self-aligned double patterning (SADP) compliant design flow. In Proceedings of SPIE. 832706--832706.Google ScholarGoogle Scholar
  17. Minoo Mirsaeedi, J. Andres Torres, and Mohab Anis. 2011. Self-aligned double-patterning (SADP) friendly detailed routing. In Proceedings of SPIE. 79740O--79740O.Google ScholarGoogle ScholarCross RefCross Ref
  18. NanGate. 2012. NanGate FreePDK45 Generic Open Cell Library. Retrieved April 2, 2016 from http://www.si2.org/openeda.si2.org/projects/nangatelib.Google ScholarGoogle Scholar
  19. Tim Nieberg. 2011. Gridless pin access in detailed routing. In ACM/IEEE Design Automation Conference (DAC’11). 170--175. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. OpenMP. 2011. The OpenMP API Specification for Parallel Programming. Retrieved April 2, 2016 from http://openmp.org/wp/. (2011).Google ScholarGoogle Scholar
  21. Muhammet Mustafa Ozdal. 2009. Detailed-routing algorithms for dense pin clusters in integrated circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 28, 3, 340--349. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. David Z. Pan, Bei Yu, and J.-R. Gao. 2013. Design for manufacturing with emerging nanolithography. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 10, 1453--1472. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. Zhongdong Qi, Yici Cai, and Qiang Zhou. 2014. Accurate prediction of detailed routing congestion using supervised data learning. In Proceedings of the IEEE International Conference on Computer Design (ICCD’14). IEEE, 97--103.Google ScholarGoogle ScholarCross RefCross Ref
  24. Michael C. Smayling, Koichiro Tsujita, Hidetami Yaegashi, Valery Axelrad, Tadashi Arai, Kenichi Oyama, and Arisa Hara. 2013. Sub-12nm optical lithography with 4x pitch division and SMO-lite. In Proceedings of SPIE. 868305--868305.Google ScholarGoogle ScholarCross RefCross Ref
  25. Synopsys. 2012. Synopsys Design Compiler. Retrieved April 2, 2016 from http://www.synopsys.com. (2012).Google ScholarGoogle Scholar
  26. Taraneh Taghavi, Charles Alpert, Andrew Huber, Zhuo Li, Gi-Joon Nam, and Shyam Ramji. 2010. New placement prediction and mitigation techniques for local routing congestion. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD’10). 621--624. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. Zigang Xiao, Yuelin Du, Haitong Tian, and Martin D. F. Wong. 2013. Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD’13). 32--39. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. Xiaoqing Xu, Brian Cline, Greg Yeric, Bei Yu, and David Z. Pan. 2014. Self-aligned double patterning aware pin access and standard cell layout co-optimization. In ACM International Symposium on Physical Design (ISPD). 101--108. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. Xiaoqing Xu, Bei Yu, Jhih-Rong Gao, Che-Lun Hsu, and David Z. Pan. 2015. PARR: Pin access planning and regular routing for self-aligned double patterning. In ACM/IEEE Design Automation Conference (DAC’15). 28:1--28:6. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. Wei Ye, Bei Yu, David Z. Pan, Yong-Chan Ban, and Lars Liebmann. 2015. Standard cell layout regularity and pin access optimization considering middle-of-line. In ACM Great Lakes Symposium on VLSI (GLSVLSI’15). 289--294. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. Yanheng Zhang and Chris Chu. 2011. RegularRoute: An efficient detailed router with regular routing patterns. In ACM International Symposium on Physical Design (ISPD’11). 45--52. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. PARR: Pin-Access Planning and Regular Routing for Self-Aligned Double Patterning

    Recommendations

    Comments

    Login options

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

    Sign in

    Full Access

    • 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
      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

      Publication History

      • Published: 16 May 2016
      • Accepted: 1 October 2015
      • Revised: 1 September 2015
      • Received: 1 July 2015
      Published in todaes Volume 21, Issue 3

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article
      • Research
      • Refereed

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader