拡張平面掃引法に基づく最小幅/間隔検証手法

金 整範  粟島 亨  佐藤 政生  大附 辰夫  

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


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



あらまし: 
VLSIのレイアウト検証で取り扱うべきデータの量は,図形の頂点数にして106~108程度に至っている.ところが,現在の汎用計算機の主メモリの容量には制限があり,このような大規模なデータのすべてを主メモリに格納することは事実上不可能である.従って,レイアウト検証を行う際には,全レイアウトデータは2次記憶装置(シーケンシャルファイル)に格納されている.扱う図形データは大規模なものなので,最悪の場合でも,図形の頂点数に比例する程度の手間で検証を行う必要がある等の前提を考慮しなくてはならない.本論文では,レイアウト検証問題の中でも,与えられたレイアウト(マスクパターン)中に設計規則で指定された最小幅,最小間隔に違反する箇所が存在するか否かを判定する問題(最小幅/間隔検証問題と呼ぶ)に焦点を当て,上述の前提を満足する処理算法を提案する.提案する算法は,平面掃引法を拡張したものであり,その時間複雑度はO(n log n),空間複雑度はO(n0.5)である.ここで,nは図形の頂点数であり,空間複雑度は主メモリ内におけるものである.また,この算法に関する計算機実験結果を報告する.