| Item type |
Symposium(1) |
| 公開日 |
2023-08-23 |
| タイトル |
|
|
タイトル |
トップダウンZDD構築法を用いたDSPブロック向けテクノロジマッピング最適解全列挙アルゴリズム |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Algorithm for Enumerating All Optimal Solutions of DSP Block Mapping Utilizing Top-down ZDD Construction |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
回路設計支援 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_5794 |
|
資源タイプ |
conference paper |
| 著者所属 |
|
|
|
立命館大学大学院情報理工学研究科 |
| 著者所属 |
|
|
|
明治大学理工学部 |
| 著者所属 |
|
|
|
立命館大学大学院情報理工学研究科 |
| 著者所属(英) |
|
|
|
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 |
| 著者名 |
芹澤, 拓也
今川, 隆司
越智, 裕之
|
| 著者名(英) |
Takuya, Serizawa
Takashi, Imagawa
Hiroyuki, Ochi
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本論文では，与えられたデータフローグラフを FPGA の DSP ブロックにテクノロジマッピングする際の全最適解を求めるアルゴリズムを提案する．柴田らが提案した DSP ブロックマッピングのための網羅的な深さ優先探索アルゴリズムは解の最適性を保証し，かつ高速であるが，最適解を 1 つしか求めることができず，枝刈りやグラフ分割などのアルゴリズムも複雑であった．提案アルゴリズムは，最適解から冗長な解まで全ての解を表現する ZDD をトップダウン ZDD 構築法で高速に生成し，その後 DSP 数を制約として絞り込みを行うことで全最適解を列挙する手法であり，様々な DSP ブロックや解の評価指標に容易に対応できると考えられる． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
This paper proposes an algorithm to enumerate all the exact-optimal technology mapping solutions of a given data flow graph for DSP blocks of FPGAs. The exhaustive depth-first search algorithm for DSP block mapping by Shibata et al. guarantees optimality and runs efficiently. However, it can find only one solution and uses several complicated pruning and graph partitioning rules to speed up. The proposed algorithm first constructs speedily a ZDD representing all mapping solutions, including optimal and redundant ones, then enumerates only all exact-optimal solutions by reconstructing the ZDD using the number of DSPs as a constraint. This method is expected to apply to various DSP blocks and optimization metrics flexibly. |
| 書誌情報 |
DAシンポジウム2023論文集
巻 2023,
p. 97-103,
発行日 2023-08-23
|
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-DAS2023016.pdf (2.0 MB)
