Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time

Zigang Xiao, Yuelin Du, Haitong Tian, Martin D F Wong

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

Abstract

Self-aligned double patterning is one of the most promising double patterning techniques for sub-20nm nodes. As in any multiple patterning techniques, layout decomposition is the most important problem. In SADP decomposition, overlay is among the most primary concerns. Most of the existing works target at minimizing the overall overlay, while others totally forbid the overlay. On the other hand, most of the works either rely on exponential time methods, or apply heuristic that cannot guarantee to find a solution. In this paper, we consider the SADP decomposition problem in row-based standard cell layout, where the overlay violations are minimized. Although SADP decomposition has been shown to be NP-hard in general, we showed that it can be solved in polynomial time when the layout is row-based standard cells. We propose a polynomial time optimal algorithm that finds a decomposition with minimum overlay violations. The efficiency of our method is further demonstrated by the experimental results.

Original languageEnglish (US)
Title of host publication2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers
Pages32-39
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

Polynomials
Decomposition

ASJC Scopus subject areas

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

Cite this

Xiao, Z., Du, Y., Tian, H., & Wong, M. D. F. (2013). Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time. In 2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers (pp. 32-39). [6691094] (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD). https://doi.org/10.1109/ICCAD.2013.6691094

Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time. / Xiao, Zigang; Du, Yuelin; Tian, Haitong; Wong, Martin D F.

2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers. 2013. p. 32-39 6691094 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD).

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

Xiao, Z, Du, Y, Tian, H & Wong, MDF 2013, Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time. in 2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers., 6691094, IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD, pp. 32-39, 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.6691094
Xiao Z, Du Y, Tian H, Wong MDF. Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time. In 2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers. 2013. p. 32-39. 6691094. (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD). https://doi.org/10.1109/ICCAD.2013.6691094
Xiao, Zigang ; Du, Yuelin ; Tian, Haitong ; Wong, Martin D F. / Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time. 2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers. 2013. pp. 32-39 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD).
@inproceedings{286919586bef4c5ba854a1a32b30c544,
title = "Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time",
abstract = "Self-aligned double patterning is one of the most promising double patterning techniques for sub-20nm nodes. As in any multiple patterning techniques, layout decomposition is the most important problem. In SADP decomposition, overlay is among the most primary concerns. Most of the existing works target at minimizing the overall overlay, while others totally forbid the overlay. On the other hand, most of the works either rely on exponential time methods, or apply heuristic that cannot guarantee to find a solution. In this paper, we consider the SADP decomposition problem in row-based standard cell layout, where the overlay violations are minimized. Although SADP decomposition has been shown to be NP-hard in general, we showed that it can be solved in polynomial time when the layout is row-based standard cells. We propose a polynomial time optimal algorithm that finds a decomposition with minimum overlay violations. The efficiency of our method is further demonstrated by the experimental results.",
author = "Zigang Xiao and Yuelin Du and Haitong Tian and Wong, {Martin D F}",
year = "2013",
month = "12",
day = "1",
doi = "10.1109/ICCAD.2013.6691094",
language = "English (US)",
isbn = "9781479910717",
series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD",
pages = "32--39",
booktitle = "2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers",

}

TY - GEN

T1 - Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time

AU - Xiao, Zigang

AU - Du, Yuelin

AU - Tian, Haitong

AU - Wong, Martin D F

PY - 2013/12/1

Y1 - 2013/12/1

N2 - Self-aligned double patterning is one of the most promising double patterning techniques for sub-20nm nodes. As in any multiple patterning techniques, layout decomposition is the most important problem. In SADP decomposition, overlay is among the most primary concerns. Most of the existing works target at minimizing the overall overlay, while others totally forbid the overlay. On the other hand, most of the works either rely on exponential time methods, or apply heuristic that cannot guarantee to find a solution. In this paper, we consider the SADP decomposition problem in row-based standard cell layout, where the overlay violations are minimized. Although SADP decomposition has been shown to be NP-hard in general, we showed that it can be solved in polynomial time when the layout is row-based standard cells. We propose a polynomial time optimal algorithm that finds a decomposition with minimum overlay violations. The efficiency of our method is further demonstrated by the experimental results.

AB - Self-aligned double patterning is one of the most promising double patterning techniques for sub-20nm nodes. As in any multiple patterning techniques, layout decomposition is the most important problem. In SADP decomposition, overlay is among the most primary concerns. Most of the existing works target at minimizing the overall overlay, while others totally forbid the overlay. On the other hand, most of the works either rely on exponential time methods, or apply heuristic that cannot guarantee to find a solution. In this paper, we consider the SADP decomposition problem in row-based standard cell layout, where the overlay violations are minimized. Although SADP decomposition has been shown to be NP-hard in general, we showed that it can be solved in polynomial time when the layout is row-based standard cells. We propose a polynomial time optimal algorithm that finds a decomposition with minimum overlay violations. The efficiency of our method is further demonstrated by the experimental results.

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

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

U2 - 10.1109/ICCAD.2013.6691094

DO - 10.1109/ICCAD.2013.6691094

M3 - Conference contribution

AN - SCOPUS:84893355134

SN - 9781479910717

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

SP - 32

EP - 39

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

ER -