A polynomial time exact algorithm for overlay-resistant self-aligned double patterning (SADP) layout decomposition

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

Research output: Contribution to journalArticlepeer-review


Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14 nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well studied in the literature, only a few attempts have been made to address the SADP layout decomposition problem. In this paper, we present a polynomial time exact (optimal) algorithm to determine if a given layout has SADP decompositions that do not have any overlay at specified critical edges. The previous approaches tried to minimize the total overlay of a given layout, which may be a problematic objective. Furthermore, all previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.

Original languageEnglish (US)
Article number6558884
Pages (from-to)1228-1239
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number8
StatePublished - Aug 5 2013


  • Computer-aided design
  • design for manufacturability
  • electronic design automation
  • layout decomposition
  • polynomial time algorithm
  • self-aligned double patterning

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A polynomial time exact algorithm for overlay-resistant self-aligned double patterning (SADP) layout decomposition'. Together they form a unique fingerprint.

Cite this