Global Routing Formulation and Maze Routing

Muhammet Mustafa Ozdal, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingChapterpeer-review


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.
Original languageEnglish
Title of host publicationHandbook of Algorithms for Physical Design Automation
EditorsCharles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar
Place of PublicationBoca Raton ; London ; New York
PublisherCRC Press
Number of pages18
ISBN (Electronic)9780429118173
ISBN (Print)9780849372421, 9780367403478
Publication statusPublished - 11 Nov 2008


Dive into the research topics of 'Global Routing Formulation and Maze Routing'. Together they form a unique fingerprint.

Cite this