回路分割のためのビンパッキングアルゴリズムFFDとその拡張
スポンサーリンク
概要
- 論文の詳細を見る
FPGAによる論理合成を典型的な例として, ブロック数最小化などの評価のもとでの回路分割問題の基本は整数ビン(箱)パッキング問題である. これはビンの容量cが入力の場合, NP困難問題であり, 高速性と精度で傑出しているFFDと呼ばれる近似解法が知られ広く利用されている. 従来研究はFFDの漸近的な精度保証に終始しているが, 論理回路設計等への応用からはcをパラメータと考えたときの正解を与える範囲が重要である. 本論文では, FFDが厳密解を出力する範囲がc≦6であることを確定する. 証明はFFDの出力が正解でない場合を考察することによる方法でわかりやすい. その考察は, c≦8で正解を出力する拡張FFDの提案につながる. FFDの簡明さと高速性は捨てがたいので, 拡張FFDを用いてc=7, 8でのFFDの正答率について実験で考察する.
- 社団法人電子情報通信学会の論文
- 1997-09-25
著者
-
梶谷 洋司
東京工業大学工学部電気・電子工学科
-
泉 知論
立命館大学 理工学部電子情報デザイン学科
-
泉 知論
京都大学 大学院 情報学研究科
-
梶谷 洋司
東京工業大学 大学院 理工学研究科 集積システム専攻
-
横丸 敏彦
東京工業大学工学部電気・電子工学科
-
泉 知論
東京工業大学工学部電気・電子工学科
関連論文
- クリティカルパスのリビジットに着目した回路分割遅延改善手法の提案
- 高位合成を有効活用するか?活用をあきらめるか?(システム設計及び一般)
- 高位合成を有効活用するか?活用をあきらめるか?(パネル討論,システム設計及び一般)
- Flipにより自己変換するスタイナ木とそのVLSI最適配線への応用(電子システムの設計技術と設計自動化)
- 複数ネットの非交差配線における探索的最適化手法の提案
- 最適配線レイアウトの為のスタイナー木生成手法Elip
- 最適配線レイアウトの為のスタイナー木生成手法Flip
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- 動的再構成可能デバイスの耐故障化に関する検討
- A-4-27 コンフィギュラブルプロセッサを用いたJPEG2000符号器の設計
- A-4-11 組込み向けJPEG2000適応型レート制御方式
- A-4-39 JPEG2000スケーラブル符方化器の構成法
- VISI回路の階層設計をサポートする階層化BSGフロアプラン
- 確率的探索手法に基づく凸多角形パッキング手法の提案
- 抽象データ構造による高密度3次元パッキング手法
- 複数ネットの非交差配線における探索的最適化手法の提案
- 複数ネットの非交差配線における探索的最適化手法の提案
- 最適配線レイアウトの為のスタイナー木生成手法Flip
- 凸型矩形を扱うMultiple-BSG配置手法の提案
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- 座標固定モジュールを扱うBSG構造におけるモジュール配置手法の考案
- 相似拡大モデルに基づき配線領域を確保したモジュール配置手法の提案
- 座標固定モジュールを扱うBSG構造におけるモジュール配置手法の考案
- 相似拡大モデルに基づき配線領域を確保したモジュール配置手法の提案
- 準同期式回路におけるスケジュールクロック木の構成
- 準同期式回路におけるスケジュールクロック木の構成
- 準同期式におけるクロック配線駆動配置
- 準同期式におけるクロック配線駆動配置
- 端子間容量行列の枝容量和最小実現の枝数最小化について(グラフ理論とその応用)
- 最小数枝付加によるk-枝連結グラフの(k+1)-枝連結グラフへの拡大構成(グラフ理論とその応用)
- 3-消去可能グラフについて(グラフ理論とその応用)
- 回路分割のためのビンパッキングアルゴリズムFFDとその拡張
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 容量を固定した整数ビンパッキング問題のFFD法による解法
- Computational Complexity Map of the Set Bin-Packing Problem
- ビンの容量を制限したキューブパッキング問題のNP完全性について
- ビンの容量を制限したキューブパッキング問題のNP完全性について
- ハードウエア動作モデルからの電力・性能推定に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- C言語からの高位合成を用いたハードウェア最適化に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- ハードウエア動作モデルからの電力・性能推定に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- ハードウエア動作モデルからの電力・性能推定に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- C言語からの高位合成を用いたハードウェア最適化に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- ハードウエア動作モデルからの電力・性能推定に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- C言語からの高位合成を用いたハードウェア最適化に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- C言語からの高位合成を用いたハードウェア最適化に関する一検討(プロセッサ, DSP, 画像処理技術及び一般)
- 二つのグラフの共通木グラフについて(グラフ理論とその応用)
- プラスティックセルアーキテクチャへのアレイ型論理マッピング手法
- 枝重み付き一般グラフの最大マッチングの下限と線形時間近似アルゴリズム
- モジュールの重なりを許さない力学的モデルによるモジュール配置手法の提案
- モジュールの重なりを許さない力学的モデルによるモジュール配置手法の提案
- A-3-4 局所方向性を持つFPGAの経由スイッチ数最小化配置アルゴリズム
- BDDサイズに着目したPCA-Chip2のための変数順序決定手法
- フロアプランの部屋間チャネル隣接を表現するHalf-State Sequence(H-Seq)
- パラメトリックBSGによるレイアウトデザインの再利用
- パラメトリックBSGによるレイアウトデザインの再利用
- A-3-1 近接度に着目した入出力ピン配置アルゴリズム
- COMP2000-17 壁と部屋に関する位相方形分割のReduct-Seqによる数え上げ
- Reduct-Seq表現による高速な一般構造フロアプラニング
- CAS2000-15 / VLD2000-24 / DSP2000-36 Reduct-Seq表現による高速な一般構造フロアプランニング
- CAS2000-15 / VLD2000-24 / DSP2000-36 Reduct-Seq表現による高速な一般構造フロアプラニング
- クリティカルパスのリビジットに着目した回路分割遅延改善手法の提案
- 最小カットを用いて適切な部分回路を抽出するための効率的手法
- 最小カットを用いて適切な部分回路を抽出するための効率的手法
- 最小カットを用いて適切な部分回路を抽出するための効率的手法
- 疑似気圧モデルに基づくVLSIフロアプランの局所修正
- 疑似気圧モデルに基づくVLSIフロアプランの局所修正
- マルチプロセッサの低消費電力化のためのクロックON/OFFスケジューリング
- マルチプロセッサの低消費電力化のためのクロックON/OFFスケジューリング
- 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
- 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
- マルチプロセッサの低消費電力化のためのクロックON/OFFスケジューリング
- 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
- 準同期式回路の実現に適したクロック木構成法
- 準同期式回路の実現に適したクロック木構成法
- 準同期式回路の実現に適したクロック木構成法
- リソース制約付き回路分割問題に関する一考察
- 線長の総和と最大に関する均衡平面スタイナー木
- 線長の総和と最大に関する均衡平面スタイナー木
- 準同期式回路のためのクロック配線および遅延挿入手法
- 密度推定に基づく全ネット同時配線手法 : 端点成長法
- スキュー制御クロックネットワークの構成
- 準同期式回路における遅延最適化によるクロック高速化
- クロックスキュー制御によるクロック周期の最小化
- 強パス遅延テスト可能な論理回路の解析と合成
- SA-1-4 PCA-Chip2におけるパイプライン通信機構の多チャネル化
- プラスティックセルアーキテクチャへの回路実装密度に関する一考察