Is your layout density verification exact?: a fast exact algorithm for density calculation

ABSTRACT

As the device shapes keep shrinking, the designs are more sensitive to manufacturing processes. In order to improve performance predictability and yield, mask layout uniformity/evenness is highly desired, and it is usually measured by the feature density with defined feasible range in manufacture process design rules. To address the density control problem, one fundamental problem is how to calculate density accurately and efficiently. In this paper, we propose a fast exact algorithm to identify the maximum density for a given layout. Compared with the existing exact algorithms, our algorithm reduces the running time from days/hours to a few minutes/seconds. And it is even faster than the existing approximate algorithms in literature.

REFERENCES

• 1: B. Biswas, Modeling in-die process variation with accuracy, http://www.eetimes.com/story/OEG20040115S0027.
• 2: L. Deng, K. Chao, H. Xiang, and D.F.Wong, Coupling-aware dummy metal insertion for lithography, Proc. Asia and South Pacific Design Automation Conf., Jan. 2006.
• 3: Andrew B. Kahng , Gabriel Robins , Anish Singh , Huijuan Wang , Alexander Zelikovsky, Filling and slotting: analysis and algorithms, Proceedings of the 1998 international symposium on Physical design, p.95-102, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274549]
• 4: A. B. Kahng, G. Robins, A. Singh and A. Zelikovsky, New Multilevel and Hierarchical Algorithms for Layout Density Control, Proc. Asia and South Pacific Design Automation Conf., pp. 221--224, Jan. 1999.
• 5: A. B. Kahng , G. Robins , A. Singh , A. Zelikovsky, New and Exact Filling Algorithms for Layout Density Control, Proceedings of the 12th International Conference on VLSI Design - 'VLSI for the Information Appliance', p.106, January 10-13, 1999
• 6: A. B. Kahng, G. Robins, A. Singh and A. Zelikovsky, Filling Algorithms and Analyses for Layout Density Control, IEEE Transactions on Computer-Aided Design 18(4), pp. 445--462, 1999.
• 7: Yu Chen , Andrew B. Kahng , Gabriel Robins , Alex Zelikovsky, Monte-Carlo algorithms for layout density control, Proceedings of the 2000 conference on Asia South Pacific design automation, p.523-528, January 2000, Yokohama, Japan [doi>10.1145/368434.368778]
• 8: Yu Chen , Andrew B. Kahng , Gabriel Robins , Alexander Zelikovsky, Practical iterated fill synthesis for CMP uniformity, Proceedings of the 37th conference on Design automation, p.671-674, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337610]
• 9: Yu Chen , Andrew B. Kahng , Gabriel Robins , Alexander Zelikovsky, Hierarchical dummy fill for process uniformity, Proceedings of the 2001 conference on Asia South Pacific design automation, p.139-144, January 2001, Yokohama, Japan [doi>10.1145/370155.370306]
• 10: Yu Chen , Andrew B. Kahng , Gabriel Robins , Alexander Zelikovsky, Closing the smoothness and uniformity gap in area fill synthesis, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505422]
• 11: Y. Chen, A. B. Kahng, G. Robins, and A. Zelikovsky, Area Fill Synthesis for Uniform Layout Density, IEEE Trans. on CAD, vol 21, No. 10, pp 1132--1147, Oct. 2002.
• 12: Y. Chen, P. Gupta, and A. B. Kahng, Performance-Impact Limited Dummy Fill Insertion, Proc. SPIE Conf. on Design and Process Integration for Microelectronic Manufacturing, pp. 75--86, Feb. 2003.
• 13: Y. Chen, A. B. Kahng, G. Robins, A. Zelikovsky, and Y. H. Zheng, Data Volume Reduction in Dummy Fill Generation, Proc. Design Automation and Testing in Europe, pp. 868--873, March 2003.
• 14: Yu Chen , Andrew B. Kahng , Gabriel Robins , Alexander Zelikovsky , Yuhong Zheng, Area Fill Generation With Inherent Data Volume Reduction, Proceedings of the conference on Design, Automation and Test in Europe, p.10868, March 03-07, 2003
• 15: Puneet Gupta , Andrew B. Kahng , Youngmin Kim , Dennis Sylvester, Self-Compensating Design for Focus Variation, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065677]
• 16: A. B. Kahng, Mini-Tutorial: IC Layout and Manufacturability: Critical Links and Design Flow Implications, Proceedings of the 12th International Conference on VLSI Design - 'VLSI for the Information Appliance', p.100, January 10-13, 1999
• 17: Ruiqi Tian , D. F. Wong , Robert Boone, Model-based dummy feature placement for oxide chemical-mechanical polishing manufacturability, Proceedings of the 37th conference on Design automation, p.667-670, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337609]
• 18: Ruiqi Tian , Xiaoping Tang , D. F. Wong, Dummy feature placement for chemical-mechanical polishing uniformity in a shallow trench isolation process, Proceedings of the 2001 international symposium on Physical design, p.118-123, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369750]
• 19: Kees Veelenturf, The road to better reliability and yield embedded DFM tools, Proceedings of the conference on Design, automation and test in Europe, p.67-68, March 27-30, 2000, Paris, France [doi>10.1145/343647.343702]
• 20: Xin Wang , Charles C. Chiang , Jamil Kawa , Qing Su, A Min-Variance Iterative Method for Fast Smart Dummy Feature Density Assignment in Chemical-Mechanical Polishing, Proceedings of the 6th International Symposium on Quality of Electronic Design, p.258-263, March 21-23, 2005 [doi>10.1109/ISQED.2005.8]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
DFM, density, fix-dissection