WEKO3
アイテム
FPGAを模したナンバーリンク問題の解の数と配線自由度の関係について
https://ipsj.ixsq.nii.ac.jp/records/238245
https://ipsj.ixsq.nii.ac.jp/records/238245c7b62cd3-47e9-4997-9c0d-1b3740ff3970
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-DAS2024021.pdf (3.8 MB)
2026年8月21日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, SLDM:会員：¥0, DLIB:会員：¥0 | ||
| Item type | Symposium(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-08-21 | |||||||||
| タイトル | ||||||||||
| タイトル | FPGAを模したナンバーリンク問題の解の数と配線自由度の関係について | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | On the Solution Count of the Modified Numberlink Problem Modeled after FPGAs and its Relation to the Routing Capacity | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | 設計支援 | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||
| 資源タイプ | conference paper | |||||||||
| 著者所属 | ||||||||||
| 立命館大学大学院情報理工学研究科 | ||||||||||
| 著者所属 | ||||||||||
| 立命館大学大学院情報理工学研究科 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Graduate School of Information Science and Engineering, Ritsumeikan University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Graduate School of Information Science and Engineering, Ritsumeikan University | ||||||||||
| 著者名 |
小味, 燎平
× 小味, 燎平
× 越智, 裕之
|
|||||||||
| 著者名(英) |
Ryohei, Komi
× Ryohei, Komi
× Hiroyuki, Ochi
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 本稿では，黎明期の SRAM 型 FPGA の配線構造を模したナンバーリンク問題を定義し，その解の数による FPGA の配線アーキテクチャの定量的評価の可能性を検討する．ナンバーリンク問題の解を全列挙する既存手法としてトップダウン ZDD 構築法 (TdZdd) を用いたものがあるが，これは格子状盤面に対する平面配線問題に特化されている．本研究では縦横の配線の交差を許容する実際の FPGA を模した盤面を対象とするよう，TdZdd を用いたアルゴリズムを拡張した．これを用い，PIP 内のパストランジスタを間引いた場合の解の総数や総配線長の最小値の変化を求め，これらの指標が FPGA の配線自由度を表すことを示唆する結果を得た． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | In this paper, we define a modified numberlink problem that mimics the routing architecture of SRAM FPGAs in their early days to investigate the possibility of quantitative evaluation of FPGA routing architecture using its number of solutions. An existing method for enumerating all solutions to the numberlink problem has been proposed based on the top-down ZDD construction method (TdZdd), which is efficient since it is specialized for single-layer orthogonal routing problems. In this study, we extend the TdZdd-based algorithm to target an actual FPGA-like board that allows intersections of vertical and horizontal paths. Using this, we obtained the total number of solutions and the minimum value of total path length when pass-transistors in the PIPs are depopulated, which suggests that these indices represent the routing capability of FPGAs. | |||||||||
| 書誌情報 |
DAシンポジウム2024論文集 巻 2024, p. 134-141, 発行日 2024-08-21 |
|||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
