Can recursive bisection alone produce routable, placements?

By A. Caldwell, Andrew B. Kahng, Igor L. Markov. Proceedings - Design Automation Conference, 2000

384 citations recorded by the source corpus.

This work focuses on congestion-driven placement of standard cells into rows in the fixed-die context. We summarize the state-of-the-art after two decades of research in recursive bisection placement and implement a new placer, called Capo, to empirically study the achievable limits of the approach. From among recently proposed improvements to recursive bisection, Capo incorporates a leading-edge multilevel min-cut partitioner [7], techniques for partitioning with small tolerance [8], optimal min-cut partitioners and end-case min-wirelength placers [5], previously unpublished partitioning tolerance computations, and block splitting heuristics. On the other hand, our “good enough” implementation does not use “overlapping” [17], multi-way partitioners [17, 20], analytical placement, or congestion estimation [24, 35]. In order to run on recent industrial placement instances, Capo must take into account fixed macros, power stripes and rows with different allowed cell orientations. Capo reads industry-standard LEF/DEF, as well as formats of the GSRC bookshelf for VLSI CAD algorithms [6], to enable comparisons on available placement instances in the fixed-die regime. Capo clearly demonstrates that despite a potential mismatch of objectives, improved mincut bisection can still lead to improved placement wirelength and congestion. Our experiments on recent industrial benchmarks fail to give a clear answer to the question in the title of this paper. However, they validate a series of improvements to recursive bisection and point out a need for transparent congestion management techniques that do not worsen the wirelength of already routable placements. Our experimental flow, which validates fixed-die placement results by violation-free detailed auto-routability, provides a new norm for comparison of VLSI placement implementations.

Subfields: Electrical and Electronic Engineering, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/1e383d7c977905e3cdaeda84d23d33bd331abb45

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Electrical and Electronic Engineering

  1. Igor L. Markov
  2. Brian Taba
  3. Dharmendra S. Modha
  4. John V. Arthur
  5. Matthew Cook
  6. Peter U. Diehl
  7. Michael Pfeiffer
  8. Garrick Orchard

In Hardware and Architecture

  1. Igor L. Markov

Citations in the corpus