An Efficient Timing-Driven Global Routing Algorithm

In this paper, we propose an efficient timing-driven global routing algorithm. Unlike other conventional global routing techniques, interconnection delays are modeled and included during routing and rerouting process in order to minimize the routing area as well as to satisfy timing constraint. The timing-driven global routing problem is formulated as a multiterminal, multicommodity flow problem with integer flows and additional timing constraint. Two efficient timing-driven Steiner tree approach and one Steiner tree improving approach have been used to create initial routing results and reroute trees respectively. The algorithm has been implemented and the experimental results are quite promising.