(12) United States Patent
`Andreev et al.
`
`I 1111111111111111 11111 111111111111111 IIIII IIIII IIIII IIIII IIIIII IIII IIII IIII
`US006324674B2
`US 6,324,674 B2
`Nov. 27, 2001
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) METHOD AND APPARATUS FOR PARALLEL
`SIMULTANEOUS GLOBALAND DETAIL
`ROUTING
`
`(75)
`
`Inventors: Alexander E. Andreev, Sunnyvale, CA
`(US); Elyar E. Gasanov, Moscow
`(RU); Ranko Scepanovic, San Jose;
`Pedja Raspopovic, Cupertino, both of
`CA(US)
`
`(73) Assignee: LSI Logic Corporation, Milpitas, CA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/062,309
`
`(22)
`
`Filed:
`
`Apr. 17, 1998
`
`(51)
`(52)
`(58)
`
`(56)
`
`Int. Cl.7 ...................................................... G06F 17/50
`U.S. Cl. ................................................................ 716/12
`Field of Search ........................... 395/500.08; 716/5,
`716/7, 12, 13, 14
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,491,641
`5,495,419
`5,568,322
`5,568,636
`
`2/1996 Scepanovic et al. .
`2/1996 Rostoker et al. .
`10/1996 Azami et al. .
`10/1996 Koford .
`
`11/1996
`5,578,840
`3/1997
`5,615,128
`6/1997
`5,636,125
`6/1997
`5,638,293
`8/1997
`5,661,663
`10/1997
`5,682,322
`1/1998
`5,712,793
`4/1998
`5,742,510
`4/1998
`5,745,363
`9/1998
`5,808,899
`* 10/1998
`5,822,214
`* cited by examiner
`
`Scepanovic et al. .
`Scepanovic et al. .
`Rostoker et al. .
`Scepanovic et al. .
`Scepanovic et al. .
`Boyle et al. .
`Scepanovic et al. .
`Rostoker et al. .
`Rostoker et al. .
`Scepanovic et al. .
`Rostoker ......................... 395/500.08
`
`Primary Examiner-Matthew Smith
`Assistant Examiner-Thuan Do
`(74) Attorney, Agent, or Firm-Mitchell, Silberberg &
`Knupp
`
`(57)
`
`ABSTRACT
`
`A method for routing nets in an integrated circuit design,
`said method comprising the steps of dividing the integrated
`circuit design with lines in a first direction and lines in a
`second direction, forming a routing graph having vertices
`and edges, wherein vertices correspond to locations where
`lines in the first direction cross lines in the second direction,
`routing nets as a function of said routing graph with parallel
`processors operating substantially simultaneously, determin(cid:173)
`ing the relative wire congestion among different areas in the
`integrated circuit design, and rerouting nets passing though
`areas with a relatively high wire congestion.
`
`36 Claims, 31 Drawing Sheets
`
`12
`
`\
`
`INPUT
`
`13
`
`IDENTIFY ELEMENTARY PAIRS
`
`14
`
`CREATE PLANAR GRAPH
`
`CREATE SPANNING TREE
`
`15
`
`16
`
`IDENTIFY BASIS ELEMENTS
`
`CONSTRUCT CONNECTED COVERING
`
`17
`
`18
`
`Page 1 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 1 of 31
`
`US 6,324,674 B2
`
`,------,□□□□□□□□□'□□□□□□□□□□
`~ □□□□□□□□□□□□□□□□□□□
`□□□□□□□□□□
`□□□□□□□□□□
`□□□□□□□□□□
`._ ____ _.ODD □□□□□□□
`□□□□□□□□□□□□□□□□□□□□
`□□□□□□□□□□□□□□□□□□ OD
`□ oo □□□ o □□□□□ o □ o □ o □ o □
`000 □□□□□□□□□□ 0 □□□□□□
`□□□ 000 □ 0 □□□□□ 0 □□ 0 □□□
`□□□□□□□□□□□□□ 0 □□□□□□
`□□□□□□□□□□□□□□□□□□□□
`□□□□□□□□□□□□□□□□□□□□
`□□□□□□□□□□□□□□□□ 0000
`□□□□□□□ o □□□□□□□□□□□ o
`□ ooo □ o □□□□□□□ oo □□□□ o
`00 □ 00 □ 0 □□□ 0 □□□ 0 □ 0 □ 00
`□ O □□ o □ oo □□□ oo □□□□□ o □
`□ o □□ o □□□□□□□□□□□□□□□------~
`□□□□□ o □□□□□□□□□□□□□□□□□
`□□□□□□□□□□□□□□□□□□□□□□□
`□ 00 □□□□□□□□□□□□□□□□□□□□
`□ DOI
`1 □□□□ 00
`□□□
`~ ~ 0000 □□
`0 □ oo._ ______ oo □□□□
`
`=> a..
`u
`
`::z:
`
`~ ~ 1gggggg
`~ gg~1
`1°00000
`0001
`~ ~ □□□□□□
`~ □ go
`u
`._~000._ ____ ___.0D □□□□~----/
`
`....J
`
`Page 2 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 2 of 31
`
`US 6,324,674 B2
`
`1
`
`\
`
`INPUT: NET LIST.PARAMETERS
`k,
`r, NUMBER OF ITERATIONS
`
`2
`
`PARTITION LARGE NETS INTO SMALLER ONES
`
`J
`
`ROUTE NETS IN PARALLEL
`
`4
`
`REROUTE THE NETS PASSING THROUGH CONGESTED AREAS
`REPEAT THIS PROCEDURE NUMBER OF ITERATIONS TIMES
`
`5
`
`REDO THE ROUTING IN OPTIMIZING MESHES
`
`6
`
`7
`
`.__,_ k=k-
`
`___ OBTAIN ROUTING ON THE
`1
`NEXT HIERARCHY LEVEL
`
`8
`
`EVENLY DISTRIBUTE VERTICAL
`LINES BETWEEN FIRST AND THIRD LAYER
`
`PERFORM THE DETAILED ROUTING
`
`OPTIMIZE THE DETAILED
`ROUTING BY CONTINUOUS DEFORMATIONS
`
`9
`
`10
`
`11
`
`FIG. 2
`
`Page 3 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 3 of 31
`
`US 6,324,674 B2
`
`FIG. 3
`
`12
`
`\
`
`INPUT
`
`13
`
`IDENTIFY ELEMENTARY PAIRS
`
`14
`
`CREATE PLANAR GRAPH
`
`CREATE SPANNING TREE
`
`15
`
`16
`
`IDENTIFY BASIS ELEMENTS
`
`CONSTRUCT CONNECTED COVERING
`
`17
`
`18
`
`41
`
`40
`
`\
`42
`
`FIG. 4A
`
`Page 4 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 4 of 31
`
`US 6,324,674 B2
`
`48
`
`45
`
`50
`
`55
`
`4 9 /
`
`46
`
`FIG. 48
`
`\
`47
`
`53
`
`51
`
`FIG. 4C
`
`52
`
`59~
`
`56
`
`58
`
`'.
`
`FIG. 4D
`
`Page 5 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 5 of 31
`
`US 6,324,674 B2
`
`60
`
`64 \
`
`FIG. 4£
`
`63
`
`I
`
`69 I
`
`FIG. 4F
`
`Page 6 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 6 of 31
`
`US 6,324,674 B2
`
`FIG. 5
`
`121"-
`
`~ 124
`
`~
`
`129
`
`✓ 130
`
`122
`
`125
`
`) ✓
`
`~
`123
`
`126~
`
`FIG. 6
`
`121-
`
`122
`)
`
`124
`87-...__
`86-....
`
`;s
`
`85-.._
`84,
`
`123
`\
`/
`
`BJ,
`82-.....
`
`" 127
`
`I
`88
`
`I\
`
`127
`
`128
`
`)
`
`129
`
`7i 'O'-
`
`i\
`\
`72 73
`
`71
`
`74,
`I\
`81-..... 1~6 75
`BO, V
`
`76"\.
`
`128 I\ V
`IJ
`77
`
`130
`
`78
`
`Page 7 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 7 of 31
`
`US 6,324,674 B2
`
`FIG. 7A
`8
`
`7
`
`6
`
`5
`
`4
`
`3
`
`2
`
`124
`
`121
`_)
`
`129
`,)
`
`130
`
`122
`. ./
`
`125
`_)
`
`127
`,)
`
`1J3
`
`128
`. ./
`
`1]6
`
`0
`
`0
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`FIG. 78
`
`124
`
`121
`.)
`
`122 125
`,)
`,)
`
`1J3
`
`8
`
`7
`
`6
`
`5
`
`4
`
`3
`
`2
`
`0
`
`0
`
`129
`,)
`
`127
`,)
`
`128
`_)
`
`126
`,)
`
`2
`
`3
`
`4
`
`130
`
`Page 8 of 52
`
`

`

