Polygon Reduction Algorithm for Layout Extraction and Parasitic Signal Calculation
Date
2002-05
Authors
Zaporojets, Olga V.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The design of a specific polygon reduction algorithm to be applied to the process of layout extraction is proposed. The algorithm is tested with the Star-RCXT parasitic signal extraction tool and the impact of the reduction algorithm is measured and analyzed. There are many polygon reduction algorithms but they all are application specific and not particularly suitable for the extraction tool. The research objective is to generate a reduction algorithm which may be used by any Electric Design Automation (EDA) layout extraction tool and which most effectively achieves a goal of maximum reduction of the number of extracted polygons and preserves connectivity and area of the polygons for further processing. The reduction algorithm described in this paper is created as a local greedy method with some history back tracking for the combined error control. It is used with trapezoidation processing, which is the most common way to perform polygon extraction by EDA tools. The reduction method developed is very general yet effective since it allows not only reduction of “not carrying information” trapezoids but trapezoids with a slight topology modification, fixing trapezoids displacements which may result from the lack of precision of a layout tool used to generate data. The trapezoidation and reduction algorithm was implemented in C++ and tested on real design data. The worst time reduction complexity is 0(n2) and the worst time complexity of the trapezoidation and reduction performed together is 0(n2 log2n). The reduction of the number of polygons achieved in the most accurate mode is 73% and it may be much higher if the less accurate mode is used. The accuracy tests displayed that extracted data produced using reduction algorithm is identical to the extraction data produced without reduction. Total reduction of the parasitic signal extraction time of the designs in the most accurate reduction mode is approximately 26%, which is very significant for the tape out time constraints in the competitive high technology industry. Implemented as a “stand alone” tool, the reduction algorithm may be used not only with Star RCXT tool created by Avant!, but with any other extraction tool.
Description
Keywords
computer algorithms, polygons
Citation
Zaporojets, O. V. (2002). Polygon reduction algorithm for layout extraction and parasitic signal calculation (Unpublished thesis). Southwest Texas State University, San Marcos, Texas.