タイミング制約を伴う概略配線問題に対するバッファ挿入と配線幅の選択を許したスタイナ木構成手法

概要

論文の詳細を見る
本稿では VLSI レイアウト設計における配線木生成において, 複数の部分木の配線トポロジを保持しながら配線木へのバッファ挿入, 配線幅拡大を同時に考慮したスタイナ木生成手法を提案する. 提案手法では, 初期配線トポロジは仮定せず, ソースを原点とするグリッド平面上に与えられたシンクノードの座標位置, およびソースより各シンクまでの要求遅延時間を元に配線木の構築を行なう. また, 配線木の構築と同時に木の枝に対してバッファ挿入, 配線幅拡大を行なう. さらに提案手法では, シンクからソースに向けてボトムアップに配線木を構築していく際に, 構築過程で生成される部分木は1形状に限定せず, 複数の部分木の生成を許すことで形状の事なる複数の配線木を構築し, 最終段階で最もスラックの大きい節点をソースからシンクまでバックトレースする事により, 最良の配線木を決定する. 全ての可能な部分木の組合せを計算すると膨大な計算時間がかかるため, 提案手法では配線木の構築過程で効果的な枝刈り手法を用い, かつ提案手法を階層的に適用する事により実用的な時間で配線木を求める事が出来る.
1998-01-30