`U.S. Patent
`US. Patent
`
`Nov. 27, 2001
`Nov. 27, 2001
`
`Sheet 8 0f 31
`Sheet 8 of 31
`
`US 6,324,674 B2
`US 6,324,674 B2
`
`-------------.---------,-----, Fl G. 7 C
`124
`4 ~ -
`
`121
`
`129
`
`3 ---------+------+-----e--------1
`
`122
`
`125
`
`127
`
`123
`
`130
`
`126
`
`128
`
`0 -+----+-----------------1
`2
`4
`3
`0
`
`129
`
`150
`
`127
`
`1.30
`F/G.
`
`Fl G. 7D
`
`2 ----------------
`
`123
`
`131
`
`151
`
`0 ---l----~-------
`2
`0
`
`Page 9 of 52
`
`Page 9 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 9 of 31
`
`US 6,324,674 B2
`
`FIG. 7E
`
`124
`
`152
`
`153
`
`123
`
`151
`
`130
`
`FIG. 7G
`
`124
`
`156
`
`130
`
`I
`
`502~
`
`FIG. 7F
`124
`
`155
`
`154
`
`130
`
`124
`
`✓ 124
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I vsoo
`
`157
`
`._/ 157
`
`FIG. 7H
`
`FIG. BA
`
`FIG. 88
`
`Page 10 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 10 of 31
`
`US 6,324,674 B2
`
`')
`/
`
`124
`
`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
`I
`I
`I
`I
`I
`I
`I
`
`\
`\
`\
`\
`
`\
`
`\
`
`\
`\
`\
`\
`\
`\
`\
`\
`\
`\
`\
`
`v : 514
`
`f
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`511'1
`
`I
`I
`
`l
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`\
`\
`
`\
`\
`
`\
`
`\
`\
`\
`\
`
`\
`
`\
`\
`\
`\
`
`\
`\
`\
`\
`\
`
`\
`
`\
`
`\
`
`\
`
`\
`\
`\
`\
`\
`\
`
`v-155
`
`'
`
`'
`
`' ,
`,
`
`' ,
`,
`
`'
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`:
`!
`
`' ,
`'
`
`' ,
`
`'
`
`513
`
`',,,,,)
`'
`
`FIG. BC
`
`\
`\
`\
`\
`
`\
`\
`\
`\✓501
`
`' ,
`'
`
`',,
`
`'
`
`' ,
`'
`
`'
`
`' ,
`'
`
`' ,
`'
`
`'
`
`\
`\
`
`\
`
`\
`\
`\
`\
`\
`
`' ,
`'
`
`'
`
`' ,
`'
`
`'
`
`\
`\
`\
`\
`\
`\
`\
`\
`\
`\
`\
`
`' ,
`
`130
`
`154~-------------- I _________________ >\..)
`
`I
`I
`
`\
`
`:
`I
`
`'V510
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`
`512
`
`Page 11 of 52
`
`

`

`U.S. Patent
`US. Patent
`
`Nov. 27, 2001
`Nov. 27, 2001
`
`Sheet 11 of 31
`Sheet 11 0f 31
`
`US 6,324,674 B2
`US 6,324,674 B2
`
`\
`
`\
`
`\\02_\\\\\45\x\\\I_x\\5_\x_
`\\_x\\\\_\x\\_\\\x\\\\\_x\\\\__\
`\\_\\\_\\x5\\Ax3\\\_\\5J\\\__
`
`\
`
`_xx5_\\\
`
`\MU\_\
`\\_1/\_/\\_//\_x4,\\_I_
`\_
`\\2.
`
`\\_1/
`\_/lllll
`
`\\\\\\\
`
`4,
`
`\\\
`
`\\x3_\\x\5nx\5v_\x_\\nx_Mx__5\\4,_x5_7_
`\_\\\x_9x\_3\\\u5\\x\"\\\\xu\\x_x\_\x_\x\x6\u
`
`FIG. 8D
`F/G.
`80
`
`Page 12 of 52
`
`Page 12 of 52
`
`

