TY - GEN
T1 - Polynomial time optimal algorithm for stencil row planning in e-beam lithography
AU - Guo, Daifeng
AU - Du, Yuelin
AU - Wong, Martin D.F.
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/3/11
Y1 - 2015/3/11
N2 - Electron beam lithography (EBL) is a very promising candidate for integrated circuit (IC) fabrication beyond the 10 nm technology node. To address its throughput issue, the Character Projection (CP) technique has been proposed, and its stencil planning can be optimized with aware of overlapping characters. However, the top level 2D stencil planning problem has been proved to be an NP-hard problem. As its most essential step, the 1D row ordering is believed hard as well, and no polynomial time optimal solution has been provided so far. In this paper, we propose a polynomial time optimal algorithm to solve the row ordering problem, which serves as the major subroutine for the entire stencil planning problem. Proof and experimental results are also provided to verify the correctness and efficiency of our algorithm.
AB - Electron beam lithography (EBL) is a very promising candidate for integrated circuit (IC) fabrication beyond the 10 nm technology node. To address its throughput issue, the Character Projection (CP) technique has been proposed, and its stencil planning can be optimized with aware of overlapping characters. However, the top level 2D stencil planning problem has been proved to be an NP-hard problem. As its most essential step, the 1D row ordering is believed hard as well, and no polynomial time optimal solution has been provided so far. In this paper, we propose a polynomial time optimal algorithm to solve the row ordering problem, which serves as the major subroutine for the entire stencil planning problem. Proof and experimental results are also provided to verify the correctness and efficiency of our algorithm.
UR - http://www.scopus.com/inward/record.url?scp=84926443731&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84926443731&partnerID=8YFLogxK
U2 - 10.1109/ASPDAC.2015.7059083
DO - 10.1109/ASPDAC.2015.7059083
M3 - Conference contribution
AN - SCOPUS:84926443731
T3 - 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015
SP - 658
EP - 664
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 -