Filling Algorithms and Analyses for Layout Density Control

In very deep-submicron VLSI, manufacturing steps involving chemical-mechanical polishing (CMP) have varying e ects on device and interconnect features, depending on local characteristics of the layout. To reduce manufacturing variation due to CMP and to improve performance predictability and yield, layout must be made uniform with respect to certain density criteria, by inserting \ ll " geometries into the layout. To date, only foundries and special mask data processing tools perform layout post-processing for density control. In the future, better convergence of performance veri cation ows will depend on such layout manipulations being embedded within the layout synthesis (place-and-route) ow. In this paper, we give the rst realistic formulation of the lling problem that arises in layout optimization for manufacturability. Our formulation seeks to add features to a given process layer, such that (i) feature area densities satisfy prescribed upper and lower bounds in all windows of given size, and (ii) the maximum variation of such densities over all possible window positions in the layout is minimized. We present e cient algorithms for density analysis, notably a multilevel approach that a ords user-tunable accuracy. We also develop exact solutions to the problem of ll synthesis, based on a linear programming approach. Thes