Patent ID: 8001514

Claim:
A method for computing a routability estimation across a collection of local routing regions associated with a circuit layout, comprising: selecting a first local routing region associated with a route overflow, wherein a respective local routing region is associated with an estimation of a number of route overflows for routing layers in a region of the circuit layout, wherein the first local routing region includes an overflowing routing layer which is associated with an overflow of k or more routes in a direction d, and wherein a respective routing layer is associated with a preferred direction D and is associated with either an overflow of R routes or an excess capacity of C routes; identifying a second local routing region, wherein the second local routing region has an excess capacity in the direction d to accommodate the overflow in the overflowing routing layer, wherein an excess path exists between the overflowing routing layer of the first local routing region and the second local routing region, and wherein the excess path is orthogonal to the direction d; transferring the overflow value k away from the overflowing routing layer to the second local routing region; computing a global overflow cost which involves summing route overflows across every layer of every local routing region; and computing an adjacent overflow cost which involves summing values of a cost function across a number of clusters of adjacent local routing regions with route overflows, wherein a value of the cost function for a cluster depends on a number of local routing regions in the cluster and a sum of the overflows across the cluster; and computing, by computer, a global routability estimation as a function of the global overflow cost and the adjacent overflow cost.