Trunk decomposition based global routing optimization

ABSTRACT

We present global routing optimization methods which are not based on rip-up and re-route framework. In particular, the routing optimization is based on trunk decomposition [13] of the global routing. In this framework, the route of a net is decomposed into sets of wiring segments. By viewing a wiring segment as an "atomic object" of perturbation, we can efficiently evaluate the effect of routing tree perturbation. We propose two complementary routing optimization methods, namely segment partitioning and segment migration. These targeted optimizers can improve congestion related routing objectives by quickly shuffling wiring segments across different routing channels. Our routing approach produces better results compared to rip-up and re-route method based router Labyrinth [14] with average total overflow reduction of more than 88% while taking only 61% of runtime required by ripup and reroute phase of Labyrinth. When applied to the output of Labyrinth, the approach, on average, reduces the total overflow by more than 97% with complete overflow elimination for four circuits, while requiring additional runtime of just 33%. On a larger benchmark suite, the total overflow reduction of more than 86% is obtained, with complete overflow elimination for eight circuits, while requiring only 19% additional runtime.

References

1. Labyrinth webpage. http://www.ece.ucsb.edu/~kastner/labyrinth.
2. C. Albrecht. Provably good global routing by a new approximation algorithm for multicommodity flow. In Proc. of Intl. Symp. on Physical Design, pages 19--25, April 2000.
3. E. Bozorgzadeh, R. Kastner, and M. Sarrafzadeh. Creating and exploiting flexibility in rectilinear steiner trees. IEEE Tran. on CAD of Integrated Circuits And Systems, 22(5):605--615, May 2003.
4. M. Burstein and R. Pelavin. Hierarchical wire routing. IEEE Tran. on CAD of Integrated Circuits And Systems, 2(4):223--234, October 1983.
5. A. E. Caldwell, A. B. Kahng, and I. L. Markov. Can recursive bisection alone produce routable placements? In Proc. of Design Automation Conf., pages 693--698, June 2000.
6. R. C. Carden and C.-K. Cheng. A global router using an efficient approximate multicommodity multiterminal flow algorithm. In Proc. of Design Automation Conf., pages 316--321, 1991.
7. J. Cong, J. Fung, M. Xie, and Y. Zhang. Mars - a multilevel full-chip gridless routing system. IEEE Tran. on CAD of Integrated Circuits And Systems, 24(3):382--394, March 2005.
8. C. Ebling, L. McMurchie, S. A. Hauck, and S. Burns. Placement and routing tools for the triptych fpga. IEEE Tran. on Very Large Scale Integration (VLSI) Systems, 3(4):473--492, 1995.
9. C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In Proc. of Design Automation Conf., pages 175--181, 1982.
10. R. T. Hadsell and P. H. Madden. Improved global routing through congestion estimation. In Proc. of Design Automation Conf., pages 28--34, June 2003.
11. H. Hou, J. Hu, and S. S. Sapatnekar. Non-hannan routing. IEEE Tran. on CAD of Integrated Circuits And Systems, 18(4):436--444, April 1999.
12. J. Hu and S. S. Sapatnekar. A survey on multi-net global routing for integrated circuits. Integration: The VLSI Journal, 31(1):1--49, November 2001.
13. D. Jariwala and J. Lillis. On interactions between routing and detailed placement. In Proc. of Intl. Conf. on CAD, pages 387--393, November 2004.
14. R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh. Pattern routing: Use and theory for increasing predictability and avoiding coupling. IEEE Tran. on CAD of Integrated Circuits And Systems, 21(7):777--790, July 2002.
15. C. Y. Lee. An algorithm for path connections and its applications. IRE Tran. on Electronic Computers, EC-10(3):346--365, 1961.
16. R. Nair. A simple yet effective technique for global routing. IEEE Tran. on CAD of Integrated Circuits And Systems, 6(2):165--172, March 1987.
17. P. Raghvan and C. D. Thompson. Multiterminal global routing: A deterministic approximation. Algorithmica, 6:73--82, 1991.

Index Terms

• Hardware

  • Electronic design automation

    • Logic synthesis

      • Circuit optimization

    • Physical design (EDA)

      • Placement

      • Wire routing

  • Hardware validation

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems