Multilevel optimization for large-scale circuit placement

We have designed and implemented a new class of fast and highly scalable placement algorithms that directly handle complex constraints and achieve total wirelengths comparable to the state of the art. Our approach exploits recent advances in (i) multilevel methods for hier-archical computation, (ii) interior-point methods for nonconvex nonlinear programming, and (iii) the Fast Multipole Method for the order N evaluation of sums over the N(N - 1)/2 pairwise interactions of N components. Significant adaptation of these methods for the placement problem is required, and we have therefore developed a set of customized discrete algorithms for clustering, declustering, slot assignment, and local refinement with which the continuous algorithms are naturally combined. Preliminary test runs on benchmark circuits with up to 184,000 cells produce total wirelengths within approximately 5-10% of those of gordian-l [1] in less than one tenth the run time. Such an ultra-fast placement engine is badly needed for timing convergence of the synthesis and layout phases of integrated circuit design.