VLSI critical area analysis via Voronoi diagrams

Critical Area is a widely accepted measure reflecting the sensitivity of a VLSI design to random defects occurring during the manufacturing process. The ability to accurately and quickly extract critical area is essential for VLSI manufacturing especially when Design for Manufacturability (DFM) changes are being considered to chip designs with the purpose of improving yield. Yield has become an ever greater-determinant of design viability and DFM efforts have been consistently on the rise in the semiconductor industry.

Critical Area is defined as, where A(r) denotes the area in which the center of a defect of radius r must fall in order to cause circuit failure and D(r) is the density function of the defect size. The most prominent defect types requiring critical area analysis are extra material defects causing shorts between different conducting regions and missing material defects causing open circuits. Missing material defects cause opens on conducting paths of interconnect layers and via blocks on contact and via layers.

Our effort to tackle the critical area extraction problem took an interdisciplinary approach combining fundamentals of computational geometry with design automation techniques. Our approach is based on the concept of a Voronoi diagram, a powerful mathematical object that encodes proximity information in a compact form.

Given a layout layer where critical area analysis needs to be performed, the layer is subdivided into small regions such that critical area within each region is easy to derive. The critical area integral becomes a summation of partial critical areas obtained within each region. Every region is associated with a single layout element that reveals the critical radius of all points within. The critical radius of a point t is the size of the smallest defect causing a fault at t. Using an appropriate distance metric, compatible with widespread assumptions on defect shapes, the critical radius simplifies to a simple linear function allowing for easy critical area integration in analytical form. A powerful scanline approach can build the appropriate layout subdivision for each type of defect fast in O(nlg n) time, where n is the size of the layout, maintaining the design in its initial hierarchical form, flattening only locally near the scanline. As soon as one region of the subdivision is available, critical area integration can be performed locally within that region and the region can be discarded. As a result memory consumption remains low keeping only a small fraction of the design flat in memory in the neighborhood of the scanline.

As an example we illustrate the case of shorts where a desired layout subdivision is obtained by a 2nd order Voronoi diagram. The 2nd order Voronoi subdivision within the Voronoi region of a polygonal site P is the portion of the Voronoi diagram of all polygons other than P within the region of P. It reveals the critical radius for shorts for all points in the region of P.



Critical area integration within each Voronoi region can be done in an analytic fashion, obtaining accurate critical area results. For the most widely used defect size distribution D(r)= 1/x³ analytic formulas simplify further and the entire critical area integral becomes a summation of simple terms derived from Voronoi edges. As a result critical area extraction becomes trivial once the appropriate layout subdivision is obtained. Our software is being used successfully by IBM Microelectronics reporting throughput improvements of more than 60 times for full chip extraction.

Rate this article

Rate from		low...		to	...high
Usefulness: