WEKO3
アイテム
トップダウンZDD構築法を用いた多端子ナンバーリンク問題の全解探索アルゴリズムの改良
https://ipsj.ixsq.nii.ac.jp/records/240472
https://ipsj.ixsq.nii.ac.jp/records/24047217e4f3e1-6454-47d1-acb5-bfdedfbb363f
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-SLDM24206005.pdf (1.3 MB)
2026年10月31日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, SLDM:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-10-31 | |||||||||||
| タイトル | ||||||||||||
| タイトル | トップダウンZDD構築法を用いた多端子ナンバーリンク問題の全解探索アルゴリズムの改良 | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | ポスター | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 立命館大学大学院情報理工学研究科 | ||||||||||||
| 著者所属 | ||||||||||||
| 明治大学理工学部 | ||||||||||||
| 著者所属 | ||||||||||||
| 立命館大学大学院情報理工学研究科 | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Graduate School of Information Science and Engineering, Ritsumeikan University | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| School of Science and Technology, Meiji University | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Graduate School of Information Science and Engineering, Ritsumeikan University | ||||||||||||
| 著者名 |
李, 宣岐
× 李, 宣岐
× 今川, 隆司
× 越智, 裕之
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | 本稿では，従来の 2 端子のナンバーリンクの拡張問題である多端子ナンバーリンクを対象とし，その全ての解を列挙するアルゴリズムを改良する．ナンバーリンクは理論的には NP 完全問題であり，実際には VLSI および PCB の平面配線を模倣しているため，これを解くための様々なアルゴリズムが開発されている．トップダウン ZDD 構築法を用いた既存手法により，ナンバーリンクの全ての解を効率的に列挙でき，これによって得られるナンバーリンクの解の個数は配線の代替経路の多さを表していると考えられ，FPGA 等の配線アーキテクチャの配線自由度などの評価指標としての利用が期待される．しかしこの ZDD ベースのアルゴリズムは，各ネットがちょうど 2 つの端子を持つというナンバーリンクの前提に特化されており，実際の配線対象となる回路とは乖離している．我々はマルチファンアウトのネットを配線できる，多端子ナンバーリンク用に拡張した ZDD ベースのアルゴリズムを提案したが，これを 2 端子のナンバーリンクに適用した時のオーバヘッドが大きいことが課題であった．本稿はこれを改善するため，総分岐数超過の検出を導入する． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AA11451459 | |||||||||||
| 書誌情報 |
研究報告システムとLSIの設計技術（SLDM） 巻 2024-SLDM-206, 号 5, p. 1-6, 発行日 2024-10-31 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-8639 | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
