TY - GEN
T1 - Network flow based cut redistribution and insertion for advanced 1D layout design
AU - Zhang, Ye
AU - Luk, Wai Shing
AU - Yang, Fan
AU - Yan, Changhao
AU - Zhou, Hai
AU - Zhou, Dian
AU - Zeng, Xuan
N1 - Funding Information:
This research was supported partly by Science Challenge Project, No. JCKY2016212A503, partly by National Science Foundation of China (NSFC) research projects 61376040, 61474026, 61574046, 61274032, 61674042, 61574044 and 91330201, partly by NSF Grant 1441695 and 1533656, partly by Chen Guang project supported by Shanghai Municipal Education Commission and Shanghai Education Development Foundation, partly by the fund of CAEP-SCNS(R2016-03-010), and partly by the Recruitment Program of Global Experts (the Thousand Talents Plan).
Publisher Copyright:
© 2017 IEEE.
PY - 2017/2/16
Y1 - 2017/2/16
N2 - End Cutting 1D layout design is a promising candidate for sub-10nm process nodes. Given a 1D layout with horizontal wires, cut redistribution technique is used for sliding the line-end cuts in order to align them vertically or resolve spacing conflicts. The aligned cuts can then be merged into a single shot of cuts. In this paper, we proposed a network flow based method for efficient cut redistribution and insertion. Normally, a pair of movable cuts could have three possible relations, left-of, right-of and merge-into. We observe that if the left-right-merge orderings of cuts are fixed, the cut redistribution can be formulated as a network flow problem, which can be solved efficiently. We also find that inserting cuts can resolve the spacing conflicts in some circumstances. This cut insertion strategy is introduced in our proposed method to reduce the spacing conflicts. Moreover, the complementary e-beam lithography for printing the cuts is also considered in this paper. Experimental results show that compared with a previous ILP-based method, our method can achieve a 200X speedup and competitive solution quality.
AB - End Cutting 1D layout design is a promising candidate for sub-10nm process nodes. Given a 1D layout with horizontal wires, cut redistribution technique is used for sliding the line-end cuts in order to align them vertically or resolve spacing conflicts. The aligned cuts can then be merged into a single shot of cuts. In this paper, we proposed a network flow based method for efficient cut redistribution and insertion. Normally, a pair of movable cuts could have three possible relations, left-of, right-of and merge-into. We observe that if the left-right-merge orderings of cuts are fixed, the cut redistribution can be formulated as a network flow problem, which can be solved efficiently. We also find that inserting cuts can resolve the spacing conflicts in some circumstances. This cut insertion strategy is introduced in our proposed method to reduce the spacing conflicts. Moreover, the complementary e-beam lithography for printing the cuts is also considered in this paper. Experimental results show that compared with a previous ILP-based method, our method can achieve a 200X speedup and competitive solution quality.
UR - http://www.scopus.com/inward/record.url?scp=85015299158&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85015299158&partnerID=8YFLogxK
U2 - 10.1109/ASPDAC.2017.7858349
DO - 10.1109/ASPDAC.2017.7858349
M3 - Conference contribution
AN - SCOPUS:85015299158
T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
SP - 360
EP - 365
BT - 2017 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017
Y2 - 16 January 2017 through 19 January 2017
ER -