Polynomial time optimal algorithm for stencil row planning in e-beam lithography

Daifeng Guo; Yuelin Du; Martin D.F. Wong

doi:10.1109/ASPDAC.2015.7059083

Polynomial time optimal algorithm for stencil row planning in e-beam lithography

Daifeng Guo, Yuelin Du, Martin D.F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

6 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	The 20th Asia and South Pacific Design Automation Conference
Publisher	IEEE
Pages	658-664
Number of pages	7
ISBN (Electronic)	9781479977925, 9781479977901 (CD)
DOIs	https://doi.org/10.1109/ASPDAC.2015.7059083
Publication status	Published - Jan 2015
Event	The 20th Asia and South Pacific Design Automation Conference - Chiba, Japan Duration: 19 Jan 2015 → 22 Jan 2015 https://ieeexplore.ieee.org/xpl/conhome/7050531/proceeding (Link to conference proceedings)

Publication series

Name	Proceedings of Asia and South Pacific Design Automation Conference

Conference

Conference	The 20th Asia and South Pacific Design Automation Conference
Country/Territory	Japan
City	Chiba
Period	19/01/15 → 22/01/15
Internet address	https://ieeexplore.ieee.org/xpl/conhome/7050531/proceeding (Link to conference proceedings)

Access to Document

10.1109/ASPDAC.2015.7059083

Cite this

@inproceedings{edaf35bb4f4c48839b2524762d745f82,

title = "Polynomial time optimal algorithm for stencil row planning in e-beam lithography",

abstract = "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.",

author = "Daifeng Guo and Yuelin Du and Wong, {Martin D.F.}",

note = "Funding Information: This work was partially supported by the National Science Foundation under grants CCF-1320585 and CCF-1421563. Publisher Copyright: {\textcopyright} 2015, IEEE; The 20th Asia and South Pacific Design Automation Conference ; Conference date: 19-01-2015 Through 22-01-2015",

year = "2015",

month = jan,

doi = "10.1109/ASPDAC.2015.7059083",

language = "English",

series = "Proceedings of Asia and South Pacific Design Automation Conference",

publisher = "IEEE",

pages = "658--664",

booktitle = "The 20th Asia and South Pacific Design Automation Conference",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/7050531/proceeding",

}

Guo, D, Du, Y & Wong, MDF 2015, Polynomial time optimal algorithm for stencil row planning in e-beam lithography. in The 20th Asia and South Pacific Design Automation Conference., 7059083, Proceedings of Asia and South Pacific Design Automation Conference, IEEE, pp. 658-664, The 20th Asia and South Pacific Design Automation Conference, Chiba, Japan, 19/01/15. https://doi.org/10.1109/ASPDAC.2015.7059083

Polynomial time optimal algorithm for stencil row planning in e-beam lithography. / Guo, Daifeng; Du, Yuelin; Wong, Martin D.F.
The 20th Asia and South Pacific Design Automation Conference. IEEE, 2015. p. 658-664 7059083 (Proceedings of Asia and South Pacific Design Automation Conference).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

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.

PY - 2015/1

Y1 - 2015/1

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 - https://www.scopus.com/record/display.uri?eid=2-s2.0-84926443731&origin=inward

U2 - 10.1109/ASPDAC.2015.7059083

DO - 10.1109/ASPDAC.2015.7059083

M3 - Conference proceeding

T3 - Proceedings of Asia and South Pacific Design Automation Conference

SP - 658

EP - 664

BT - The 20th Asia and South Pacific Design Automation Conference

PB - IEEE

T2 - The 20th Asia and South Pacific Design Automation Conference

Y2 - 19 January 2015 through 22 January 2015

ER -

Polynomial time optimal algorithm for stencil row planning in e-beam lithography

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this