Random-walk based capacitance extraction with optimized transition volumes

Abstract

A CAD method for capacitance extraction includes decomposing a semiconductor structure model representing a three-dimensional, into virtual layers. Each virtual layer has polygons corresponding to conductors in the semiconductor structure model. The semiconductor structure model or includes a geometric point. The method includes creating spatial indexes respectively for the virtual layers. Each spatial index indicates respectively for each spatial index cell of a corresponding virtual layer at least one candidate conductor of the corresponding virtual layer. The method includes creating optimal transition squares for the geometric point respectively for one or more consecutive virtual layers according to spatial indexes of the one or more consecutive virtual layers. The geometric point is located in one of the one or more consecutive virtual layers. The optimal transition squares are constrained by one or more candidate conductors of the one or more consecutive virtual layers. The method includes creating an optimal transition cube for the geometric point considering the one or more candidate conductors based on the optimal transition squares. The method includes calculating capacitance of the three-dimensional circuit using surfaces of the optimal transition cube.