A simple fast exact density calculation algorithm

VLSI technology is facing an extreme challenge due to the miniaturization and complexity of leading-edge products. Density control is a must step to ensure the yield and performance for the manufacturing smaller, faster and cheaper chips. A fundamental problem in the density control is how to calculate density correctly and efficiently. In this paper, we propose a simple but efficient two-level hierarchical approach to exactly identify the maximum density window for a given layout. Comparing with the latest work (Xiang et al., 2007), the new algorithm shows big runtime reductions on testcases which have a long runtime.