方形パッキング法の一算法
スポンサーリンク
概要
- 論文の詳細を見る
方形パッキング問題とは, 幅と高さが任意であるいくつかの方形が与えられたとき, 最小面積の方形内にこれらを互いに重複なく配置する問題であり, 面積が製造コストに大きく影響するVLSIの配置設計に応用することができる.この問題はNP困難な最適化問題であることから, SA法などのヒューリスティック算法を用いた解法が試みられてきたが, その際配置解の表現法が探索の効率化の鍵となる.近年, Sequence-Pairと呼ばれる配置解の画期的な表現法が提案され, 高品質な解を高速に探索する途が拓かれた.本論文では, この表現法に基づいて, 単純な幾何学的な手続きによって方形パッキングを求める高速な算法を提案し, 本算法が方形数の多いデータに対しても高速に良質な配置解を探索することを, MCNCベンチマークデータami49などの評価を通して示す.
- 社団法人電子情報通信学会の論文
- 1998-10-25
著者
-
重弘 裕二
大阪工業大学
-
白川 功
大阪大学大学院工学研究科情報システム工学専攻
-
神戸 尚志
近畿大学理工学部電気電子工学科
-
長尾 明
シャープ株式会社
-
澤 卓
奈良先端科学技術大学院大学情報科学研究科
-
重弘 裕二
大阪大学大学院工学研究科情報システム工学専攻
-
神戸 尚志
シャープ株式会社
-
神戸 尚志
シャープ
-
澤 卓
奈良先端科学技術大学院大学情報科学研究科:(現)住友電気工業株式会社
-
重弘 裕二
大阪大学大学院工学研究科情報システム工学専攻:(現)大阪工業大学
関連論文
- メディア処理向け再構成可能アーキテクチャでの動画像復号処理の実現(VLSI設計技術とCAD)
- IEEE 802.15.4を用いたホームネットワーク向け無線ネットワークプロトコル(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 異種個体集団が共存する遺伝的アルゴリズムによる論理回路の自動合成
- データセンターの役割 (特集 データセンター)
- 4相NMOSダイナミックロジック用アレイセル(非線形回路とシステム,及び一般)
- 4相NMOSダイナミックロジック用アレイセル
- 組込み用プロセッサの低消費電力化に関する一手法
- 改善解探索速度に基づくエージェント探索法のフィルタ回路合成への適用
- nMOSレベルシフタ回路の性能比較(低消費電力回路,システムオンシリコンを支える設計技術)
- グラウンド平面・シールド配線によるシステム・オン・パネルの配線間容量の低減と容量見積りの容易化(レイアウト設計,システムLSI設計とその技術)
- 領域分割による配線間容量モデル化手法について(通信と非線形特集及び一般)
- 製造ばらつきを考慮したDフリップフロップの性能評価
- 配線間容量モデル化とその評価について
- A-1-8 W-CDMAターボ符号処理向けVLSIアーキテクチャ
- A-1-7 W-CDMA用階層化ディジタルマッチトフィルタ
- 異種個体集団が共存する遺伝的アルゴリズムによるVLSIのチャネル配線手法
- 異種個体集団が共存するGAによるVLSIのチャネル配線手法 (第15回ファジィシステムシンポジウム--やりまっせ!新世紀のたおやか技術 日本ファジィ学会設立10周年記念大会) -- (GA拡張手法)
- フラクタル次元を利用したVLSIレイアウト向きクラスタリング手法
- A-3-15 組込みシステム用実行ファイルの効率的圧縮および実行方法の提案
- Simulated Annealing法における解空間の視覚化
- 方形パッキング法の一算法
- 最小コストフロー問題の高速解法とそのVLSIコンパクション問題への適用
- コンパクション問題に対するフロｰ･テンション平衡理論の適用
- C言語によるレイアウト記述の一手法
- 改善解探索速度に基づくエージェント探索法のフィルタ回路合成への適用
- 方形系列対に基づく遺伝的アルゴリズムを用いたフロアプラン設計
- ファジィ推論を用いた動的パラメトリックGAによる配電損失最小化問題の解法
- 異種個体集団が共存する遺伝的アルゴリズムによる負荷融通問題の解法
- 近傍解コストの分布に基づく最適化手法の提案と評価(セッション5)
- MPEG-4動画像符号化向けハイブリッドエラー隠ペい方式
- A-3-8 Bach C 言語による Ogg Vorbis デコーダの VLSI 化設計
- 組み込みCPUと専用回路によるOgg Vorbis音楽デコーダのVLSI化設計
- 組み込みCPUと専用回路によるOgg Vbrbis音楽デコーダのVLSI化設計
- A-3-8 組み込みCPU向けOgg VorbisデコーダのVLSI実装
- Particle Swarm Optimizationを用いた組合せ最適化問題の解法
- メディア処理向け小面積リコンフィギャラブルアーキテクチャ(リコンフィギャラブルアーキテクチャI,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- nMOSレベルシフタ回路の性能比較手法について(モデル・回路,組込技術とネットワークに関するワークショップETNET2008)
- nMOSレベルシフタ回路の性能比較手法について(モデル・回路,組込技術とネットワークに関するワークショップETNET2008)
- nMOSレベルシフタ回路の性能比較手法について(モデル・回路,組込技術とネットワークに関するワークショップETNET2008)
- 小型LCD駆動回路用タイミングパルス生成回路の自動レイアウトシステム(性能及び製造性考慮物理設計,システムオンシリコンを支える設計技術)
- 交通渋滞緩和のための遺伝的アルゴリズムに基づく道路交通管制
- 製造ばらつきを考慮したDフリップフロップの性能評価
- 大規模教育用計算機システムにおける授業・運用支援システムの設計と実装
- 無線ホームネットワークにおける消費電力および即時性の改善手法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 無線ホームネットワークにおける消費電力および即時性の改善手法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- データセンターの役割
- 医療用監視システムとその通信制御用LSIの設計(電子システムの設計技術と設計自動化)
- 医療用監視システムのための通信制御用LSI
- 医療用監視システムのための通信制御用LSI
- 医療用監視システムのための通信制御用LSI
- 表面弾性波素子を用いた監視システムとその応用
- 顔オブジェクトのリアルタイム抽出アルゴリズム
- 顔オブジェクトのリアルタイム抽出アルゴリズム
- 顔オブジェクトのリアルタイム抽出アルゴリズム
- A-3-4 MPEG-4オーディオデコーダにおけるノイズレス復号器およびスペクトル予測器のVLSI化設計
- マルチスレッドプロセッサのデータキャッシュ制御方式
- 電子透かしのMPEG-4ビットストリームエラー検出への応用
- MPEG-4ビデオ符号化における電子透かしを用いたエラー検出手法
- MPEG-4ビデオ符号化における電子透かしを用いたエラー検出手法
- D-11-38 電子透かしを用いたMPEG-4ビデオ伝送におけるエラー検出方式の検討
- MPEG-4ビデオ伝送に対するエラー隠蔽アルゴリズムおよびアーキテクチャ
- MPEG-4ビデオ伝送に対するエラー隠蔽アルゴリズムおよびアーキテクチャ
- MPEG-4ビデオ伝送に対するエラー隠蔽アルゴリズムおよびアーキテクチャ
- 動き検出を利用したMPEG-4ビデオにおけるエラー隠蔽アルゴリズムの提案
- 動き検出を利用したMPEG-4ビデオにおけるエラー隠蔽アルゴリズムの提案
- 動き検出を利用したMPEG-4ビデオにおけるエラー隠蔽アルゴリズムの提案
- nMOSレベルシフタ回路の性能比較手法について(モデル・回路,組込技術とネットワークに関するワークショップETNET2008)
- 液晶ディスプレイ用サンプリング回路におけるサンプリングパルスとトランジスタサイズの最適設計手法(VLSI設計技術とCAD)
- 液晶ディスプレイ用サンプリング回路の最適性について(演算回路/専用回路,システムオンシリコン設計技術並びにこれを活用したVLSI)
- 液晶ディスプレイ用サンプリング回路の最適性について(演算回路/専用回路,システムオンシリコン設計技術並びにこれを活用したVLSI)
- 画素充電率制約を満足する液晶ドライバ回路のトランジスタサイズ決定技術(システムオンシリコン設計技術並びにこれを活用したVLSI)
- 画素充電率制約を満足する液晶ドライバ回路のトランジスタサイズ決定技術(システムオンシリコン設計技術並びにこれを活用したVLSI)
- 配線間容量モデル化とその評価について
- 配線間容量モデル化とその評価について
- 条件分岐制御のあるデータパスのスケジューリング手法
- 映像伝送用高性能ディジタルフィルタのVLSI化設計
- 論理関数処理に基づく順序回路のテスト生成法
- H.263拡張INTRA符号化モードのコーデックとそのVLSIアーキテクチャ
- H.263拡張INTRA符号化モードのコーデックとそのVLSIアーキテクチャ
- 多層プリント回路板の電源供給系におけるインピーダンスシミュレーション(2. 電気設計)(エレクトロニクス実装のためのシミュレーション技術)
- nMOSダイナミック論理を用いた液晶駆動回路の設計手法(システムオンシリコン設計技術並びにこれを活用したVLSI)
- nMOSダイナミック論理を用いた液晶駆動回路の設計手法(システムオンシリコン設計技術並びにこれを活用したVLSI)
- データフレーム選択再送手法に基づいた映像伝送システムの設計
- データフレーム選択再送手法に基づいた映像伝送システムの設計
- データフレーム選択再送手法に基づいた映像伝送システムの設計
- 方形パッキング手法によるMMIC向き配置配線手法
- 方形パッキング手法によるMMIC向き配置配線手法
- 方形パッキング法の一算法
- 方形パッキング法の一算法
- 方形パッキング法の一算法
- 組込みシステム向けJava実行環境の構築
- 組込みシステム向けJava実行環境の構築
- 組込みシステム向けJava実行環境の構築
- A-3-12 組込みプロセッサ向けJavaアクセラレータのVLSI化設計
- 携帯端末向け低電力H.263コーデックコアのVLSI化設計
- 再帰的最尤復号アルゴリズムを用いた誤り訂正復号器のVLSI設計
- 再帰的最尤復号アルゴリズムを用いた誤り訂正復号器のVLSI設計
- 交通渋滞緩和のための遺伝的アルゴリズムに基づく道路交通管制
- 近傍解の評価値の改善量の期待値に基づく近傍探索法
- 交通渋滞緩和のための遺伝的アルゴリズムに基づく道路交通管制