抽象データ構造による高密度3次元パッキング手法
スポンサーリンク
概要
- 論文の詳細を見る
様々な大きさの直方体を, 重なりなく, できるだけ小さな直方体の箱の中に配置するという3次元パッキング問題を自動で解くことは, 倉庫やトラックへの荷物の詰め込みシステムへの応用が期待できる. しかし, この問題はNP-hardであるため, 本稿では, 確率的な探索手法を用いた配置体積の最小化手法を提案する. 本手法の鍵は, 直方体のラベルの順列組による直方体間の上下左右前後の位置関係の表現方法と, 順列組から互いに重ならない配置の生成方法にある。また順列組が生成する配置の中に, 最小体積の配置が存在することを証明する. さらにsimulated annealingにより, 様々な順列組を探索する実験では, 実用時間内で高品質な配置の出力に成功した.
- 1999-05-24
著者
-
坂主 圭史
東京工業大学工学部電気・電子工学科
-
梶谷 洋司
東京工業大学工学部電気・電子工学科
-
中武 繁寿
東京工業大学工学部電気・電子工学科
-
山崎 博之
東京工業大学:(現)鉄道情報システム株式会社
-
山崎 博之
東京工業大学 工学部 電気・電子工学科
-
山崎 博之
東京工業大学理工学研究科集積システム
-
梶谷 洋司
東京工業大学 大学院 理工学研究科 集積システム専攻
-
中武 繁寿
北九州市立大学国際環境工学部情報メディア工学科
-
坂主 圭史
東京工業大学 集積システム専攻
関連論文
- 数理計画法に基づく大規模配置最適化枠組みの提案(レイアウト,信号処理,LSI,及び一般)
- クリティカルパスのリビジットに着目した回路分割遅延改善手法の提案
- クロストーク制約を考慮したシーケンス・ペアに基づくコンパクション手法の提案(低消費電力/耐ノイズ・ばらつき設計(2),システムオンシリコン設計技術並びにこれを活用したVLSI)
- 等長配線制約を考慮したシーケンス・ペア法に基づくコンパクション手法(信号処理,LSI,及び一般)
- アナログICレイアウト設計における回路図クラスタ情報に基づくマルチレベル配置手法の提案(VLSIの設計/検証/テスト及び一般配置配線)
- クロストークノイズとシールド効果を考慮したクロスポイント割り当ての高速解法(VLSIの設計/検証/テスト及び一般配置配線)
- アナログICレイアウト設計における回路図クラスタ情報に基づくマルチレベル配置手法の提案(VLSIの設計/検証/テスト及び一般 配置配線)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- クロストークノイズとシールド効果を考慮したクロスポイント割り当ての高速解法(VLSIの設計/検証/テスト及び一般 配置配線)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- アナログICレイアウト設計における回路図クラスタ情報に基づくマルチレベル配置手法の提案
- クロストークノイズとシールド効果を考慮したクロスポイント割り当ての高速解法
- Flipにより自己変換するスタイナ木とそのVLSI最適配線への応用(電子システムの設計技術と設計自動化)
- 複数ネットの非交差配線における探索的最適化手法の提案
- 最適配線レイアウトの為のスタイナー木生成手法Elip
- 最適配線レイアウトの為のスタイナー木生成手法Flip
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- 基板電位調整を伴うプログラマブルCMOSアナログ回路の提案(再構成可能デバイス/キャリブレーション,システムオンシリコン設計技術並びにこれを活用したVLSI)
- トランジスタ・アレイ方式に基づくオペアンプのレイアウト設計およびその評価(物理設計,デザインガイア2009-VLSI設計の新しい大地-)
- MOSトランジスタ特性の距離/空間ばらつきにおけるレイアウト構造依存性の解析(物理設計,デザインガイア2009-VLSI設計の新しい大地-)
- レイアウト構造を意識したばらつきモデル化及びそのオペアンプ設計における検証(システムと信号処理及び一般)
- CAS2010-7 レイアウト構造を意識したばらつきモデル化及びそのオペアンプ設計における検証(システムと信号処理及び一般)
- レイアウト構造を意識したばらつきモデル化及びそのオペアンプ設計における検証(システムと信号処理及び一般)
- クロストーク制約を考慮したシーケンス・ペアに基づくコンパクション手法の提案(低消費電力/耐ノイズ・ばらつき設計(2),システムオンシリコン設計技術並びにこれを活用したVLSI)
- 等長配線制約を考慮したシーケンス・ペア法に基づくコンパクション手法(信号処理,LSI,及び一般)
- 等長配線制約を考慮したシーケンス・ペア法に基づくコンパクション手法(信号処理,LSI,及び一般)
- 規則バルク構造に基づくアナログマクロレイアウト生成手法(性能及び製造性考慮物理設計,システムオンシリコンを支える設計技術)
- 多層パラメトリック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の経由スイッチ数最小化配置アルゴリズム
- モジュールの重なりを許さない力学的モデルによるモジュール配置手法(システムLSIの設計技術と設計自動化)
- 実効クロックスキュー最小化のためのクロック木構成法
- 実効クロックスキュー最小化のためのクロック木構成法
- 実効クロックスキュー最小化のためのクロック木構成法
- フロアプランの部屋間チャネル隣接を表現する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スケジューリング
- 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
- 準同期式回路の実現に適したクロック木構成法
- 準同期式回路の実現に適したクロック木構成法
- 準同期式回路の実現に適したクロック木構成法
- リソース制約付き回路分割問題に関する一考察
- 線長の総和と最大に関する均衡平面スタイナー木
- 線長の総和と最大に関する均衡平面スタイナー木
- 準同期式回路のためのクロック配線および遅延挿入手法
- 密度推定に基づく全ネット同時配線手法 : 端点成長法
- スキュー制御クロックネットワークの構成
- 準同期式回路における遅延最適化によるクロック高速化
- クロックスキュー制御によるクロック周期の最小化
- 強パス遅延テスト可能な論理回路の解析と合成