United States Patent 55
`5,841,664
`Nov. 24, 1998
`[45] Date of Patent:
`Cai et al.
`
`[11] Patent Number:
`
`US005841664A
`
`[54] METHOD FOR OPTIMIZING TRACK
`ASSIGNMENTIN A GRID-BASED CHANNEL
`ROUTER
`
`[75]
`
`Inventors: Yang Cai, San Jose; Michael
`Chin-Hsen Lin, Fremont, both of Calif.
`
`[73] Assignee: Avant! Corporation, Fremont, Calif.
`
`[21] Appl. No.: 614,129
`
`[22]
`
`Filed:
`
`Mar. 12, 1996
`
`Int. Cho oceeeeeeeee GO6F 17/00; GO6F 15/50
`[51]
`[52] U.S. Ch oe 364/490; 364/488; 364/489;
`364/491
`[58] Field of Search oo... 364/488-491
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,615,011
`5,272,645
`5,375,069
`
`.oceccscecssssssssseessseessseeee 364/491
`9/1986 Linsker
`
`12/1993 Kawakamietal. .....
`.. 364/491
`12/1994 Sato et ab. ec ceeeeeteeee 364/490
`OTHER PUBLICATIONS
`
`Tong Gao & L. Liu. “Minimum Crosstalk Channel Rout-
`ing”. Jul. 11, 1993. Urbana, II.
`Peter M. Maurer. “Automatic Routing of Integrated Circuit
`Connections: A Tutorial”. Apr. 15, 1990. Tampa, FI.
`C.-L. Tse and W. Kinsner. “A graph—based heuristic channel
`router.” Sep. 1988. Amsterdam, The Netherlands.
`Howard H. Chen.“Breaking Cycles and Vertical Constraints
`in Deutsch’s New and More Difficult Channel—Routing
`Problems.” Aug. 14, 1989. Yorktown Heights, NY.
`
`T.W. Her & D.F. Wong. “On Over—the—Cell Channel Rout-
`ing with Cell Orientations Consideration.” Jun. 1, 1995. NY.
`
`P. Saratachandran “Dynamic Programming Approach for
`Multilayers Neural Network Optimization,” IEEE, pp.
`1397-1402, Jul. 1991.
`
`Primary Examiner—Kevin J. Teska
`Assistant Examiner—Vuthe Siek
`Attorney, Agent, or Firm—ThomasE. Schatzel; Law Offices
`of Thomas E. Schatzel
`
`[57]
`
`ABSTRACT
`
`track assignment in a grid-based
`A method for optimal
`channel
`router.
`Initially,
`interconnection information is
`extracted from a global routing result. Multiple pin nets
`derived from the interconnection information are decom-
`
`posed into simpler mapped segments. A channel grid map is
`then built and marked with existing objects. Next, a vertical
`constraint graph specifying the relative positions of the
`mapped segments is constructed. A first track is computed.
`A track assignment
`loop is repeated until all requisite
`connectionsare realized. The track assignmentloop includes
`the steps of breaking cycles and long paths and collecting a
`set of feasible links. One or more weighting functions are
`assigned to each suchfeasible link. A dynamic programming
`approach is used to select an optimal set of feasible links
`according to the weighting functions. In addition, an optimal
`set of feasible links corresponding to unpreferred layers is
`collected by applying dynamic programming. Finally, the
`chosen feasible links are physically realized on the current
`track.
`
`16 Claims, 6 Drawing Sheets
`
`
`
`| 06
`
`
`108
`le
`¥
`WEIGH FEASIBLE LINKS[~~
`
`EXTRACT CONNECTIONS
`
`
`COLLECT FEASIBLE LINKS
`
`
`107
`
`PROCESS VCG
`
`
` Y
`
`
`
`
`LY ¥
`
`
`
`102
`
`103
`
`104
`
`105
`
`BUILD CHANNEL GRID Map
`
`LY
`
`¥
`
`WARK CHANNEL GRID Mae
`
`
`
`BUILD VERTICAL CONSTRAINT v
`GRAPH
`
` Y
`
`DETERMINE FIRST ROUTING
`TRACK
`
`LU
`
`©
`
`(START
`
`Y
` y
`
`OPTIMIZE SELECTION OF
`FEASIBLE LINKS
`
`[\_,109
`
`COLLECT UNPREFERRED LAYER OF
`FEASIBLE LINKS
`
`
`IK_110
`
`REALIZE CHOSEN LINKS
`
`
`
`
`[-\“
`
`NO
`
`
`
`DETERMINE NEXT ROUTING
`TRACK
`
`y
`
`rN
`
`413
`
`
`
`
`UPDATE VCG
`
`"4
`
`Page | of 12
`
`FLEX LOGIX EXHIBIT 1042
`
`FLEX LOGIX EXHIBIT 1042
`
`Page 1 of 12
`
`

`

`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 1 of 6
`
`5,841,664
`
`START
`
`EXTRACT CONNECTIONS
`
`BUILD CHANNEL GRID MAP
`
`MARK CHANNEL GRID MAP
`
`BUILD VERTICAL CONSTRAINT
`GRAPH
`
`DETERMINE FIRST ROUTING
`TRACK
`
`101
`
`102
`
`103
`
`104
`
`105
`
`FIG.
`
`IA
`
`Page 2 of 12
`
`Page 2 of 12
`
`

`

`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 2 of 6
`
`5,841,664
`
`PROCESS VCG
`
`106
`
`COLLECT FEASIBLE LINKS
`
`WEIGH FEASIBLE LINKS
`
`OPTIMIZE SELECTION OF
`FEASIBLE LINKS
`
`COLLECT UNPREFERRED LAYER OF
`FEASIBLE LINKS
`
`
`
`
`
`
`
`
`
`REALIZE CHOSEN LINKS
`
`aon
`
`NO
`
`DETERMINE NEXT ROUTING
`TRACK
`
`UPDATE VCG
`
`Page 3 of 12
`
`107
`
`108
`
`109
`
`110
`
`111
`
`413
`
`114
`
`FIG.
`
`IB
`
`Page 3 of 12
`
`

`

`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 3 of 6
`
`5,841,664
`
`206
`
`203
`
`202
`
`201
`
`
`FIG. 2
`
`Page 4 of 12
`
`Page 4 of 12
`
`

`

`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 4 of 6
`
`5,841,664
`
`
`
`FIG. 4
`
`
`
`Page 5 of 12
`
`Page 5 of 12
`
`

`

`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 5 of 6
`
`5,841,664
`
`
`700 701
`
`yo703 704 705 706
`
`FIG. 7
`
`Page 6 of 12
`
`Page 6 of 12
`
`

`

`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 6 of 6
`
`5,841,664
`
`708
`
`ViVd
`
`AOVYOLS
`
`SOIAAG
`
`WNOIS
`
`LNdNI
`
`LNdLNO
`
`WNOS
`
`808
`
`TOYLNOD
`
`YOSsND
`
`£08
`
`108
`
`
`8‘Sls
`
`YOSSAN0Ud
`
`AV1dSId
`
`Ele)ela
`
`G08
`
`Page 7 of 12
`
`Page 7 of 12
`
`
`
`
`

`

