Linear programming (LP) based methods are attractive for solving the placement problem because of their ability to model Half-Perimeter Wirelength (HPWL) and timing. However, it has been technically difficult to model overlaps in LP. This difficulty in modeling overlaps restricted the domain of LP-based methods to incremental placers, where LP is used to calculate the optimal locations of a small subset of cells with no regard to overlaps. In this paper, we enlarge the scope of LP-based methods from just operating on a small subset of cells to operating on all cells of a functional block circuit. We show how to model, reduce and prevent overlaps in LP-based placement flows. We use our ideas to construct (1) a global optimal whitespace allocator, and (2) a global overlap remover and cell spreader. We also modify our methods to fit in a timing-driven placement flow. Compared to our default industrial flow, our results show an improvement by an average of 7.64% in wirelength, and by an average of 21%in total negative slack. Furthermore, we conduct a benchmarking study, where we surprisingly show that academic placers fail to consistently produce good results on relatively small functional blocks.
展开▼
