Triple patterning aware detailed placement with constrained pattern assignment

Haitong Tian, Yuelin Du, Hongbo Zhang, Zigang Xiao, Martin D.F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. There are various concerns for TPL decompositions. For standard cell based designs, assigning the same pattern for the same type of cells is a desired property for TPL decomposition. It is more robust for process variations and gives the chip similar physical and electrical characteristics as well as more reliable and predictable performance. Assigning the same type of pattern for the same type of cell is called a constrained pattern assignment (CPA) problem. In this paper, we integrated the flow of detailed placement and TPL decompositions with CPA coloring constraints. We focused on refining a layout to make it CPA-friendly during the detailed placement stage while minimizing the area and HPWL (half perimeter wire length) overhead. A weighted partial MAX SAT approach is proposed which guarantees to obtain a CPA-friendly detailed placement result while minimizing the area overhead. An efficient graph model is also proposed to compute the locations of the cells with optimal HPWL. Our formulation is very efficient and achieves a 79.4% area overhead reduction compared with the approach of fixing cell colors beforehand. Better HPWL are also achieved consistently over all benchmarks.

Original languageEnglish (US)
Title of host publication2014 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - Digest of Technical Papers
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages116-123
Number of pages8
EditionJanuary
ISBN (Electronic)9781479962785
DOIs
StatePublished - Jan 5 2015
Externally publishedYes
Event2014 33rd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - San Jose, United States
Duration: Nov 2 2014Nov 6 2014

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
NumberJanuary
Volume2015-January
ISSN (Print)1092-3152

Other

Other2014 33rd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014
CountryUnited States
CitySan Jose
Period11/2/1411/6/14

Fingerprint

Lithography
Wire
Decomposition
Coloring
Refining
Color

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Cite this

Tian, H., Du, Y., Zhang, H., Xiao, Z., & Wong, M. D. F. (2015). Triple patterning aware detailed placement with constrained pattern assignment. In 2014 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - Digest of Technical Papers (January ed., pp. 116-123). [7001341] (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD; Vol. 2015-January, No. January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICCAD.2014.7001341

Triple patterning aware detailed placement with constrained pattern assignment. / Tian, Haitong; Du, Yuelin; Zhang, Hongbo; Xiao, Zigang; Wong, Martin D.F.

2014 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - Digest of Technical Papers. January. ed. Institute of Electrical and Electronics Engineers Inc., 2015. p. 116-123 7001341 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD; Vol. 2015-January, No. January).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Tian, H, Du, Y, Zhang, H, Xiao, Z & Wong, MDF 2015, Triple patterning aware detailed placement with constrained pattern assignment. in 2014 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - Digest of Technical Papers. January edn, 7001341, IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD, no. January, vol. 2015-January, Institute of Electrical and Electronics Engineers Inc., pp. 116-123, 2014 33rd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014, San Jose, United States, 11/2/14. https://doi.org/10.1109/ICCAD.2014.7001341
Tian H, Du Y, Zhang H, Xiao Z, Wong MDF. Triple patterning aware detailed placement with constrained pattern assignment. In 2014 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - Digest of Technical Papers. January ed. Institute of Electrical and Electronics Engineers Inc. 2015. p. 116-123. 7001341. (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD; January). https://doi.org/10.1109/ICCAD.2014.7001341
Tian, Haitong ; Du, Yuelin ; Zhang, Hongbo ; Xiao, Zigang ; Wong, Martin D.F. / Triple patterning aware detailed placement with constrained pattern assignment. 2014 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - Digest of Technical Papers. January. ed. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 116-123 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD; January).
@inproceedings{91b8a8815b1e40aea0a29309d0b54af1,
title = "Triple patterning aware detailed placement with constrained pattern assignment",
abstract = "Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. There are various concerns for TPL decompositions. For standard cell based designs, assigning the same pattern for the same type of cells is a desired property for TPL decomposition. It is more robust for process variations and gives the chip similar physical and electrical characteristics as well as more reliable and predictable performance. Assigning the same type of pattern for the same type of cell is called a constrained pattern assignment (CPA) problem. In this paper, we integrated the flow of detailed placement and TPL decompositions with CPA coloring constraints. We focused on refining a layout to make it CPA-friendly during the detailed placement stage while minimizing the area and HPWL (half perimeter wire length) overhead. A weighted partial MAX SAT approach is proposed which guarantees to obtain a CPA-friendly detailed placement result while minimizing the area overhead. An efficient graph model is also proposed to compute the locations of the cells with optimal HPWL. Our formulation is very efficient and achieves a 79.4{\%} area overhead reduction compared with the approach of fixing cell colors beforehand. Better HPWL are also achieved consistently over all benchmarks.",
author = "Haitong Tian and Yuelin Du and Hongbo Zhang and Zigang Xiao and Wong, {Martin D.F.}",
year = "2015",
month = "1",
day = "5",
doi = "10.1109/ICCAD.2014.7001341",
language = "English (US)",
series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "January",
pages = "116--123",
booktitle = "2014 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - Digest of Technical Papers",
address = "United States",
edition = "January",

}

