A New Two-Dimensional Routing Algorithm

A new heuristic algorithm for two-dimensional routing utilizing two distinct layers is described. It is assumed that all terminals are on the boundary of a rectilinear routing region with or without cutout sections. Terminals on vertical boundary segments are assumed to be on one layer and those on horizontal boundary segments are on the other layer. This algorithm finds all possible paths with minimum corners for a net and then chooses one of those paths by considering path length, the likelihood of blocking nets not yet routed, the usage of vacant tracks, and the necessity of going through an area expected to be congested. A dynamic data structure is maintained. If h and v are the numbers of horizontal and vertical tracks, n is the number of nets, and t is the number of terminals, then the storage requirement is o(hv) and the time complexity is o((t-n)hv). For h=23, v=64, n=47, and t=130 the storage required is 60K bytes and cpu time is 16 seconds. This algorithm is implemented in the C language on a VAX 11/780 under the Berkeley Unix (FOOTNOTE: Unix is a trademark of Bell Laboratories.) Operating system, as part of the LTX layout system of the layout aids group at Bell Laboratories, Murray Hill.