Provably good and practically efficient algorithms for CMP dummy fill

Feng Chunyang, Zhou Hai, Yan Changhao, Tao Jun, Zeng Xuan*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


To reduce chip-scale topography variation in Chemical Mechanical Polishing (CMP) process, dummy fill is widely used to improve the layout density uniformity. Previous researches formulated the dummy fill problem as a standard Linear Program (LP). However, solving the huge linear program formed by real-life designs is very expensive and has become the hurdle in deploying the technology. Even though there exist efficient heuristics, their performance cannot be guaranteed. In this paper, we develop a dummy fill algorithm that is both efficient and with provably good performance. It is based on a fully polynomial time approximation scheme by Fleischer [4] for covering LP problems. Furthermore, based on the approximation algorithm, we also propose a new greedy iterative algorithm to achieve high quality solutions more efficiently than previous Monte-Carlo based heuristic methods. Experimental results demonstrate the effectiveness and efficiency of our algorithms.

Original languageEnglish (US)
Title of host publication2009 46th ACM/IEEE Design Automation Conference, DAC 2009
Number of pages6
StatePublished - Nov 10 2009
Event2009 46th ACM/IEEE Design Automation Conference, DAC 2009 - San Francisco, CA, United States
Duration: Jul 26 2009Jul 31 2009

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Other2009 46th ACM/IEEE Design Automation Conference, DAC 2009
CountryUnited States
CitySan Francisco, CA


  • Covering linear programming
  • Design for manufacturability
  • Dummy fill problem

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation

Fingerprint Dive into the research topics of 'Provably good and practically efficient algorithms for CMP dummy fill'. Together they form a unique fingerprint.

Cite this