2分決定グラフのための変数順決定アルゴリズムとその評価
スポンサーリンク
概要
- 論文の詳細を見る
Bryantは論理関数を効率的に処理する手法として,場合分けの変数順をすべてのパスで固定した2分決定グラフ(BDD)を提案し,BDDの効率的な演算アルゴリズムを示した.64ビットのALUが表現できる等.BDDは従来の論理関数表現手段と比べ,極めて強力であることが示されたが,場合分けの変数l頂によって,BDDの大きさが大きく変化するという問題点がある・そこで本稿では,BDDの変数順についての各種実験結果と,それらから得られた変数順決定アルゴリズムについて述べる.まず,ベンチマーク回路に対する実験結果から,人が描く回路図上に現れる変数を上から順に順序付けしたものが極めてよい結果をもたらすことを示す.次に,これの根拠となる定理を幾つか示し,それらの定理に基づく変数順決定アルゴリズムとその評価を示す.この変数順決定アルゴリズムは回路図から得られる順よりもよい結果をもたらし,100入力,3,000ゲート以上の回路をBDDで表現できるようになった.
- 一般社団法人情報処理学会の論文
- 1990-04-15
著者
-
藤田 昌宏
富士通研究所人工知能研究部
-
松永 裕介
(株)富士通研究所 CAD 研究部
-
藤沢 久典
富士通研
-
藤田 昌宏
(株)富士通研究所
-
角田 多苗子
(株)富士通研究所
-
藤沢 久典
(株)富士通研究所
-
藤田 昌宏
富士通研
-
藤田 昌宏
東京大学、大規模集積システム設計教育研究センター
-
藤田 昌宏
東京大学大規模集積システム設計教育研究センター|科学技術振興機構戦略的創造研究推進事業crest
-
松永 裕介
(株)富士通研究所
関連論文
- 動的パッチ読み出し機構を備えた製造後機能修正可能アクセラレータ (画像工学)
- 動的パッチ読み出し機構を備えた製造後機能修正可能アクセラレータ (集積回路)
- 動的パッチ読み出し機構を備えた製造後機能修正可能アクセラレータ (信号処理)
- 状態変数の動的削除を用いた状態数え上げの効率化
- 等価状態の部分的抽出による大規模順序回路の簡単化
- 不完全指定有限状態機械に対する高速な状態数簡単化アルゴリズム
- ハードウェアデバッグ支援のためのエラー入出力トレースの上位レベル設計における再現手法(高位レベルテスト・検証,VLSI設計とテスト及び一般)
- 製造後デバッグのための入出力シーケンススライシング手法(設計/テスト/検証)
- 充足可能性判定に基づくシステムレベルデバッグ支援手法におけるバグモデルの導入による効率化
- 上位設計記述の解析を利用した製造後機能テストの効率化
- 動的パッチ読み出し機構を備えた製造後機能修正可能アクセラレータ
- パワーゲーティング技術を搭載したシステムLSIの電源ノイズ抑制
- 依存グラフを用いた局所的な記号シミュレーションによるC言語記述に対する等価性検証手法の提案(システムLSI設計及び一般)
- 依存グラフを用いた局所的な記号シミュレーションによるC言語記述に対する等価性検証手法の提案(システムLSI設計及び一般)
- C言語を対象とした記述間の差異に基づく効率的な等価性検証手法(システムオンシリコン設計技術並びにこれを活用したVLSI)
- C言語を対象とした記述間の差異に基づく効率的な等価性検証手法(システムオンシリコン設計技術並びにこれを活用したVLSI)
- C言語でのハードウェア記述に対する効率的な等価性検証手法の提案(システム設計及び一般)
- C言語でのハードウェア記述に対する効率的な等価性検証手法の提案(システム設計及び一般)
- ループ融合を利用した複数のforループからのパイプラインハードウェア合成
- 1M-5 ワードレベル論理式の充足可能性判定問題を利用したシステムレベル設計デバッグ支援手法(モデリング・上流設計,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- 潜在的多様性を考慮したプログラマブルハードウェアの高位合成手法(プログラマブルデバイスと設計技術,システムオンシリコンを支える設計技術)
- 設計固有セルライブラリの自動生成手法(論理設計,デザインガイア2009-VLSI設計の新しい大地)
- イベントドリブン法による分散回路シミュレーション方式
- 回路圧縮によるシミュレーションの高速化手法
- 高精度イベントドリブン回路シミュレーションの回路分割
- 予測法に基づく高精度イベントドリブン回路シミュレーション方式
- 予測法に基づく高精度イベントドリブン回路シミュレーション方式
- A-60 短チャネルMOSFETのトランジスタ縮約法(A-3. VLSI設計技術,一般講演)
- A-59 高精度イベントドリブンMOS回路シミュレーション方式(A-3. VLSI設計技術,一般講演)
- 仮想マルチプロセッサモデルに基づく高速SoCプロトタイピング手法(高位設計1,デザインガイア2010-VLSI設計の新しい大地-)
- 仮想マルチプロセッサモデルに基づく高速SoCプロトタイピング手法(高位設計1,デザインガイア2010-VLSI設計の新しい大地-)
- C-12-17 Power Gating技術を搭載したシステムLSIの電源ノイズ抑制手法(電源回路・ノイズ対策,C-12.集積回路,一般セッション)
- 高性能SoCプロトタイプのFPGA実装方式の検討(論理設計1,デザインガイア2010-VLSI設計の新しい大地-)
- 高性能SoCプロトタイプのFPGA実装方式の検討(論理設計1,デザインガイア2010-VLSI設計の新しい大地-)
- 上位設計記述の解析を利用した製造後機能テストの効率化 (ディペンダブルコンピューティング)
- 上位設計記述の解析を利用した製造後機能テストの効率化 (VLSI設計技術)
- 時相論理に基づく論理回路検証システム
- RTL-Tokioに基づくパイプライン化支援
- RTL-Tokio : レジスタトランスファレベル動作記述言語
- 時相論理型言語Tokioによる論理回路検証系の評価
- 時相論理型言語Tokioによるハードウェア記述 : 時間に依存するfactによる同期記述
- 1M-6 動作合成された束データ方式による非同期式回路とその動作仕様に対する等価性検証手法(モデリング・上流設計,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- 2分決定グラフを用いた推移的閉包計算アルゴリズムと形式的検証への応用
- Boolean Relationからの多段論理回路の合成
- 2. 形式的検証手法の実設計への適用例 ( 論理設計の形式的検証)
- 特集「論理設計の形式的検証」の編集にあたって
- VLSI実設計に於ける形式的検証の適用
- 多入力論理関数に対する効率的なWalshスペクトルの計算手法とそのテクノロジマッピングへの応用
- チャネル境界上の端子位置決定法
- Rectangular Dualに基づくマクロセル配置手法
- 多段論理合成における二段論理式簡単化の一手法
- 順序付き2分決定グラフと許容関数を用いた多段論理回路簡単化手法 (回路自動合成と最適化論文特集)
- 大規模回路の多段論理簡単化について
- 順序回路の簡単化について
- 遅延を意識したレジスタトランスファレベルからの合成について
- 2分決定グラフのための変数順決定アルゴリズムとその評価
- 遅延時間の増加を押さえたトランスダクション法について
- トランスダクション法に基づく多段論理回路簡単化機能をもつ論理合成システム
- 2分決定グラフを利用したトランスダクション法の改良
- 時相論理による仕様記述支援システム
- グラフに基づく論理照合アルゴリズムの評価と改良
- 論理とそのVLSI設計への応用 (VLSI設計の新しい流れ)
- 発見的手法に基づくスケーラブルなインクリメンタル高位合成(高位設計1,デザインガイア2010-VLSI設計の新しい大地-)
- 発見的手法に基づくスケーラブルなインクリメンタル高位合成(高位設計1,デザインガイア2010-VLSI設計の新しい大地-)
- 2P-1 動的ウェブアプリケーションの操作に対する画面間遷移の網羅的検証(ソフトウェアの検査・検証,学生セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- 不完全指定有限状態機械に対する高速な状態数簡単化アルゴリズム
- インクリメンタル高位合成に向けた設計記述間差分の計算手法 (ディペンダブルコンピューティング)
- インクリメンタル高位合成に向けた設計記述間差分の計算手法 (コンピュータシステム)
- システムレベル設計における同期検証フレームワークの提案
- システムレベル設計における同期検証フレームワークの提案
- データ符号化によるVLSIにおける低消費電力・高信頼データ伝送手法の検討
- データ符号化によるVLSIにおける低消費電力・高信頼データ伝送手法の検討(低消費)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- トランスダクション法に基づく多段論理回路簡単化機能をもつ論理合成システムとその評価
- 時相論理型言語Tokioを利用したハードウェア機能設計
- インクリメンタル高位合成に向けた設計記述間差分の計算手法
- インクリメンタル高位合成に向けた設計記述間差分の計算手法
- 論理合成システムにおける遅延時間最適化手法
- Rectangle coveringを用いたタイミング制約生成手法
- Rectangle coveringを用いたタイミング制約生成手法
- Rectangle coveringを用いたタイミング制約生成手法
- 複数クロックを考慮したタイミング制約生成手法
- 複数クロックを考慮したタイミング制約生成手法
- 多段論理回路を対象とした状態割当手法に関する評価と考察
- 1.ハードウェア/ソフトウェア協調設計のコンピュータ支援における問題および方法について (ハードウェア/ソフトウェア・コデザイン)
- FPGAを用いたSmith-Waterman Algorithmの高速化(科学技術計算)
- Satisfiability Don't Caresを用いた多段論理回路の簡単化
- 高位合成ツールを利用したハードウェアアルゴリズムの最適化(最適化技術,システム設計及び一般)
- 反例と設計分割に基づく高位設計に対する効率的な設計修正支援手法(検証技術,システム設計及び一般)
- 形式的検証を用いたプロセッサエラー回復機構の耐性評価手法の検討(検証技術,システム設計及び一般)
- 論理関数の充足不可能性に注目した論理回路デバッグ手法の検討
- 論理関数の充足不可能性に注目した論理回路デバッグ手法の検討
- ゲート回路シミュレーションにおけるGPGPUを利用したアサーション自動抽出
- 低消費電力LSIのための電源電圧制御技術(招待講演)
- 論理関数の充足不可能性に注目した論理回路デバッグ手法の検討(設計技術,組込み技術とネットワークに関するワークショップETNET2012)
- 論理関数の充足不可能性に注目した論理回路デバッグ手法の検討(設計技術,組込み技術とネットワークに関するワークショップETNET2012)
- 動作レベル・レジスタ転送レベル混在設計記述向け高位合成手法(動作レベル設計と配線手法,システムオンシリコンを支える設計技術)
- 潜在的な依存関係を利用した高位設計デバッグ支援手法(システム設計,システム設計及び一般)
- 誤差を有するシステムのシミュレーション結果に対する統計的解析とそのハードウェアによる高速化(設計環境,システム設計及び一般)
- プログラム可能な素子を利用したゲートレベル回路のデバッグ手法
- プログラム可能な素子を利用した大規模回路の自動修復手法