Advertisement

A Graph-Based Global Router Algorithm

  • Carl Sechen
Chapter
  • 79 Downloads
Part of the The Kluwer International Series in Engineering and Computer Science book series (SECS, volume 54)

Abstract

This chapter presents a general-purpose, graph-based global router algorithm. The quality of the solution produced by the global router is independent of the routing order of nets, a common limitation among previous algorithms. The global router is independent of the layout style since the only inputs to the algorithm are a net list and a channel graph (such as that generated by the algorithm of Chapter 7). In the input to the global router, each pin in the net list has been assigned to a specific position on a channel edge in the graph, including electrically equivalent pins. The global router makes full use of equivalent pins to minimize the routing length of a net. The global router minimizes the sum of the routing lengths of all of the nets subject to the satisfaction of the capacity constraints of the edges. The constraints result from the fixed widths of the channel edges.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    E. Lawler, “Combinatorial Optimization: Networks and Matroids,” (1976).zbMATHGoogle Scholar
  2. 1.
    E. S. Kuh and M. Marek-Sadowska, “Global Routing,” (1986).Google Scholar
  3. 2.
    R. Prim, “Shortest Connecting Networks and Some Generalizations,” (1957).Google Scholar
  4. 3.
    M. Vecchi and S. Kirkpatrick, “Global Wiring by Simulated Annealing,” (1983).Google Scholar
  5. 4.
    R. Karp, R. Leighton, R. Rivest, C. Thompson, U. Vazirani, and V. Vazirani, “Global Wire Routing in Two Dimensional Arrays,” (1983).Google Scholar
  6. 5.
    A. Ng, P. Raghavan, and C. Thompson, “A Specification Language for Describing Rectilinear Steiner Tree Configurations,” (1986).Google Scholar
  7. 6.
    P. Raghavan and C. Thompson, “Provably Good Routing in Graphs: Regular Arrays,” (1985).Google Scholar
  8. 7.
    A. Ng Raghavan, and C. Thompson, “Experimental Results for a Linear Program Global Router,” (1987).Google Scholar
  9. 1.
    A. Ng Raghavan, and C. Thompson, “Experimental Results for a Linear Program Global Router,” (1987).Google Scholar
  10. 2.
    P. Raghavan and C. Thompson, “Multiterminal Global Routing: A Deterministic Approximation Scheme,” (1987).Google Scholar
  11. 3.
    R. Prim, ”Shortest Connecting Networks and Some Generalizations,” (1957).Google Scholar
  12. 4.
    E. Dijkstra, “A Note on Two Problems in Connection with Graphs,” (1959).Google Scholar
  13. 5.
    E. Lawler, “Combinatorial Optimization: Networks and Matroids,” (1976).zbMATHGoogle Scholar
  14. 1.
    E. Lawler, “Combinatorial Optimization: Networks and Matroids” (1976).zbMATHGoogle Scholar
  15. 1.
    G. Srinath, “NLAGR,” (1986).Google Scholar
  16. 2.
    G. Srinath, “NLAGR,” (1986).Google Scholar

Copyright information

© Kluwer Academic Publishers, Boston 1988

Authors and Affiliations

  • Carl Sechen
    • 1
  1. 1.Yale UniversityUSA

Personalised recommendations