`5,841,664
`
`1
`METHOD FOR OPTIMIZING TRACK
`ASSIGNMENTIN A GRID-BASED CHANNEL
`ROUTER
`
`FIELD OF THE INVENTION
`
`The present invention pertains to a method for optimizing
`the track assignment phase in a grid-based channel router.
`BACKGROUND OF THE INVENTION
`
`Advances in semiconductor technology have led the way
`towards more versatile, powerful, and faster integrated cir-
`cuit
`(IC) chips in the fields of computer systems,
`telecommunications,
`instrumentation, etc. The trend is
`towards even larger, more complex and sophisticated IC
`chips in an effort to meet and improve upon the demands
`imposedbystate-of-the-art performance. Today, a single IC
`chip can contain upwards of millions of transistors. As the
`complexity, functionalities, speed, and size of these chips
`increase, it is becoming a much more critical and difficult
`task to properly design, layout, and test the next generation
`of chips.
`In order to meet these demands, a highly specialized field,
`commonly referred to as “electronic design automation”
`(EDA), has evolved, whereby computers are extensively
`used to automate the design, layout, and testing process.
`Indeed, it has now cometo the point where the process has
`become so overwhelming that integrated circuits cannot be
`designed without the help of computer-aided design (CAD)
`systems. Computers are ideally suited to these tasks because
`they can be programmed to reduce or decomposelarge,
`complicated circuit designs into a multitude of much simpler
`functions. Whereupon, the computers can be programmed to
`iteratively solve these much simpler functions. In addition,
`CAD tools may then be employed to compact or otherwise
`minimize the die size required for a particular circuit.
`Minimizing the die size is important because as the die size
`shrinks, more dies(i.e., chips) can be fabricated from a given
`wafer. This directly translates into lower production costs.
`Typically, the process begins with an engineer defining
`the input/output signals, desired functionalities, and perfor-
`mance characteristics of the new IC chip. This information
`is fed into a logic synthesis program which generates a
`specification defining the integrated circuit in terms of a
`particular semiconductor technology (e.g., very large scale
`integration—VLSI). This specification can be regarded as a
`template for the realization of the physical embodimentof
`the integrated circuit
`in terms of transistors,
`routing
`resources, etc. Next, a place and route CAD toolis used to
`determine the routing, pinouts, wiring, interconnections and
`general physical layout of the chip.
`One common methodused in the layout of a chip involves
`a grid-based channel approach.In this approach, the routing
`area (i.e., the channel) of the chip is divided into a number
`of different metal layers. Each of the metal layers is com-
`prised of straight lines or “tracks” that run in one axis. For
`example, the metall and metal3 layers might have rows of
`tracks running horizontally, whereas the metal2 layer is
`comprised wholly of columns of tracks running vertically.
`Vias are used to connect the tracks of one metal layer to the
`tracks of another metal layer. Given this grid, one objective
`of the place and route process involves track assignment.
`The objective of track assignmentis to assign a feasible set
`of wires and vias for each track to achieve the best result.
`
`In the past, prior art grid-based channel routers have
`focused on using heuristic approaches to assigning tracks.
`However, these types of approaches tendedto be inflexible.
`
`10
`
`25
`
`30
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`What works well under certain circumstances will not work
`optimally under different circumstances. There typically was
`no method for weighting different design criteria.
`Furthermore, the channel routers could not satisfy more than
`a single objective at any given time. In addition, these prior
`art approaches typically lacked any kind of control mecha-
`nism. As a result,
`there was no easy control over layer
`assignment of wires, wiring patterns and crosstalk noises;
`nor was there any mechanism to control the wiring pattern
`of certain spacial or critical nets (e.g., CLOCK or RESET).
`In addition,
`there was no mechanism for the intelligent
`selection or trade-off between run time and quality. As a
`result, die size and performancesuffered.
`Thus, there is a need for a grid-based channel router that
`produces optimal
`track assignment.
`It would be highly
`preferable if such a router could produce optimal results,
`given any weighting function withoutrestriction on weight-
`ing criteria. The present invention offers such a grid-based
`channel router solution having the improved characteristics
`of optimality, versatility of weighting functions, flexibility
`of control, and selectivity of unpreferred layer wires.
`SUMMARYOF THE INVENTION
`
`The present invention pertains to a method for achieving
`optimal track assignment in a grid-based channelrouter. In
`a grid-based channel router, the routing area or channel is
`subdivided by horizontal and vertical straight lines to form
`grids. Each straight line is referred to as a track. The track
`assignment problem entails assigning a feasible set of wires
`and vias for each track to achieve the most optimal layout
`design of a VLSIcircuit.
`The initial step of the currently preferred embodimentof
`the present invention is to extract interconnection informa-
`tion from a global routing result. Multiple pin nets derived
`from the interconnection information are decomposed into
`simpler, mapped segments. A channel grid mapis then built
`and marked with existing objects. Next, a vertical constraint
`graph specifying the relative positions of the mapped seg-
`ments is constructed. Thereupon,a first track is computed. A
`track assignmentloop is repeated until all requisite connec-
`tions are realized. The track assignment loop includes the
`steps of breaking cycles and long paths and collecting a set
`of feasible links. One or more weighting functions are
`assigned to each feasible link. A dynamic programming
`approach is used to select an optimal set of feasible links
`according to the weighting functions. In addition, an optimal
`set of feasible links corresponding to unpreferred layers is
`collected by applying dynamic programming. Finally, the
`chosen feasible links are physically realized on the current
`track. If all connections have been made, the track assign-
`ment
`loop is finished. Otherwise,
`the vertical constraint
`graph is updated, the next routing track is determined, and
`the track assignment loop is repeated for this new routing
`track.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The present invention is illustrated by way of example,
`and not by wayof limitation, in the figures of the accom-
`panying drawings and in whichlike reference numerals refer
`to similar elements and in which:
`
`FIG. 1A is a flowchart describing the initial steps of the
`present invention for optimal track assignment in a grid-
`based channel router.
`
`FIG. 1B is a flowchart describing the steps of the track
`assignment cycle according to the currently preferred
`embodiment of the present invention.
`
`Page 8 of 12
`
`Page 8 of 12
`
`

`

`5,841,664
`
`3
`FIG. 2 shows a channel grid map that is comprised of
`three metal layers which are connected by a numberofvias.
`FIG. 3 shows an exemplary pin net as may be specified by
`the global routing result.
`FIG. 4 illustrates an example of information conveyed in
`a sample VCG.
`FIG. 5 shows a cycle consisting of three nodes.
`FIG. 6 shows three possible sets of feasible links for
`implementing a segment that connects two points.
`FIG. 7 shows a channel having a wire running through a
`grid line on a preferred metall layer and an unpreferred
`metal2 layer.
`FIG. 8 illustrates an exemplary computer system upon
`which the present invention may be implemented or prac-
`ticed.
`
`DETAILED DESCRIPTION
`
`track assignment process in a grid-based
`An optimal
`channel router is described. In the following description, for
`purposes of explanation, numerous specific details are set
`forth in order to provide a thorough understanding of the
`present invention. It will be obvious, however, to one skilled
`in the art that the present invention may be practiced without
`these specific details. In other instances, well-knownstruc-
`tures and devices are shown in block diagram form in order
`to avoid obscuring the present invention.
`FIGS. 1A and 1B are flowcharts describing the overall
`steps of the track assignment process according to the
`present
`invention. Initially in step 101,
`the connections
`information is extracted from a netlist specification that was
`generated accordingto the integrated circuit design. A global
`routing result specifies pin locations and which of the pins
`are to be connected. Next, the channel grid map is built in
`step 102. In the currently preferred embodiment, the channel
`grid map is comprised of three metal
`layers which are
`connected by a numberof vias, as shown in FIG. 2. The
`metall layer 201 and metal 3 layer 203 are comprised of
`horizontal tracks, whereas the metal 2 layer 202 is com-
`prised of vertical tracks. These horizontal and vertical tracks
`define an overlapping grid upon the routing or channelarea.
`Vias are used to connect the track of one metal layer to the
`track of another metal layer. For example, via 204 connects
`vertical track 205 of metal2 layer 202 to a horizontal track
`206 of the metal3 layer 203. The pins are connected to the
`metal2 layer 202 and routed through the metall and metal2
`layers to other points by meansofthe vias. It should be noted
`that the present invention may be applied to any numberof
`metal layers as well as different types of grid configurations.
`For purposes of track assignment,the pins are represented
`as points which are to be connected. Pin “nets” comprised of
`three or more interconnected pins, are decomposed into
`simpler combinations of two-pin subnets. These two-pin
`subnets are commonly known as “mapped segments.”
`Referring to FIG. 3, a particular pin net 301 might be
`specified by the global routing result. In this example, pin
`net 301 is comprised of three interconnected points
`302-304. This pin net 301 can be decomposed into two
`mapped segments, shown as 305 and 306. Mapped segment
`305 is comprised of a point-to-point connection 307 estab-
`lished between points 302 and 303. And mapped segment
`306 is comprised of a separate point-to-point connection 308
`that
`is established between points 303 and 304. Future
`processing is then performed on a mapped segmentbasis.
`Referring back to the flowchart of FIG. 2A, once the
`channelgrid maphas beenbuilt, existing objects (e.g., wires,
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`vias, etc.) are marked on the channel grid map, step 103.
`Next, a vertical constraint graph (VCG)is built according to
`the mapped segments. The VCG is used to maintain the
`relative positions of these segments inside the channel. An
`example of the information conveyed in a VCGis shown in
`FIG. 4. Two mapped segments 401 and 402 are shown.
`Mapped segment 401 is comprised of an interconnection
`between nodes 403 and 404, and mapped segment 402 is
`comprised of an interconnection between nodes 405 and
`406. In this example, the interconnection for mapped seg-
`ment 401 is comprised of metal2 (m2), metall (m1), and
`metal2 (m2) lines. Likewise, the second mapped segment
`402 is comprised of m2, m1, and m2 lines. However,it can
`be seen that the vertical m2 connection 407 corresponding to
`mapped segment 402 cannot extend beyond the vertical m2
`connection 408 of mapped segment 401. Otherwise, a short
`circuit would develop. The vertical m2 line of mapped
`segment 402 can extend throughout the range of 407, but
`cannot extend beyond the height of 407. A VCG is devel-
`oped to contain the vertical ordering of the lines for each
`mapped segment in order to prevent short circuits from
`occurring.
`After the VCG has been generated, thefirst track (i.e., a
`straight
`line of the grid along the channel direction) is
`computed, as shownin step 105 of FIG. 1A.In the currently
`preferred embodiment, tracks are assigned on an outside-in
`approach, wherebythe first track is the best track that is
`selected from either the top-most or bottom-most position.
`Next, a track assignment cycle is repeated until all the
`requisite track assignments are made. Thesteps of this track
`assignment loop are shown in FIG. 1B assteps 106-114.
`Basically, the VCG is processed, step 106. All feasible links
`are then collected, step 107. The feasible links are weighted
`according to one or more objectives, step 108. Next, an
`optimal set of feasible links is selected according to the
`results of the weighting functions, step 109. The feasible
`links corresponding to the unpreferred layers are collected,
`and the chosenlinksarefinally realized, steps 110-111. Step
`112 determines whether all connections have been com-
`
`the VCG is
`the loop is done. Otherwise,
`pleted. If so,
`updated, and the loop is repeated for the next routing track,
`steps 113 and 114.
`Amoredetailed description of the track assignment loop
`is now offered. The first step 106 of this loop is to process
`the VCG so that cycles and long paths are broken. FIG. 5
`showsa cycle consisting of three nodes 501-503. Node 1 is
`above node 3; node 3 is above node 2; and node 2 is above
`node 1. It can be seen that by following the sequence of
`connections, one returns back to the original starting point.
`In order to complete the routing, this cycle must first be
`broken. One example of how this cycle can be broken is
`depicted by implementing a node 1'. Node 1' breaks the path
`from node 3 to node 1. Consequently, node 1 is no longer
`above node 3. Likewise, longpaths must be broken. Long-
`paths consist of a sequenceoflines, all in the samedirection.
`Each node on the longpath is on a different row because one
`node is above the previous node. Hence, numerous rowsare
`consumed, unless the longpath is broken.
`The final goal of the channel routing problem is to
`complete all of the requisite routing within a minimal area
`(i.e., to minimize the die size). This is accomplished in the
`present invention on a row-by-rowbasis. Links are collected
`for each of the mapped segments. A link is either a vertical
`or horizontal connection. These links are used to render the
`
`point-to-point segments that were established earlier. Refer-
`ring back to FIG. 1B, step 107 calls for collecting all feasible
`links. A feasible link is defined as a complete or partial legal
`
`Page 9 of 12
`
`Page 9 of 12
`
`

`

