| 講演名 | 2007/5/4 DAGカバリング問題の下限とそれを用いた厳密アルゴリズムについて(検証/最適化,システム設計及び一般) 松永 裕介, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | セルライブラリ用のテクノロジマッピングやFPGA用のテクノロジマッピングはDAGカバリング問題として定式化できることが知られている.しかし,DAGカバリング閥題はNP困難に属することも知られており,現在のところ,効率のよい厳密アルゴリズムは存在しない。本稿では与えられたDAGを木状グラフに変形することで,DAGカバリング問題の下限を求める手法を提案する.さらにこの下限の計算法の応用としてDAGカバリングの近似解法および厳密解法について延べる.ベンチマーク回路を用いた実験では2入力ゲート換算で数百ゲート規模の回路の場合には厳密解が数秒から数千秒で求められることを確認した. |
| 抄録(英) | Technology mapping with cell libraries or FPGAs can be formulated as DAG covering problem, which is known to be NP-hard. So far, no efficient algorithms exist to solve it exactly. This paper proposes novel methods to compute the lower bound for DAG covering problem by transforming a DAG into a tree graph. A heuristic algorithm as well as an exact algorithm are also described using these lower bounds. The experiments with benchmark circuits show the effectiveness of the proposed methods. For several circuits with handreds gates, the proposed algorithm find the exact minimum solutions within seconds to thousands seconds. |
| キーワード(和) | DAGカバリング / テクノロジマッピング / FPGA |
| キーワード(英) | DAG covering / technology mapping / FPGA |
| 資料番号 | VD2007-8 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2007/5/4(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | DAGカバリング問題の下限とそれを用いた厳密アルゴリズムについて(検証/最適化,システム設計及び一般) |
| サブタイトル（和） | |
| タイトル（英） | On lower bounds for DAG covering problem and their application to the exact algorithm |
| サブタイトル（和） | |
| キーワード(1)（和/英） | DAGカバリング / DAG covering |
| キーワード(2)（和/英） | テクノロジマッピング / technology mapping |
| キーワード(3)（和/英） | FPGA / FPGA |
| 第 1 著者 氏名（和/英） | 松永 裕介 / Yusuke MATSUNAGA |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Faculty of Information Science and Electorical Engineering, Graduate School of Kyushu University |
| 発表年月日 | 2007/5/4 |
| 資料番号 | VD2007-8 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 32 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |