TY - GEN
T1 - A polynomial time triple patterning algorithm for cell based row-structure layout
AU - Tian, Haitong
AU - Zhang, Hongbo
AU - Ma, Qiang
AU - Xiao, Zigang
AU - Wong, Martin D.F.
N1 - Funding Information:
This work was partially supported by the National Science Foundation under grant CCF-1017516 and a grant from the semiconductor Research Corporation (SRC).
Publisher copyright:
© 2012 ACM
PY - 2012/11/5
Y1 - 2012/11/5
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84872340080&partnerID=8YFLogxK
U2 - 10.1145/2429384.2429396
DO - 10.1145/2429384.2429396
M3 - Conference proceeding
AN - SCOPUS:84872340080
SN - 9781450315739
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
SP - 57
EP - 64
BT - ICCAD '12: Proceedings of the International Conference on Computer-Aided Design
A2 - Hu, Alan J.
PB - Association for Computing Machinery (ACM)
T2 - 2012 30th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2012
Y2 - 5 November 2012 through 8 November 2012
ER -