A Timing Driven Congestion Aware Global Router

The multi-net Global Routing Problem (GRP) is a problem of routing a set of nets subject to resources and delay constraints. Many modern routers use FLUTE (Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design) as the basic method to construct Steiner trees. Here we first give another method MAD (Modified Algorithm Dijkstra) to construct timing-driven Steiner trees for each net. The Elmore delays of the trees constructed by MAD and FLUTE are almost same. Next we describe the Gradient algorithm which is used to reduce the congestion. We implemented our algorithm on ISPD 98 benchmarks and compared the wire length and maximum overflow of our router with Labyrinth Predictable Router. Our router performs better in terms of wire length and is much faster.