A polynomial time triple patterning algorithm for cell based row-structure layout

Haitong Tian, Hongbo Zhang, Qiang Ma, Zigang Xiao, Martin D.F. Wong

Research output: Contribution to journalConference articlepeer-review


As minimum feature size keeps shrinking, and the next generation lithography (e.g, EUV) further delays, double patterning lithography (DPL) has been widely recognized as a feasible lithography solution in 20nm technology node. However, as technology continues to scale to 14/10nm, DPL begins to show its limitations and usually generates too many undesirable stitches. Triple patterning lithography (TPL) is a natural extension of DPL to conquer the difficulties and achieve a stitch-free layout decomposition. In this paper, we study the standard cell based row-structure layout decomposition problem in TPL. Although the general TPL layout decomposition problem is NP-hard, in this paper we will show that for standard cell based TPL layout decomposition problem, it is polynomial time solvable. We propose a polynomial time algorithm to solve the problem optimally and our approach has the capability to find all stitch-free decompositions. Color balancing is also considered to ensure a balanced triple patterning decomposition. To speed up the algorithm, we further propose a hierarchical algorithm for standard cell based layout, which can reduce the run time by 34.5% on average without sacrificing the optimality. We also extend our algorithm to allow stitches for complex circuit designs, and our algorithm guarantees to find optimal solutions with minimum number of stitches.

Original languageEnglish (US)
Article number6386589
Pages (from-to)57-64
Number of pages8
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
StatePublished - 2012
Event2012 30th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2012 - San Jose, CA, United States
Duration: Nov 5 2012Nov 8 2012

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'A polynomial time triple patterning algorithm for cell based row-structure layout'. Together they form a unique fingerprint.

Cite this