An efficient quadratic placement based on search space traversing technology

A very large-scale standard cell placement problem has too complicated solution space for conventional analytical quadratic placement methods to achieve the “optimal” or near-optimal solution in it. The rugged terrain of solution space makes those methods easy to get stuck at local optima. In this paper, a novel quadratic placement based on search space traversing technology is proposed to search the optimal or near-optimal solution. This method first employs a pre-partitioning to cut down the problem scale and reconstruct the problem structure, and then combines the Lagrange relaxation method and the Lagrange multipliers method together in quadratic placement to solve the global placement. Finally, after eliminating overlaps, a full-chip force-directed post-adjustment is employed to reduce the negative effect of pre-partitioning. Experimental results on benchmarks show encouraging results.