`

`U.S. Patent
`US. Patent
`
`Nov. 27, 2001
`Nov. 27, 2001
`
`Sheet 12 of 31
`Sheet 12 0f 31
`
`US 6,324,674 B2
`US 6,324,674 132
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`564
`
`FIG. 8£
`85
`
`O
`
`r\ 724
`l \\
`I
`\ ‘\\\
`I
`\
`\ \
`I
`\
`\ \\
`I
`\
`I
`\
`l
`I
`I
`I
`l
`I
`I
`I
`
`\
`
`\
`
`‘
`
`\
`
`\\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\\
`
`\
`
`\
`
`\
`
`\\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`IIIII
`
`f
`
`’
`
`I,
`
`/
`
`,
`
`I
`
`I
`I
`I
`I
`I
`I
`
`582
`
`I
`
`/
`
`I,
`534‘
`.
`I
`\
`
`\
`\
`
`’1’
`
`\ /
`I
`
`\\
`
`/
`
`‘\\\
`
`x g I: x
`I H \2 \
`\ x
`’
`’I
`‘
`\
`‘
`\
`/"
`I,
`I
`I
`I
`\
`\
`\
`’/
`\\ 7'
`’l
`I
`I
`\I 57 \U
`\\
`\\
`X
`I
`:
`\\\ ,’/
`I
`\\/
`/
`\
`I
`\
`l<
`I k \
`,I
`I“ \
`:
`590 \\
`\\,
`\‘535\\ //
`[589 \\
`\'
`|
`\
`l?\
`I
`|
`\
`I
`I\\
`:
`J [I 586\\
`I
`//’\
`\\
`\ ‘4
`wow/7 I
`: ————— 4‘- ————— I ————————— P~
`x
`,
`,/|\\ \\\\
`J’/ I‘
`\
`//
`I,
`I \
`\\\\T\z/
`\ 576 )II
`I
`\
`[I
`I
`\ /\\~\\
`/’
`I
`I
`I, H \\
`K
`\\‘/<’
`I
`I
`\‘
`57,
`I
`'
`7” \I
`Ii,
`\\‘\\I
`I
`\ 57 \\ I,
`,” \
`T‘\J
`\\
`\(
`:
`I
`577
`\ 573;
`
`\
`
`\\
`
`\
`
`\
`
`/
`
`\
`
`7
`
`\
`
`127
`\\\\
`
`\\
`
`\
`
`\
`
`\\
`
`x
`579
`
`\
`
`\\\
`
`\
`
`\\\
`
`Page 13 of 52
`
`Page 13 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 13 of 31
`
`US 6,324,674 B2
`
`,,,,
`,,
`
`,.--
`
`,.--
`
`1
`\
`
`,
`
`'
`
`0)
`
`Cl
`00
`
`"">'\,,
`
`__ ,.--
`
`,,
`,.,,
`,.
`
`,,
`
`_,.,-
`,.,
`,.
`,,,,,
`,,.,,,.
`,."
`
`0)
`C..,,
`
`,\,
`,. \ '
`,,, ,,,
`\ \ IC)
`,4
`/ ,,
`I,,
`
`I~
`I I/
`I I/
`~ _ , ft
`r-.;__,
`f/
`I
`It)
`It
`I
`11
`I
`I I
`I
`,'
`/ /
`I
`/
`
`'
`
`'
`
`(Q
`
`' ,
`'
`
`,
`
`\
`\
`\
`\
`\
`\
`'
`":""'\
`\ \_ C) ',
`\
`::::
`', )
`..._.
`,
`
`I
`
`~
`~
`,,_ ~,,.,, ____________ \_ ______ 7,' _Jj --r----- \ ______ ',
`,," 1/l
`I"'' ---
`/
`/ I
`I ~ I
`<::)
`I I
`/
`1,...
`/
`I
`,.,,
`I
`/
`(Q
`;:.;!
`I "'-./1
`I
`I
`I
`I,,
`1
`I
`I
`_,./\
`/ I
`I
`(Q
`/
`\..
`/
`I
`-
`I
`,.
`I
`/
`;
`v"
`, ,
`,
`-...
`, =- ~
`ll)
`~
`/
`,.
`I
`- ,
`I
`-- ... /
`/ /
`/
`/ I
`-,.,_
`/
`/
`\ I
`-,L
`/
`I
`\/
`I 'r-
`I
`I\
`/
`/
`/ I
`/
`I
`/
`I
`I
`
`Ii\\ - -
`
`/
`
`I
`
`I
`
`I
`
`I
`
`,
`
`,
`
`,
`
`,
`'
`
`- - -
`
`- -
`
`_
`
`--..r _,
`'r 0)
`Cl
`It)
`
`\
`
`\
`,
`
`,
`
`/
`I
`I
`I
`
`/
`
`/
`
`I
`/
`I (Q
`
`- •
`
`\
`\
`
`I
`
`I
`I
`
`,f
`
`0C)
`C\,j
`,,_
`
`,,"11
`
`, h
`
`I
`I
`I
`I
`I
`I ~
`I ~
`
`I
`11 \
`I
`\\
`I
`\\
`\\
`I
`,
`, ,
`I
`I
`\ \
`,,--
`I
`' \
`I
`I ,,"
`I
`\ \
`)"
`I
`I
`I
`,, I
`\
`\
`I
`--.<."'
`I
`I
`I
`I
`- ... I
`,,.,,
`I
`\
`\
`\
`/ C\1/, ,,r"
`\ o\
`"-
`,'
`I
`~ I
`I ~ \
`C\j
`/
`,,_ J/ I
`\
`~ I ~ _/i (\ \
`/ <0,,,,1
`/
`tC)
`,,_
`\
`~ 11
`/
`I \ ; \ ~ , ' ,.,,"
`/
`/
`\ ~----t--•"------ 7
`I
`I
`\
`\
`\
`I ,,
`/
`I 0)
`/ ((Q / : __ ,.--,,
`I
`I
`J.--- ,," I'
`,/ / (Q
`.,
`I
`\
`,-"' 1/f\
`/
`/
`/ I
`\
`,,
`I
`\
`:
`1y"',,
`,' 11
`I
`\
`/
`I
`,
`I \
`I
`.,,,.,,. \
`/
`\
`\
`.,V
`111 "-''
`I
`I <o/ , _,.-
`I
`,,"' I
`I
`/
`I
`I
`,,_ \
`I
`I
`,,
`I
`/
`I
`,,
`,, / \ _,.,, : , / '- I.C')
`, ,,,. , c~ )..--/ \ , , ,,
`-~,
`I
`I
`,,"
`I
`I
`/
`I
`~--:--i / I
`l°
`/ 1,,-~
`I,,,,
`I
`II
`/i
`1
`\
`i / )'
`1..,---
`I I
`t
`/
`I
`,, \
`I/
`~
`fW')
`----I
`I /
`/ / ,,/'
`,,_ 0C)
`/ Qt)
`~\
`I /
`/
`/ ,,
`I
`/ \(Q,,_"' ! I I/ / _,,1"
`(Q 00
`r(::-;-~--------_-_-_-_-_-_-_-_--4- -----7--;--t-;_, -_--;_-_-_ _:_-_-_-_-:_~-:,~~
`I
`I
`I
`..... ' - I
`\
`'-' \ , , I
`.;
`- I -.,
`\
`/
`I 1I 1,/
`I _/_
`
`r--., / -..-: \ I tC)
`- ( (Q
`/
`I
`I
`I
`/~ -,, /
`I
`:
`I
`-,-i--.,
`\ I
`C:::S
`/
`I
`(Q""'
`/
`'-.
`:
`\I
`I'
`/ _____ j-J- ____ _::-~)
`I
`--~
`/
`- - ,-"1
`
`" -
`c:::)
`
`,,_
`(Q
`
`I
`
`\
`
`ClQ
`
`:
`
`/
`, . / - \
`I /
`
`I
`/
`
`/
`/
`I
`I
`/
`I
`I
`
`/
`
`fw')
`00
`ll)
`
`I
`\ , . /
`I
`,,"
`,'
`/ /
`J
`- -
`,,
`,,,." _____
`I
`I
`,,
`,. -
`I,.-:_ - -
`
`/
`/
`
`I
`
`Y
`
`I
`/
`
`/
`
`C\j
`,,_
`
`.,/"
`I
`t.;"
`
`;
`1
`
`I
`/\
`
`-
`(Q
`
`.-1--
`/
`~--1
`,.-/
`I
`/
`I
`.,. /
`1
`; (Q
`I
`,-" /
`I
`,,.
`.....
`I
`1 ~),,I'/
`/
`\,,,....
`I
`~ :
`Vlr)I /
`\
`I
`/
`C) \
`I / /
`- C)
`\
`I //
`./_
`(0
`\ Ill'
`
`1
`
`/
`I
`
`/
`
`I
`
`/
`
`/
`
`-.
`'
`', ' ,
`~ ,
`........
`C\j
`' ,
`,,_
`' { ,
`
`\
`' ,
`
`,
`
`\
`
`'
`
`\
`
`-
`_ )
`.-....
`~
`ll)
`
`\
`
`\
`
`'
`
`✓,'
`
`I
`
`fw')
`'\_C\j
`._
`
`I
`
`\
`
`I
`I
`
`....
`
`/ ~
`r--7---+-----L--,r I
`,,.
`I "") C\j
`,,."'
`I
`I
`I
`\
`/
`I 1N, ._ /'
`/
`I~
`I
`(
`I tC) I
`I -
`I
`I
`,,.)
`I ~ ,' ~ /
`,N,, ,,v,.,.. ✓·- /
`,
`I I /
`,,,,.
`I
`tC)
`/
`' , I
`/
`I 1,,-1
`"-
`I
`1
`l /
`It) \_ '
`I ,,....
`/
`I
`- -
`....... ,
`I
`I
`/
`/
`..,-
`I',
`\,
`\ .),
`I
`._
`I
`,-'{ I
`I
`/ -
`1
`' , I
`(Q
`I
`/'-
`\ I
`I
`/
`-
`. , /
`1
`/ (Q /
`\ \ I
`,,"
`',t
`I
`I
`',
`I
`1\ I I
`I / ' , ,,
`I'
`,,v,
`\I I ;--' /
`,
`I
`I
`I
`I
`\\ I I
`I
`I
`,-"
`' ,
`I
`1
`' \ I
`/ // .,,,..,,,..
`' ,
`\\II 1
`I I I',..,,
`,
`11/ I'
`'-,
`
`I
`
`/
`
`-
`C)
`,,..
`..._.
`
`'
`
`-?: _____ 7 ______ '_:-ll
`-
`C',j -
`
`C\j
`
`~
`--
`tCS
`
`'
`
`~
`
`Page 14 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 14 of 31
`
`US 6,324,674 B2
`
`581
`
`\
`
`124
`\ /JA ' ,
`
`'
`
`' ,
`' ,
`'
`
`I
`
`/111\
`//i/11
`/
`I
`/11
`II I
`/
`I
`/r-._/
`II I
`/ I
`,-
`11 I
`/5/14/-i:\
`121"\.
`~/
`/ ( ! I
`,,,-----/§!;Ji : '1
`
`I\\
`I \ \
`I
`I
`\
`I
`I
`I
`\
`
`__./
`T-1--l_
`/
`/'"""I
`I
`I - - - -~
`I
`/
`/
`I
`I
`I
`- - - -
`\ i 5,'7'4 I
`I
`I
`.J'
`I
`I
`I
`{
`
`' ,
`' ,
`
`__./
`
`' ,
`
`584
`',.r
`585
`',, __
`
`,
`
`' ,
`,
`
`- - - - -
`
`6!!__
`
`/
`' ,
`- - - - ,,...,
`
`_:;;,n,
`
`129
`
`'
`
`,J
`
`'
`
`/
`
`i
`
`\/580
`
`I
`
`I
`
`57,
`/9
`)
`,.._
`' ,
`--........
`.._
`
`\
`I
`\
`I
`I
`I
`I
`
`I
`
`----.......
`
`'-..
`
`130
`
`I
`I
`I
`....,--
`
`-
`
`-
`
`- - -
`
`I
`I
`
`5J7
`
`- - -,
`; - - /
`-
`/
`/
`/
`/
`
`/
`/
`I
`I
`/
`~
`/
`/
`/
`
`609
`
`I '600'
`I V \ I
`\ / \
`\~
`571 ( ' \ \ I
`I I I 57'6 \1
`✓ I
`\ I I
`\ \ I I
`(
`\ I I
`I \II
`I I I I
`I 11 I
`I 111
`\
`
`\ / 605 I
`I /
`\
`11
`/I
`
`/ I
`'/
`f1
`I
`I
`/
`I I
`I
`I
`/
`I -%---
`I
`/
`I
`I _\-1- I
`I C,, 7
`/
`I
`I
`>J
`I
`I
`..-1--
`I UV.J
`I\
`\ - - I
`\
`1602 11 ' )
`_-1--1'"
`\
`I
`I
`\
`\
`\
`\
`j }
`:
`\
`\ ' V I
`
`i\
`I I
`I
`I
`I
`I
`I
`I
`I
`I
`
`1,
`
`I
`I
`I
`
`601
`
`- - -
`
`/
`I
`I
`I
`:-
`\ --........
`\
`\
`\
`
`)
`
`123
`
`\
`
`I
`' , I
`I
`I
`'
`\
`'",l :
`
`I
`'
`I
`\
`I
`I
`\
`I
`/
`; , I
`I
`/
`\ I
`I
`co7 \ \
`' , /
`I
`l-, u,
`\ I
`/
`11
`I ' ,
`/
`\\
`I
`\\
`(
`I
`\ \
`I
`' , \\ I /
`',,~I/
`I I
`\
`I
`~
`I 616
`/
`\\
`\
`I
`\
`\\
`I\
`\
`I
`,,
`128
`\ \\ /
`,,/
`' '"
`
`\ r l',-j
`
`I I
`\ I
`
`\606 11
`
`\
`
`(
`
`615
`
`\
`
`I
`I\
`\ \I/
`
`,," i/ 624
`
`""')
`,,
`
`126
`
`FIG. BG
`
`621~/ \ / \ 6.'2'2/ I "v 608
`\
`~ - - - - - /ii\
`I
`I
`- -
`--
`/ / I \
`I
`I
`\ ) I
`____ - - -
`/
`I I
`I
`I
`I
`I
`\
`/ 15.2•7\ I
`--
`I I
`___
`/
`I
`I
`I
`I
`-<.,_
`/
`/ I
`I ___
`I
`I
`v
`\ I
`l
`/
`I _J.-
`,,.,.
`I
`I
`I
`I
`I L
`,, _1--
`/
`I
`I
`I
`,,...
`I
`620
`-I 7.---'{' I
`I
`, /
`I
`I
`I
`122"-II
`I
`.l--
`12•1::
`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
`11'
`I
`I
`I
`I
`\ ('\--.... , I :(>, \ /617
`/)
`/
`I
`/
`/
`'618 1
`/
`/ 590
`I
`I
`\ I ' , , ' , ¥/
`co4 \
`, 127 I
`I
`I
`\
`I
`I
`\
`I
`I
`/ 1 / u,
`I
`I
`1
`\
`I
`I
`I
`I
`I
`I
`I
`\
`I
`I
`I
`I
`\
`I
`I
`I
`._
`I
`I
`I
`I
`I
`I
`\
`,.._
`I
`I
`' , I
`I
`\
`'-1.
`I
`1
`I
`I
`I
`\
`/ ' , I
`' , I
`I
`I
`I
`'r-
`I
`)
`/
`:
`I
`I
`/
`I
`
`\I
`,\
`/ I
`I
`/
`
`I
`I
`I
`/
`I
`I I
`I I
`
`\
`
`I
`
`I
`
`r I
`
`\
`I
`\
`I
`
`I
`I
`I
`
`'.J.
`\
`I \
`'l,
`l'.J 1
`\
`\
`I
`1'1-,.
`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
`I
`\
`I
`\
`I
`I
`I
`I
`
`' , ' /
`\~
`--~ /
`\
`/
`\
`/ 11
`I\
`/
`I I
`I \
`/
`I I
`I
`I
`/
`I
`I
`I
`\
`I
`I
`\ /
`I
`I
`Y
`I
`I
`I
`/ I
`I
`I
`1
`\
`\
`I
`/
`\
`
`\
`
`/
`
`\ I
`
`Page 15 of 52
`
`

`

