An accelerated modulus-based matrix splitting iteration method for mixed-size cell circuits legalization

Mixed-size cell circuits dominate in advanced technology node designs, with attendant increases in layout complexity. The introduction of multi-row-height cells requires additional constraints, such as power line alignment, to be considered in the legalization stage, in addition to eliminating overlap while maintaining the results of the global placement stage as much as possible. In this paper, a three-stage legalization methodology is presented. The first is cell preprocessing, namely cell diffusion based on the network flow algorithm. Then the legalization problem is modeled as a quadratic programming problem, which is converted into a linear complementarity problem and solved by an accelerated modulus-based matrix splitting iteration method. Finally, the illegal cells are reshaped. Experimental results reveal that our method achieves 11.8% and 0.4% reduction in total displacement, respectively, over existing two state-of-the-art works, and is 1.407x faster than the modulus-based matrix splitting iteration method. In particular, the proposed approach provides a reference for solving large-scale quadratic programming problems.