BonnPlace Legalization: Minimizing Movement by Iterative Augmentation

We describe BONNPLACELEGAL, an algorithm for VLSI placement legalization. Based on a minimum-cost flow algorithm that iteratively augments flows along paths, our approach ensures that only augmentations are considered that can be realized exactly by cell movements. Hence, this method avoids realization problems that are inherent to previous flow-based legalization algorithms. As a result, it combines the global perspective of minimum-cost flow approaches with the efficiency of local search algorithms. The tool is mainly designed to minimize total and maximum cell movement, but it is flexible enough to optimize other objective functions provided that the effect of single cell movements on them can be estimated efficiently. We compare our approach to legalization tools from industry and academia by experiments on dense recent real-world designs and public benchmarks. The results show that we are much faster and produce significantly better results in terms of average (linear and quadratic) and maximum movement than any other tool. The experiments also demonstrate that by minimizing squared movement we also produce a smaller increase in net length than the other tools.