An efficient method for gradient-aware dummy fill synthesis

In advanced VLSI fabrication, dummy fill is widely employed to solve the pattern dependent manufacturability issues. In this paper, a new linear programming formulation for dummy fill synthesis is proposed, which takes more consideration to the density gradient besides the pattern density. Based on the covering linear programming (CLP), a fast iterative approximation scheme is designed to solve this newly formulated problem. The complexity of the new method is proved to be O(n2log(n)). Experimental results demonstrate the effectiveness of the new formulation, and show good accuracy and time efficiency of the proposed method. Compared with the ordinary LP method, speedup over magnitude is achieved with the acceptable overfill amount.

► A new LP formulation for gradient-aware dummy fill synthesis is proposed.
► Gradient constraints are eliminated by a scan-and-fix method with complexity O(n).
► An iterative scheme is designed based on covering linear programming (CLP).
► About one order speedup over LP method is achieved with acceptable overfill amount.