ABSTRACT
This chapter considers methods that reduce overlaps by recursive partitioning of the chip area and the set of cells to be placed. It describes methods how the partitioning results can be incorporated in the ensuing netlength optimization steps and deals with practical aspects of analytical placement implementations. The most widely adopted quality measure is netlength. Netlength can be defined in various ways, but the idea is always to estimate the wirelength after routing a given placement. A key step in analytical placement is to find a placement that minimizes netlength, disregarding overlaps. For analytical placers, the existence of some preplaced pins is mandatory. Though most analytical placement algorithms optimize quadratic netlength, there are some approaches that use different objective functions. Another interpretation of quadratic placement is in the context of electrical networks. Stability is an essential feature of placement algorithms—it is much more important than obtaining results that are close to optimum.
