Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement

We demonstrate that Steiner-tree wirelength (StWL) correlates with routed wirelength (rWL) much better than the more common half-perimeter wirelength (HPWL) objective. Therefore, we develop a technique to optimize StWL in global and detail placement without a significant runtime penalty. This new optimization, along with congestion-driven whitespace distribution, improves overall Place-and-Route results, making the use of HPWL unnecessary. Additionally, our empirical results provide ample evidence that the fidelity of net-length estimates is more important than their accuracy in Place-and-Route. The new data structures that make our min-cut algorithms fast can also be useful in multilevel analytical placement. Our placement algorithm Rigorous Optimization Of Steiner-Trees Eases Routing (ROOSTER) outperforms the best published results for Dragon, Capo, FengShui, mPL-R/WSA, and APlace in terms of rWL by 10.7%, 5.6%, 9.3%, 5.5%, and 4.2%, respectively. Via counts, which are especially important at 90 nm and below, are improved by 15.6% over mPL-R/WSA and 11.9% over APlace