Post-routing layer assignment for double patterning

Jian Sun, Yinghai Lu, Hai Zhou, Xuan Zeng*

*Corresponding author for this work

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

14 Scopus citations


Double patterning lithography, where one-layer layout is decomposed into two masks, is believed to be inevitable for 32nm technology node of the ITRS roadmap. However, post-routing layer assignment, which decides the layout pattern on each layer, thus having great impact on double patterning related parameters, has not been explored in the merit of double patterning. In this paper, we propose a post-routing layer assignment algorithm for double patterning optimization. Our solution consists of three major phases: multi-layer assignment, single-layer double patterning, and via reduction. For phase one and three, multi-layer graph is constructed and dynamic programming is employed to solve optimization problem on this graph. In the second phase, single-layer double patterning is proved NP-hard and existing algorithm is implemented to optimize single layer double patterning problem. The proposed method is tested on CBL (Collaborative Benchmarking Laboratory) benchmarks and shows great performance. In comparison with single-layer double patterning, our method achieves 73% and 27% average reduction for unresolvable conflicts and stitches respectively, with only 9% increase of via number. When double patterning is constrained on only the bottom two metal layers as in current technology, these numbers become 62%, 8% and 0.42%.

Original languageEnglish (US)
Title of host publication2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
Number of pages6
StatePublished - Mar 28 2011
Event2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011 - Yokohama, Japan
Duration: Jan 25 2011Jan 28 2011

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC


Other2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Post-routing layer assignment for double patterning'. Together they form a unique fingerprint.

Cite this