`U.S. Patent
`US. Patent
`
`Nov. 27, 2001
`Nov. 27, 2001
`
`Sheet 15 of 31
`Sheet 15 0f 31
`
`US 6,324,674 B2
`US 6,324,674 B2
`
`
`
`::r::: cc
`1%GE
`
`Page 16 of 52
`
`Page 16 of 52
`
`

`

`FIG. 9 I
`F/G.
`
`I
`
`121
`
`"
`
`,____
`I\ I
`
`fiiflmflflfiI
`Jig-III-
`
`l~ ( I ~~flfl
`' -
`
` lflmmflill
`Isanfiama
`asasmauz
`i-nflfimial‘
`
`I
`
`I
`
`'
`
`I
`
`I
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`z 0
`
`~
`N
`~-..J
`N
`0
`0
`'"""'
`
`'JJ. =-~
`
`~
`'"""' O'I
`0 ....,
`
`~
`'"""'
`
`130
`
`e
`rJ'J.
`O'I
`~
`N
`
`,I;;.. °' -...,l
`
`,I;;..
`~
`N
`
`'
`
`fi—nlflfllfil
`
`Page 17 of 52
`
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 17 of 31
`
`US 6,324,674 B2
`
`
`
`Isaaanll
`
`
`IMMIHIEH
`
`lumngznm
`
`
`filmmmiaa
`
`
`Humans-r
`k
`
`
`mileaggl
`
`
`
`filaaaaal
`
`final-III
`
`
`
`F/G.70
`
`(.'.)
`C:
`
`Page 18 of 52
`
`

