An efficient quadratic placement based on search space traversing technology

作者：Lu Yongqiang^*; Hong Xianlong; Zhou Qiang; Cai Yici; Gu Jun

来源：Integration, the VLSI Journal, 2007, 40(3): 253-260.

DOI：10.1016/j.vlsi.2005.10.002

• quadratic placement
• q-place
• global placement
• search space traversing technology
• standard cell

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.

• 出版日期2007-4
• 单位香港科技大学; 清华大学