Provably good and practically efficient algorithms for CMP dummy fill

ABSTRACT

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.

REFERENCES

• 1: Y. Chen, A. B. Kahng, G. Robins, and A. Zelikovsky. Monte-Carlo algorithms for layout density control. In Proceedings of ASP-DAC, pages 523--528, 2000.
• 2: Y. Chen, A. B. Kahng, G. Robins, and A. Zelikovsky. Practical iterated fill synthesis for CMP uniformity. In Proceedings of ACM/IEEE Design Automation Conference, pages 671--674, 2000.
• 3: Y. Chen, A. B. Kahng, G. Robins, and A. Zelikovsky. Area fill synthesis for uniform layout density. IEEE Trans. on CAD, 21(10):1132--1147, 2002.
• 4: L. Fleischer. A fast approximation scheme for fractional covering problems with variable upper bounds. In Proceedings of ACM-SIAM symposium on Discrete algorithms, pages 1001--1010, 2004.
• 5: N. Garg and J. Könemann. Faster and simpler algorithms for multicommodity flow and other fractinal packing problems. In Proceedings of IEEE Symposium on Foundations of Computer Science, pages 300--309, 1998.
• 6: T. E. Gbondo-Tugbawa. Chip-Scale Modeling of Pattern Dependencies in Copper Chemical Mechanical Polishing Processes. PhD thesis, Massachusetts Institute of Technology, 2002.
• 7: A. Kahng, G. Robins, A. Singh, and A. Zelikovsky. Filling algorithms and analyses for layout density control. IEEE Trans. on CAD, 18(4):445--462, 1999.
• 8: A. B. Kahng and K. Samadi. CMP fill synthesis: A survey of recent studies. IEEE Trans. on CAD, 27(1):3--19, 2008.
• 9: S. Lakshminarayanan, P. J. Wright, and J. Pallinti. Electrical characterization of the copper CMP process and derivation of metal layout rules. IEEE Trans. on Semiconductor Manufacturing, 16(4):668--676, 2003.
• 10: M. Mukherjee and K. Chakraborty. A randomized greedy method for rectangular-pattern fill problems. IEEE Trans. on CAD, 27(8):1376--1384, 2008.
• 11: D. O. Ouma. Modeling of Chemical Mechanical Polishing for Dielectric Planarization. PhD thesis, Massachusetts Institute of Technology, 1998.
• 12: P. Raghavan and C. D. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365--374, 1978.
• 13: R. Tian, D. F. Wong, and R. Boone. Model-based dummy feature placement for oxide chemical mechanical polishing manufacturability. In Proceedings of ACM/IEEE Design Automation Conference, pages 667--670, 2000.
• 14: X. Wang, C. C. Chiang, J. Kawa, and Q. Su. A min-variance iterative method for fast smart dummy feature density assignment in chemical-mechanical polishing. In Proceedings of ISQED, pages 258--263, 2005.
• 15: H. Xiang, L. Deng, R. Puri, K.-Y. Chao, and M. D. F. Wong. Fast dummy-fill density analysis with coupling constraints. IEEE Trans. on CAD, 27(4):633--642, 2008.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design

Keywords:
covering linear programming, design for manufacturability, dummy fill problem