Efficient approximation algorithms for chemical mechanical polishing dummy fill

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

To reduce chip-scale topography variation in chemical mechanical polishing process, dummy fill is widely used to improve the layout density uniformity. Previous researches formulated the density-driven 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. Furthermore, dummy fill can also change the interconnect coupling capacitance which might lead to a significant influence on circuit delay, crosstalk, and power consumption. In this paper, we develop a dummy fill algorithm that can be applied to solve both the traditional density-driven problem and the problem considering fill-induced coupling capacitance impact. The proposed algorithm is both efficient and with provably good performance, which is based on a fully polynomial time approximation scheme by Fleischer for covering LP problems. Moreover, 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. Final experimental results demonstrate the effectiveness and efficiency of our algorithms.

Original languageEnglish (US)
Article number5715601
Pages (from-to)402-415
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume30
Issue number3
DOIs
StatePublished - Mar 2011

Funding

Manuscript received February 4, 2010; revised May 17, 2010 and August 15, 2010; accepted September 16, 2010. Date of current version February 11, 2011. This work was supported in part by the NSFC Research Projects 60976034, 61076033, and 60806013, the National Basic Research Program of China under the Grants 2005CB321701 and 2011CB309701, the National Major Science and Technology Special Projects 2008ZX01035-001-05 and 2009ZX02023-4-3 of China during the 11th Five Year Plan Period, the Doctoral Program Foundation of the Ministry of Education of China 200802460068, the Program for Outstanding Academic Leader of Shanghai and NSF, under CCF-0238484 and CCF-0811270. This paper was recommended by Associate Editor D. Z. Pan. Dr. Zhou was a recipient of the CAREER Award from the National Science Foundation in 2003.

Keywords

  • Coupling capacitance
  • covering linear programming
  • design for manufacturability
  • dummy fill problem

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Efficient approximation algorithms for chemical mechanical polishing dummy fill'. Together they form a unique fingerprint.

Cite this