In this paper, we present FastPlace -- a fast, iterative, flat placement algorithm for large-scale standard cell designs. FastPlace is based on the quadratic placement approach. The quadratic approach formulates the wirelength minimization problem as a convex quadratic program, which can be solved efficiently by some analytical techniques. However it suffers from some drawbacks. First, the resulting placement has a lot of overlap among cells. Second, the resulting total wirelength may be long as the quadratic wirelength objective is only an indirect measure of the linear wirelength. Third, existing net models tend to create a lot of non-zero entries in the connectivity matrix, which slows down the quadratic program solver. To handle the above problems we propose: (1) An efficient Cell Shifting technique to remove cell overlap from the quadratic program solution and produce a global placement with even cell distribution. (2) An Iterative Local Refinement technique, to reduce the wirelength according to the half-perimeter measure. (3) A Hybrid Net Model which is a combination of the traditional clique and star models. This net model greatly reduces the number of non-zero entries in the connectivity matrix and results in a significant speedup of the solver. Experimental results show that FastPlace is on average 13.0 and 97.4 times faster than Capo and Dragon respectively. Correspondingly, the average wirelength is just 1.0% and 1.6% higher.
展开▼
