Reduct-Seq表現による高速な一般構造フロアプラニング
スポンサーリンク
概要
- 論文の詳細を見る
VLSIレイアウト設計の支援ツールであるフロアプラナがモジュール配置問題を効率よく扱うためには, 空き領域のない一般構造フロアプランを計算機が扱いやすいデータ構造で表すことが重要である.本研究では, n部屋から構成される一般構造フロアプランを長さ3nの記号列で表現するReduct-Seqを提案する.一般構造フロアプランとReduct-Seqは, 互いにΟ(n)時間で変換が可能である.またReduct-Seqは, 一般構造フロアプランと1対1に対応するReduct-Seqの総数を数えた挙げた結果, 一般構造フロアプランの総数は, スライス構造フロアプランの総数より非常に大きいわけではないことが判明した.よって, Reduct-Seqを用いれば, スライス構造フロアプランの解空間を探索する時間と同程度の時間で一般構造フロアプランの解空間を探索することが出来る.各部屋に大きさをもつモジュールを入れることにより, 最小面積配置アルゴリズムを実装し, 幾つかの回路に対し, 解空間の探索にSimulated Annealingを用いて実験した結果, いずれの回路に対しても, 高密度なフロアプランが生成された.
- 2000-06-15
著者
-
坂主 圭史
東京工業大学工学部電気・電子工学科
-
梶谷 洋司
東京工業大学工学部電気・電子工学科
-
梶谷 洋司
東京工業大学 大学院 理工学研究科 集積システム専攻
-
翠川 賢太郎
東京工業大学大学院理工学研究科集積システム専攻
-
坂主 圭史
東京工業大学 集積システム専攻
関連論文
- クリティカルパスのリビジットに着目した回路分割遅延改善手法の提案
- Flipにより自己変換するスタイナ木とそのVLSI最適配線への応用(電子システムの設計技術と設計自動化)
- 複数ネットの非交差配線における探索的最適化手法の提案
- 最適配線レイアウトの為のスタイナー木生成手法Elip
- 最適配線レイアウトの為のスタイナー木生成手法Flip
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- 多層パラメトリックBSGによるコアセルの配置アルゴリズム
- VISI回路の階層設計をサポートする階層化BSGフロアプラン
- 確率的探索手法に基づく凸多角形パッキング手法の提案
- 抽象データ構造による高密度3次元パッキング手法
- 複数ネットの非交差配線における探索的最適化手法の提案
- 複数ネットの非交差配線における探索的最適化手法の提案
- 最適配線レイアウトの為のスタイナー木生成手法Flip
- 凸型矩形を扱うMultiple-BSG配置手法の提案
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- 座標固定モジュールを扱うBSG構造におけるモジュール配置手法の考案
- 相似拡大モデルに基づき配線領域を確保したモジュール配置手法の提案
- 座標固定モジュールを扱うBSG構造におけるモジュール配置手法の考案
- 相似拡大モデルに基づき配線領域を確保したモジュール配置手法の提案
- 準同期式回路におけるスケジュールクロック木の構成
- 準同期式回路におけるスケジュールクロック木の構成
- 準同期式におけるクロック配線駆動配置
- 準同期式におけるクロック配線駆動配置
- 端子間容量行列の枝容量和最小実現の枝数最小化について(グラフ理論とその応用)
- 最小数枝付加によるk-枝連結グラフの(k+1)-枝連結グラフへの拡大構成(グラフ理論とその応用)
- 3-消去可能グラフについて(グラフ理論とその応用)
- 回路分割のためのビンパッキングアルゴリズムFFDとその拡張
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 容量を固定した整数ビンパッキング問題のFFD法による解法
- ビンの容量を制限したキューブパッキング問題のNP完全性について
- Q-sequenceによるフロアプランの全列挙アルゴリズムと外壁隣接要求問題への応用
- Q-sequenceによるフロアプランの全列挙アルゴリズムと外壁隣接要求問題への応用
- Q-sequenceによるフロアプランの全列挙アルゴリズムと外壁隣接要求問題への応用
- 二つのグラフの共通木グラフについて(グラフ理論とその応用)
- 枝重み付き一般グラフの最大マッチングの下限と線形時間近似アルゴリズム
- 配線可能性を保証するSequence-Pairを用いた配置手法
- 配線可能性を保証するSequence-Pairを用いた配置手法
- 配線可能性を保証するSequence-Pairを用いた配置手法
- モジュールの重なりを許さない力学的モデルによるモジュール配置手法の提案
- モジュールの重なりを許さない力学的モデルによるモジュール配置手法の提案
- A-3-4 局所方向性を持つFPGAの経由スイッチ数最小化配置アルゴリズム
- 実効クロックスキュー最小化のためのクロック木構成法
- 実効クロックスキュー最小化のためのクロック木構成法
- 実効クロックスキュー最小化のためのクロック木構成法
- フロアプランの部屋間チャネル隣接を表現する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スケジューリング
- 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
- 準同期式回路の実現に適したクロック木構成法
- 準同期式回路の実現に適したクロック木構成法
- 準同期式回路の実現に適したクロック木構成法
- リソース制約付き回路分割問題に関する一考察
- 線長の総和と最大に関する均衡平面スタイナー木
- 線長の総和と最大に関する均衡平面スタイナー木
- 準同期式回路のためのクロック配線および遅延挿入手法
- 密度推定に基づく全ネット同時配線手法 : 端点成長法
- スキュー制御クロックネットワークの構成
- 準同期式回路における遅延最適化によるクロック高速化
- クロックスキュー制御によるクロック周期の最小化
- 強パス遅延テスト可能な論理回路の解析と合成