| 講演名 | 2015-10-06 可変成形型電子ビーム露光装置のためのサイズ上限を考慮した矩形分割手法 長谷川 充(東京農工大), 藤吉 邦洋(東京農工大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | LSIのマスク製造に広く用いられている可変成形型電子ビーム露光装置は矩形に成形した電子ビームを照射するため、入力であるレイアウト上のレクトリニア多角形を、指定された大きさ以下で出来るだけ少ない数の矩形の集合に分割する処理が必要となる。この問題に対して、Kahngらは整数線形計画法を用いた手法と発見的な手法を提案したが、超多項式の計算時間がかかったり、単純な問題でも最小数の矩形に分割できない場合がある。そこで本稿では、レクトリニア多角形を指定された大きさ以下で最小数の矩形に分割することを多項式時間でどこまでできるのかを明らかにすることを目的とし、レクトリニア凸多角形の凹頂点を通るスライス分割線優先で再帰的に分割するという方針のもと、動的計画法を用いた分割手法を提案する。そして、レクトリニア凸多角形の分割がその頂点数に対して多項式の時間にてできることを示し、計算機実験によりその動作を確認する。 |
| 抄録(英) | Since variable shaped-beam mask writing machines for LSI mask production can expose a rectangle shaped-beam, we need to partition rectilinear polygons in layout into a set of rectangles of the minimum number with considering size limit. For this problem, Kahng proposed an ILP method and a heuristic method. However, the former needs super-polynomial time and the latter may not obtain the optimum solution. In this paper, we propose a new fracturing method for convex rectilinear polygons using dynamic programming, which cut each polygon by slicing-lines through concave vertices firstly. The proposed method can solve the problem in polynomial time though it uses $O(n^4)$ memories in the worst case. Computer experiments confirm the space and time complexity of the method. |
| キーワード(和) | 多角形分割 / EB露光装置 / マスクデータ / 動的計画法 |
| キーワード(英) | Polygon Fracturing / EB writing / mask data / Dynamic Programming |
| 資料番号 | CAS2015-34,NLP2015-95 |
| 発行日 | 2015-09-28 (CAS, NLP) |
| 研究会情報 | |
| 研究会 | NLP / CAS |
|---|---|
| 開催期間 | 2015/10/5(から2日開催) |
| 開催地（和） | アステールプラザ（広島市） |
| 開催地（英） | Aster Plaza |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 神野 健哉(日本工大) / 田中 聡(村田製作所) |
| 委員長氏名（英） | Kenya Jinno(Nippon Inst. of Tech.) / Satoshi Tanaka(Murata) |
| 副委員長氏名（和） | 藤坂 尚登(広島市大) / 高橋 俊彦(新潟大) |
| 副委員長氏名（英） | Naoto Fujisaka(Hiroshima City Univ.) / Toshihiko Takahashi(Niigata Univ.) |
| 幹事氏名（和） | 長谷川 幹雄(東京理科大) / 和田 昌浩(甲南大) / 山脇 大造(日立) / 越田 俊介(東北大) |
| 幹事氏名（英） | Mikio Hasegawa(Tokyo Univ. of Science) / Masahiro Wada(Konan Univ.) / Taizou Yamawaki(Hitachi) / Shunsuke Koshita(Tohoku Univ.) |
| 幹事補佐氏名（和） | 中野 秀洋(東京都市大) / 麻原 寛之(福岡大) / 橘 俊宏(湘南工科大) / 中村 洋平(日立) |
| 幹事補佐氏名（英） | Hidehiro Nakano(Tokyo City Univ.) / Hiroyuki Asahara(Fukuoka Univ.) / Toshihiro Tachibana(Shonan Inst. of Tech.) / Yohei Nakamura(Hitachi) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Nonlinear Problems / Technical Committee on Circuits and Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 可変成形型電子ビーム露光装置のためのサイズ上限を考慮した矩形分割手法 |
| サブタイトル（和） | |
| タイトル（英） | Polygon Fracture Method Considering Maximum Shot Size for Variable Shaped-Beam Mask Writing |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 多角形分割 / Polygon Fracturing |
| キーワード(2)（和/英） | EB露光装置 / EB writing |
| キーワード(3)（和/英） | マスクデータ / mask data |
| キーワード(4)（和/英） | 動的計画法 / Dynamic Programming |
| 第 1 著者 氏名（和/英） | 長谷川 充 / Mitsuru Hasegawa |
| 第 1 著者 所属（和/英） | 東京農工大学(略称：東京農工大) Tokyo University of Agriculture and Technology(略称：TUAT) |
| 第 2 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro Fujiyoshi |
| 第 2 著者 所属（和/英） | 東京農工大学(略称：東京農工大) Tokyo University of Agriculture and Technology(略称：TUAT) |
| 発表年月日 | 2015-10-06 |
| 資料番号 | CAS2015-34,NLP2015-95 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | CAS-239,NLP-240 |
| ページ範囲 | pp.69-74(CAS), pp.69-74(NLP), |
| ページ数 | 6 |
| 発行日 | 2015-09-28 (CAS, NLP) |