Faster and better global placement by a new transportation algorithm

We present BonnPlace, a new VLSI placement algorithm that combines the advantages of analytical and partitioning-based placers. Based on (non-disjoint) placements minimizing the total quadratic netlength, we partition the chip area into regions and assign the circuits to them (meeting capacity constraints) such that the placement is changed as little as possible. The core routine of our placer is a new algorithm for the transportation problem that allows to compute efficiently the circuit assignments to the regions. We test our algorithm on a set of industrial designs with up to 3.6 millions of movable objects and two sets of artificial benchmarks showing that it produces excellent results. In terms of wirelength, we can improve the results of leading-edge placement tools by about 5%.