ECO routing based on network flow method

Abstract

In this paper, a new ECO routing approach to the problem of resolving pin inaccessibility on standard cells is presented. The conventional ECO routing approaches conceptually divide the rerouting path search problem for a set of target nets to rip-up and reroute into two interdependent tasks: (i) (Off-cell routing) repairing the routing path between the net terminal outside of the cell and the cell boundary and (ii) (On-cell routing) repairing the routing path between the cell boundary and the pin on the cell where they have conventionally performed tasks (i) and (ii) iteratively for each target net. Yet, there is no easy way to accurately predict the final result of task (ii) for all nets during task (i). In our approach, we place the primary importance on resolving pin inaccessibility on cells. Consequently, we perform on-cell routing for all ripped-up nets simultaneously to resolve the pin inaccessibility first by utilizing flexible cell boundary access points and then to adjust the sub-paths outside of the cell. For a number of benchmark circuits, it is shown that our approach of early consideration of entire on-cell routing is very effective, resolving the pin inaccessibility of 71.09% out of all nets for which a commercial ECO router has failed to find legal routes.