`5,841,664
`
`5
`realization of mapped segments on the current track. There
`may exist many different feasible links for accomplishing a
`segment. For example, FIG. 6 showsthree possible sets of
`feasible links for implementing a segment 603 that connects
`point 601 to point 602. In the right-most set, feasible links
`605 and 606 connect point 601 to point 604, thereby forming
`a partial segment. Eventually, other feasible links must be
`implemented to connect point 604 to point 602.
`The feasible links are then weighted according to one or
`more metrics (see step 108 of FIG. 1B). A weight is a
`measurementof a pre-determined merit of the feasible links.
`A user assigns a “weight” to indicate the degree of impor-
`tance that is placed on variousattributes of the design. In
`other words, to each feasible link, a weight is assigned to
`measure the merit of having that particular feasible link
`being realized on the current track. In the present invention,
`there are no restrictions on how the feasible links are to be
`weighted. Weighting functions can be used to minimize
`congestion or channel density. For instance, a set of feasible
`links that achieves minimal congestion will result
`in a
`greater value than one which results in a great deal of
`congestion. Based on this information,
`the feasible links
`associated with less congestion is preferred over the set of
`feasible links having greater congestion. Weighting func-
`tions can also be used to reduce the wire length and via
`number. This can be used to improve performance.
`Likewise, they can be used to optimize vertical constraints
`(e.g., preference is weighted towards favoring longer Y
`lengths to yield better channel utilization). Furthermore,
`weighting functions can be used to exclude or discourage the
`selection of unfavorable feasible links. It should be noted
`that the present invention allows any combination of differ-
`ent objectives to be specified by the user.
`With the concept of feasible links and the choice of
`weighting functions, there are provided twolevels of flex-
`ible control mechanism over the behavior of the channel
`router. First, this provides a ready control mechanism over
`the layer assignment for wires, wiring patters and crosstalk
`noise problems. Also, by limiting the number of feasible
`links, one can arrive at the best trade-off between run time
`and quality. In addition,
`this mechanism can be used to
`control the wiring pattern of certain special or critical nets
`(e.g., CLOCK, RESET,etc.). This is becoming increasingly
`important as one advances into the deep submicron level,
`where the result of the channel router has to be carefully
`manipulated in order
`to satisfy stringent performance
`requirements.
`Based on the summed weighting functions, an optimalset
`of feasible links that can be legally realized as a whole on the
`currenttrack, is then selected (see step 109 of FIG. 1B). This
`set of feasible links is optimally selected by applying a
`dynamic programming approach. The dynamic program-
`ming approachentails reducing a large instance of a problem
`into several smaller instances of the problem; solving for the
`smaller instances and expandingthe solutions back to solve
`for the original, larger instance. A detailed description of
`dynamic programming can be found in the text book by
`Alto, Hopcroft, and Ullman, The Design and Analysis of
`Computer Algorithms, Addison-Wesley (1974). As an
`example, the dynamic programming approach can be used to
`solve for N columnsby recursively solving for N-1, N-2,
`N-3, etc. columns.
`the
`In order to further minimize the channel width,
`currently preferred embodimentof the present invention has
`the ability to optimally select wires in preferred layers as
`well as unpreferred layers. This step corresponds to block
`110 of the flowchart of FIG. 1B. As described above, each
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`the
`layer has a preferred direction. For instance,
`metal
`preferred direction for the metal2 layer is vertical; and the
`preferred direction for the metall and metal3 layers is
`horizontal. A wire running throughthe grid line of a channel
`can exist either on the preferred layer or on an unpreferred
`layer that runs in a different direction. In other words,
`unpreferred layer wires are used in channel routing to share
`tracks with preferred layer wires to reduce the channel
`width.
`
`FIG. 7 shows a channel 700 having a wire running
`through a grid line on a preferred metall layer and an
`unpreferred metal2 layer. Normally, most of the pins
`701-706 are connected to the metal2 layer. Consequently,
`the metal2 layer is usually reserved for these pin connec-
`tions. Other connections are made through the metall and
`metal3 layers. However, under certain circumstances, a track
`may run through two different layers—a preferred layer and
`an unpreferred layer. For example, there are no pins in area
`707. Hence, track 708 can contain a metall wire 709 and a
`metal2 wire 710. In this example, the metal2 wire is in the
`unpreferred layer. Furthermore, since the metal2 layer can
`operate with the metall layer,
`the metal2 wire does not
`occupy any additional space of the channel. This serves to
`minimize the die size. In the track assignment process,
`unpreferred layer wires are chosen in the dynamic program-
`ming approach along with the preferred layer wires. Unpre-
`ferred layer wires are also selected in a second phase where,
`for each chosen preferred layer wire, an optimallegal set of
`unpreferred layer wires covered by it is chosen, again by
`using a dynamic programming approach. Utilizing as many
`unpreferred layer wires as possible will help reduce the
`channel width.
`
`The chosen set of optimal links are finally physically
`realized on the current track (see step 111 of FIG. 1B). This
`is accomplished by converting the feasible links into physi-
`cal wires and vias with nonzero dimensions. A determination
`is then made as to whether all connections have been made,
`step 111. If so,
`then the loop ends. Otherwise,
`the next
`routing track is determined, step 113. The vertical constraint
`graph is updated, step 114. The track assignment loop of
`steps 106-112 is repeated for the next track.
`FIG. 8 illustrates an exemplary computer system 800
`upon which the present invention may be implemented or
`practiced. It is appreciated that the computer system 800 of
`FIG. 8 is exemplary only and that the present invention can
`operate within a number of different computer systems
`including general purpose computers systems, embedded
`computer systems, and computer systems specially adapted
`for electronic design automation.
`Computer system 800 of FIG. 8 includes an address/data
`bus 809 for conveying digital
`information between the
`various components,a central processor unit (CPU) 801 for
`processing the digital information and instructions, a ran-
`dom access memory (RAM) 802 for storing the digital
`information and instructions, a read only memory (ROM)
`803 for storing information and instructions of a more
`permanent nature. In addition, computer system 800 may
`also include a data storage device 104 (e.g., a magnetic,
`optical, floppy, or tape drive) for storing vast amounts of
`data, and an I/O interface 808 for interfacing with peripheral
`devices (e.g., computer network, modem,etc.). It should be
`noted that the present invention may be embodied Devices
`which may be coupled to computer system 800 include a
`display device 805 for displaying information (e.g., channel
`grid map, vertical constraint graphs, weighting functions,
`feasible links, etc.) to a computer user, an alphanumeric
`input device 806 (e.g., a keyboard), and a cursor control
`
`Page 10 of 12
`
`Page 10 of 12
`
`

