层次版图连接关系提取

Hierarchical Netlist Extraction in VLSI layout Verification

本文提出了一种新的层次版图连接关系提取算法,其利用投影法和版图倒序树(Inverse Layout Tree,简记为ILT)构建同一原始图形在不同层次单元之间的关联,并在基于边的扫描线算法的基础上利用组合器的方法建立版图数据的正确连接。此算法能够极好的保持版图中原有的层次,在此算法基础上进行的层次网表提取能够使层次LVS得到最大程度的支持;同时,算法具有很高的效率,只需占用很少的资源。目前,九天EDA系列工具中的层次版图验证工具已经采用此算法。

In this paper, a new algorithm of hierarchical netlist extraction is proposed. It is based on the data structure of Inverse Layout Tree(ILT). The algorithm builds the hierarchical relations of all geometries among cells in different levels and records connect information through a 'graph container' based on scan line method. By using this algorithm, the original layout hierarchy could be well kept and the extracted netlist has the same hierarchical information as the layout. The method has high efficiency and is successfully used in Zeni Hierarchical Layout Verification tools.