電気系レイアウトDAに於ける概略配線問題を対象とした超大規模整数計画問題について
スポンサーリンク
概要
- 論文の詳細を見る
電気系レイアウトDA(Design Automation)の種々の問題は組合せ最適化問題として定式化できる。本稿では、特に概略配線問題を平面多種フロー問題として定式する際の超大規模整数計画問題について論じる。レイアウトDA問題は部品を配置する配置問題と部品間を配線する配線問題とからなる。配線問題は概略配線と詳細配線問題の各々からなる。概略配線問題は、配線領域を分割した小領域単位に各配線がどの領域を通過するかを決定する問題である。目的関数は、配線長合計最小化、混雑度平準化、特定の配線経路長の最小化、である。この問題を解くために本稿では問題を平面多種フロー問題として定式化するが、それは制約式の数は数万程度の超大規模整数計画問題となり、処理時間は百数十時間を要すると推定される。従来は処理時間を実用レベルに抑えるために問題の規模を削減する手法を組み込んでいたが、本稿では、階層化並列処理を目的として、改めて超大規模整数計画問題の処理時間と解の整数性を実験したので報告する。
- 一般社団法人情報処理学会の論文
- 1995-07-19
著者
関連論文
- パフォーマンスドリブン・レイアウト手法(1. レイアウト設計)(エレクトロニクス実装のためのシミュレーション技術)
- Rent's Ruleに基づく概略配線問題生成手法(プロセッサ,DSP,画像処理技術及び一般)
- Rent's Ruleに基づく概略配線問題生成手法(プロセッサ,DSP,画像処理技術及び一般)
- Rent's Rule に基づく概略配線問題生成手法(プロセッサ,DSP,画像処理技術及び一般)
- Rent's Ruleに基づく概略配線問題生成手法(プロセッサ,DSP,画像処理技術及び一般)
- 経時変化からみた母音「あ」の非線形性について(信号処理,LSI,及び一般)
- 音声解析からみたリアプノフ指数計算手法の比較(信号処理,LSI,及び一般)
- 経時変化からみた母音「あ」の非線形性について(信号処理, LSI, 及び一般)
- 音声解析からみたリアプノフ指数計算手法の比較(信号処理, LSI, 及び一般)
- 経時変化からみた母音「あ」の非線形性について(信号処理, LSI, 及び一般)
- 音声解析からみたリアプノフ指数計算手法の比較(信号処理, LSI, 及び一般)
- VoyagerによるPCクラスタ上の階層型並列分散配置処理について
- VoyagerによるPCクラスタ上の階層型並列分散配置処理について
- VoyagerによるPCクラスタ上の階層型並列分散配置処理について
- 概略配線結果を線分探索の方向として利用する予測線分探索法
- 概略配線結果を線分探索の方向として利用する予測線分探索法
- VLSI自動設計システムに於けるランダマイズドクラスタリングアルゴリズム
- VLSI自動設計システムに於けるランダマイズドクラスタ配置アルゴリズムの外部端子位置決定手法
- 親の形質を詳細に利用する遺伝的アルゴリズムを用いた電子系DAに於ける部品配置手法
- 電子系DAに於いて部品配置を同時に行う概略配線問題の定式化について
- 電気系DAに於けるデータベースマネージャを対象とした自動プログラミング技術の応用について
- 電気系DAに於けるデータベースマネージャを対象とした自動プログラミング技術の応用について
- 電気系レイアウトDAに於ける概略配線問題を対象とした超大規模整数計画問題について
- 製品検査処理の並列分散化に関する一手法
- 特集「システム実装を支える設計・シミュレーション技術」に寄せて