Subgrid detailed routing

Abstract

Disclosed is a subgrid detailed router that performs searches for wire locations at the grid level. Once a solution is found, the wire is placed in a based upon a finer subgrid. Specifically, the present invention includes subgrids that in a preferred embodiment have a resolution that is 16×greater than the resolution of the conventional grids. This increased resolution is useful for improving routing density with variable width and variable spacing designs. In operation, the subgrid detailed router of the present invention searches at the grid level for potential wire paths using a code associated with each grid. This code contains data corresponding to each of the subgrids, such that upon completion of a routing a net, information exists that allows for the placement of the net at locations corresponding to the subgrid that has finer resolution than the grid which was used to implement the routing search. Thus, the present invention is as efficient as conventional grid based routers in finding an appropriate path.

We claim:  
     
         1 . A method of automatically extending a wire location representation from one grid to another grid comprising: 
 comparing a first plurality of subgrid indicia associated with certain subgrids of the one grid with a second plurality of subgrid indicia associated with certain subgrids of the another grid to determine whether the wire representation can be extended from the one grid to the another grid, wherein each of the subgrid indicia indicates one of availability and nonavailability of a corresponding wire portion representation and the first plurality of subgrid indicia and the second plurality of subgrid indicia are adjacent to each other.