`

`U.S. Patent
`US. Patent
`
`Nov. 27, 2001
`Nov. 27, 2001
`
`Sheet 18 0f 31
`Sheet 18 of 31
`
`US 6,324,674 B2
`US 6,324,674 B2
`
`
`
`:5
`L.‘
`
`Page 19 of 52
`
`Page 19 of 52
`
`

`

`U.S. Patent
`US. Patent
`
`Nov. 27, 2001
`Nov. 27, 2001
`
`Sheet 19 0f 31
`Sheet 19 of 31
`
`US 6,324,674 B2
`US 6,324,674 B2
`
`
`
`~
`:5
`G::
`L.‘
`
`Page 20 of 52
`
`Page 20 of 52
`
`

`

`U.S. Patent
`US. Patent
`
`Nov. 27, 2001
`Nov. 27, 2001
`
`Sheet 20 0f 31
`Sheet 20 of 31
`
`US 6,324,674 B2
`US 6,324,674 B2
`
`
`
`£5
`I4,
`
`Page 21 of 52
`
`Page 21 of 52
`
`

`

`U.S. Patent
`US. Patent
`
`Nov. 27, 2001
`Nov. 27, 2001
`
`Sheet 21 0f 31
`Sheet 21 of 31
`
`US 6,324,674 B2
`US 6,324,674 B2
`
`n?N
`
`N
`
`”5
`Q
`‘0
`
`o;
`S
`
`D
`3%
`
`f\
`NN
`
`‘0
`'22
`«3
`
`2
`<0
`
`0,
`Q
`$3
`
`V~
`%
`
`Co
`NN
`
`N)
`NN
`
`~ -
`
`C)
`N
`~
`
`~
`\\
`
`~
`%
`G::
`
`Page 22 of 52
`
`"3
`
`N “
`
`3
`
`~ -
`ESto
`
`~ -
`
`-c-...
`-
`
`N a
`
`Page 22 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 22 of 31
`
`US 6,324,674 B2
`
`FIG. 12
`
`122
`
`•
`'\
`124
`
`FIG. 13
`
`121
`
`126
`
`126
`
`Page 23 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 23 of 31
`
`US 6,324,674 B2
`
`4-.---~--_.., _____ _
`
`FIG. 14
`
`702
`
`703
`
`706
`
`704
`
`700
`
`701
`
`705
`0 -+------4---_,._ _______ :;____~
`2
`4
`3
`0
`
`FIG. 15A
`
`FIG. 158
`
`LEVEL 2
`
`Page 24 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 24 of 31
`
`US 6,324,674 B2
`
`FIG. 16A 16
`
`15
`14
`13
`12
`11
`10
`9
`8
`7
`6
`5
`4
`3
`2
`1
`0
`
`I
`
`720
`\
`
`FIG. 168 16
`
`722
`
`0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
`
`'
`
`721
`
`I '
`
`0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
`
`15
`14
`13
`12
`l1
`10
`9
`8
`7
`6
`5
`4
`3
`2
`1
`0
`
`Page 25 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 25 of 31
`
`US 6,324,674 B2
`
`730
`
`r---7
`740_/t ___ I
`
`I
`
`I
`
`FIG. 19
`80
`\
`84
`\ ______
`
`(__
`
`81
`
`I
`I
`I
`I
`I
`I
`
`82
`I
`L/
`---------------
`
`I
`I
`I
`I
`I
`I
`
`FIG. 17
`
`731
`
`81
`\
`)
`
`82
`\
`LJ
`
`I
`I
`I
`f'..85
`I
`
`85
`84
`84
`------~---~- -----~
`
`83
`J
`
`8(
`
`81
`LJ
`
`I
`I
`I
`I
`I
`I
`
`I
`
`: 84
`
`I
`I
`
`I
`
`I 85
`~--~-
`I
`I
`I
`I
`I
`I
`I
`I
`
`___ }_ __
`85
`85-1
`
`I
`
`I 84
`
`------V- --
`
`I
`
`V-85
`
`I
`I
`I
`
`I 84
`
`I
`
`------,
`I 8Z
`______ j,d.
`,_ _____________ ------•
`
`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
`
`f"'...8s
`
`8Z
`
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`
`•--7-- -----7-------------;------ -----1
`
`85
`
`84
`
`84
`
`84
`
`'--- 83
`
`Page 26 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 26 of 31
`
`US 6,324,674 B2
`
`70 \
`
`INPUT:
`NET LIST, PARAMETERS
`k, r, NUMBER OF ITERATIONS
`
`v11
`
`PARTITION LARGE NETS /72
`INTO SMALLER ONES
`
`CONSTRUCT THE ROUTING /73
`GRAPH AND- CALCULATE
`CAPACITIES
`
`CREATE TILENETS, HYPERTREES v14
`AND SUPERFORESTS
`
`ADD PROJECTED OCCUPANCIES BASED V
`
`ON HYPERTREES BOUNDING BOXES
`CALCULATE PENALTIES
`
`75
`
`ROUTE NETS IN PARALLEL. AS SOON
`AS A NET IS ROUTED, ITS PROJECTED /
`OCCUPANCY IS REPLACED WITH
`THE ACTUAL ONE AND THE AFFECTED
`PENALTIES ARE RECALCULATED.
`
`'6
`7i
`
`REROUTE THE NETS PASSING THROUGH V
`CONGESTED AREAS. REPEAT THIS PROCEDURE
`NUMBER OF ITERATIONS TIMES
`
`77
`
`FIG. 18
`
`Page 27 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 27 of 31
`
`US 6,324,674 B2
`
`FIG.
`
`20
`
`INPUT:
`A NET (A SET OF PINS),
`PARAMETER k
`
`1001
`
`1000
`
`/
`
`FIND ALL BASIS ELEMENTS
`
`CALCULATE COMPLEXITY OF
`EACH BASIS ELEMENT
`
`CALCULATE COMPLEXITY OF
`EACH SUBSET NOTING ON
`WHICH BASIS ELEMENT IT
`IS ACHIEVED ON
`
`1002
`
`1003
`
`1004
`
`GO BACKWARDS THROUGH THE LIST
`OF THE BASIS ELEMENTS THE
`COMPLEXITY WAS ACHIEVED ON
`AND ADD THEM TO THE HYPEREDGES
`
`1005
`
`1020
`
`1021
`
`FIG. 21A
`
`1027
`
`1029
`
`1026
`
`FIG. 218
`
`1032
`
`1035
`
`1030
`
`1033
`
`1034
`1031 FIG. 21C
`
`Page 28 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 28 of 31
`
`US 6,324,674 B2
`
`FIG. 22
`
`1020
`
`\._
`
`INPUT:
`NET LIST, PARAMETER k, FIRST LEVEL ROUTING
`
`1021
`
`FOR EACH NET GENERATE LOCAL TASKS
`
`1022
`
`SOLVE LOCAL TASKS IN PARALLEL,
`GIVING EACH PROCESSOR A HORIZONTAL LINE
`
`1023
`
`.-------.. NO
`.__ __ k=k-1 - -
`
`1024
`
`END
`
`FIG. 24
`1030~
`
`INPUT:
`NET LIST, PARAMETER k, FIRST LEVEL ROUTING
`
`1031
`
`FOR EACH OPTIMIZING MESH AND EACH NET FRAGMENT
`PASSING THROUGH IT GENERATE GENERAL TASKS
`
`1032
`
`SOLVE GENERAL TASKS IN PARALLEL, GIVING
`EACH PROCESSOR AN OPTIMIZING MESH
`
`1033
`
`GET ROUTING ON NEXT LEVEL
`USING THE ALGORITHM FROM [2]
`
`1034
`
`Page 29 of 52
`
`

