An effective iterative density aware detailed placement algorithm

The requirement for high performance detailed placement continues to grow in modern physical synthesis flows. During the optimization of placement, HPWL is the most basic and important objective while some other important metrics such as placement density also needs to be carefully monitored, preserving the overall quality of a given placement. We present an effective detailed placement algorithm for total HPWL and density optimization. First, we perform a density-aware cell swapping technique to improve wirelength. Second, cell re-ordering is performed to handle left-right order problem of cells within a segment, picking the order with the best HPWL. Third, a bloating and refinement technique is performed to evenly distribute the cells in regular bins, reducing bin utilization. Wirelength and cell density are iteratively optimized until the improvement is converged. The algorithm is tested on ICCAD13 benchmark suites. Using the evaluation script of ICCAD13 contest, we achieved an average of 4.86% reduction in HPWL and 10.48% reduction in scaled HPWL.