DAGカバリング問題の下限とそれを用いた厳密アルゴリズムについて(検証/最適化,システム設計及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
セルライブラリ用のテクノロジマッピングやFPGA用のテクノロジマッピングはDAGカバリング問題として定式化できることが知られている.しかし,DAGカバリング閥題はNP困難に属することも知られており,現在のところ,効率のよい厳密アルゴリズムは存在しない。本稿では与えられたDAGを木状グラフに変形することで,DAGカバリング問題の下限を求める手法を提案する.さらにこの下限の計算法の応用としてDAGカバリングの近似解法および厳密解法について延べる.ベンチマーク回路を用いた実験では2入力ゲート換算で数百ゲート規模の回路の場合には厳密解が数秒から数千秒で求められることを確認した.
- 2007-05-04
著者
関連論文
- 部分一括描画装置の処理能力向上のための描画面積最適化(計算機システム化技術,システムLSI設計とその技術)
- マルチプレクサの削減を目的としたバインディング改善手法(合成及び演算器最適化,システム設計及び一般)
- マルチプレクサの削減を目的としたバインディング改善手法(システム設計及び一般)
- DAGカバリング問題の下限とそれを用いた厳密アルゴリズムについて(システム設計及び一般)
- DAGカバリング問題の下限とそれを用いた厳密アルゴリズムについて(検証/最適化,システム設計及び一般)
- FPGA向けテクノロジ・マッピングにおける深さ最小ネットワーク生成のための効率的なカット列挙手法(FPGA実装設計,FPGA応用及び一般)
- 順序回路のタイミング例外パス検出のための実用的方法(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- 順序回路のタイミング例外パス検出のための実用的方法(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 信号線間の含意関係に着目したフォールスパス検出手法(VLSIの設計/検証/テスト及び一般論理合成及び高位合成)
- 信号線間の含意関係に着目したフォールスパス検出手法(VLSIの設計/検証/テスト及び一般 論理合成及び高位合成)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 信号線間の含意関係に着目したフォールスパス検出手法
- LUT型FPGAを対象とした消費電力および遅延の見積もり手法について(デザインガアイ2006-VLSI設計の新しい大地を考える研究会)
- LUT型FPGAを対象とした消費電力および遅延の見積もり手法について(高速化/低消費電力化II,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- セルベース設計に適したSER評価の為のパルス発生確率解析手法(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- 消費電力を考慮したprefix graph合成手法について(システム設計及び一般)
- 消費電力を考慮したprefix graph合成手法について(算術演算回路,システム設計及び一般)
- キャリーチェインを用いたマルチオペランド加算器のFPGA向け低電力合成手法
- AI-1-6 ディペンダブルVLSI設計技術への挑戦(AI-1.デイベンダブルVLSIに向けて,依頼シンポジウム,ソサイエティ企画)
- ソフトエラーに起因するパルスのラッチ確率のモデル化(ディペンダブル設計,物理設計及び一般)
- 順序回路のソフトエラー耐性評価手法の状態数削減による高速化(システム設計・高位論理設計,システムオンシリコンを支える設計技術)
- 算術演算器を含む回路に対する高速なソフトエラー率評価手法(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- 算術演算器を含む回路に対する高速なソフトエラー率評価手法(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- キャラクタプロジェクション法のためのセルライブラリ開発手法(プロセッサ, DSP, 画像処理技術及び一般)
- キャラクタプロジェクション法のためのセルライブラリ開発手法(プロセッサ, DSP, 画像処理技術及び一般)
- キャラクタプロジェクション法のためのセルライブラリ開発手法(プロセッサ, DSP, 画像処理技術及び一般)
- キャラクタプロジェクション法のためのセルライブラリ開発手法(プロセッサ, DSP, 画像処理技術及び一般)
- 順序回路のソフトエラー耐性評価における高精度な近似評価手法(ディペンダブル設計,システム設計及び一般)
- 有限状態機械の分割に基づく定常状態確率の近似計算手法(ディペンダブル設計,システム設計及び一般)
- 順序回路のソフトエラー耐性評価における近似手法の計算精度および実行時間の評価(ディペンダブル設計,デザインガイア2009-VLSI設計の新しい大地)
- 順序回路のソフトエラー耐性評価における近似手法の計算精度および実行時間の評価(ディペンダブル設計,デザインガイア2009-VLSI設計の新しい大地-)
- SER評価のための論理回路におけるパルスの伝搬解析(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- セルベース設計に適したSER評価の為のパルス発生確率解析手法(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- SER評価のための論理回路におけるパルスの伝搬解析(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- テスト生成における間接含意の効率的な生成方法(テスト,システム設計及び一般)
- テスト生成における間接含意の効率的な生成方法(テスト,システム設計及び一般)
- プログラマブルコントローラ向けプロセッサ・アーキテクチャの評価(専用システム)
- プログラマブルコントローラ向けアーキテクチャの検討と評価
- プログラマブルコントローラ向けアーキテクテャの検討と評価(プロセッサ)
- FPGAを対象とした部分積加算回路の合成について(プロセッサ,システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- FPGAを対象とした部分積加算回路の合成について(プロセッサ,システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- FPGAを対象とした部分積加算回路の合成について(プロセッサ,システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- キャリーチェインを用いたマルチオペランド加算器のFPGA向け低電力合成手法 (リコンフィギャラブルシステム)
- キャリーチェインを用いたマルチオペランド加算器のFPGA向け低電力合成手法 (コンピュータシステム)
- キャリーチェインを用いたマルチオペランド加算器のFPGA向け低電力合成手法 (VLSI設計技術)
- イニシエーション・インターバルとアロケーションの制約下における総面積最小を目的としたパイプライン・スケジューリング手法(高位・論理合成,システムオンシリコンを支える設計技術)
- スイッチング確率を考慮したprefix graph合成手法の改良について(合成及び演算器最適化,システム設計及び一般)
- スイッチング確率を考慮したprefix graph合成手法の改良について(システム設計及び一般)
- Lingのキャリー計算に基づくparallel prefix adder合成について(論理・レイアウト最適化,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- Lingのキャリー計算に基づくparallel prefix adder合成について(論理・レイアウト最適化,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- Lingのキャリー計算に基づくparallel prefix adder合成について(論理・レイアウト最適化,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- フレックスマージ : LUT数削減を目的としたLUT型FPGA向け論理最適化手法(論理設計,デザインガイア2009-VLSI設計の新しい大地)
- フレックスマージ:LUT数削減を目的としたLUT型FPGA向け論理最適化手法(論理設計,デザインガイア2009-VLSI設計の新しい大地-)
- A-35 論理回路の最大遅延分布の下限を与える正規分布(最適化,A.アルゴリズム・基礎)
- AT-1-6 ソフトエラー耐性を考慮したEDA技術(AT-1.集積回路におけるソフトエラー-測定法,回路技術,EDA-,チュートリアルセッション,ソサイエティ企画)
- 順序回路のソフトエラー率解析手法の非明示的列挙による高速化について(システム・論理設計技術,物理設計及び一般)
- 順序回路のタイミング例外パス検出のための実用的方法(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 順序回路のタイミング例外パス検出のための実用的方法(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 信号線間の含意関係に着目したフォールスパス検出手法(VLSIの設計/検証/テスト及び一般 論理合成及び高位合成)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 信号線間の含意関係に着目したフォールスパス検出手法(VLSIの設計/検証/テスト及び一般 論理合成及び高位合成)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- キャラクタプロジェクション法における描画面積の最適化による描画時間の削減(組込技術とネットワークに関するワークショップETNET2006)
- キャラクタプロジェクション法における描画面積の最適化による描画時間の削減(組込技術とネットワークに関するワークショップETNET2006)
- キャラクタプロジェクション法における描画面積の最適化による描画時間の削減(組込技術とネットワークに関するワークショップETNET2006)
- Parallel prefix adder合成を用いた乗算器の最適化手法について (第20回 回路とシステム軽井沢ワークショップ論文集) -- (演算器設計)
- FPGA向けテクノロジ・マッピングにおける深さ最小ネットワーク生成のための効率的なカット列挙手法(FPGA実装設計,FPGA応用及び一般)
- FPGA向けテクノロジ・マッピングにおける深さ最小ネットワーク生成のための効率的なカット列挙手法(FPGA実装設計,FPGA応用及び一般)
- FPGA向けテクノロジ・マッピングにおける深さ最小ネットワーク生成のための効率的なカット列挙手法(FPGA実装設計,FPGA応用及び一般)
- LUT型FPGA向けテクノロジ・マッピングにおける深さ制約下のLUT数削減手法(FPGA/設計事例,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- LUT型FPGA向けテクノロジ・マッピングにおける深さ制約下のLUT数削減手法(FPGA/設計事例,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- LUT型FPGA向けテクノロジ・マッピングにおける深さ制約下のLUT数削減手法(FPGA/設計事例,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- LUT段数最小かつ個数極小なLUT型FPGA向けテクノロジ・マッピング(デザインガアイ2006-VLSI設計の新しい大地を考える研究会)
- LUT段数最小かつ個数極小なLUT型FPGA向けテクノロジ・マッピング(論理・回路設計,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- LUT段数最小かつ個数極小なLUT型FPGA向けテクノロジ・マッピング(論理・回路設計,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- LUT型FPGAを対象とした消費電力および遅延の見積もり手法について(高速化/低消費電力化II,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 一般化並列カウンタを用いたマルチオペランド加算器合成問題のILPによる定式化 (VLSI設計技術)
- 最大の可観測性ドントケア集合の抽出におけるCODCを用いた近似手法(VLSI設計技術,FPGA応用及び一般)
- 最大の可観測性ドントケア集合の抽出におけるCODCを用いた近似手法(VLSI設計技術,FPGA応用及び一般)
- 最大の可観測性ドントケア集合の抽出におけるCODCを用いた近似手法(VLSI設計技術,FPGA応用及び一般)
- 組み合わせ回路のソフトエラー耐性評価における近似手法の統計科学的な精度評価 (VLSI設計技術)
- Prefix graphにおける遅延時間の見積もり手法について(VLSIの設計/検証/テスト及び一般(デザインガイア))
- Prefix graphにおける遅延時間の見積もり手法について(VLSIの設計/検証/テスト及び一般(デザインガイア))
- Prefix graphにおける遅延時間の見積もり手法について(VLSIの設計/検証/テスト及び一般(デザインガイア))
- Prefix graphにおける遅延時間の見積もり手法について(VLSIの設計/検証/テスト及び一般(デザインガイア))
- コンテクストを考慮したparallel prefix adder合成手法(システムLSI設計及び一般)
- コンテクストを考慮したparallel prefix adder合成手法(システムLSI設計及び一般)
- 組み合わせ論理回路におけるソフトエラーの論理マスク効果の正確な見積り手法について(プロセッサ,システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- 組み合わせ論理回路におけるソフトエラーの論理マスク効果の正確な見積り手法について(プロセッサ,システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- 組み合わせ論理回路におけるソフトエラーの論理マスク効果の正確な見積り手法について(プロセッサ,システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- FPGA向け動作合成におけるメモリバインディングとスケジューリングアルゴリズムについて(ICCAD報告と動作合成)
- ICCAD報告(ICCAD報告と動作合成)
- FPGA向け動作合成におけるメモリバインディングとスケジューリングアルゴリズムについて(ICCAD報告と動作合成,FPGA応用及び一般)
- ICCAD報告(ICCAD報告と動作合成,FPGA応用及び一般)
- FPGA向け動作合成におけるメモリバインディングとスケジューリングアルゴリズムについて(ICCAD報告と動作合成,FPGA応用及び一般)
- ICCAD報告(ICCAD報告と動作合成,FPGA応用及び一般)
- FPGA向け動作合成におけるメモリバインディングとスケジューリングアルゴリズムについて(ICCAD報告と動作合成,FPGA応用及び一般)
- ICCAD報告(ICCAD報告と動作合成,FPGA応用及び一般)
- 専用演算器の使用を考慮した効率的な動作合成手法(論理・レイアウト最適化,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 専用演算器の使用を考慮した効率的な動作合成手法(論理・レイアウト最適化,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 専用演算器の使用を考慮した効率的な動作合成手法(論理・レイアウト最適化,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 専用演算器と演算のチュイニングのトレードオフを考慮した動作合成手法 (第20回 回路とシステム軽井沢ワークショップ論文集) -- (高位合成)
- チェイニングを考慮した動作合成手法(設計・合成, 組込技術とネットワークに関するワークショップ)