| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2023-11-17 14:50 集合対間配線問題に対するSATを用いた配線手法の改良 ○長倉光輝・藤吉邦洋（東京農工大）  VLD2023-77 ICD2023-85 DC2023-84 RECONF2023-80 |
|
| 抄録 | （和） | 集合対間配線問題とは，同数のソース端子とシンク端子が与えられ，これらの端子間を任意の組合せで1対1接続する単層配線問題である． 集合対間配線では端子間の配線長やその差を小さくすることが求められる． この配線はプリント基板上のバス配線やエスケープ配線の部分問題として現れる． この問題の最適解を求める手法として，整数線形計画問題（ILP）ソルバを用いた手法と充足可能性問題（SAT）ソルバを用いた手法が提案されている． しかし，従来のSATソルバを用いた手法では，配線長の制御のために用いる制約が膨大で，配線領域が大きい場合にはメモリ不足で解けなかった． そこで，今回の研究では配線領域が大きい問題でも解けるように，従来のSATソルバを用いた集合対間配線の改良手法を提案する． |
| （英） | 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. |
|
| キーワード | （和） | 集合対間配線問題 / PCB / SAT / / / / / |
| （英） | Set-Pair Routing Problem / SAT / / / / / / | |
| 文献情報 | 信学技報, vol. 123, no. 258, VLD2023-77, pp. 243-248, 2023年11月. | |
| 資料番号 | VLD2023-77 | |
| 発行日 | 2023-11-08 (VLD, ICD, DC, RECONF) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | VLD2023-77 ICD2023-85 DC2023-84 RECONF2023-80 |
|
| 研究会情報 | |
| 研究会 | VLD DC RECONF ICD IPSJ-SLDM |
| 開催期間 | 2023-11-15 - 2023-11-17 |
| 開催地（和） | くまもと市民会館シアーズホーム夢ホール |
| 開催地（英） | Civic Auditorium Sears Home Yume Hall |
| テーマ（和） | デザインガイア2023 -VLSI設計の新しい大地- |
| テーマ（英） | Design Gaia 2023 -New Field of VLSI Design- |
| 講演論文情報の詳細 | |
| 申込み研究会 | VLD |
| 会議コード | 2023-11-VLD-DC-RECONF-ICD-SLDM |
| 本文の言語 | 日本語 |
| タイトル（和） | 集合対間配線問題に対するSATを用いた配線手法の改良 |
| サブタイトル（和） | |
| タイトル（英） | An Improved Routing Method by SAT for Set-Pair Routing Problem |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 集合対間配線問題 / Set-Pair Routing Problem |
| キーワード(2)（和/英） | PCB / SAT |
| キーワード(3)（和/英） | SAT / |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 長倉 光輝 / Koki Nagakura / ナガクラ コウキ |
| 第1著者 所属（和/英） | 東京農工大学 (略称： 東京農工大) okyo University of Agriculture and Technology (略称： TUAT) |
| 第2著者 氏名（和/英/ヨミ） | 藤吉 邦洋 / Kunihiro Fujiyoshi / フジヨシ クニヒロ |
| 第2著者 所属（和/英） | 東京農工大学 (略称： 東京農工大) okyo University of Agriculture and Technology (略称： TUAT) |
| 講演者 | 第1著者 |
| 発表日時 | 2023-11-17 14:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | VLD |
| 資料番号 | VLD2023-77, ICD2023-85, DC2023-84, RECONF2023-80 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.258(VLD), no.259(ICD), no.260(DC), no.261(RECONF) |
| ページ範囲 | pp.243-248 |
| ページ数 | 6 |
| 発行日 | 2023-11-08 (VLD, ICD, DC, RECONF) |
[研究会発表申込システムのトップページに戻る]