The advancement of technology nodes has intensified the focus on mixed-cell-height circuit design, posing challenges to traditional legalization techniques. In this paper, we propose a novel and efficient accelerated Newton-based matrix splitting (ANMS) iteration method to address the mixed-cell-height circuit legalization problem. Our approach reformulates this problem into a generalized absolute value equation and leverages matrix splitting and the latest estimate vector to enhance computational efficiency. We also introduce a relaxation variant within the ANMS framework, namely, the accelerated Newton-based successive overrelaxation (ANSOR) method, which is particularly effective in scenarios requiring high computational performance and precise parameter tuning. The proposed method achieves linear computational complexity. Furthermore, we perform an in-depth analysis of the sufficient convergence conditions for the ANMS method and optimize cells that have excessive displacement. Experimental results show that the proposed ANMS method achieves a speedup of 1.09× – 4.94× compared to state-of-the-art methods, while maintaining the quality of solution. This makes it highly suitable for addressing complex placement design challenges.

The evolution of advanced technology nodes has prompted a shift toward mixed-cell-height circuit design, while the introduction of technology and fence region constraints further increases the complexity of placement. In this article, we innovatively transform the mixed-cell-height circuit legalization problem into a generalized absolute value equation (GAVE) and propose a novel and effective robust Newton (RN) iteration method to address the challenge of the legalization problem. 1 First, the window-based cell insertion technique is applied to obtain the initial cell row allocation and cell order, and the cells are allocated to the matching region based on the R-tree structure. Then, the legalization problem of cells within the region is transformed into a GAVE, and an RN iteration method is proposed to solve the GAVE. Finally, the maximum displacement cells and technology violation cells are optimized based on a greedy method. Experimental results confirm the efficiency and robustness of the proposed method compared with the state-of-the-art methods.