TY - GEN
T1 - An efficient linear time triple patterning solver
AU - Tian, Haitong
AU - Zhang, Hongbo
AU - Xiao, Zigang
AU - Wong, Martin D.F.
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/3/11
Y1 - 2015/3/11
N2 - Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. In this paper, we applied triple patterning lithography on standard cell based designs, and proposed a novel algorithm to solve the problem. The algorithm guarantees to find a legal TPL decomposition with optimal number of stitches if one exists. A graph model is proposed to reduce the number of vertices in the solution graph, and a fast approach is developed to achieve simultaneous runtime and memory improvement. An efficient approach to limit the number of stitches is also proposed, which greatly reduces the total number of stitch candidates and enables an incremental implementation of the algorithm. Experimental results shows that the proposed algorithm is very efficient, which achieves 39.1% runtime improvement and 18.4% memory reduction compared with the state-of-the-art TPL algorithm on the same problem.
AB - Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. In this paper, we applied triple patterning lithography on standard cell based designs, and proposed a novel algorithm to solve the problem. The algorithm guarantees to find a legal TPL decomposition with optimal number of stitches if one exists. A graph model is proposed to reduce the number of vertices in the solution graph, and a fast approach is developed to achieve simultaneous runtime and memory improvement. An efficient approach to limit the number of stitches is also proposed, which greatly reduces the total number of stitch candidates and enables an incremental implementation of the algorithm. Experimental results shows that the proposed algorithm is very efficient, which achieves 39.1% runtime improvement and 18.4% memory reduction compared with the state-of-the-art TPL algorithm on the same problem.
UR - http://www.scopus.com/inward/record.url?scp=84926429871&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84926429871&partnerID=8YFLogxK
U2 - 10.1109/ASPDAC.2015.7059006
DO - 10.1109/ASPDAC.2015.7059006
M3 - Conference contribution
AN - SCOPUS:84926429871
T3 - 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015
SP - 208
EP - 213
BT - 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2015 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015
Y2 - 19 January 2015 through 22 January 2015
ER -