Method for optimizing track assignment in a grid-based channel router

Claim 1

A grid-based method for routing wire connections through a routing channel area between nodes by an automated computer design system, the method comprising the steps of: extracting from an externally supplied netlist specification a set of wire connection information that relates to a particular semiconductor integrated circuit design, wherein nodes that are described to be interconnected in pin-nets are decomposed into a plurality of mapped segments each comprising two-pin subnets, and wherein said mapped segments are each directly vectored between a pair of pins in a two-pin subnet; building a channel grid map comprised of a plurality of metal layers interconnectable by a plurality of vias, wherein each metal layer defines a system of horizontal tracks or vertical tracks with one system of horizontal tracks or vertical tracks being preferred over another in particular metal layers, and such systems of horizontal tracks and vertical tracks in all said metal layers together defining an orthogonally overlapping grid within a channel routing area, and wherein individual said vias are used to connect a track of one metal layer to a criss-crossing track of another metal layer; earmarking any existing wires and vias on said channel grid map; building a vertical constraint graph (VCG) that identifies which portions of each vertical track in each of a corresponding said plurality of metal layers have already been earmarked for use by previously routed mapped segments, wherein a mapped segment currently being routed is constrained from using any already-earmarked portions of said vertical tracks in said plurality of metal layers; computing a plurality of track assignments by first breaking cycles and longpaths between said nodes to reduce the number of interconnections with said channel routing area to complete a particular pin net according to said netlist specification, then by assigning a feasible set of wires and vias for each track to achieve a particular result; controlling a layer assignment process through the use of a selected set of weighting functions chosen for each said metal layer to balance a plurality of objectives in a final design, and that provides a mechanism for an intelligent trade-off between computer run time and design-result quality; completing all of a requisite routing within a minimal channel routing area on a row-by-row basis wherein a zigzag chain of individual feasible horizontal and vertical wire segment links with ideal zero line widths are assembled according to said layer assignment process and that attempt to approximate a direct vector of each said mapped segment; and physically realizing each of said zigzag chains of individual feasible horizontal and vertical wire segment links with ideal zero line widths by assigning a finite line width to each.