Constrained pattern assignment for standard cell based triple patterning lithography

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 candidates for 14/10nm technology node. Apart from obtaining legal TPL decompositions, various concerns have been raised by the designers, among them consistently assigning the same pattern for the same type of standard cells and balancing the usage of the three masks are two most critical ones. In this paper, a hybrid approach (SAT followed by a sliding-window approach) is proposed targeting at these two problems. To assign the same pattern for the same type of standard cell, we pre-color the boundary polygons of each type of cell by solving a small SAT problem. Following that we propose a sliding-window based approach to compute a locally balanced decomposition. Our algorithm guarantees to find a feasible solution if one exists. Experimental results verify that the problem can be solved very efficiently with the proposed algorithm. Superior locally balanced decompositions are achieved compared with the previous approach in [19].

Original languageEnglish (US)
Title of host publication2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers
Pages178-185
Number of pages8
DOIs
StatePublished - Dec 1 2013
Event2013 32nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - San Jose, CA, United States
Duration: Nov 18 2013Nov 21 2013

Publication series

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

Other

Other2013 32nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013
CountryUnited States
CitySan Jose, CA
Period11/18/1311/21/13

Fingerprint

Lithography
Decomposition
Masks
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. (2013). Constrained pattern assignment for standard cell based triple patterning lithography. In 2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers (pp. 178-185). [6691116] (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD). https://doi.org/10.1109/ICCAD.2013.6691116

Constrained pattern assignment for standard cell based triple patterning lithography. / Tian, Haitong; Du, Yuelin; Zhang, Hongbo; Xiao, Zigang; Wong, Martin D.F.

2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers. 2013. p. 178-185 6691116 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD).

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

Tian, H, Du, Y, Zhang, H, Xiao, Z & Wong, MDF 2013, Constrained pattern assignment for standard cell based triple patterning lithography. in 2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers., 6691116, IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD, pp. 178-185, 2013 32nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013, San Jose, CA, United States, 11/18/13. https://doi.org/10.1109/ICCAD.2013.6691116
Tian H, Du Y, Zhang H, Xiao Z, Wong MDF. Constrained pattern assignment for standard cell based triple patterning lithography. In 2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers. 2013. p. 178-185. 6691116. (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD). https://doi.org/10.1109/ICCAD.2013.6691116
Tian, Haitong ; Du, Yuelin ; Zhang, Hongbo ; Xiao, Zigang ; Wong, Martin D.F. / Constrained pattern assignment for standard cell based triple patterning lithography. 2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers. 2013. pp. 178-185 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD).
@inproceedings{cfa00c617c9f486aa282f4bebd80ff68,
title = "Constrained pattern assignment for standard cell based triple patterning lithography",
abstract = "Triple patterning lithography (TPL) has been recognized as one of the most promising candidates for 14/10nm technology node. Apart from obtaining legal TPL decompositions, various concerns have been raised by the designers, among them consistently assigning the same pattern for the same type of standard cells and balancing the usage of the three masks are two most critical ones. In this paper, a hybrid approach (SAT followed by a sliding-window approach) is proposed targeting at these two problems. To assign the same pattern for the same type of standard cell, we pre-color the boundary polygons of each type of cell by solving a small SAT problem. Following that we propose a sliding-window based approach to compute a locally balanced decomposition. Our algorithm guarantees to find a feasible solution if one exists. Experimental results verify that the problem can be solved very efficiently with the proposed algorithm. Superior locally balanced decompositions are achieved compared with the previous approach in [19].",
author = "Haitong Tian and Yuelin Du and Hongbo Zhang and Zigang Xiao and Wong, {Martin D.F.}",
year = "2013",
month = "12",
day = "1",
doi = "10.1109/ICCAD.2013.6691116",
language = "English (US)",
isbn = "9781479910717",
series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD",
pages = "178--185",
booktitle = "2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers",

}

TY - GEN

T1 - Constrained pattern assignment for standard cell based triple patterning lithography

AU - Tian, Haitong

AU - Du, Yuelin

AU - Zhang, Hongbo

AU - Xiao, Zigang

AU - Wong, Martin D.F.

PY - 2013/12/1

Y1 - 2013/12/1

N2 - Triple patterning lithography (TPL) has been recognized as one of the most promising candidates for 14/10nm technology node. Apart from obtaining legal TPL decompositions, various concerns have been raised by the designers, among them consistently assigning the same pattern for the same type of standard cells and balancing the usage of the three masks are two most critical ones. In this paper, a hybrid approach (SAT followed by a sliding-window approach) is proposed targeting at these two problems. To assign the same pattern for the same type of standard cell, we pre-color the boundary polygons of each type of cell by solving a small SAT problem. Following that we propose a sliding-window based approach to compute a locally balanced decomposition. Our algorithm guarantees to find a feasible solution if one exists. Experimental results verify that the problem can be solved very efficiently with the proposed algorithm. Superior locally balanced decompositions are achieved compared with the previous approach in [19].

AB - Triple patterning lithography (TPL) has been recognized as one of the most promising candidates for 14/10nm technology node. Apart from obtaining legal TPL decompositions, various concerns have been raised by the designers, among them consistently assigning the same pattern for the same type of standard cells and balancing the usage of the three masks are two most critical ones. In this paper, a hybrid approach (SAT followed by a sliding-window approach) is proposed targeting at these two problems. To assign the same pattern for the same type of standard cell, we pre-color the boundary polygons of each type of cell by solving a small SAT problem. Following that we propose a sliding-window based approach to compute a locally balanced decomposition. Our algorithm guarantees to find a feasible solution if one exists. Experimental results verify that the problem can be solved very efficiently with the proposed algorithm. Superior locally balanced decompositions are achieved compared with the previous approach in [19].

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

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

U2 - 10.1109/ICCAD.2013.6691116

DO - 10.1109/ICCAD.2013.6691116

M3 - Conference contribution

AN - SCOPUS:84893382011

SN - 9781479910717

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

SP - 178

EP - 185

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

ER -