Optimisation Study of VLSI Circuit Cell Placement Based on Rectilinear Minimum Steiner Tree and Simulated Annealing Algorithm

Large-scale integration (VLSI) integrates numerous circuit elements onto a single chip, significantly impacting Electronic Design Automation (EDA). This paper investigates the effects of wire length, circuit grid density, and routing density using Half-Perimeter Wire Length (HPWL) and Rectilinear Steiner Minimum Tree (RSMT) models. For wire length, Steiner points are iteratively added to the given set of coordinates for each group, and Kruskal's algorithm is applied to determine the minimum spanning tree with the shortest total wire length. The grey relational model is used to evaluate the solution based on grey relational coefficients. For grid density, the study divides the element density into three cases: single obstruction, multiple non-overlapping obstructions, and multiple overlapping obstructions. The objective function minimizes wire length, constrained by a grid density threshold of 0.9, with simulated annealing used for optimization. In routing density analysis, improvements to existing methods are proposed by calculating group-specific routing densities and overall grid routing density, using Matlab to compute overlapping regions and derive the final results.