An efficient tile-based ECO router using routing graph reduction and enhanced global routing flow

Engineering change order (ECO) routing is frequently requested in the later design stage for the purpose of delay and noise optimization. ECO routing is complicated as a result of huge existing obstacles and the requests for various design rules. The tile-based routing model results in fewer nodes of the routing graph than grid and connection-based routers; however, the number of nodes of the tile-based routing graph has grown to over a billion for system-on-chip designs, while no notable progress has been achieved in the routing speed of the tile-based router since it was proposed. This paper first proposes a novel routing graph reduction (RGR) method for promoting tile propagation speed and then depicts a new ECO routing design flow with RGR and enhanced global routing flow (EGRF). RGR can be used to remove redundant tiles as well as align and merge neighboring tiles in order to diminish tile fragmentation such that the tile-based ECO router can run twice as fast while still producing an optimal path. Compared with a commercial placement and routing tool, the proposed tile-based router with RGR obtains better routing performance and routing quality for three ECO routings. EGRF incorporates ECO global routing considering via-resource congestion metric with extended routing and global cell (GCell) restructuring to prevent routing failure in routable designs. The ECO router with the proposed design flow can perform up to 20 times faster than the original tile-based router at the cost of only a slight decline in routing quality. Experimental results also demonstrate that a more congested layout tends to have higher graph reduction rate. Also discussed herein are further refinements by dynamic weighting of via and wire resources based on the vacancy density of the routed design and further application of RGR to multiple-net routing.