TY - GEN

T1 - Triple patterning aware detailed placement with constrained pattern assignment

AU - Tian, Haitong

AU - Du, Yuelin

AU - Zhang, Hongbo

AU - Xiao, Zigang

AU - Wong, Martin D.F.

PY - 2015/1/5

Y1 - 2015/1/5

N2 - Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. There are various concerns for TPL decompositions. For standard cell based designs, assigning the same pattern for the same type of cells is a desired property for TPL decomposition. It is more robust for process variations and gives the chip similar physical and electrical characteristics as well as more reliable and predictable performance. Assigning the same type of pattern for the same type of cell is called a constrained pattern assignment (CPA) problem. In this paper, we integrated the flow of detailed placement and TPL decompositions with CPA coloring constraints. We focused on refining a layout to make it CPA-friendly during the detailed placement stage while minimizing the area and HPWL (half perimeter wire length) overhead. A weighted partial MAX SAT approach is proposed which guarantees to obtain a CPA-friendly detailed placement result while minimizing the area overhead. An efficient graph model is also proposed to compute the locations of the cells with optimal HPWL. Our formulation is very efficient and achieves a 79.4% area overhead reduction compared with the approach of fixing cell colors beforehand. Better HPWL are also achieved consistently over all benchmarks.

AB - Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. There are various concerns for TPL decompositions. For standard cell based designs, assigning the same pattern for the same type of cells is a desired property for TPL decomposition. It is more robust for process variations and gives the chip similar physical and electrical characteristics as well as more reliable and predictable performance. Assigning the same type of pattern for the same type of cell is called a constrained pattern assignment (CPA) problem. In this paper, we integrated the flow of detailed placement and TPL decompositions with CPA coloring constraints. We focused on refining a layout to make it CPA-friendly during the detailed placement stage while minimizing the area and HPWL (half perimeter wire length) overhead. A weighted partial MAX SAT approach is proposed which guarantees to obtain a CPA-friendly detailed placement result while minimizing the area overhead. An efficient graph model is also proposed to compute the locations of the cells with optimal HPWL. Our formulation is very efficient and achieves a 79.4% area overhead reduction compared with the approach of fixing cell colors beforehand. Better HPWL are also achieved consistently over all benchmarks.

UR - http://www.scopus.com/inward/record.url?scp=84936881778&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84936881778&partnerID=8YFLogxK

U2 - 10.1109/ICCAD.2014.7001341

DO - 10.1109/ICCAD.2014.7001341

M3 - Conference contribution

AN - SCOPUS:84936881778

T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD

SP - 116

EP - 123

BT - 2014 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - Digest of Technical Papers

PB - Institute of Electrical and Electronics Engineers Inc.

ER -