分枝限定に基づく最適解を保証するリソースバインディング手法

• Item type: Journal(1)
• 公開日: 1999-04-15
• タイトル: 分枝限定に基づく最適解を保証するリソースバインディング手法
• タイトル / 言語: en
• タイトル: An Optimal Binding Algorithm in High - level Synthesis System for Digital Signal Processing
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：電子システムの設計技術と設計自動化
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 論理合成
• 著者所属: 早稲田大学理工学部電子・情報通信学科
• 著者所属: 早稲田大学理工学部電子・情報通信学科
• 著者所属: 早稲田大学理工学部電子・情報通信学科
• 著者所属: 早稲田大学理工学部電子・情報通信学科
• 著者所属(英): en
• 著者所属(英): Department of Electronics, Information and Communication Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Electronics, Information and Communication Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Electronics, Information and Communication Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Electronics, Information and Communication Engineering, Waseda University
• 著者名: 中本, 真児; 戸川, 望; 柳澤, 政生; 大附, 辰夫
• 著者名(英): Shinji, Nakamoto; Nozomu, Togawa; Masao, Yanagisawa; Tatsuo, Ohtsuki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では ディジタル信号処理ハードウェアのデータパス設計を対象としたリソースバインディング手法を提案する. 提案手法は分枝限定法により 接続コストを最小化するようにデータフローグラフ内の演算を演算器に 演算結果データをレジスタに データ転送をデータ転送路に割り当てる. 提案手法は直接 分枝限定法をリソースバインディング問題に適用したものである. 従来のようにリソースバインディング問題を演算器割当て レジスタ割当て データ転送路割当てに分割することなく 1つの問題として扱うことが可能となり 現実的な時間で最適解を得ることができる. さらに分枝限定法を適用する際に 前処理として発見的手法により解空間を削減し高速に準最適解を算出することができる. 計算機実験により リソースバインディングの典型的な例題に対して数秒から4日程度で最適解を得ることを確認した.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes an optimal resource binding algorithm in the high-level synthesis system for digital signal processing. The algorithm is based on the branch-and-bound method and assigns operations, variables and data transfers in given data-flow graph to functional units, registers and data path so as to minimize the costs for interconnections. Since the branch-and-bound method is directly applied to are source binding problem, the proposed algorithm can provide an optimal solution without dividing the resource binding problem in to three subtasks, such as functional unit, register and data path binding. Moreover, before applying the branch-and-bound method, the algorithm reduces the design space by using a heuristic algorithm, and obtains near-optimal solutions. Experimental results demonstrate effectiveness and efficiency of the algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 40, 号 4, p. 1565-1577, 発行日 1999-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764