VLSI設計における1次元モジュール配置改良問題

大村 道郎  若林 真一  宮尾 淳一  吉田 典可  

誌名
電子情報通信学会論文誌 A   Vol.J73-A   No.11   pp.1858-1866
発行日: 1990/11/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: VLSI設計技術
キーワード: 


本文: PDF(548.3KB)>>
論文を購入




あらまし: 
VLSIレイアウト設計の一方式であるビルディングブロック方式において,モジュールの1次元配置が初期配置として与えられた場合のモジュールの配置改良問題について議論する.まず,(1)入力として与えられるネットリストが外部端子とモジュール間を接続する2端子ネットのみからなる場合を考え,モジュールの配置順序を保存したまま,x座標のみで定義される仮想配線長を最小にする配置改良問題PM0を定式化し,この問題に対するアルゴリズム,およびその最適性の証明を与える.また,モジュールの移動範囲に制約を加えた問題PM1も問題PMOに対するアルゴリズムを拡張することにより解くことができることを示す.次に,(2)問題PM1に対し,モジュール,および外部端子間を接続する一般の多端子ネットを許すように拡張した問題PM2が問題PM1に帰着できることを示す.最後に,(3)配線モデルとしてリバールーチングを採用し,y座標(セパレーション)を含めた配線長の最小化問題PM3について議論し,モジュール数とネット数の多項式時間で最適に解けることを示す.