Critical area computation for missing material defects in VLSI circuits

Abstract

We address the problem of computing critical area for missing material defects in a circuit layout. The extraction of critical area is the main computational problem in VLSI yield prediction. Missing material defects cause open circuits and are classified into breaks and via-blocks. Our approach is based on the L∞ medial axis of polygons and the weighted LINF Voronoi diagram of segments. The critical area problem for both breaks and via-blocks is reduced to a weighted LINF Voronoi diagram of segments. This reduction results in a plane sweep algorithm to compute critical area in one pass. The time complexity is O(n log n) in the case of breaks and O(n log n+K) in the case of via-blocks, where n is the size of the input and K is bounded by the number of interacting vias (in practice K is small). The critical area computation assumes square defects and reflects all possible defect sizes following the D(r) = r02/r3 defect size distribution. The method is presented for rectilinear layouts.