Files in this item
Files | Description | Format |
---|---|---|
application/pdf ![]() | (no description provided) |
Description
Title: | Polynomial time optimal algorithm for stencil row planning in e-beam lithography |
Author(s): | Guo, Daifeng |
Advisor(s): | Wong, Martin D.F. |
Department / Program: | Electrical & Computer Eng |
Discipline: | Electrical & Computer Engr |
Degree Granting Institution: | University of Illinois at Urbana-Champaign |
Degree: | M.S. |
Genre: | Thesis |
Subject(s): | E-beam
Stencil Planning 1D Character Placement |
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 awareness of overlapping characters. However, the top-level 2D stencil planning problem has been proven 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. Previous research formulates the problem as the travelling salesman problem, which is NP-hard and solves it by heuristics. In this thesis, we formulate the problem as a matching problem and propose a polynomial time optimal algorithm, which serves as the major subroutine for the entire stencil planning problem. The optimality of the algorithm is proved, and experimental results are also provided to show that our work makes a great improvement in efficiency and correctness to solve the row ordering problem. |
Issue Date: | 2014-09-16 |
URI: | http://hdl.handle.net/2142/50492 |
Rights Information: | Copyright 2014 Daifeng Guo |
Date Available in IDEALS: | 2014-09-16 2016-09-22 |
Date Deposited: | 2014-08 |
This item appears in the following Collection(s)
-
Dissertations and Theses - Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering -
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois