Novel techniques 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 wire-lengths comparable to the state of the art. Our approach exploits recent advances in (i) multilevel methods for hierarchical 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. Experimental test runs on benchmark circuits with up to 184,000 cells produce total wirelengths within approximately 5–10% of those of GORDIAN-L [SDJ91] in less than one tenth the run time.; We have also applied the multilevel optimization techniques to timing-driven FPGA placement under routability constraints. We have built a complete clustering and placement package, with simultaneous timing and routability optimization. Compared with state-of-the-art academic FPGA placer VPR, we have achieved the longest path delay reduction of up to 38.8%, 15.6% on average with no runtime overhead and only a 4.1% increase in total wirelength. Compared with the latest FPGA vendor place and route tool, we achieved around 4.9% improvement in terms of fmax. Our basic timing optimization is based on the concept of net weighting; we have developed a new net weighting algorithm, which significantly outperforms existing ones. In particular, this algorithm computes all timing critical paths through each edge, which is the first exact algorithm, to the best of our knowledge.