FastPlace: efficient analytical placement using cell shifting, iterative local refinement,and a hybrid net model

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 that 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 nonzero entries in the connectivity matrix that 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 also accelerate the convergence of the solver. This technique produces a global placement with even cell distribution in a very short time; 2) an iterative local refinement technique to reduce the wirelength according to the half-perimeter measure; and 3) a hybrid net model that is a combination of the traditional clique and star models. This net model greatly reduces the number of nonzero entries in the connectivity matrix and results in a significant speedup of the solver. Experimental results show that FastPlace is on average 13.4/spl times/,102/spl times/, and 19.9/spl times/ faster than state-of-the art academic placers Capo, Dragon, and Gordian-Domino, respectively, on a set of IBM benchmarks.

I. Introduction

In recent years, the role of placement in the physical design of large chips has grown dramatically [1], [2]. The main reason is that placement of circuit modules determines interconnect length to a large extent, and hence, interconnect delay and routing resource demand. Interconnect delay has become the determining factor of circuit performance in present day integrated circuits. Hence, placement has become a major contributor to timing closure results. Current circuits often contain over a million placeable components, and it is predicted that circuit sizes will continue to double every three years [3]. Also, Cong et al. [4], [5] showed that existing placement algorithms are not scalable and stable. Therefore, it is likely that existing approaches may not be able to handle future circuits much larger in size. Hence, it is very essential to have extremely efficient placement algorithms.