多層多端子位相配線におけるネット当りのビア数について
スポンサーリンク
概要
- 論文の詳細を見る
多層基板で線幅,線間の制限を考えずにビア数を最小とする配線経路と層割当てを求める問題はネットを2端子ネットに限ったとしてもNP困難であり,多くの発見的アルゴリズムが効率化の観点から研究されている.しかしながら解の性質については,層数を2に制限したときの最適解(ビア総数最小解)におけるt端子ネットのビア数はたかだかt-1であるという事実が証明されている程度である.また,層数を限定しない多層TVM問題においてはビアと端子の性質の定義が1種類でなくなり複雑になることが知られている.本論文は上述の定理を一般化し,配線層数を制限しない一般問題の最適解において,t端子ネット当り隣接層接続型ビア数の上限はt-1であることを証明し,この上限数のビアを要する問題のクラスの存在を構成的に示す.更に,全層接続型ビアについても同様の結果を示す.
- 社団法人電子情報通信学会の論文
- 1994-11-25
著者
関連論文
- アナログ集積回路での共通重心に対応した配置手法に関する研究(物理設計,物理設計及び一般)
- PCB設計における直線バス構造に沿う最適モジュｰル配置
- スライス構造における配線領域を確保する最適フロアプラン
- モジュール配置問題を解く限定スライス構造の提案
- モジュール配置問題を解く限定スライス構造の提案
- ビンの容量を制限したキューブパッキング問題のNP完全性について
- ハイブリット IC 平面レイアウト対話設計における配線位相を保つ端子移動アルゴリズム
- アナログレイアウトエディタに適した位相配線のデータ構造と修正アルゴリズム
- 枝重み付き一般グラフの最大マッチングの下限と線形時間近似アルゴリズム
- 多端子ネットの2端子ネット集合へのビア数に関する等価変換