Post-routing layer assignment for double patterning with timing critical paths consideration

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Double patterning lithography is promising for 32 nm technology and beyond. In this technique, one-layer layout is decomposed into two masks. Much work has been proposed to solve feature decomposition problem. However, post-routing layer assignment, which determines the layout features 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 formulate post-routing layer assignment for double patterning problem for the first time. Both this problem and traditional single layer double patterning problem are proved to be NP-complete. An effective algorithm is further proposed to solve it. The algorithm consists of three major phases: multi-layer assignment to minimize double patterning risks, single layer double patterning, and via reduction. Since blind post-routing layer assignment may jeopardize timing critical paths obtained in the routing stage, our algorithm also considers total wire length and coupling capacitance on critical paths as timing metrics. Experimental results on Collaborative Benchmarking Laboratory benchmarks demonstrate the effectiveness of our algorithm. In comparison with single layer double patterning, our method achieves 62% and 11% average reduction on unresolvable conflicts and stitches, respectively, with only 0.30% increase of via number in layouts. Furthermore, the via height and parallel wire length on critical paths are decreased by 8% and 14% on average.

Original languageEnglish (US)
Pages (from-to)153-164
Number of pages12
JournalIntegration, the VLSI Journal
Issue number2
StatePublished - Mar 2013


  • Algorithm
  • Double patterning
  • Layer assignment
  • NP-completeness
  • Timing critical paths

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering


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

Cite this