A Method for Improved Final Placement Employing Branch-And-Bound with Hierarchical Placement Encoding and Tightened Bounds

Xitian Li1 and John Lillis2
1ECE Dept of University of Illinois at Chicago, 2CS Dept of University of Illinois at Chicago


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 experiment starts with the placements of 12 of the largest MCNC benchmarks from VPR \cite{vpr:5}, iteratively extracts and releases parts of the cells to larger regions (that defines the search space) and optimally (or nearly optimally) places these cells with respect to the search space. The experiment shows 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).