Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Michigan Univ., Ann Arbor, MI
Abstract :
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
Keywords :
circuit optimisation; integrated circuit interconnections; integrated circuit layout; network routing; ROOSTER; Rigorous Optimization Of Steiner-Trees Eases Routing; Steiner wirelength optimization; Steiner-tree wirelength; integrated circuit layout; min-cut algorithms; net-length estimates; place-and-route results; placement algorithm; routed wirelength; very-large-scale integration; whitespace distribution; Algorithm design and analysis; Data structures; Design automation; Field programmable gate arrays; Integrated circuit layout; Routing; Runtime; Silicon; Steiner trees; Very large scale integration; Algorithms; design automation; integrated circuit layout; routing; very-large-scale integration;
