A Method for improved final placement employing branch-and-bound with hierarchical placement encoding and tightened bounds

A new method employing branch-and-bound for improved final placement is presented for the final step of detailed placement problem where the objective is to optimize (and tradeoff) total bounding box wirelength and timing. First, we view the placement of a cell as a bit-sequence which hierarchically encodes the procedure of constraining the cell to an exact location (exact row and column). Such bit sequences indicate a recursive dissection of the layout area. We argue that the search strategy indicated by the placement encoding has compelling advantages over typical ones in terms of search efficiency. Second, the branch-and-bound method with hierarchical placement encoding can inherently expose the possibly improved configurations and provide a mechanism for exploiting the abundant opportunities for tradeoffs between different design objectives. Our experiments start with the placements of 12 of the largest MCNC benchmarks from VPR, iteratively extract and release parts of the cells to larger regions (that defines the search space) and optimally (or nearly optimally) place these cells with respect to the search space. The experiments show that the wire length of the placements can be improved 11% on average with simultaneous reduction in the critical path delay of the routed placements (6.3% on average).