research-article

TPL-Aware Displacement-driven Detailed Placement Refinement with Coloring Constraints

Authors:

Tao Lin,

Chris ChuAuthors Info & Claims

ISPD '15: Proceedings of the 2015 Symposium on International Symposium on Physical Design

Pages 75 - 80

https://doi.org/10.1145/2717764.2717770

Published: 29 March 2015 Publication History

Get Access

Abstract

To minimize the effect of process variation for a design in triple patterning lithography (TPL), it is beneficial for all standard cells of the same type to share a single coloring solution. In this paper, we investigate the TPL-aware detailed placement refinement problem under these coloring constraints. Given an initial detailed placement, the positions of standard cells are perturbed and a TPL solution complying with the coloring constraints is derived while minimizing cell displacement, lithography conflicts and stitches. We prove that this problem is NP-complete and show that it can be formulated as a mixed integer linear program. Since mixed integer linear programming is very time consuming, we propose an effective heuristic algorithm. In our approach, important adjacent pairs of standard cells are recognized firstly, since they have significant impact on cell displacement. Then a tree-based heuristic is applied to generate a good initial solution for our linear programming-based refinement. Experimental results show that compared with mixed integer linear programming, our heuristic approach is comparable in solution quality while using very short CPU runtime.

References

[1]

B. Yu, K. Yuan, B. Zhang, D. Ding, and D. Z. Pan, "Layout decomposition for triple patterning lithography," in Proceedings of the International Conference on Computer-Aided Design, pp. 1--8, 2011.

Digital Library

Google Scholar

[2]

S.-Y. Fang, Y.-W. Chang, and W.-Y. Chen, "A novel layout decomposition algorithm for triple patterning lithography," in Proceedings of the 49th Annual Design Automation Conference, pp. 1185--1190, 2012.

Digital Library

Google Scholar

[3]

J. Kuang and E. F. Y. Young, "An efficient layout decomposition approach for triple patterning lithography," in Proceedings of the 50th Annual Design Automation Conference, pp. 69--75, 2013.

Digital Library

Google Scholar

[4]

Y. Zhang, W.-S. Luk, H. Zhou, C. Yan, and X. Zeng, "Layout decomposition with pairwise coloring for multiple patterning lithography," in Proceedings of the International Conference on Computer-Aided Design, pp. 170--177, 2013.

Digital Library

Google Scholar

[5]

H. Tian, H. Zhang, Q. Ma, Z. Xiao, and M. D. F. Wong, "A polynomial time triple patterning algorithm for cell based row-structure layout," in Proceedings of the International Conference on Computer-Aided Design, pp. 57--64, 2012.

Digital Library

Google Scholar

[6]

H. Tian, Y. Du, H. Zhang, Z. Xiao, and M. D. F. Wong, "Constrained pattern assignment for standard cell based triple patterning lithography," in Proceedings of the International Conference on Computer-Aided Design, pp. 178--185, 2013.

Digital Library

Google Scholar

[7]

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 Proceedings of the International Conference on Computer-Aided Design, pp. 163--169, 2013.

Digital Library

Google Scholar

[8]

Z. Chen, H. Yao, and Y. Cai, "Suald: Spacing uniformity-aware layout decomposition in triple patterning lithography.," in ISQED, pp. 566--571, 2013.

Google Scholar

[9]

Q. Ma, H. Zhang, and M. D. F. Wong, "Triple patterning aware routing and its comparison with double patterning aware routing in 14nm technology," in Proceedings of the 49th Annual Design Automation Conference, pp. 591--596, 2012.

Digital Library

Google Scholar

[10]

Y.-H. Lin, B. Yu, D. Z. Pan, and Y.-L. Li, "Triad: A triple patterning lithography aware detailed router," in Proceedings of the International Conference on Computer-Aided Design, pp. 123--129, 2012.

Digital Library

Google Scholar

[11]

B. Yu, X. Xu, J.-R. Gao, and D. Z. Pan, "Methodology for standard cell compliance and detailed placement for triple patterning lithography," in Proceedings of the International Conference on Computer-Aided Design, pp. 349--356, 2013.

Digital Library

Google Scholar

[12]

M. R. Garey and D. S. Johnson. A Guide to the Theory of NP-Completeness. Macmillan Higher Education, 1979.

Digital Library

Google Scholar

[13]

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

Google Scholar

Cited By

View all