`

`U.S. Patent
`US. Patent
`
`Nov. 27, 2001
`Nov. 27, 2001
`
`Sheet 29 of 31
`Sheet 29 0f 31
`
`US 6,324,674 B2
`US 6,324,674 B2
`
`,--------r--------,--------~---------r--------T--------,
`W:-
`
`I
`I
`I
`:
`
`.-
`U
`
`__._nnu_u_F___uU_Fm_<u________r||||||||||._.
`IIIIIIIIIIPIIIIIIIIII.—
`
`mfim6E
`
`<
`
`I
`I
`I
`I
`
`N
`U
`
`I
`I
`I
`I
`
`I
`I
`I
`I
`
`I
`I
`I
`I
`
`L.i....N
`
`I
`I
`I
`I
`
`
`
` .T.........,_r........4.,.........2.____m:nnJn___u_________,.........+........F..........2.uunNu___.ua__ouunnu_,.........+........+.........2____n_un_nnm__ou_____.__.1.........+........+.........,_uuuu____uwe__N<“nuuu_T.........h........+_.........2.
`
`0
`
`I
`I
`I
`I
`I
`~---
`I
`I
`I
`I
`I
`.-
`1~
`I
`I
`I
`I
`~---
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`N
`I
`N
`. -
`__.
`I
`I
`""
`N
`0
`-
`(!)
`I
`-
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`~--------~--------~---------1---------~--------~--------~
`
`I
`I
`I
`I
`I
`
`---~
`
`---~
`
`I
`I
`I
`:
`
`N
`
`
`
` .1..........a..........a..........2.__N.___I__uy__No"____________
`
`I
`I
`I
`I
`N I
`I i
`I
`I
`I
`I
`
`_J w
`c;j
`
`_J
`
`._m_>m._Emmmzo
`
`
`
`1-(cid:173)z w
`
`Q::
`Q::
`:::,
`<..)
`
`_J w
`c:i _J
`
`d>u._325%
`
`
`
`er,
`::::>
`0
`
`25 Q::
`
`Cl..
`
`,-----------------,------------------r-----------------,
`
`U
`
`L.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
`
`~-------- --------,------- ~--------r-------- --------~
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`———-————+————-——- ~--——-——4
`I
`I
`
`W
`
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`~-------- --------,------· ~--------r-------- --------~
`
`I
`
`I
`I
`I
`I
`i
`T
`I
`I
`I
`I
`
`~
`
`__.
`-
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`-
`'-"
`
`,,..
`-.J
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`~-----------------~------------------~-----------------~
`
`Page 30 of 52
`
`Page 30 of 52
`
`
`
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 30 of 31
`
`US 6,324,674 B2
`
`1063
`
`1064
`
`1071
`
`FIG. 25
`
`INPUT: NET LIST, PARAMETERS n.
`
`DIVIDE NETS INTO GROUPS OF n.
`ASSIGN A LOCK TO EACH GROUP
`
`1061
`
`1062
`
`CREATE CHARACTER ARRAY a(), FILL IT WITH ZEROS
`EACH PROCESSOR GETS A REGION
`
`FOR EACH SUBNET IN THE REGION, FIND ITS NET, SAY i
`
`NO
`
`1067
`
`RELEASE LOCK
`
`1068
`
`ROUTE THE SUBNET
`
`1069
`
`1070
`
`Page 31 of 52
`
`

`

