Patent ID: 7661085

Claim:
A method for performing global routing on an integrated circuit design, said method comprising: dividing said integrated circuit design into a plurality of G-cells using a computer system, wherein said plurality of G-cells are interconnected by a plurality of nets; decomposing said plurality of nets into a plurality of corresponding wires; prerouting some of said wires to connect said plurality of G-cells; initiating a box around a region of said integrated circuit design in which wires are most congested; performing a BoxRouting routine starting with wires within said box until all wires within said integrated circuit design are routed, wherein said BoxRouting routine includes performing progressive integer linear programming (ILP) routing to route as many unrouted wires within said box as possible without incurring routing congestion; performing adaptive maze routing to route any remaining unrouted wire within said box after said ILP routing performance; and performing box expansion to expand said box on every direction such that a new box covers all of said box; and performing postrouting on wires within said integrated circuit design.