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 journalJournal articlepeer-review

22 Citations (Scopus)


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
Article number6558884
Pages (from-to)1228-1239
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number8
Publication statusPublished - Aug 2013

User-Defined Keywords

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


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