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 - 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
Country/TerritoryUnited States
CitySan Jose, CA
Period11/18/1311/21/13

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time'. Together they form a unique fingerprint.

Cite this