Optimal Mixed-Cell-Height Detailed Placement with Discrete Spacing Costs

Mixed-cell-height VLSI circuits are widely used to meet various design requirements. Due to design for manufacturability (DFM) considerations such as layout-dependent effects (LDEs), drain-to-drain abutment (DDA), and pattern coloring for multiple patterning, different spacings between adjacent cells affect performance, modeled as discrete spacing costs. A state-of-the-art dynamic programming (DP) approach can address this problem but can only handle a few cell rows simultaneously due to its high complexity. In this article, we propose a novel DP algorithm that can solve the problem optimally and more efficiently. Additionally, several optimality-preserving reduction techniques are employed to derive full-chip optimal solutions for large-scale designs. Experimental results demonstrate that the proposed approach significantly outperforms existing methods in terms of total spacing cost and total displacement.