Effective decomposition algorithm for self-aligned double patterning lithography

Hongbo Zhang*, Yuelin Du, Martin D.F. Wong, Rasit Topaloglu, Will Conley

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

22 Citations (Scopus)


Self-aligned double patterning (SADP) lithography is a novel lithography technology that has the intrinsic capability to reduce the overlay in the double patterning lithography (DPL). Although SADP is the critical technology to solve the lithography difficulties in sub-32nm 2D design, the problems of how to decompose a layout with reasonable overlay and how to perform a decomposability check remain open with no published work. In this paper, by formulating the problem into a SAT formation, we can solve the above two problems optimally. This is the first published paper with a detailed algorithm to perform the SADP decomposition. In a layout, we can efficiently check whether a layout is decomposable. For a decomposable layout, our algorithm guarantees to find a decomposition solution with reasonable overlay reduction requirement. With little changes on the clauses in the SAT formula, we can address the decomposition problem for both the positive tone process and the negative tone process. Experimental results validate our method, and decomposition results for Nangate Open Cell Library and larger test cases are also provided with competitive run times.

Original languageEnglish
Title of host publicationOptical Microlithography XXIV
EditorsMircea V. Dusa
ISBN (Print)9780819485328
Publication statusPublished - Mar 2011
EventOptical Microlithography XXIV - San Jose, United States
Duration: 1 Mar 20113 Mar 2011

Publication series

NameProceedings of SPIE - The International Society for Optical Engineering
ISSN (Print)0277-786X


ConferenceOptical Microlithography XXIV
Country/TerritoryUnited States
CitySan Jose
Internet address

Scopus Subject Areas

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Decomposability check
  • Negative tone process
  • Overlay reduction
  • Positive tone process
  • Sadp decomposition
  • Sat


Dive into the research topics of 'Effective decomposition algorithm for self-aligned double patterning lithography'. Together they form a unique fingerprint.

Cite this