`U.S. Patent
`
`Nov. 27, 2001
`
`Sheet 31 of 31
`
`US 6,324,674 B2
`
`FIG. 26
`800 \
`
`806
`
`NETLIST - - - - -
`
`MEM
`
`804
`
`802
`
`808
`
`NETLIST
`t - - - - - , t - - - - - - i WITH HIGH
`FANOUT NETS
`ELIMINATED
`
`FIG. 27
`
`900
`
`914
`
`INFO
`
`901
`
`INPUT
`
`MEMORY
`
`906
`
`OUTPUT
`
`908
`
`912
`
`LAYOUT
`
`910
`
`Page 32 of 52
`
`

`

`US 6,324,674 B2
`
`1
`METHOD AND APPARATUS FOR PARALLEL
`SIMULTANEOUS GLOBALAND DETAIL
`ROUTING
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`The present invention generally relates to the art of
`microelectronic integrated circuits. In particular, the present
`invention relates to the art of processing high fanout nets for 10
`purposes of routing integrated circuit chips.
`2. Description of Related Art
`An integrated circuit chip (hereafter referred to as an "IC"
`or a "chip") comprises cells and connections between the
`cells formed on a surface of a semiconductor substrate. The 15
`IC may include a large number of cells and require complex
`connections between the cells.
`A cell is a group of one or more circuit elements such as
`transistors, capacitors, and other basic circuit elements
`grouped to perform a function. Each of the cells of an IC 20
`may have one or more pins, each of which, in turn, may be
`connected to one or more other pins of the IC by wires. The
`wires connecting the pins of the IC are also formed on the
`surface of the chip.
`A net is a set of two or more pins which must be
`connected. Because a typical chip has thousands, tens of
`thousands, or hundreds of thousands of pins which must be
`connected in various combinations, the chip also includes
`definitions of thousands, tens of thousands, or hundreds of
`thousands of nets, or sets of pins. All the pins of a net must
`be connected. The number of the nets for a chip is typically
`in the same order as the order of the number of cells on that
`chip. Commonly, a majority of the nets include only two
`pins to be connected; however, many nets comprise three or
`more pins. Some nets may include hundreds of pins to be
`connected. A netlist is a list of nets for a chip.
`Microelectronic integrated circuits consist of a large num(cid:173)
`ber of electronic components that are fabricated by layering
`several different materials on a silicon base or wafer. The
`design of an integrated circuit transforms a circuit descrip(cid:173)
`tion into a geometric description which is known as a layout.
`A layout consists of a set of planar geometric shapes in
`several layers.
`The layout is then checked to ensure that it meets all of the 45
`design requirements. The result is a set of design files in a
`particular unambiguous representation known as an inter(cid:173)
`mediate form that describes the layout. The design files are
`then converted into pattern generator files that are used to
`produce patterns called masks by an optical or electron beam 50
`pattern generator.
`During fabrication, these masks are used to pattern a
`silicon wafer using a sequence of photolithographic steps.
`The component formation requires very exacting details
`about geometric patterns and separation between them. The 55
`process of converting the specifications of an electrical
`circuit into a layout is called the physical design.
`Currently, the minimum geometric feature size of a com(cid:173)
`ponent is on the order of 0.2 microns. However, it is
`expected that the feature size can be reduced to 0.1 micron 60
`within the next few years. This small feature size allows
`fabrication of as many as 4.5 million transistors or 1 million
`gates of logic on a 25 millimeter by 25 millimeter chip. This
`trend is expected to continue, with even smaller feature
`geometries and more circuit elements on an integrated 65
`circuit, and of course, larger die ( or chip) sizes will allow far
`greater numbers of circuit elements.
`
`2
`Due to the large number of components and the exacting
`details required by the fabrication process, physical design
`is not practical without the aid of computers. As a result,
`most phases of physical design extensively use Computer
`5 Aided Design (CAD) tools, and many phases have already
`been partially or fully automated. Automation of the physi(cid:173)
`cal design process has increased the level of integration,
`reduced turn around time and enhanced chip performance.
`The objective of physical design is to determine an
`optimal arrangement of devices in a plane or in a three
`dimensional space, and an efficient interconnection or rout(cid:173)
`ing scheme between the devices to obtain the desired
`functionality.
`A IC Configuration.
`An exemplary integrated circuit chip is illustrated in FIG.
`1 and generally designated by the reference numeral 26. The
`circuit 26 includes a semiconductor substrate 26A on which
`are formed a number of functional circuit blocks that can
`have different sizes and shapes. Some are relatively large,
`such as a central processing unit (CPU) 27, a read-only
`memory (ROM) 28, a clock/timing unit 29, one or more
`random access memories (RAM) 30 and an input/output
`(1/0) interface unit 31. These blocks, commonly known as
`25 macroblocks, can be considered as modules for use in
`various circuit designs, and are represented as standard
`designs in circuit libraries.
`The integrated circuit 26 further comprises a large
`number, which can be tens of thousands, hundreds of
`30 thousands or even millions or more of small cells 32. Each
`cell 32 represents a single logic element, such as a gate, or
`several logic elements interconnected in a standardized
`manner to perform a specific function. Cells that consist of
`two or more interconnected gates or logic elements are also
`35 available as standard modules in circuit libraries.
`The cells 32 and the other elements of the circuit 26
`described above are interconnected or routed in accordance
`with the logical design of the circuit to provide the desired
`functionality. Although not visible in the drawing, the vari(cid:173)
`ous elements of the circuit 26 are interconnected by elec(cid:173)
`trically conductive lines or traces that are routed, for
`example, through vertical channels 33 and horizontal chan(cid:173)
`nels 34 that run between the cells 32.
`B. Layout Design Process.
`The input to the physical design problem is a circuit
`diagram, and the output is the layout of the circuit. This is
`accomplished in several stages including partitioning, floor
`planning, placement, routing and compaction.
`1. Partitioning
`A chip may contain several million transistors. Layout of
`the entire circuit cannot be handled due to the limitation of
`memory space as well as the computation power available.
`Therefore it is normally partitioned by grouping the com(cid:173)
`ponents into blocks such as subcircuits and modules. The
`actual partitioning process considers many factors such as
`the size of the blocks, number of blocks and number of
`interconnections between the blocks.
`The output of partitioning is a set of blocks, along with the
`interconnections required between blocks. The set of inter(cid:173)
`connections required is the netlist. In large circuits, the
`partitioning process is often hierarchical, although non(cid:173)
`hierarchical ( e.g. flat) processes can be used, and at the
`topmost level a circuit can have between 5 to 25 blocks.
`However, greater numbers of blocks are possible and con(cid:173)
`templated. Each block is then partitioned recursively into
`smaller blocks.
`
`40
`
`Page 33 of 52
`
`

`

`US 6,324,674 B2
`
`4
`The layering operation adds thin layers of material,
`including insulators, semiconductors, and conductors, to a
`wafer surface. During the layering operation, layers are
`either grown or deposited. Oxidation involves growing a
`silicon dioxide ( an insulator) layer on a silicon wafer.
`Deposition techniques include, for example, chemical vapor
`deposition, evaporation, and sputtering. Semiconductors are
`generally deposited by chemical vapor deposition, while
`conductors are generally deposited with evaporation or
`sputtering.
`Patterning involves the removal of selected portions of
`surface layers. After material is removed, the wafer surface
`has a pattern. Such a pattern may include the wires that
`connect cells. Where the present invention is utilized, the
`wiring patterns will be formed as a function of the output of
`the present invention. The wiring patterns will be a material
`removed may form a hole or an island. The process of
`patterning is also known to those skilled in the relevant art
`as microlithography, photolithography, photomasking and
`masking. The patterning operation serves to create parts of
`the semiconductor device on the wafer surface in the dimen-
`sions required by the circuit design and to locate the parts in
`their proper location on the wafer surface.
`Doping involves implanting dopants in the surface of the
`wafer through openings in the layers to create then-type and
`p-type pockets needed to form the N-P junctions for opera(cid:173)
`tion of discrete elements such as transistors and diodes.
`Doping is generally achieved with thermal diffusion (wafer
`is heated and exposed to the desired dopant) and ion
`30 implantation ( dopant atoms are ionized, accelerated to high
`velocities and implanted into the wafer surface).
`
`3
`2. Floor Planning and Placement
`This step is concerned with selecting good layout alter(cid:173)
`natives for each block of the entire chip, as well as between
`blocks and to the edges. Floor planning is a critical step as
`it sets up the ground work for a good layout. Floor planning 5
`is discussed in U.S. Pat. No. 4,918,614, entitled "Hierarchi-
`cal Floorplanner" issued to Modarres on Apr. 17, 1990. Said
`patent is incorporated herein as though set forth in full.
`During placement, the blocks are exactly positioned on the
`chip. The goal of placement is to find a minimum area 10
`arrangement for the blocks that allows completion of inter(cid:173)
`connections between the blocks. Placement is typically done
`in two phases. In the first phase, an initial placement is
`created. In the second phase, the initial placement is evalu(cid:173)
`ated and iterative improvements are made until the layout 15
`has minimum area and conforms to design specifications.
`One particular placement process is described in U.S. Patent
`Application of R. Scepanovic et al., entitled "Advanced
`Modular Cell Placement System With Neighborhood Sys(cid:173)
`tem Dri