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

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 (US)
Title of host publication	20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	658-664
Number of pages	7
ISBN (Electronic)	9781479977925
DOIs	https://doi.org/10.1109/ASPDAC.2015.7059083
State	Published - Mar 11 2015
Event	2015 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015 - Chiba, Japan Duration: Jan 19 2015 → Jan 22 2015

Publication series

Name	20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015

Other

Other	2015 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015
Country/Territory	Japan
City	Chiba
Period	1/19/15 → 1/22/15

ASJC Scopus subject areas

Computer Science Applications
Electrical and Electronic Engineering
Control and Systems Engineering
Modeling and Simulation

Online availability

10.1109/ASPDAC.2015.7059083

Library availability

Discover UIUC Full Text

Cite this

Guo, D., Du, Y., & Wong, M. D. F. (2015). Polynomial time optimal algorithm for stencil row planning in e-beam lithography. In 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015 (pp. 658-664). Article 7059083 (20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015). Institute of Electrical and Electronics Engineers Inc.. 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.
20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 658-664 7059083 (20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

@inproceedings{1468ca538fba4693b89f216db29201b6,

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 = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 2015 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015 ; Conference date: 19-01-2015 Through 22-01-2015",

year = "2015",

month = mar,

day = "11",

doi = "10.1109/ASPDAC.2015.7059083",

language = "English (US)",

series = "20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "658--664",

booktitle = "20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015",

address = "United States",

}

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/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 -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this