Hamiltonian Path Based Mixed-Cell-Height Legalization for Neighbor Diffusion Effect Mitigation

In modern circuit designs, standard cells are designed with different heights based on the power, area, and other characteristics to address various design requirements. For those cells with different heights, in particular, there are inter-cell diffusion steps if the diffusion heights of neighboring cells are different, called the neighbor diffusion effect (NDE) which has become critical in advanced technology nodes. In this paper, we present a Hamiltonian-path-based mixed-cell-height legalization algorithm for NDE mitigation. We first present a row assignment method considering both cell displacements and diffusion steps to assign cells to their desired rows that meet the power-rail alignment constraints. Then, we propose a Hamiltonian-path-based diffusion-step reduction method to effectively reduce the NDE violations while preserving the global placement solution. Particularly, we develop a 2-approximation algorithm to find a minimum weight Hamiltonian path connecting two vertices, and a 1.5-approximation algorithm to find a minimum weight Hamiltonian path with a specified end vertex. Finally, we present an NDE-aware legalization method with design compaction to resolve overlaps and NDE violations. Experimental results show that our algorithm can resolve all NDE violations without any area overhead in reasonable runtime.