1111111111111111 IIIIII IIIII 11111 1111111111 11111 1111111111 11111 11111 111111111111111 11111111
`US 20070028201Al
`
`c19) United States
`c12) Patent Application Publication
`Mehrotra et al.
`
`c10) Pub. No.: US 2007/0028201 Al
`Feb. 1, 2007
`(43) Pub. Date:
`
`(54) ENHANCED ROUTING GRID SYSTEM AND
`METHOD
`
`(75)
`
`Inventors: Sharad Mehrotra, Cedar Park, TX
`(US); Parsotam T. Patel, Austin, TX
`(US); Joe T. Rahmeh, Austin, TX (US)
`
`Correspondence Address:
`J. SCOTT DENKO
`ANDREWS & KURTH LLP
`111 CONGRESS AVE., SUITE 1700
`AUSTIN, TX 78701 (US)
`
`(73) Assignee: Staktek Group L.P.
`
`(21) Appl. No.:
`
`11/477,078
`
`(22) Filed:
`
`Jun.28, 2006
`
`Related U.S. Application Data
`
`(63) Continuation-in-part of application No. 11/148,911,
`filed on Jun. 9, 2005.
`
`Publication Classification
`
`(51)
`
`Int. Cl.
`G06F 17150
`
`(2006.01)
`
`(52) U.S. Cl. ................................. 716/12; 716/13; 716/14
`
`(57)
`
`ABSTRACT
`
`Routing systems and methods are provided having various
`strategies for optimizing and evaluating possible routes for
`netlist connections. In one embodiment, a data structure or
`matrix provides cost related data weighted to evaluate the
`impact proposed a connection or segment will have upon an
`attribute of interest such as, for example, speed, manufac(cid:173)
`turability or noise tolerance. This cost information can be
`related to terrain costs as well as shape costs to provide
`multidimensional cost information for connections. Process(cid:173)
`ing such higher information cost data is made more efficient
`with an additive process that is less demanding than a
`computationally intensive iterative multiplication process.
`Various methods are also disclosed for shifting and adjusting
`routing grids to improve use of available space or reduce run
`time in routing. In another embodiment, a parallel process(cid:173)
`ing scheme is used to process multiple regions on multiple
`processors simultaneously without creating conflicts, that
`could arise, for example, when two processors try to route a
`trace on the same gridpoint. In another embodiment, various
`methods are used to spread nets over one or more wiring
`layers.
`
`1301
`,----------..........
`Perform Global Routing
`For One Or More Sets
`Of One Or More Traces
`
`Begin Processing Global
`Routing Sets
`
`Apply Sparse Grid Technique
`To Global Route To
`Produce Sparse Grid
`
`1304
`.------~~----L....,
`Apply Detailed Subgrid,
`Other Modified Grid
`Technique To Produce
`Modified Grids
`
`1305
`, - - - - -~ - - - - - ' - - - - - .
`
`Divide Global Route Into
`Parallel Processing Areas
`Which May Have Boundaries
`Along Boundaries Of Sparse
`Grid(s)
`
`Parallel Processing Of Route
`Searches
`
`Yes
`
`Page 1 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 1 of 24
`
`US 2007/0028201 Al
`
`12~
`
`8
`6
`
`14
`
`~18
`
`FIG. 1A
`
`Page 2 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 2 of 24
`
`US 2007/0028201 Al
`
`8
`6
`
`14
`
`(1, 100)
`
`16
`
`FIG. 1B
`
`Page 3 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 3 of 24
`
`US 2007/0028201 Al
`
`12"
`
`22
`
`200nm
`
`6
`
`Offset
`100nm
`
`FIG. 2
`
`Page 4 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 4 of 24
`
`US 2007/0028201 Al
`
`36~35, 33\ 33\ 35,
`/14
`
`36_/
`32~
`36_/ 35J
`
`.,,,.-33
`~34r .t;34r '.1(34
`r
`L ~3.1 _j L ~
`.,,.-35
`
`v14
`
`v14
`
`~6
`
`~ 8
`
`/33
`
`36__,,J'
`
`38/ 38/
`
`38/
`
`FIG. 3A
`
`Page 5 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 5 of 24
`
`US 2007/0028201 Al
`
`X
`
`6
`
`8
`
`FIG. 38
`
`Page 6 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 6 of 24
`
`US 2007/0028201 Al
`
`12~
`
`41\
`
`(4)\
`
`(4)\ £3\ (3)►\ l
`
`s'\
`
`(3)\ ~f2
`7~
`e 1
`
`(1)~ £1, •
`
`T
`
`(1)\
`
`(2);\ l
`
`FIG. 4
`
`Page 7 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 7 of 24
`
`US 2007/0028201 Al
`
`10
`
`T
`
`10
`
`A
`
`R
`
`s
`
`10
`
`10
`
`A
`
`10
`
`10
`
`10
`
`FIG. 5
`
`Page 8 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 8 of 24
`
`US 2007/0028201 Al
`
`.r62
`
`1
`
`1
`
`1
`
`1
`
`0 D D D D D
`
`0 D D D
`
`0
`
`1
`
`1
`
`1
`
`1
`
`D
`
`0
`
`0
`
`0 D
`
`0 D
`
`0
`
`0
`
`0
`
`0
`
`D
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0 D D D D
`
`0 D D D D
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0 D
`
`0
`
`0
`
`0 D 0 D 0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0 D
`
`0 D
`
`0
`
`0
`
`64
`
`6,'_/
`
`64
`
`FIG. 6A
`
`Page 9 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 9 of 24
`
`US 2007/0028201 Al
`
`,r62
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`1
`
`0
`
`0
`
`0
`
`0
`
`1
`
`1
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`1
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`1
`
`0
`
`0
`
`0
`
`1
`
`0
`
`0
`
`0
`
`-
`
`0
`68- 0
`0
`0
`
`0
`
`0
`
`1
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`14, 0
`0
`
`68
`~
`74J
`
`68
`
`"
`
`0
`
`0
`
`0
`
`0
`
`0
`
`63"i
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0~
`66
`
`68
`
`0
`
`" 0
`
`0
`
`0
`
`0
`
`/
`
`61
`
`FIG. 68
`
`Page 10 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 10 of 24
`
`US 2007/0028201 Al
`
`.. 1s""""'-------------~:---- 76'\ _____________ r9"'-- < - - - : 77
`!
`77 !
`:
`:
`:
`~
`I
`I
`I ~ i
`, ________________________ : _____________ , 77
`t ~
`
`1-1 72
`
`I
`
`:
`
`I
`t
`I
`
`I
`
`66
`
`77
`
`71
`
`77
`
`i 0
`['-11
`
`•-------------------~ ____ J
`
`74
`
`70
`
`IFDG. l
`
`Page 11 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 11 of 24
`
`US 2007/0028201 Al
`
`r 801
`..
`Perform Global Routing
`Search
`
`,,
`rB 02
`Determine Presence Of One
`Or More Large Unblocked
`Fields Along Global Route
`,,
`rB 03
`Apply Sparse Routing Grid
`Over Normal Routing Grid
`For Each Unblocked Field
`
`,B 04
`••
`Search For Desired Routes
`On Combined Grids
`
`,B 05
`n
`Store Traces In Normal
`Routing Grid Structure
`
`,,
`rB 06
`Remove Sparse Routing
`Grid Structure
`
`FIG. 8
`
`Page 12 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 12 of 24
`
`US 2007/0028201 Al
`
`.,
`
`~ ; [ j
`/ ~ ~
`,I ~-v
`~l--"
`~
`
`; ~ ;
`; L,
`; L,
`
`/
`/
`/
`
`lO
`O')
`fj- -- -- -- -- -- --
`
`L, L,
`L,
`
`t----
`/V
`
`~ O')
`
`-- -- --
`
`-- -- -
`
`1,
`
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`L--
`
`,_ __ .. --
`
`._ __ .. --
`
`/I; 1,-v
`~~ /V
`~~
`~
`f:;
`.,v
`~ L,
`~ r---
`~ -
`
`L,
`
`L,
`
`/
`
`L,
`
`~ L, ! L,
`
`~
`I::
`
`~ ~/ ~
`L, ._,
`-- -~ ') - -- -- --
`~-
`~ I/
`I/ ~
`~ /
`I;:: t-- f\
`~ L,
`
`L, ,I
`
`L,
`
`L,
`
`I/
`I/
`I/ ,I
`I/ ,I
`
`C"')
`O')
`
`; - -- -- --
`
`/ /
`
`/I<
`I'-,
`/ /
`lO
`/
`; / O')
`
`/ / i--...
`/ / \
`~ / ~
`/ / a-.
`
`r-....
`0)
`l.)
`
`--
`
`c:o
`0)
`~
`
`t
`I
`I
`
`-- J
`
`~
`O')
`l.)
`
`--
`
`"-I
`
`- O') LJ
`
`I
`I
`I
`
`1--- -- --
`
`I
`I
`I
`
`-- -- -- --
`
`-- -- -
`
`~-
`co
`co
`co
`
`I
`I
`
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`
`I
`I
`
`/P
`
`; /
`
`,, /
`,, /
`v/
`l,'l/
`~ t;':
`"t:": "v
`"
`i,,v
`
`L, /
`
`/
`
`. / / /I
`V/,-
`
`---\- -- --
`
`r-....
`O')
`
`co
`co
`
`I
`I
`I
`I
`
`L--~-- --
`
`(
`,...
`C\I
`
`{ ( (
`
`, I~
`":,,
`:::~r--.
`'\. ,.._
`-- -- -- -- -- -- --
`
`O')
`
`I
`
`---•
`
`Page 13 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 13 of 24
`
`US 2007/0028201 Al
`
`.,
`
`Designate Two Or More Areas
`For Processing In First Period
`
`1~
`
`Designate Two Or More Areas
`For Processing In Second Period
`
`,,
`Divide Any Traces That -
`Cross Adjacent Areas Into
`Subtraces
`
`r 1001
`
`r 1002
`
`r 1003
`
`,,
`Route Traces And Subtraces
`In First Processing Period Areas
`In Parallel
`
`r 1004
`
`1,
`Route Traces And Subtraces
`In Second Processing Period Areas
`In Parallel
`
`r 1005
`
`FIG. 10
`
`Page 14 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 14 of 24
`
`US 2007/0028201 Al
`
`co
`,._
`<:::)
`,._
`
`• •
`• •
`
`C\11
`
`•--------------------
`
`,_
`,_
`
`• •
`
`C\11
`
`~ ,.._
`,.._
`
`CC\J ~
`,.._,.._ ,.._
`,._,.._ ,.._
`,._,.._,.._
`
`Page 15 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 15 of 24
`
`US 2007/0028201 Al
`
`1220
`
`I
`I
`I
`I
`I
`I
`
`I
`
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`
`I
`
`I
`I
`I
`I
`
`H-+ 1222
`+--t---1
`
`I 1224.
`•
`H-+
`•
`+-H12oa~:
`I
`I
`•
`
`I
`I
`I
`I
`I
`
`I
`I
`
`I
`I
`I
`I
`I
`I
`
`I
`I
`
`----11---
`--- "'-1226
`
`------- --
`
`\...1214
`
`1218
`
`..-1206
`✓
`••••••
`
`~1210
`••••••
`
`\...
`
`1202
`
`\
`'---
`
`1204
`
`FIG. 12
`
`11216
`
`• • •
`1212/:
`•
`
`Page 16 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 16 of 24
`
`US 2007/0028201 Al
`
`1301
`
`1302
`
`1303
`
`1304
`
`1305
`
`1306
`
`Perform Global Routing
`For One Or More Sets ..
`Of One Or More Traces·_·
`
`Begin Processing Global
`Routing Sets
`
`Apply Sparse Grid Technique
`To Global Route To
`Produce Sparse Grid
`
`Apply Detailed Subgrid,
`Other Modified Grid
`Technique To Produce
`Modified Grids
`
`Divide Global Route Into
`Parallel Processing Areas
`Which May Have Boundaries
`Along Boundaries Of Sparse
`Grid(s)
`
`Parallel Processing Of Route
`Searches
`
`1308
`
`End
`
`FIG. 13
`
`Page 17 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 17 of 24
`
`US 2007/0028201 Al
`
`8
`
`8
`
`1
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`f
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`
`!~149
`
`I
`I
`I
`I
`
`149
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`
`IFDG. 14
`
`Page 18 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 18 of 24
`
`US 2007/0028201 Al
`
`151
`151
`
`· l.
`
`l
`
`~ -
`
`:
`
`~
`
`I- - -
`
`152
`
`- -
`...
`...
`153/
`
`- --
`..
`..
`-
`"-153
`
`FIG. 15
`
`151
`151
`..
`- - - - -
`
`.l
`
`~
`
`~
`
`152
`
`- - - - -
`-
`
`...
`
`FIG. 16
`
`Page 19 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 19 of 24
`
`US 2007/0028201 Al
`
`1701
`
`Begin Route Search
`For Trace Preferably
`Having X-shape
`
`1703
`
`Yes
`Mark With Normal
`~-~ Cost And Proceed
`With Search
`
`-1705
`
`Yes
`
`Mark With Cost
`Of Lowest Cost
`Allowed Shape
`And Proceed
`With Search
`
`1702
`
`Query
`Gridpoint.
`Does Gridpoint Allow
`Placement Of
`X-shape
`?
`No
`
`Does
`Gridpoint Allow
`Placement Of Any
`Alternative
`Shape
`?
`No
`
`1706
`
`Grid point
`Is
`Blocked
`
`FIG. 17A
`
`Page 20 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 20 of 24
`
`US 2007/0028201 Al
`
`1710
`
`1750
`
`1760
`
`"-1740
`
`1710
`
`1700
`
`FIG« 178
`
`Page 21 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 21 of 24
`
`US 2007/0028201 Al
`
`11910
`
`Initial Routing
`
`,,
`
`~ 1920
`
`Ripup - Reroute
`
`,,
`
`f 1930
`
`Layer Balancing
`
`,.,
`
`( 1940
`
`Detailed Routing
`
`FIG. 19
`
`Page 22 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 22 of 24
`
`US 2007/0028201 Al
`
`2010
`
`2020
`
`2025
`
`2030
`
`Begin Initial Routing
`
`Prioritize Nets For Initial
`Routing
`
`Order Pairs Of Adjacent
`Layers
`
`Select Highest Priority
`Unrouted Net
`
`Is
`r-2040
`There A
`Pair Of Adjacent Layers _Ye_s---.
`Where Net
`Fits
`?
`
`2050
`2060
`~ - -_ . . ,_ __ __.___,_
`Assign Each Net Edge To ____ ---1 Assign Net To Preferred
`Optimal Available Layer
`layer
`
`, - - - - - - - ' - - - - ' - - - - , ,
`
`Yes
`
`More
`Unassigne
`
`2070
`
`No
`
`2080
`
`Perform Ripup-Reroute
`
`FIG. 20
`
`Page 23 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 23 of 24
`
`US 2007/0028201 Al
`
`Begin Ripup-Reroute
`
`Prioritize Nets For
`Ripup-Reroute
`
`2110
`
`r2120
`
`2130
`
`Select Highest Priority
`Net To Reroute
`
`2140
`Reroute Net And Determine
`Layer Assignment Of Rerouted
`Net
`
`Yes
`
`2150
`
`No
`,.._........... ___ ............._ __ ~
`12160
`Perform Layer Balancing
`
`. FIG~ 21
`
`Page 24 of 38
`
`

`

`Patent Application Publication Feb. 1, 2007 Sheet 24 of 24
`
`US 2007/0028201 Al
`
`2210
`
`2220
`
`Begin Layer Balancing
`
`Determine Resource
`Utilization Of Each
`Wiring Layer
`
`2230
`Any
`No
`Wiring Layers
`Unbalanced
`?
`Yes
`
`Identify Candidate Net
`For Rebalancing
`
`2240
`
`2250
`
`Relocate Candidate
`Net
`
`FIG. 22
`
`-2260
`
`Perform Detailed
`Routing
`
`Page 25 of 38
`
`

`

`US 2007/0028201 Al
`
`Feb. 1, 2007
`
`1
`
`ENHANCED ROUTING GRID SYSTEM AND
`METHOD
`
`RELATED APPLICATIONS
`
`[0001] The present application is a continuation-in-part of
`U.S. patent application Ser. No. 11/148,911, filed Jun. 9,
`2005, pending, which application is incorporated by refer(cid:173)
`ence herein.
`
`TECHNICAL FIELD
`
`[0002] The present invention relates to systems and meth(cid:173)
`ods for routing traces or wires for an integrated circuit or
`other electronic design.
`
`BACKGROUND
`
`[0003] A layout is a map of electrical connections on
`various layers in a semiconductor integrated circuit. Com(cid:173)
`puter-driven routing systems are often used to build layouts
`to articulate designs to be expressed in an integrated circuit.
`Such systems typically use a netlist which is a description of
`required connections between terminals, and create a routed
`design or layout to make such required connections.
`
`[0004] Typically such computer driven routing systems
`are grid based systems that route traces on a routing grid.
`Some systems also employ a gridless routing scheme, in
`which routing shapes may be placed at very precise loca(cid:173)
`tions.
`
`[0005]
`In such a conventional grid based routing system,
`each layer of an integrated circuit chip is represented as a
`routing grid. The grids for the various layers together form
`a 3D routing grid. A typical integrated circuit will have at
`least one semiconductor layer and three wiring layers. The
`three wiring layers are sometimes referred to as HVH
`(horizontal-vertical-horizontal).
`'Horizontal' or 'vertical'
`indicates that the layer is generally used to make traces that
`traverse in that direction. Vias interconnect adjacent layers.
`
`[0006] To perform routing, the router must first receive
`chip technology data including various rules such as geo(cid:173)
`metric rules that describe parameters such as the character(cid:173)
`istics of layers on which rectangles representing wires can
`be generated, the minimum allowed width of any part of a
`trace, and the minimum allowed separation between traces.
`Typically, a router includes a global routing step for allo(cid:173)
`cating groups of nets to be routed through corresponding
`general routing areas.
`
`[0007] A number of conventions are employed in typical
`routing systems and methods. For example, the common
`"centerline convention" places the center of traces on the
`routing grid gridlines. When a net is routed, for various
`reasons, the trace must be distanced from existing obstacles
`or structures, such as, for example, other traces, including
`vias, and pins of other nets that have been previously routed
`on the grid.
`
`[0008] As integrated circuits employ smaller sizes such as,
`for example, submicron-sized designs, the congestion of
`traces in a circuit design tends to increase. Further, modern
`designs tend to have wires or traces having different and
`non-uniform size and spacing. Typical grid-based systems
`may not efficiently handle such increased congestion and
`
`size variation. The increased congestion and size variation
`place greater constraints on the routing grid pitch employed
`in a particular region.
`
`[0009] One common approach to such increased conges(cid:173)
`tion and size variation is to reduce the pitch of the routing
`grid to allow more precise placement. Such a scheme causes,
`however, significant increase in the number of grid points
`and a corresponding increase in search time.
`
`[0010] Another approach is to use a gridless or shape(cid:173)
`based routing system. Such a system tracks traces and other
`obstacles based upon their relative locations. Shape-based
`systems are typically not limited to a predefined routing grid.
`The systems are, however, typically slow and complex.
`
`[0011]
`In the IC industry, different objectives for a design
`are served by different design features. For example, design
`attributes that improve manufacturability may not so readily
`serve the interests of feature density just as attributes that
`serve reduced delay may not so readily serve other interests.
`The trade offs between manufacturability, reduced delay and
`timing sensitivity have typically been allocated with meth(cid:173)
`ods that are less than systematic and efficient.
`
`[0012] What is needed, therefore, are routing techniques
`that provide speed similar to a grid-based system, but
`accuracy and flexibility that compares favorably with a
`shape-based system but which provide efficient management
`of the trade offs between manufacturability, timing, and
`reduced delay.
`
`SUMMARY
`
`[0013] Routing systems and methods are provided having
`various strategies for optimizing and evaluating possible
`routes for netlist connections. In one embodiment, a data
`structure or matrix provides cost-related data weighted to
`evaluate a connection or segment of a connection based
`upon an attribute of interest such as, for example, reduced
`delay (i.e., impact on speed), manufacturability or noise
`tolerance. In some embodiments, the attribute-weighted cost
`information includes cost information related to neighbor(cid:173)
`hood or terrain costs and intrinsic or shape costs to provide
`multidimensional cost information for connections. In some
`embodiments, the processing of such higher information
`cost data is made more efficient with an additive process that
`is less demanding than a computationally intensive iterative
`multiplication process.
`
`[0014]
`In another embodiment, certain traces are offset
`from the routing grid to help provide efficient grid usage.
`Other embodiments have an enhanced routing grid capabil(cid:173)
`ity that provide those parts of a dense routing grid employed
`to efficiently route off main grid sites or pins, for example.
`Various methods are also disclosed for shifting and adjusting
`routing grids to improve use of available space or reduce run
`time in routing.
`
`[0015]
`In another embodiment, a parallel processing
`scheme is used to process multiple regions on multiple
`processors simultaneously without creating conflicts, that
`could arise, for example, when two processors try to route a
`trace on the same gridpoint.
`
`[0016]
`In another embodiment, various methods are pro(cid:173)
`posed to spread nets over one or more wiring layers.
`
`Page 26 of 38
`
`

`

`US 2007/0028201 Al
`
`Feb. 1, 2007
`
`2
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0017] FIG. lA depicts a prior art grid labeling scheme.
`
`[0018] FIG. 1B depicts a finer granularity grid labeling
`strategy that weights the cost of a connection or structure.
`
`[0019] FIG. 2 depicts a method of enhancing grid preci(cid:173)
`sion and usability by offsetting traces from gridpoints.
`
`[0020] FIG. 3A depicts a step in using a subgrid according
`to one embodiment of the present invention.
`
`[0037] FIG. 20 depicts a flow chart illustrating a method
`for initial routing in a preferred embodiment of a method for
`routing connections in an integrated circuit chip design.
`
`[0038] FIG. 21 depicts a flow chart illustrating a method
`for ripup-reroute in a preferred embodiment of a method for
`routing connections in an integrated circuit chip design.
`
`[0039] FIG. 22 depicts a flow chart illustrating a method
`for layer balancing in a preferred embodiment of a method
`for routing connections in an integrated circuit chip design.
`
`[0021] FIG. 3B depicts a reduced subgrid according to an
`embodiment of the present invention.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`[0022] FIG. 4 depicts a route for a connection from a
`source to a target as a series of steps.
`
`[0023] FIG. 5 depicts a routing strategy according to one
`preferred embodiment of the present invention.
`
`[0024] FIG. 6A and FIG. 6B illustrate a sparse grid flyover
`technique according to one embodiment of the present
`invention.
`
`[0025] FIG. 7 depicts a global routing scheme using sparse
`routing grids according to one embodiment of the present
`invention.
`
`[0026] FIG. 8 depicts a flow chart of a global routing
`scheme using sparse routing grids.
`
`[0027] FIG. 9 illustrates a parallel processing routing
`scheme according to one embodiment of the present inven(cid:173)
`tion.
`
`[0028] FIG. 10 depicts a flow chart of a parallel processing
`routing scheme according to one embodiment of the present
`invention.
`
`[0029] FIG. 11 illustrates a parallel processing routine
`scheme according to another embodiment of the present
`invention.
`
`[0030] FIG. 12
`illustrates a global routing function
`employed in combination with a parallel processing function
`in a scheme according to one embodiment of the present
`invention.
`
`[0031] FIG. 13 depicts a flow chart of a global routing
`function employed in combination with a parallel processing
`function according to one embodiment of the present inven(cid:173)
`tion.
`
`[0032] FIG. 14
`illustrates a grid adjustment scheme
`according to one embodiment of the present invention.
`
`[0033] FIG. 15 and FIG. 16 illustrate a trace adjustment
`scheme according to one embodiment of the present inven(cid:173)
`tion.
`
`[0034] FIG. 17 illustrates an exemplary global spreading
`technique according to one embodiment of the present
`invention.
`
`[0035] FIG. 18 is an expanded view of an exemplary
`multi-layer configuration of an integrated circuit chip.
`
`[0036] FIG. 19 depicts a flow chart illustrating a preferred
`embodiment of a method for routing connections in an
`integrated circuit chip design.
`
`[0040] FIG. lA depicts a prior art grid labeling scheme.
`Grid 12 is a routing grid upon which traces are routed to
`make connections between desired locations in the grid area,
`such as, for example, gridpoints 14. The depicted grid 12 is
`formed of horizontal gridlines 6 and vertical gridlines 8
`which intersect to create gridpoints 14.
`
`[0041] Typically, routing a path or trace 16 requires rout(cid:173)
`ing path segments between certain gridpoints or pins. A
`search algorithm searches the grid to find an unblocked route
`through which to route trace 16. Once a route is found, many
`routing systems record the route using a one-bit scheme in
`which "1" represents that a gridpoint 14 is blocked and "O"
`represents that a gridpoint 14 is open for use (unblocked).
`More sophisticated systems employ a two-bit matrix typi(cid:173)
`cally stored as a data structure 18 to represent the status of
`each gridpoint 14. Such a scheme enables matrix or data
`structure 18 to contain blocking information for more than
`one type of trace 16. In FIG. 1, the data structures 18 have
`two bits, the first or left-hand-depicted bit representing the
`status of each respective gridpoint 14 as being blocked or
`unblocked for a single-wide trace 16 while the second or
`right-hand depicted bit represents the status of each respec(cid:173)
`tive gridpoint as blocked or unblocked for use by a double(cid:173)
`wide trace.
`
`[0042] One embodiment of the present invention employs
`data structures that provide a deeper information related to
`a proposed route for a connection. Rather than bits indicative
`of one of two states (i.e., blocked/unblocked), the data
`structures or matrices 18 of a preferred embodiment express
`values representative of the impact upon selected attributes
`of interest such as, for example, reduced delay, noise toler(cid:173)
`ance, or manufacturability that result from routing the path
`or trace through a segment of the path bounded by a
`particular grid vertex with which the matrix or data structure
`has been associated. Although any number of values can be
`expressed by the cost matrix 18 in preferred embodiments,
`preferably, at least two matrix values are expressed by the
`cost matrix or data structure 18, each of the two values
`taking on one of at least three possible range values to
`convey more than a binary unblocked/blocked evaluation of
`the degree of impact that would impinge upon a selected
`attribute of interest by incorporation of the selected segment
`into a possible path for the proposed netlist connection.
`Typically, one of the range values available for expression
`by a matrix value of data structure 18 represents a prohibi(cid:173)
`tion on use of that segment for the proposed path with a
`proposed shape.
`
`[0043] As shown in FIG. lB, in the depicted embodiment,
`gridpoint 14 1 is shown having a data structure 18 that
`
`Page 27 of 38
`
`

`

`US 2007/0028201 Al
`
`Feb. 1, 2007
`
`3
`
`expresses two matrix values (n1 , n2 ). The n 1 matrix value has
`taken on the range value 1 and the n2 matrix value has taken
`on the range value 100. Thus, data structure or matrix 18
`contains (1,100), which indicates the associated gridpoint is
`blocked for use by a single-wide trace and a double-wide
`trace because for the first matrix value n 1 , a "1" range value
`indicates complete prohibition on use by a single wide trace
`and for the second matrix value n2 , a "100" range value
`indicates complete prohibition on use by a double wide
`trace. The use of 100 in the n2 position of the (ni, n2 ) matrix
`indicates a maximal blockage and corresponds to earlier
`systems that expressed that condition with a "1". Such
`disability results, in this example, from the expression of
`depicted trace 16 along a route that already includes grid(cid:173)
`point 14 1 .
`[0044] When complete prohibition (blockage) is indicated
`by more than a "1" range value for a matrix value (ni, n2 , *
`* *n,,), in preferred embodiments, that typically means that
`other range values are available for that matrix value to
`express a degree of impact upon an attribute of interest other
`or less than complete blockage for a proposed shape. For
`example, where the range value 100 indicates blockage for
`the matrix value n2, there is typically available at least one
`range value more than "0" and less than "100" for that
`matrix value. Thus, the matrix value can take one of at least
`three different range values, at a minimum. When larger
`range values such as "100" are employed, in a typical
`preferred embodiment, there will be many range values
`available to allow a more continuum-like indication of
`impact upon an attribute of interest arising from use of that
`proposed segment or path.
`
`[0045] Gridpoint 142 is also depicted as being entirely
`unavailable for both a single-wide and a double-wide trace.
`This is expressed by the respective matrix value range
`values (1,100) for matrix 18. This is because gridpoint 142
`is within the design rule keepout or spacing requirement for
`the depicted trace 16. The spacing requirement is typically
`determined by desired electrical properties of traces 16. For
`example, if the depicted trace 16 is 100 nm wide, the design
`rules may specify a spacing requirement that it be 100 nm
`from any neighboring trace. Suppose, for example, that the
`depicted gridlines are arranged to form a 100 nm pitch grid.
`In such a case, gridpoint 142 would be within 100 nm of
`trace 16, and is, therefore, blocked by the spacing require(cid:173)
`ment or spacing zone of trace 16. Gridpoint 142 is shown
`blocked for both single-wide and double-wide traces 16, as
`indicated by (1,100).
`
`[0046] The next gridpoint 143 is shown as having data
`structure or matrix 18 containing (0, 50). Such range values
`indicate, in this example embodiment, that gridpoint 143 is
`unblocked for use by a single-wide trace, and may, if the cost
`is acceptable, be employed for use with a double-wide trace.
`The indication of a relative cost of 50 in the n2 position of
`the cost matrix (nl, n2) indicates that, although it is not
`absolutely prohibited, use of a double wide trace at 143 will
`come with some impact. The character of that impact is
`determined by the weighting given to that site by an opti(cid:173)
`mization tool.
`
`[0047] The optimization tool is directed to assign a cost
`for particular sites or vertices 14n depending upon the
`relative values placed upon the attributes of interest such as
`manufacturability, reduced delay, and noise tolerance, for
`
`example. Preferably, when absolutely prohibited by prior
`use at that layer or the design rules, the maximum of the
`costing continuum of the matrix will be indicated. In this
`example, that number is 100. The number used to indicate
`complete prohibition is arbitrary, but expanding the range
`from 1 to 100 allows a finer gradation of cost to allow finer
`evaluation of attributes of interest such as reduced delay,
`noise tolerance or manufacturability, for example. Those of
`skill will note that other attributes of interest may be woven
`into the cost weighting, but reduced delay, noise, and
`manufacturability are the principal attributes of interest. The
`output of the optimization tool then becomes a label for a
`particular locus of the grid or a pin and that label is
`employed to find lower cost routes for particular connec(cid:173)
`tions.
`[0048] The next gridpoint 144 is shown as having a cost
`matrix of (0, 10), indicating it is unblocked for use by both
`single-wide and has some, but minimal cost for use with
`double-wide traces. If a double-wide trace were to be routed
`along gridpoint 144 , it would not overlap or violate the
`spacing requirement of the depicted trace 16. Also, the
`depicted trace 16 would not violate the spacing requirement
`of a double-wide trace if it were routed on gridpoint 144 ,
`assuming the required double-wide spacing is 150 nm.
`However, in this example, it will induce some noise impact
`if this exemplar trace is a high power trace and switching
`along trace 16 propagates disturbances some distance from
`trace 16.
`[0049] The depicted method may be used to indicate and
`store in router data storage, data about a variety of different
`trace types and other shapes that may be placed on a grid 12
`and their impact on proposed routes, paths or segments. The
`data is then used by search algorithms when finding routes
`for other traces. Those of skill will recognize that routers
`implement methods and algorithms with software that
`induces instructions for implementation of the desired
`method or algorithm. Those of skill will also recognize that
`the trace size and spacing used in this example are merely
`exemplary and it is expected that systems will use a variety
`of trace sizes and other shapes.
`[0050] FIG. 2 depicts a method of enhancing grid preci(cid:173)
`sion and usability by offsetting traces from gridpoints. The
`depicted portion of grid 12 has example single wide trace 16
`and example double-wide traces 22. Gridlines 6 and 8 form
`a standard routing grid having, in this example, a 200 nm
`spacing. The left-hand exemplar traces 16 and 22 are routed
`along gridline 8 1 . Trace 16 is a single-wide trace with a 100
`nm width and a 100 nm spacing requirement. Traces 22 are
`double wide traces with a 200 nm width and a 150 nm
`spacing requirement.
`[0051] The upper depicted double-wide trace 22, is cen(cid:173)
`tered on vertical gridline 81 and therefore blocks gridline 8 1
`and gridline 82 because gridline 82 is within the required 150
`nm spacing for the trace 22 1 . The first gridline 8 available for
`routing a single-wide or double-wide trace beside the upper
`depicted trace 22 1 is gridline 8y Because the upper depicted
`trace 22 1 is centered on gridline 81 , it blocks not only
`gridline 8 1 , but also the neighboring gridline 82 to its right
`and the corresponding neighboring gridline to its left (not
`shown). Thus three gridlines 8 are blocked by upper
`depicted trace 22 1 .
`[0052]
`In such a scheme, area may be wasted. The
`example grid size does not allow optimal spacing. To reduce
`
`Page 28 of 38
`
`

`

`US 2007/0028201 Al
`
`Feb. 1, 2007
`
`4
`
`the pitch of the gridlines, however, to achieve more optimal
`spacing may greatly slow down the routing program by
`significantly increasing the number of gridpoints searched.
`
`[0053] The lower depicted double-wide trace 222 is placed
`according to a preferred method of the invention to help
`optimize space efficiency, or packing, without decreasing the
`pitch of the gridlines employed. The lower trace 222 is
`centered on an offset line 24. Line 24 is offset from gridline
`82 by 100 nm. With such an offset location, the vertical
`portion of offset placed lower trace 222 blocks only two
`gridlines, 82 and 83 , rather than blocking three gridlines. In
`this example, gridpoints 14 on gridline 81 beside offset lower
`trace 222 may be employed for routing a single-wide trace
`which is spaced at the correct 150 nm spacing from offset
`lower trace 222 . Thus, the depicted method provides more
`efficiently spaced traces.
`
`[0054] A proper offset distance may be determined for a
`particular shape such as, for example, a double wide trace,
`an analog trace, or other special trace, by shifting an outline
`of the shape with its associated spacing over a desired grid
`and determining which offset position blocks the smallest
`number of gridlines. Preferably, the offset position is deter(cid:173)
`mined in advance of the routing step. The offset position is
`preferably associated with a particular type o