配線プログラムに適した新データ構造の評価
スポンサーリンク
概要
- 論文の詳細を見る
VLSIレイアウトCADの配線プログラムではチップ内のセルや配線を表す図形データを効率よく扱うためPriority Search Tree(以下PST)などのデータ構造を用いることが必須である.しかし,PSTは矩形データを4本の構成線分に分解して扱うため計算機上で非常に大きな主記憶を必要とする.そこで本稿ではPSTを直接矩形が扱えるように拡張した新データ構造を提案する.データ数がnの時,この新データ構造はO(n)のメモリを使用し,平面上で指定点から指定方向にもっとも距離の小さい図形の検索をO(√<n>log n)の処理時間で実現する.配線プログラムを実行する上で新データ構造とPSTを比較した計算機実験結果とともに,新データ構造の有効性を示す.
- 一般社団法人情報処理学会の論文
- 1994-06-24
著者
関連論文
- 高性能 VLSI のクロック配線方式
- 貫通電流を考慮するトランジスタサイジング手法
- 貫通電流を考慮するトランジスタサイジング手法
- 配線プログラムに適した新データ構造の評価
- ディレイ・スキュー最小化のための線幅最適化クロック配線手法