| Item type |
SIG Technical Reports(1) |
| 公開日 |
2023-11-10 |
| タイトル |
|
|
タイトル |
集合対間配線問題に対するSATを用いた配線手法の改良 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
An Improved Routing Method by SAT for Set-Pair Routing Problem |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
アルゴリズム，VLSI試作・実用化 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
東京農工大学大学院工学府電気電子工学専攻 |
| 著者所属 |
|
|
|
東京農工大学大学院工学府電気電子工学専攻 |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Electrical and Electronic Engineering, Tokyo Univercity of Agriculture and Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Electrical and Electronic Engineering, Tokyo Univercity of Agriculture and Technology |
| 著者名 |
長倉, 光輝
藤吉, 邦洋
|
| 著者名(英) |
Koki, Nagakura
Kunihiro, Fujiyoshi
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
集合対間配線問題とは，同数のソース端子とシンク端子が与えられ，これらの端子間を任意の組合せで 1 対 1 接続する単層配線問題である．集合対間配線では端子間の配線長やその差を小さくすることが求められる．この配線はプリント基板上のバス配線やエスケープ配線の部分問題として現れる．この問題の最適解を求める手法として，整数線形計画問題（ILP）ソルバを用いた手法と充足可能性問題（SAT）ソルバを用いた手法が提案されている．しかし，従来の SAT ソルバを用いた手法では，配線長の制御のために用いる制約が膨大で，配線領域が大きい場合にはメモリ不足で解けなかった．そこで，本研究では配線領域が大きい問題でも解けるように，従来の SAT ソルバを用いた集合対間配線の改良手法を提案する． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
A set-pair routing problem is a single-layer routing problem in which combinations of these pins to be connected by routing is flexible. The problem requires routing in which minimum the longest routing length and the length difference. The set-pair routing appears partially in a printed circuit board (PCB). In addition, several methods have been proposed to find a suboptimal routing solution by using flow graph. Furthermore, two methods have been proposed for finding the optimal routing solution to this problem, one using the integer linear programming (ILP) solver and the other using the satisfiability problem (SAT) solver. However, the conventional method using the SAT solver has a huge number of constraints used to control the routing length, and when the routing area is large, it cannot be solved due to insufficient memory. Therefore, this paper presents an improved routing method for a set-pair routing problem using the SAT solver to solve problems with large routing areas. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11451459 |
| 書誌情報 |
研究報告システムとLSIの設計技術（SLDM）
巻 2023-SLDM-204,
号 50,
p. 1-6,
発行日 2023-11-10
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8639 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-SLDM23204050.pdf (1.2 MB)
