WEKO3
アイテム
LSIの配線問題 -DAシンポジウムの配線問題解法コンテスト-：3．SATを用いた解法
https://ipsj.ixsq.nii.ac.jp/records/185699
https://ipsj.ixsq.nii.ac.jp/records/185699032545c6-d735-4c53-b225-dffc064ddbf8
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-MGN590306.pdf (742.6 kB)
|
Copyright (c) 2018 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Magazine(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2018-02-15 | |||||||||
| タイトル | ||||||||||
| タイトル | LSIの配線問題 -DAシンポジウムの配線問題解法コンテスト-：3．SATを用いた解法 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | LSI Routing Problem - Routing Problem Solver Contest at DA Symposium -：3. Problem Solving with SAT Technologies | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | 小特集 | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | article | |||||||||
| 著者所属 | ||||||||||
| 九州大学 | ||||||||||
| 著者所属 | ||||||||||
| 神戸大学 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Kyushu Univ. | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Kobe Univ. | ||||||||||
| 著者名 |
松永, 裕介
× 松永, 裕介
× 田村, 直之
|
|||||||||
| 著者名(英) |
MATSUNAGA, Yusuke
× MATSUNAGA, Yusuke
× TAMURA, Naoyuki
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 本稿ではSATソルバーを用いて配線問題を解く手法について解説を行う．まず，配線問題をグラフ上の経路探索問題と見なし，どの枝が経路として用いられているかを表す命題変数を導入することで，配線問題を命題論理式に変換する．変換された命題論理式がSATソルバーによって充足可能と判定された場合には，充足可能な割り当て結果から1となっている変数に対応する枝を得ることにより最終的な配線結果を得ることができる．SATソルバーを用いた手法は単層の配線問題およびビア付きの多層の配線問題に対しては非常に効率的である．層間を結ぶ配線経路に制約のない一般の多層配線問題に対しては定められた時間内で解を求めることができない場合もありよりよりヒューリスティックの開発が必要である． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN00116625 | |||||||||
| 書誌情報 |
情報処理 巻 59, 号 3, p. 232-238, 発行日 2018-02-15 |
|||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
