WEKO3
アイテム
折れ曲がり制約を含む配線問題のNP完全性
https://ipsj.ixsq.nii.ac.jp/records/141653
https://ipsj.ixsq.nii.ac.jp/records/14165385558794-f88f-4ce3-be16-803cd45781a1
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-SLDM15171003.pdf (1.3 MB)
2100年1月1日からダウンロード可能です。
|
Copyright (c) 2015 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.
|
|
| SLDM:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2015-05-07 | |||||||||
| タイトル | ||||||||||
| タイトル | 折れ曲がり制約を含む配線問題のNP完全性 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | NP-completeness of Routing Problem with Bend Constraint | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | レイアウト・テスト | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 東京工業大学大学院理工学研究科通信情報工学専攻 | ||||||||||
| 著者所属 | ||||||||||
| 東京工業大学大学院理工学研究科通信情報工学専攻 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Department of Communications and Computer Engineering, Tokyo Institute of Technology | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Department of Communications and Computer Engineering, Tokyo Institute of Technology | ||||||||||
| 著者名 |
本江, 俊幸
× 本江, 俊幸
× 高橋, 篤司
|
|||||||||
| 著者名(英) |
Toshiyuki, Hongo
× Toshiyuki, Hongo
× Atsushi, Takahashi
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 次世代リソグラフイ技術の 1 つである側壁プロセスを 2 回用いる SAQP(Self-Aligned Quadruple Patterning) は微細な配線パターンを実現する有望な技術の 1 つであるが，すべての配線パターンを実現できるわけではない．そこで，SAQP で実現可能な配線パターンを生成するために，特殊な 3 色グリッドを用いる配線パターン生成手法が提案されたその生成手法では，配線は SAQＰ の製造工程に応じて 3 種類に分類される．最終工程に対応する配線は，分岐は許されず，さらに折れ曲がりが禁止されるグリッドが存在する．そのため，最終工程に対応する配線パターンを生成するために，3 色グリッドに対応するグラフ上で折れ曲がり制約を満たす 2 点間のパスを求めるアルゴリズムが必要となる．本稿では，グラフ上に折れ曲がり制約が与えられたとき，一般に，2 点間に折れ曲がり制約を満たすパスが存在するか否かの判定問題は NP 完全であることを示す． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Self-Aligned Quadruple Patterning (SAQP) in which side-wall process is repeated twice is an important manufacturing technique to realize tiny routing pattern in next generation lithography, however, every routing pattern is not realized. In order to obtain SAQP feasible routing patterns, a routing pattern generation method in which a special 3-color grid is used was proposed. In the routing pattern generation method, routing is classified into three according to the manufacturing process of SAQP. Among them, routing corresponding to the last manufacturing process neither allow to branch off nor to bend at several grids. Therefore, an algorithm that obtains a path between two vertices that satisfies bend constraint is required to obtain a routing that corresponds to the last manufacturing process. In this paper, the problem deciding whether there exists a path that satisfies the bend constraint is proved to be NP-complete in general. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA11451459 | |||||||||
| 書誌情報 |
研究報告システムとLSIの設計技術（SLDM） 巻 2015-SLDM-171, 号 3, p. 1-6, 発行日 2015-05-07 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8639 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
