高配線率線分探索の一手法
スポンサーリンク
概要
- 論文の詳細を見る
VLSIの自動レイアウトにおいてはチャネル配線法が広く用いられている. しかし, 階層的レイアウトにおいて集積密度の大きな向上を達成するためには, 端子が列状に並んでいることを前提としたチャネル配線法のみでは限界があり, 任意に分散した端子間を接続できる配線法の併用が不可欠であると考えられる. このような目的に適用できる配線法としては迷路法, 線分探索法などが報告されているが, 処理時間, プロセス制約への対応など種々の点で実際的な回路への適用には不十分であった. 本論文では, ブロック間配線に適用できる配線手法として, 線分探索法を拡張した"予測線分探索法"を提案し, いくつかの適用例を示す. 予測線分探索法は2点間の接続において, スタート点からターゲット点に向う直接的な探索に, 結合力強化のため"先読み"を加えた手法を基本としている. これに, 二重探索防止のためのフラグ, バック・トラッキングを組み合わせ, 経路が存在すれば必ず接続できることを保証している. 本手法と2層配線に拡張した迷路法とを比較した結果, ネット長では7%程度増加するが, スルーホール数は20〜35%減少し, VLSIのブロック間配線において迷路法より高い配線完了率が得られた. 処理時間は迷路法の1/10〜1/30であった.
- 一般社団法人情報処理学会の論文
- 1985-11-15