`

`5,841,664
`
`7
`device 807 (e.g., mouse, trackball, light pen, etc.) for input-
`ting data and selections.
`The foregoing descriptions of specific embodimentsof the
`present
`invention have been presented for purposes of
`illustration and description. They are not intended to be
`exhaustive or to limit the invention to the precise forms
`disclosed, and obviously many modifications and variations
`are possible in light of the above teaching. The embodiments
`were chosen and described in order to best explain the
`principles of the invention and its practical application, to
`thereby enable others skilled in the art to best utilize the
`invention and various embodiments with various modifica-
`
`tions as are suited to the particular use contemplated. It is
`intended that the scope of the invention be defined by the
`claims appended hereto and their equivalents.
`Whatis claimedis:
`1. A grid-based method for routing wire connections
`through a routing channel area between nodes by an auto-
`mated 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 decomposedinto a plurality of mapped
`segments each comprising two-pin subnets, and
`wherein said mapped segments are each directly vec-
`tored 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 cur-
`rently 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 byfirst break-
`ing cycles and longpaths between said nodes to reduce
`the numberof interconnections with said channel rout-
`
`10
`
`15
`
`20
`
`25
`
`40
`
`45
`
`50
`
`ing 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
`
`55
`
`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 ver-
`tical wire segmentlinks with ideal zero line widths are
`
`60
`
`65
`
`8
`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 indi-
`vidual feasible horizontal and vertical wire segment
`links with ideal zero line widths by assigning a finite
`line width to each.
`2. The method of claim 1, wherein:
`the weighting function is used to minimize congestion.
`3. The method of claim 1, wherein:
`the weighting function is used to minimize channel
`density, wherein the channel is comprised of a routing
`area of the layout.
`4. The method of claim 1, wherein:
`the weighting function is used to minimize wire lengths.
`5. The method of claim 1, wherein:
`the weighting function is used to minimize a numberof
`vias.
`6. The method of claim 1, wherein:
`the weighting function is used to optimize vertical con-
`straints.
`7. The method of claim 1, further comprising the steps of:
`assigning a combination of a plurality of weighting func-
`tions;
`selecting optimal feasible links according to the combi-
`nation of weighting functions.
`8. The method of claim 1 further comprising the step of:
`limiting a number of feasible links to characterize run
`time and quality of the layout.
`9. The method of claim 1, further comprising the steps of:
`selecting and implementing a set of unpreferred layer
`wires by using a dynamic programming approach.
`10. In a computer implemented channelrouter for design-
`ing a circuit, a method of assigning a set of wires and vias
`for a plurality of tracks of a channel routing area, comprising
`the steps of:
`a) breaking cycles and long paths associated with mapped
`segments which define interconnections of the circuit;
`b) determining a plurality of feasible links corresponding
`to the mapped segments for a current track;
`c) applying one or more weighting functions to the
`feasible links, wherein the weighting functions measure
`a merit of realizing a particular feasible link onto the
`current track;
`d) selecting an optimal set of feasible links according to
`the weighting functions;
`e) realizing the optimal set of feasible links;
`f) repeating steps a—e until each connection ofthe circuit
`has been routed; and
`g) determining a set of preferred layer wires and a set of
`unpreferred layer wires by using dynamic
`programming, wherein an unpreferred layer wire shares
`a sametrack as a preferred layer wire;
`wherein, the weighting functions include a combination
`of criteria for minimizing channel density, minimizing
`wire length, minimizing a numberofvias, optimizing
`vertical constraints, and discouraging selection of unfa-
`vorable feasible links.
`11. The method of claim 10 further comprising the steps
`
`of:
`
`extracting interconnection information from a