{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/50492"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/50492","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"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 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.","abstract_html":"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.","abstract_has_math":false,"creators":["Guo, Daifeng"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Wong, Martin D.F."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-09-16T17:18:00Z","date_published":"2014-09-16T17:18:00Z","updated_at":"2026-07-22T22:25:40Z","subjects":["E-beam","Stencil Planning","1D Character Placement"],"languages":["en"],"rights":["Copyright 2014 Daifeng Guo"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/50492","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wong, Martin D.F."]},{"key":"dc:creator","label":"Author","values":["Guo, Daifeng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-09-16T17:18:00Z","2016-09-22T20:59:17Z","2014-08","2014-09-16"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["E-beam","Stencil Planning","1D Character Placement"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Daifeng Guo"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/50492"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-07-24T12:50:21Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 5 thesisrefs.bib: 43311 bytes, checksum: c965cf7bca360b49c4ae099775b37f4b (MD5) ack.tex: 72 bytes, checksum: eadd9e0078743e45f263fc0fe082f9eb (MD5) abs.tex: 1057 bytes, checksum: cf307f7a736e5945e4df023bdb09b6bf (MD5) ecethesis_daifeng.tex: 53700 bytes, checksum: 64420b5c3f16e7a6665f9e881f8ce0dc (MD5) Guo_Daifeng.pdf: 1001024 bytes, checksum: ec85dc30a12f0d051c15b5f6c1df1708 (MD5)","Made available in DSpace on 2014-09-16T17:18:00Z (GMT). No. of bitstreams: 6 Daifeng_Guo.pdf: 1001024 bytes, checksum: ec85dc30a12f0d051c15b5f6c1df1708 (MD5) thesisrefs.bib: 43311 bytes, checksum: c965cf7bca360b49c4ae099775b37f4b (MD5) ack.tex: 72 bytes, checksum: eadd9e0078743e45f263fc0fe082f9eb (MD5) abs.tex: 1057 bytes, checksum: cf307f7a736e5945e4df023bdb09b6bf (MD5) ecethesis_daifeng.tex: 53700 bytes, checksum: 64420b5c3f16e7a6665f9e881f8ce0dc (MD5) license.txt: 4058 bytes, checksum: c3a37295c64d86ba0e0fbab267583223 (MD5)","Embargo set by: Seth Robbins for item 50603 Lift date: 2016-09-16T17:18:17Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 50603 on 2016-09-22T20:59:17Z."]},{"key":"dc:title","label":"Title","values":["Polynomial time optimal algorithm for stencil row planning in e-beam lithography"]}]}],"canonical_facts":{"dc:contributor":["Wong, Martin D.F."],"dc:creator":["Guo, Daifeng"],"dc:date":["2014-09-16T17:18:00Z","2016-09-22T20:59:17Z","2014-08","2014-09-16"],"dc:description":["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.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-07-24T12:50:21Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 5 thesisrefs.bib: 43311 bytes, checksum: c965cf7bca360b49c4ae099775b37f4b (MD5) ack.tex: 72 bytes, checksum: eadd9e0078743e45f263fc0fe082f9eb (MD5) abs.tex: 1057 bytes, checksum: cf307f7a736e5945e4df023bdb09b6bf (MD5) ecethesis_daifeng.tex: 53700 bytes, checksum: 64420b5c3f16e7a6665f9e881f8ce0dc (MD5) Guo_Daifeng.pdf: 1001024 bytes, checksum: ec85dc30a12f0d051c15b5f6c1df1708 (MD5)","Made available in DSpace on 2014-09-16T17:18:00Z (GMT). No. of bitstreams: 6 Daifeng_Guo.pdf: 1001024 bytes, checksum: ec85dc30a12f0d051c15b5f6c1df1708 (MD5) thesisrefs.bib: 43311 bytes, checksum: c965cf7bca360b49c4ae099775b37f4b (MD5) ack.tex: 72 bytes, checksum: eadd9e0078743e45f263fc0fe082f9eb (MD5) abs.tex: 1057 bytes, checksum: cf307f7a736e5945e4df023bdb09b6bf (MD5) ecethesis_daifeng.tex: 53700 bytes, checksum: 64420b5c3f16e7a6665f9e881f8ce0dc (MD5) license.txt: 4058 bytes, checksum: c3a37295c64d86ba0e0fbab267583223 (MD5)","Embargo set by: Seth Robbins for item 50603 Lift date: 2016-09-16T17:18:17Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 50603 on 2016-09-22T20:59:17Z."],"dc:identifier":["http://hdl.handle.net/2142/50492"],"dc:language":["en"],"dc:rights":["Copyright 2014 Daifeng Guo"],"dc:subject":["E-beam","Stencil Planning","1D Character Placement"],"dc:title":["Polynomial time optimal algorithm for stencil row planning in e-beam lithography"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:40Z"}