| 講演名 | 2007-01-17 FPGA用テクノロジマッピングにおける効率的なカット列挙手法について(FPGAとその応用及び一般) 松永 裕介, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿ではカット列挙を行う効率的なアルゴリズムの提案を行う.他の多くの既存アルゴリズムと異なり,本アルゴリズムはトップダウン型の列挙アルゴリズムに基づいている.カット展開を行う際の終了条件を適切に定めて探索範囲を狭めることでトップダウン型の処理を高速に行っている.実験結果より,本アルゴリズムがほぼ列挙されるカット数に比例した手間で処理を行っていることが示されている.また,実験結果より既存のボトムアップ型アルゴリズムはカット数に比例した手間では処理を行えず,カット列挙の際にファンインのカット数の積に比例した手間を必要としていることも明らかになった.通常,ファンインのカット数の積はオーダーとしてカット数より大きいため,既存のボトムアップアルゴリズムに対して本提案アルゴリズムは計算時間の点で優位であると言える.また,ボトムアップアルゴリズムは列挙したカットを保持しておかなければならないのに対して提案アルゴリズムでは保持する必要がないため,使用メモリ量的にも優位である. |
| 抄録(英) | This paper presents a novel efficient algorithm for cut enumeration. Unlike other existing algorithm, the proposed algorithm is based on the top-down algorithm. Strictly Limiting the search space with the proposed idea of terminate condition of cut expansion makes the top-down algorithm efficient. The experimental results show that the proposed algorithm runs in almost linear time to the number of enumerated cuts. The experimental results also show that the bottom-up algorithm does not run in linear time to the number of enumerated cuts but runs in linear time to the product size of cut merging, which is much larger than the number of enumerated cuts in general. |
| キーワード(和) | テクノロジマッピング / FPGA / カット列挙 |
| キーワード(英) | technology mapping / FPGA / cut enumeration |
| 資料番号 | VLD2006-93,CPSY2006-64,RECONF2006-64 |
| 発行日 |
| 研究会情報 | |
| 研究会 | RECONF |
|---|---|
| 開催期間 | 2007/1/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Reconfigurable Systems (RECONF) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | FPGA用テクノロジマッピングにおける効率的なカット列挙手法について(FPGAとその応用及び一般) |
| サブタイトル（和） | |
| タイトル（英） | On Efficient Cut Enumeration in technology mapping for FPGA |
| サブタイトル（和） | |
| キーワード(1)（和/英） | テクノロジマッピング / technology mapping |
| キーワード(2)（和/英） | FPGA / FPGA |
| キーワード(3)（和/英） | カット列挙 / cut enumeration |
| 第 1 著者 氏名（和/英） | 松永 裕介 / Yusuke MATSUNAGA |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Faculty of Information Science and Electorical Engineering, Graduate School of Kyushu University |
| 発表年月日 | 2007-01-17 |
| 資料番号 | VLD2006-93,CPSY2006-64,RECONF2006-64 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 457 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |