This chapter discusses the basics of global routing formulation and a high-level overview of global routing algorithms and presents a global routing grid model and describes how to set the edge capacities in such a model. It also discusses the common objectives of global routing algorithms and also describes algorithms to route a single net, with a particular focus on maze routing and its extensions. The chapter provides a high-level overview of algorithms to route multiple nets and explores good congestion metric needs to consider not only the edge capacities, but also through capacities. It also describes each interconnect layer is used for either horizontal or vertical connections. Global routing is typically represented as a graph problem to capture the adjacencies and capacities of the routing region. The channel capacity indicates the number of nets that can use this channel without overflow, and the channel length indicates the amount of wirelength necessary to pass through this channel.
|Title of host publication||Handbook of Algorithms for Physical Design Automation|
|Editors||Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar|
|Place of Publication||Boca Raton ; London ; New York|
|Number of pages||18|
|ISBN (Print)||9780849372421, 9780367403478|
|Publication status||Published - 11 Nov 2008|