Method and Apparatus for Global Routing of an Integrated Circuit

Physical Sciences : Electrical

Available for non-exclusive licensing


  • Zhigang Pan, Ph.D. , Electrical and Computer Engineering
  • Minsik Cho, M.S. , Electrical and Computer Engineering

Background/unmet need

Global routing is a key step in the physical design of integrated circuits (ICs) and is necessary to plan the overall wiring and routing configuration.

Invention Description

This invention discloses a novel method and apparatus to perform global routing for lCs. This invention has several key features for better global routing; namely, PreRouting, BoxRouting, and PostRouting. The PreRouting step routes simple and unambiguous nets first, and also obtains rough congestion estimations. The BoxRouting step is performed in an incremental and progressive manner. BoxRouting starts from the most congested regions and places that portion in a routing box. The box is then gradually expanded until the entire chip is covered. This is accomplished by a progressive integer linear programming (ILP) formulation. The BoxRouting results are further improved through a PostRouting step, which smoothly trades off wire length and congestion.


  • Effective in improving the quality of results and turnaround time
  • Can also be combined with placement and other design steps to allow more effective design closure


  • The progressive nature of BoxRouting differs from traditional hierarchical approaches which divide the circuit into same-sized pieces.
  • BoxRouting uses a routing box and box expansion starting from the most congested region, and focuses on the circuit enclosed by the routing box.

Market potential/applications

Integrated and VLSI (very large scale integration) circuit designers and manufacturers

IP Status