Zhong YYu TYang KFang SSwartz WLienig J(2020)Via Pillar-aware Detailed PlacementProceedings of the 2020 International Symposium on Physical Design10.1145/3372780.3375561(17-24)Online publication date: 30-Mar-2020
https://dl.acm.org/doi/10.1145/3372780.3375561
Lin YLi WGu JRen HKhailany BPan D(2020)ABCDPlace: Accelerated Batch-based Concurrent Detailed Placement on Multi-threaded CPUs and GPUsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.2971531(1-1)Online publication date: 2020
https://doi.org/10.1109/TCAD.2020.2971531
Debacker PHan KKahng ALee HRaghavan PWang L(2017)Vertical M1 Routing-Aware Detailed Placement for Congestion and Wirelength Reduction in Sub-10nm NodesProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062338(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062338
Show More Cited By

Index Terms

TPL-Aware Displacement-driven Detailed Placement Refinement with Coloring Constraints
1. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Software implementation planning
        Software design techniques
    2. Software development process management
      1. Software development methods

Recommendations

Cell density-driven detailed placement with displacement constraint
ISPD '14: Proceedings of the 2014 on International symposium on physical design

Modern placement process involves global placement, legalization, and detailed placement. Global placement produce a placement solution with minimized target objective, which is usually wire-length, routability, timing, etc. Legalization removes cell ...
Pin Accessibility-Driven Detailed Placement Refinement
ISPD '17: Proceedings of the 2017 ACM on International Symposium on Physical Design

The significantly increased number of routing design rules at sub-20nm nodes has made pin access one of the most critical challenges in detailed routing. Resolving pin access issues in detailed routing stage may be too late due to the fixed pin ...
Routability-Driven Blockage-Aware Macro Placement
DAC '14: Proceedings of the 51st Annual Design Automation Conference

We present a new floorplan representation, called circular-packing trees (CP-trees), for the problem of macro placement. Our CP-trees can flexibly pack movable macros toward corners or pre-placed macros along chip boundaries circularly to optimize macro ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISPD '15: Proceedings of the 2015 Symposium on International Symposium on Physical Design

March 2015

204 pages

ISBN:9781450333993

DOI:10.1145/2717764

General Chair:
Azadeh Davoodi
University of Wisconsin - Madison
,
Program Chair:
Evangeline Young
The Chinese University of Hong Kong

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: 29 March 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ISPD'15

Sponsor:

SIGDA

ISPD'15: International Symposium on Physical Design

March 29 - April 1, 2015

California, Monterey, USA

Acceptance Rates

ISPD '15 Paper Acceptance Rate 14 of 37 submissions, 38%;

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

15
Total Citations
View Citations
112
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhong YYu TYang KFang SSwartz WLienig J(2020)Via Pillar-aware Detailed PlacementProceedings of the 2020 International Symposium on Physical Design10.1145/3372780.3375561(17-24)Online publication date: 30-Mar-2020
https://dl.acm.org/doi/10.1145/3372780.3375561
Lin YLi WGu JRen HKhailany BPan D(2020)ABCDPlace: Accelerated Batch-based Concurrent Detailed Placement on Multi-threaded CPUs and GPUsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.2971531(1-1)Online publication date: 2020
https://doi.org/10.1109/TCAD.2020.2971531
Debacker PHan KKahng ALee HRaghavan PWang L(2017)Vertical M1 Routing-Aware Detailed Placement for Congestion and Wirelength Reduction in Sub-10nm NodesProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062338(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062338
Mak WKuo WZhang SLei SChu C(2017)Minimum Implant Area-Aware Placement and Threshold Voltage RefinementIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.266181936:7(1103-1112)Online publication date: Jul-2017
https://doi.org/10.1109/TCAD.2017.2661819
Lin YYu BXu BPan D(2017)Triple Patterning Aware Detailed Placement Toward Zero Cross-Row Middle-of-Line ConflictIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.264884336:7(1140-1152)Online publication date: Jul-2017
https://doi.org/10.1109/TCAD.2017.2648843
Lin YYu BZou YLi ZAlpert CPan D(2017)Stitch aware detailed placement for multiple E-beam lithographyIntegration10.1016/j.vlsi.2017.02.00458(47-54)Online publication date: Jun-2017
https://doi.org/10.1016/j.vlsi.2017.02.004
Tseng KChang YLiu C(2016)Minimum-implant-area-aware detailed placement with spacing constraintsProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2898045(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2898045
Kuang JChow WYoung E(2016)Triple Patterning Lithography Aware Optimization and Detailed Placement Algorithms for Standard Cell-Based DesignsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2015.246146324:4(1319-1332)Online publication date: Apr-2016
https://doi.org/10.1109/TVLSI.2015.2461463
Lin YYu BPan D(2016)Detailed placement in advanced technology nodes: A survey2016 13th IEEE International Conference on Solid-State and Integrated Circuit Technology (ICSICT)10.1109/ICSICT.2016.7999056(836-839)Online publication date: Oct-2016
https://doi.org/10.1109/ICSICT.2016.7999056
Lei SMak WChu C(2016)Minimum implant area-aware placement and threshold voltage refinement2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2016.7428010(192-197)Online publication date: Jan-2016
https://doi.org/10.1109/ASPDAC.2016.7428010
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.

Cited By

Index Terms

Recommendations

Cell density-driven detailed placement with displacement constraint

Pin Accessibility-Driven Detailed Placement Refinement

Routability-Driven Blockage-Aware Macro Placement