United States Patent (19)
`Rostoker et al.
`
`54
`
`75
`
`(73
`
`COMPUTER IMPLEMENTED METHOD FOR
`PRODUCING OPTIMIZED CELL
`PLACEMENT FOR INTEGRATED CIRCLUT
`CHIP
`
`Inventors: Michael D. Rostoker, Boulder Creek;
`James S. Koford, San Jose; Edwin R.
`Jones, Sunnyvale; Douglas B. Boyle,
`Palo Alto; Ranko Scepanovic,
`Cupertino, all of Calif.
`Assignee: LSI Logic Corporation, Milpitas,
`Calif.
`
`Notice:
`
`The term of this patent shall not extend
`beyond the expiration date of Pat. No.
`5.495.419.
`
`21
`22
`
`Appl. No.: 559,206
`Fed:
`Nov. 13, 1995
`
`Related U.S. Application Data
`Continuation of Ser. No. 229,826, Apr. 19, 1994, Pat. No.
`5,495,419.
`Int. Clam. G06F 19/00
`U.S. Cl. ... 364/468.28: 364/468.2:
`364/491
`Field of Search ............................ 364/468, 488-493,
`364/468.03, 468.2, 468.28; 395/10, 13
`
`I63)
`
`51
`52)
`
`(58
`
`US005636125A
`Patent Number:
`11
`45 Date of Patent:
`
`5,636,125
`*Jun. 3, 1997
`
`56
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,144,563 9/1992 Date et al. .............................. 364/491
`5,200,908 4/1993 Date et al. .............................. 364/491
`5,495,419 2/1996 Rostoker et al. ....................... 364468
`Primary Examiner-James P. Trammell
`Attorney, Agent, or Firm-Oppenheimer Poms Smith
`57
`ABSTRACT
`In a physical design automation system for producing an
`optimized cell placement for an integrated circuit chip, a
`placement optimization methodology is decomposed into a
`plurality of cell placement optimization processes that are
`performed simultaneously by parallel processors on input
`data representing the chip. The results of the optimization
`processes are recomposed to produce an optimized cell
`placement. The fitness of the optimized cell placement is
`analyzed, and the parallel processors are controlled to selec
`tively repeat performing the optimization processes for
`further optimizing the optimized cell placement if the fitness
`does not satisfy a predetermined criterion. The system can
`be applied to initial placement, routing, placement improve
`ment and other problems. The processors can perform the
`same optimization process on different placements, or on
`areas of a single placement. Alternatively, the processors can
`perform different optimization processes simultaneously on
`a single initial placement, with the resulting processed
`placement having the highest fitness being selected as the
`optimized placement. The processors can further selectively
`reprocess areas of a placement having high cell interconnect
`congestion or other low fitness parameters.
`17 Claims, 33 Drawing Sheets
`
`
`
`
`
`PARALLE PROCESS
`
`
`
`R4 the
`
`
`
`
`
`REFOCUS
`OPTIMIZATION
`
`
`
`
`
`OPTIMIZATION
`EAIATION
`
`RECOMPOSITION
`
`OBJECTIVE
`REACHED
`2
`
`Page 1 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 1 of 33
`
`5,636,125
`
`
`
`VN
`
`n N- to ten colo)
`n-SNNN
`SSSSSS
`
`o r l) on to Co. in or oy
`NaNNNNNNN
`SSSSSSSSS
`
`cN n w to ge
`ann SN
`SSESSESSENSS
`
`N- r o YN \, n)
`NNNNNN
`SSSSSSSS
`
`
`
`&
`
`r
`S
`
`Y
`es
`
`S.
`
`S
`
`
`
`DDDDD
`DDDDDDDD
`DDDDDDDDD
`DDDDDDDDDDDDDDD
`DDDDDDDDDDDDDDD
`Š-(DODDDDDDDDDDDDDDDD
`DDDDDDDDDDDDDDDDDD
`DDDDDDDDDDDDDD
`D
`
`s H DO
`
`DDD
`
`M DO
`
`S
`SS
`
`D D
`DD
`DO
`
`S
`
`Page 2 of 66
`
`

`

`U.S. Patent
`US. Patent
`
`J
`
`3
`
`
`
`an
`
`$88qumE2:$3$26
`
`1,mgmmmugq59,38wa
`mgMmm
`
`
`
`
`
`
`
`
`SQNN
`
`f
`
`0Eggfr2SEESEEmmaNEW‘
`
`5,636,125
`5,636,125
`
`B$5.85
`
`ESS:
`I
`
`
`
`g
`
`V.
`
`Page 3 of 66
`
`Page 3 of 66
`
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 3 of 33
`
`5,636,125
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SWOII WON HIO3dS 1/1d/WI
`
`Page 4 of 66
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 3, 1997
`Jun. 3, 1997
`
`Sheet 4 of 33
`Sheet 4 of 33
`
`5,636,125
`5,636,125
`
`
`
`«emmmgeml
`
`E_ES:53
`
`
`__.1IlllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllrIIII.u_nm2%£338_m"“SSEa8EEQSQ"n__u_"“Eagmtfimw.mm$258?$595$,qu"um3952%mamzmsfim“mm‘_rL
`
`
`mommmgsmn.
`
`xkbém:#63
`
`kw
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`9 '60/-/
`
`m6E
`
`\EQ‘E:
`
`Page 5 of 66
`
`Page 5 of 66
`
`
`
`
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 5 of 33
`
`5,636,125
`
`
`
`SXSWI 0707/WWW.001
`
`894
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 6 of 66
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 3, 1997
`
`Sheet 6 of 33
`
`5,636,125
`
`5
`
`
`
`2M,:233%$33.3m$333EEEaEgg3NEE
`.\$33wt.3.0:36:3ESv3.3ga3.3
`
`we
`
`5$3$5an3Na.a*33w3;
`
`B3QmE3E335WENENNQNQWVS33%mgagfimtv.3
`M,§§aMgGE
`s§§IE}Ira“Ex33asNEaN33Ea
`
`Page 7 Of 66
`
`Page 7 of 66
`
`
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 3, 1997
`Jun. 3, 1997
`
`Sheet 7 of 33
`Sheet 7 of 33
`
`5,636,125
`5,636,125
`
`
`
`
`
`
`
`
`
`9 / '0/-] Z ] '0/-/
`
`m:GERNGE
`
`K33S
`
`Page 8 of 66
`
`Page 8 of 66
`
`
`
`

`

`US. Patent
`
`Jun. 3, 1997
`
`Sheet 8 of 33
`
`5,636,125
`
`
`
`EEEE
`§§§§
`
`§§§§
`
`§§§§
`
`EN
`
`N“3.23
`
`
`
`EEEEEEEE
`
`§§§§
`
`EEEE
`E3
`EE
`Elgmxa
`EEES
`
`m
`
`Ia.“
`3E
`m?EEE
`ENNQ
`§§
`EE
`
`V.
`(\1
`
`9L
`
`L
`
`Page 9 of 66
`
`Page 9 of 66
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 3, 1997
`Jun. 3, 1997
`
`Sheet 9 of 33
`Sheet 9 of 33
`
`5,636,125
`5,636,125
`
`F769.26
`
`
`
`Š 11 ss ŠssŠ
`
`F/G.25
`
`Page 10 of 66
`
`Page 10 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 10 of 33
`
`5,636,125
`
`
`
`
`
`C)
`
`
`
`
`
`
`
`
`
`
`
`
`
`ODI
`
`ld. He
`- s
`
`
`
`H
`S
`
`CN
`
`S
`
`N
`
`N
`S
`
`
`
`
`
`S
`
`:
`
`DRaid
`N4 SN SNNO
`y
`
`
`
`
`
`
`
`
`
`
`
`Page 11 of 66
`
`

`

`U
`
`3
`
`m
`
`n
`
`(
`
`
`tSD$wW22338:Qazwm
`«MR,atQnu
`on”F35:~33WW.©\I.\
`
`
`
`qn/Emma~52meQ533%
`
`
`
`mamas22%ng
`
`1,NMwt
`
`J«$2So96$5.kcE25E35
`m.223quS:5ng
`
`
`
`mMKhfimadmwmomm&mm223qu952%E5rW
`
`w33figmastS8%3.25>6E35thSfig
`
`cm#33quNS58%$3233SEEma$8,333was53%
`
`
`
`
`Tlllllntd|IIIILl1ILSSS:EEEqu\zggaofimmSEE
`TtIQmIIIL§R€$EEK
`
`a_.k._mémmbg9.:E3P5i...EagaEVE;EmmiSESEEE2E3~58
`
`
`
`
`
`6.,NM,.UE1$22338E2ESmy
`5fHI.\u\M.
`
`r0r0
`
`Page 12 of 66
`
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 12 of 33
`
`5,636,125
`
`
`
`
`
`
`
`
`
`
`
`
`
`SWOI/%007 d'%S
`
`
`
`
`
`}}}/N/100 NOI!!!007 INEW}}}ONI
`
`Page 13 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 13 of 33
`
`5,636,125
`
`FIG. 34d
`
`COst --
`min cost --
`
`940
`940
`
`avg cost --
`
`990
`
`max cost as 1000
`
`Variance - -
`
`94.800000
`
`min cost . .
`
`940
`
`avg cost -
`
`979
`
`max cost - 990
`
`Variance -
`
`83.04.0000
`
`min cost --
`
`930
`
`avg Cost --
`
`971.
`
`max cost = 980
`
`variance --
`
`78.440000
`
`min cost --
`
`930
`
`avg cost --
`
`963
`
`max cost = 980
`
`Variance - -
`
`100,480000
`
`min cost --
`
`900
`
`avg Cost --
`
`954
`
`max cost = 970
`
`Variance - -
`
`124.520000
`
`cost - -
`min cost --
`
`890
`890
`
`avg cost --
`
`943
`
`max cost = 960
`
`Variance
`
`- 13.720000
`
`rain cost --
`
`880
`
`avg cost --
`
`931
`
`max cost = 950
`
`variance --
`
`168.000000
`
`in cost --
`
`860
`
`avg cost --
`
`917
`
`max cost = 940
`
`variance
`
`. 185. 680000
`
`nin cost --
`
`840
`
`avg cost -
`
`902
`
`max cost = 920
`
`Variance
`
`- 218.760000
`
`min cost -
`
`830
`
`avg cost -
`
`max cost = 910
`
`Variance
`
`- 233,860000
`
`10
`10
`
`780
`760
`
`avg COst
`
`865
`
`variance
`
`279.400000
`
`step - -
`step - -
`ICICSnlS
`step - -
`mcmcsins
`step - -
`mCICSns
`step - -
`NCACSnlS
`step - -
`mcmcsins
`step - -
`step - -
`ACIACSnlS
`step - .
`incCSns
`step - -
`IctacSms
`step - -
`IncIncSnls
`step - -
`mcmcsins
`step - -
`step - -
`MCFACSnts
`step - -
`INCITICSns
`step - -
`RcmCSnls
`step - -
`mcmcsins
`step - -
`CBCSnls
`step - -
`step - -
`IncIncSns
`step - -
`ICRCSnlS
`step - -
`mCPCsnils
`Step - -
`ICIncSms
`step - -
`PCACSnls
`Step - -
`step - -
`
`CoSt - -
`in cost --
`
`max cost as 890
`
`11.
`
`min cost --
`
`760
`
`avg cost --
`
`845
`
`max cost is 870
`
`Variance - -
`
`307. 600000
`
`12
`
`min cost --
`
`760
`
`avg cost -
`
`822
`
`max cost is 850
`
`variance
`
`287.520000
`
`13
`
`min cost --
`
`70
`
`avg cost --
`
`799
`
`max cost = 820
`
`Variance
`
`14
`
`min cost --
`
`700
`
`avg cost -
`
`771
`
`max cost = 800
`
`Variance
`
`- 356,600000
`- 376.720000
`
`15
`15
`
`COSt --
`min cost --
`
`660
`660
`
`avg cost --
`
`744
`
`max cost = 770
`
`Variance
`
`369.020000
`
`6
`
`Rain cost - -
`
`60
`
`avg cost --
`
`716
`
`max cost = 740
`
`Variance - -
`
`422.540000
`
`17
`
`min cost --
`
`590
`
`avg cost -
`
`max cost = 710
`
`variance
`
`- 480.500000
`
`18
`
`nin cost --
`
`570
`
`avg COst --
`
`649
`
`max cost = 680
`
`variance
`
`- 460.480000
`
`19
`
`nin cost --
`
`550
`
`avg cost --
`
`69
`
`max cost = 650
`
`Variance
`
`. 421.880000
`
`20
`2O
`
`COst - -
`min cost --
`
`500
`500
`
`avg cost --
`
`max cost = 620
`
`variance
`
`. 443.640000
`
`Page 14 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 14 of 33
`
`5,636,125
`
`FIG. 34b
`
`2.
`
`min cost --
`
`430
`
`avg cost --
`
`558
`
`max cost m
`
`590
`
`Variance -- 446,800000
`
`22
`
`min cost --
`
`430
`
`avg cost --
`
`527
`
`max cost me
`
`560
`
`Variance
`
`- - 483.120000
`
`23
`
`min cost --
`
`410
`
`avg cost --
`
`494
`
`Tax cost =
`
`520
`
`Variance - -
`
`446.420000
`
`24
`
`min cost --
`
`380
`
`avg cost --
`
`A59
`
`max cost =
`
`490
`
`Variance - -
`
`433.560000
`
`25
`25
`
`COst --
`min cost --
`
`340
`340
`
`avg cost --
`
`428
`
`max cost =
`
`460
`
`Variance - -
`
`395.740000
`
`26
`
`min cost --
`
`310
`
`avg cost --
`
`398
`
`max cost =
`
`420
`
`Variance - -
`
`361.140000
`
`27
`
`in cost --
`
`290
`
`avg cost --
`
`367
`
`max cost =
`
`390
`
`Variance - -
`
`354.640000
`
`28
`
`Pain cost --
`
`260
`
`avg cost --
`
`336
`
`max cost =
`
`360
`
`Variance - -
`
`376.020000
`
`29
`
`min cost --
`
`220
`
`avg cost --
`
`305
`
`max cost F
`
`330
`
`Variance
`
`... 358. 800000
`
`278
`
`300
`
`Variance
`
`- 301.240000
`
`mcmcsins
`step --
`NCCSnls
`step - -
`mCMcSnls
`step - -
`mCMcSnts
`step - -
`mcmCSnls
`step - -
`step - -
`mcmcsnils
`step - -
`ICIncSns
`step - -
`mcmcsins
`step - -
`CCSnlS
`step - -
`cancSnlS
`step - -
`step --
`FCICSns
`step - -,
`mcmcsins
`step - -
`mcincSnls
`step - -
`Acmcsnils
`step - -
`Rcmcsins
`step - -
`step - -
`mcmcsins
`step - -
`racRCSnls
`step - -
`TCTCSS
`step - -
`mcmcSnls
`step --
`mCacSnls
`step --
`
`30
`30
`
`COst - -
`rain cost --
`
`190
`190
`
`avg cost --
`
`max cost =
`
`31.
`
`nin cost --
`
`180
`
`avg cost --
`
`251.
`
`max cost =
`
`270
`
`Variance
`
`- 268.800000
`
`32
`
`Rain cost --
`
`140
`
`avg cost --
`
`225
`
`max cost =
`
`250
`
`Variance
`
`- 292.600000
`
`33
`
`rain cost --
`
`30
`
`avg cost --
`
`201
`
`max cost =
`
`220
`
`Variance
`
`286.600000
`
`34
`
`nin cost --
`
`90
`
`avg cost --
`
`176
`
`max cost =
`
`200
`
`Variance
`
`- - 271.500000
`
`35
`35
`
`Cost --
`rain cost --
`
`90
`90
`
`avg cost --
`
`151
`
`Pax cost -
`
`170
`
`Variance
`
`- - 230480000
`
`36
`
`min cost --
`
`70
`
`avg cost --
`
`130
`
`max cost =
`
`150
`
`Variance - -
`
`218.600000
`
`37
`
`rain cost --
`
`60
`
`avg cost --
`
`1.
`
`max cost =
`
`130
`
`Variance
`
`- 187.640000
`
`38
`
`min cost --
`
`30
`
`avg Cost --
`
`92
`
`max cost =
`
`110
`
`Variance
`
`- - 80.760000
`
`39
`
`min cost --
`
`20
`
`avg cost --
`
`73
`
`max cost =
`
`90
`
`Variance
`
`- 179.520000
`
`40
`
`COst - -
`
`Page 15 of 66
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 3, 1997
`Sheet 15 of 33
`Sheet 15 of 33
`Jun. 3, 1997
`FIG. 35
`FIG. 35
`5
`E
`-u
`.1
`'2
`3 it
`d
`8
`L)
`.4
`...
`C.
`50
`1
`50
`1.
`51
`7
`51
`7
`52
`99
`52
`99
`53
`51
`53
`51.
`54
`22
`54
`22
`55
`27
`55
`27
`56
`53
`56
`53
`57
`36
`57
`36
`58
`65
`58
`65
`59
`31
`59
`31.
`60
`75
`60
`75
`61
`40
`61.
`40
`
`5
`E
`'2
`_:
`8 it
`8
`d
`.4
`<3
`a
`C-d
`0
`58
`O
`58
`1
`29
`1.
`29
`2
`6
`2
`6
`3
`19
`3
`19
`4
`38
`4
`38
`5
`20
`5
`20
`6
`42
`6
`42
`7
`71
`7
`71
`8
`10
`8
`10
`9
`3
`9
`3
`10
`47
`10
`47
`11
`4
`11
`4
`12
`50
`12
`50
`13
`6O
`13
`50
`14
`44
`14.
`44
`15
`72
`15.
`72
`16
`28
`6
`28
`17
`52
`7
`52
`18
`44
`18
`44
`19
`58
`19
`58
`20
`80
`20
`80
`21
`52
`2.
`52
`22
`48
`22
`48
`23
`61
`23
`6.
`24
`64
`24
`64
`25
`32
`25
`32
`26
`76
`26
`76
`27
`89
`27
`89
`28
`25
`28
`25
`29
`59
`29
`59
`30
`97
`30
`97
`31
`55
`31
`55
`32
`8
`32
`8
`33
`13
`33
`13
`34
`98
`34
`98
`35
`82
`35
`82
`36
`95
`36
`95
`37
`33
`37
`33
`38
`37
`38
`37
`39
`0
`39
`O
`40
`30
`AO
`30
`41
`77
`41
`77
`42
`54
`42
`54
`43
`15
`A3
`15
`44
`81
`A4
`8.
`45
`26
`45
`26
`46
`2
`46
`2
`47
`49
`A7
`49
`48
`23
`A8
`23
`49
`86
`49
`86
`
`62
`62
`63
`63
`64
`64
`65
`65
`66
`66
`67
`67
`68
`68
`69
`69
`70
`70
`71
`71.
`72
`72
`73
`73
`74
`74
`75
`75
`76
`76
`77
`77
`78
`78
`79
`79
`8O
`80
`81
`81
`82'
`82
`83
`83
`84
`84
`85
`85
`86
`86
`87
`87
`88
`88
`89
`89
`90
`90
`91
`9.
`92
`92
`93
`93
`94
`94
`95
`95
`96
`96
`97
`97
`98
`98
`99
`99
`
`5
`5
`45
`45
`83
`83
`69
`69
`87
`87
`91
`9.
`24
`24
`93
`93
`69
`69
`43
`43
`34
`34
`50
`50
`46
`46
`92
`92
`12
`12
`20
`20
`5
`5
`85
`85
`35
`35
`16
`6
`84
`84
`96
`96
`41
`41
`17
`17
`67
`67
`63
`63
`68
`68
`39
`39
`57
`57
`9
`9
`90
`90
`56
`56
`87
`87
`88
`88
`74
`74
`62
`62
`15
`5
`21
`2.
`
`5,636,125
`5,636,125
`
`Page 16 of 66
`
`Page 16 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 16 of 33
`
`5,636,125
`
`FIG. 36
`
`2000
`
`100 0
`
`MINIMUM
`
`r
`0
`
`20
`
`40
`GENERATIONS
`
`60
`
`80
`
`
`
`ALIERATIONS
`
`Page 17 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 17 of 33
`
`5,636,125
`
`50
`
`r
`
`r s
`
`a
`
`O
`O
`
`100
`
`80
`
`S
`s
`& 60
`s
`s
`S 40
`
`Q
`
`
`
`20
`
`FIG. 45
`
`MAXIMUM
`
`
`
`MINIMUM AVERGE
`
`100
`
`200
`GENERATIONS
`
`300
`
`400
`
`it *
`
`-H
`
`--
`
`--
`---
`
`--
`
`--
`t
`t
`
`
`
`
`
`s
`
`EE
`
`EE
`i
`EEEEEEEE
`
`al
`
`EEEEEEE
`
`EE
`
`SE
`EE
`
`0
`f0
`
`20
`
`FIG. 46
`
`50
`40
`30
`WIRELENGTH BASED COST VALUE
`
`60
`
`Page 18 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 18 of 33
`
`5,636,125
`FIG. 47
`
`40
`
`35
`
`30
`
`25
`
`20
`
`CONGESION
`
`WIRELENGTH
`
`15
`
`10
`
`O f0 20 30 40 50 60 70 BO 90 100
`COST ALUE
`
`
`
`60
`
`
`
`
`
`40
`
`20
`
`0
`
`AVERAGE
`
`MINIMUM
`
`20
`GENERATIONS
`
`40
`
`FIG. 48
`
`Page 19 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 19 of 33
`
`5,636,125
`
`Worker -- started
`unique Worker name -- WOrk2
`network path ... net
`parse petlist
`40 statements
`220 names
`440 Conns
`140 prins
`100 cells
`40 pads
`2 types
`2 max pins on pet so. 0x
`2.000000 average pins/net
`3.142857 average pins/cell
`1.000000 min. bound wirelength
`load chip description
`load padref
`load optimal placement
`Working on region (0, 0) - (9, 9)
`step
`O cost: in 38.05 avg 46.01 tax 53.67
`std dev - 2.85 avg distance ... 0.00
`cheat a 990.00 (nin a 970.00, tax = 000.00)
`ranko = 38.05 yugo = 31.68 wire = 6.30
`step . .
`O
`cost -- 38.048944
`NMNMMNHCCCCCCR
`step
`1 cost: in 33.59 avg 43.56 max 50.61
`std dev -- 3.29 avg distance
`98.98
`cheat = 970.00 (nin a 950.00, tax r 1000.00)
`ranko s 29.10 yugo - 31.52 wire = 5.14
`NNNMMNNICCCCCCR
`step
`2 cost: in 29.10 avg 39.48 aax 48.95
`std dev -- 4.15 avg distance. 96.76
`cheat = 980.00 (nin = 950.00, tax = 1000,00)
`ranko = 29.10 yugo as 31.59 wire F 5.14
`NNNNNMMCCCCCCR
`step
`3 cost: in 26.90 avg 36.16 max 48.16
`std dev - 4.67 avg distance
`97.94
`cheat = 980.00 (in = 920.00, tax = 1000.00)
`ranko = 26.90 yugo = 31.52 wire = 4.50
`NNMNNNMNCCCCCCR
`step
`4 cost; in 23.26 avg 32.59 max 46.99
`std dev -- 4.67 avg distance
`95.21
`cheat = 950.00 (in = 90.00, tax = 1000,00)
`ranko 23.26 yugo 32.27 wire is 4.26
`NNMMNMNNCCCCCCR
`step
`5 cost: Pain 21.54 avg 29.38 Bax 43.33
`std dev . . 4.09 avg distance - 90.03
`cheat s 980.00 (in = 90.00, ax = 1000.00)
`ranko is 21.54 yugo as 31.76 wire E 4.26
`step - -
`5
`Cost - - 2.543444
`NNNMMNMCCCCCCR
`step
`6 cost: min 19.19 avg 27.21 max 40.92
`std dev - 4.04 avg distance -82.35
`cheat is 980.00 (in as 920.00, tax = 1000.00)
`ranko = 19.19 yugo = 31.75 wire = 4.01
`NNNNNNMCCCCCCR
`
`FIG. 490
`7 cost: Pain 38.42 avg 25.20 max 40.36
`step
`std dev -- 3.83 avg distance - 83.71
`cheat = 980.00 (Rin as 880.00, Pax = 1000,00)
`18.43 yugo = 31.71 wire = 3.92
`ranko
`NMNMNCCCCCCR
`step
`8 cost: Rin 18.43 avg 23.02 Tax 35.82
`std dev .. 3.18 avg distance - 89.51
`cheat = 980.00 (min = 860.00, tax = 1000.00)
`ranko = 18.43 yugo = 31.71 wire = 3.92
`NNNMMNNICCCCCCR
`step
`9 cost: min 17.27 avg 22.08 Rax. 38.14
`std dev -- 3.36 avg distance
`89.64
`cheat is 890.00 (Min = 850.00, max = 990,00)
`ranko a 7.27 yugo F 31.01 wire = 3.63
`NNNNMMNMMCCCCCCR
`step
`10 cost: in 16.13 avg 20.99 Max 34.48
`std dev .. 3.09 avg distance. 89.64
`cheat s 850.00 (min = 850.00, lax at 990.00)
`ranko = 16.13 yugo = 31.01 wire s 3.50
`step --
`10
`cost -- 16.125446
`NNMNNN NCCCCCCR
`step
`11 cost: in 15.73 avg 19.84 max. 34.48
`std dev -- 3.02 avg distance .. 88.60
`cheat is 830.00 (Rin = 820.00, ax = 990.00)
`ranko = 15.73 yugo = 31.05 wire = 3.34
`NNMMNNMNNCCCCCCR
`step
`12 cost: nin 15.03 avg 18.81 max 29.43
`std dev - 2.42 avg distance .. 88.25
`cheat a 880.00 (Rin a 780.00, axis 990.00)
`ranko = 15.03 yugo a 31.05 wire = 3.34
`NNNMMNCCCCCCR
`step
`13 cost: nin 14.61 avg 17.77 Hax 36.13
`std dev -- 2.61 avg distance - 87.88
`cheat as 880,00 (in = 770.00, Pax = 980,00)
`ranko = 13.22 yugo = 30.91 wire = 3.20
`NNNMMNNMCCCCCCR
`step
`14 cost: in 13.22 avg 16.77 Rax. 24.76
`std dev -- 2.51 avg distance .. 87.88
`cheat a 820.00 (ain = 790.00, tax = 970.00)
`ranko = 13.22 yugo = 30,91 wire = 3.02
`NNNNN NCCCCCCR
`step
`15 cost: in 12.22 avg 15.91 max 22.79
`std dev - 2.12 avg distance. 83.45
`cheat = 800.00 (in s 780.00, max = 960,00)
`ranco = 12.22 yugo is 30.91 wire = 3.02
`step --
`15
`cost -- 12.21924.7
`NMMNNMNCCCCCCR
`step
`16 cost: Rin 11.51 avg 15.40 max 26.64
`std dev - 2.57 avg distance. 85.07
`cheat = 840.00 (in a 720.00, rax = 930.00)
`rmako 11.51 yugo is 30.05 wire = 2.62
`MNNMNNNNCCCCCCR
`step
`17 cost: Pin 11.10 avg 14.84 max 22.19
`std dev -- 2.00 avg distance -- 86.10
`
`Page 20 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 20 of 33
`
`5,636,125
`
`FIG. 49b
`ranko = 8.05 yugo s 26.11 wire = 1.79
`cheat = 680.00 (min = 680.00, Max = 920.00)
`NNNNNNNNMCCCCCCR
`ranko = 11.10 yugo = 29.55 wire = 2.58
`NMNMMNMCCCCCCR
`step
`28 cost: min 1.64 avg 2.08 max 3.01
`std dev -- 0.25 avg distance.-- 64.42
`step
`18 cost: Rin 10.39 avg 14.32 max 23.80
`cheat = 380.00 (min = 380.00, ax = 750,00)
`std dev - 2.39 avg distance .. 87.77
`ranko = 7.11 yugo 25.69 wire at 1.64
`cheat is 690.00 (in = 670.00, tax = 930.00)
`NMNMMMMMCCCCCCR
`ranko = 10.39 yugo a 28.34 wire 2.38
`NNNMMMNNMCCCCCCR
`step
`29 cost: Rin 1.64 avg 2.02 max 2.88
`switching cost function to wire
`std dev -- 0.25 avg distance .. 64.29
`cheat = 380.00 (min = 380.00, Pax = 700.00)
`step
`19 cost: in 2.33 avg 2.94 max 4.86
`ranko is 7.11 yugo = 25.69 wire = 1.64
`std dev -- 0.39 avg distance .. 87.00
`NNNMMMNNMCCCCCCR
`cheat = 730.00 (in = 660.00, max = 910,00)
`ranko = 9.94 yugo 28.77 wire = 2.33
`step
`30 cost: min 1.52 avg 1.95 max 2.73
`NNNNMMNMMCCCCCCR
`std dev -- 0.21 avg distance - 62.90
`cheat = 350.00 (ain a 300.00, Tax at 770,00)
`step
`20 cost: min 2.24 avg 2.82 max 4.86
`ranko = 6.41 yugo = 25.22 wire = 1.52
`stddey ... 0.45 avg distance: 83.97
`step ...
`30
`cost - . 1.518182
`cheat = 700.00 (in = 640.00, tax = 920.00)
`NNNNMMNMMCCCCCCR
`ranko = 9.64 yugo - 28.67 wire = 2.24
`step --
`20
`cost -- 2.236364
`step
`31 cost: min 1.50 avg 1.89 max 2.98
`NNMNHNNMNCCCCCCR
`std dev -- 0.25 avg distance .. 58.80
`cheat a 350.00 (Rin 300.00, max = 890.00)
`step
`21 cost: min 2.21 avg 2.68 max 4.21
`ranko is 6.62 yugo = 24.83 wire = 1.50
`std dev ... 0.30 avg distance .. 81.75
`NNNNMNNMNCCCCCCR
`cheat = 670.00 (min = 630.00, Rax = 870.00)
`ranko is 9.47 yugo 28.34 wire = 2.21
`step
`32 cost: min 1.48 avg 1.85 Rax 2.66
`NNMMNMNNCCCCCCR
`std dev -- 0.24 avg distance. 58,53
`cheat = 270.00 (in = 270.00, max = 690.00)
`step
`22 cost: min 2.15 avg 2.57 Pax 3.58
`ranko = 6.41 yugo = 24.71 wire = 1.48
`std dev -- 0.23 avg distance -- 80.25
`NNMMNNNNCCCCCCR
`cheat = 670.00 (min = 610.00, Rax = 860.00)
`ranko = 8.93 yugo = 28.25 wire = 2.15
`step
`33 cost: in 1.42 avg 1.78 max 3.70
`NNNNMMMNMCCCCCCR
`std dev -- 0.30 avg distance - 56.60
`cheat F 260.00 (min = 220.00, max = 820.00)
`step
`23 cost: min 2.05 avg 2.51 max 3.98
`ranko is 6.10 yugo = 24.62 wire = 1.42
`std dev -- 0.34 avg distance .. 79.18
`NNNMMMMNMCCCCCCR
`cheat = 630.00 (min = 480.00, max = 860.00)
`ranko = 8.66 yugo = 27.16 wire = 2.05
`step
`34 cost: Rin 1.35 avg 1.70 Biax 2.35
`NNNMMMNNMCCCCCCR
`std dev -- 0.20 avg distance. 53.01
`cheat = 210.00 (min = 70.00, max 680.00)
`step
`24 cost: min 1.92 avg 2.38 lax 3.25
`ranko = 5.82 yugo F 24.47 wire F 1.35
`std dev -- 0.22 avg distance .. 73.32
`NNNMMMNNMCCCCCCR
`cheat 600.00 (rain a 460.00, tax
`820.00)
`ranko = 8.02 yugo = 27.70 wire = 1.92
`step
`35 cost: in 1.342 avg 1.65 max 2.64
`NNNNMMMMCCCCCCR
`std dev -- 0.22 avg distance. 50.26
`cheat 210.00 (ain = 190.00, max = 560.00)
`step
`25 cost: min 1.93 avg 2.29 max 3.00
`ranko = 5.57 yugo = 24.23 wire = 1.34
`std dev -- 0.19 avg distance .. 73.47
`step --
`35
`cost - . 1.336364
`cheat s 600.00 (in a 460, 00, Pax 890.00)
`NMMNMMNNNCCCCCCR
`ranko is 8.02 yugo 27.70 wire = 1.92
`step --
`25
`cost -- 1.918182
`step
`36 cost: in 3.28 avg 1.57 max 3.39
`NNNMMNNNCCCCCCR
`std dev - 0.23 avg distance. 45.58
`cheat = 160.00 (Min = 160.00, max = 840.00)
`Step
`26 COst; in 1.82 avg 2.2 Rax. 3.22
`stddey - 0.23 avg distance .. 69.91
`ranco = 5.48 yugo a 23.79 wire a 1.38
`NMMNNMMNCCCCCCR
`cheat = 500.00 (in = 460.00, tax = 750,00)
`ranko = 7.71 yugo = 27.10 wire = 1.82
`step
`37 Cost: nin 1.22 avg 1.52 max 2.05
`NNNMMMMMMCCCCCCCR
`std dev - 0.14 avg distance. 41.10
`cheat = 110.00 (min = 110.00, max = 660.00)
`step
`27 cost: in 1.79 avg 2.12 Max 2.68
`rmako = 5.37 yugo = 23.22 wire = 1.22
`std dev - 0.18 avg distance. 66.09
`MNNMMNNNNCCCCCCR
`cheat = 400.00 (min = 400.00, Max at 800.00)
`
`Page 21 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 21 of 33
`
`5,636,125
`
`FIG. 49C
`
`step
`
`38 cost: min 1.20 avg 1.46 max 1.88
`std dev -- 0.15 avg distance -- 39.63
`cheat = 110.00 (min = 110.00, max = 440.00)
`ranko = 4.99 yugo = 23.21 Wire = 1.20
`NNNNMNMNMMCCCCCR
`
`step
`
`39 cost: min 1.30 avg 1.42 max 2.63
`std dev -- 0.23 avg distance -- 38.48
`cheat = 70.00 (min = 70.00, max = 700.00)
`ranko = 4.49 yugo = 22.55 wire = 1.10
`NNNMMMMNMNCCCCCR
`
`step
`
`40 cost: min 1.03 avg 1.31 max 1.76
`std dev -- 0.16 avg distance -- 29.62
`cheat = 20.00 (Min = 20.00, Max = 520.00)
`ranco = 4.13 yugo = 2.86 Wire = 1.03
`step --
`40
`cost -- 1.027273
`NNNNMMNNMCCCCCCR
`
`step
`
`41 cost: min 1.00 avg 1.23 max 1.90
`std dev -- 0.18 avg distance -- 23.37
`cheat = 0.00 (min = 0.00, max = 530.00)
`ranko = 4.00 yugo = 21.61 Wire = 1.00
`NNNMNNMNCCCCCCR
`
`step
`
`43 cost: min 1.00 avg 1.11 max 1.75
`std dev -- 0.15 avg distance -- 11.71
`cheat = 0.00 (min = 0.00, max = 390.00)
`ranko 4.00 yugo = 21.6l wire = 1.00
`MNNMMNM
`
`Page 22 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 22 of 33
`
`5,636,125
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SS}N/1/ 3/7/177/17
`
`OG
`60/-/
`
`@@SJÁ379; (d3007 SS3M1 I J
`
`?
`
`
`
`
`
`Page 23 of 66
`
`

`

`US. Patent
`
`Jun. 3, 1997
`
`Sheet 23 of 33
`
`5,636,125
`
`
`
`54
`
`F/G.
`
`Page 24 of 66
`
`Page 24 of 66
`
`

`

`US. Patent
`
`Jun. 3, 1997
`
`Sheet 24 of 33
`
`5,636,125
`
`
`
`
`
`
`
`
`
`707770,72“
`
`0)
`of
`
`a
`
`2,73
`
`,72
`
`r\
`N“
`
`m {
`
`\f
`
`“1(\J
`
`V.
`N“
`
`a aaaa
`
`
`amamaamaaaaaaaaaaaaaaa
`aaaaaa
`
`anaaaaw 2,70
`mamamama
`
`mamaaaaaaaamm
`aaaa
`aaaaaamaaaaaa
`naaaaaa
`aaaaaaa
`mama
`
`
`
`
`7.3,7275,7.3
`
`
`
`
`
`77,73E727077,7777,72 72,7772,7272,73
`
`
`aaaaaaaaaaama
`ammamaa
`
`
`77,70
`
`77,9
`
`m
`
`ma
`
`
`
`
`
`
`an
`
`
`n
`
`
`
`
`
`55
`
`FIG.
`
`Page 25 of 66
`
`Page 25 of 66
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 3, 1997
`Jun. 3, 1997
`
`Sheet 25 of 33
`Sheet 25 of 33
`
`5,636,125
`5,636,125
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`s s
`
`
`
`
`aa 70,7770,7270,73
`
`
`
`mamamama
`mama
`3,70mama
`73,7073,7773,7273,73
`
`
`
`77,7077,7777,7277,73
`
`
`
`72,7072,7772,7272,73
`
`
`
`S
`02 8,77
`
`s
`s
`
`.177
`s
`a
`S
`s s f
`mamam
`mamamam
`amamwm
`mammam
`mam
`mama
`mama
`mama
`aaamaam
`
`
`
`mam
`mamaaaaama
`
`
`mama
`s
`aaaamlamamamamama
`mam
`mam
`mam
`
`
`am
`s s s
`Iaa
`
`
`
`
`
`
`
`
`
`
`
`
`
`s
`77,7
`
`S
`56
`s
`FIG.
`
`Page 26 of 66
`
`Page 26 of 66
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 3, 1997
`Jun. 3, 1997
`
`Sheet 26 of 33
`Sheet 26 of 33
`
`5,636,125
`5,636,125
`
`
`
`
`
`
`
`
`
`S.
`A8
`
`S
`A76
`
`
`
`
`
`
`S
`A75
`
`
`
`S.
`A74
`
`
`
`
`
`”.2
`as
`
`*2
`N
`
`”,3
`00‘
`
`
`
`”3N
`03‘
`
`2‘2
`§
`
`
`
`a
`
`N
`S
`N
`N
`N
`~~-.‘:
`”N683:
`
`N N
`
`
`
`nmamwmnmnwwmw
`72,6
`s
`7,7
`72,472,572,7
`
`S
`A72
`Se
`A9
`
`
`
`s
`
`
`s
`amu
`72,7272,7.3
`mun-
`S
`2,72
`
`s
`s
`
`s a
`s s
`
`”3N
`In"
`
`(\I
`
`7,
`aannunnmmww
`runnnnnnnmnuma
`manna
`
`
`
`
`
`
`
`
`
`
`
`
`
`72,77
`
`7,70
`
`72,9
`
`72,8
`
`72,3.
`
`S.s
`
`t
`
`S
`
`r
`s
`
`n
`
`s
`
`
`
`s
`
`72,2
`
`S
`A73
`
`s
`
`S
`57
`s
`F/G.
`
`Page 27 of 66
`
`Page 27 of 66
`
`

`

`US. Patent
`
`Jun. 3, 1997
`
`Sheet 27 of 33
`
`5,636,125
`
`[70
`
`E75
`
`E20
`
`[25
`
`E5
`
`3
`
`
`
` [24
`
`
`
`I;
`{'3
`
`0:1
`
`.2
`
`£23
`
`g gE:
`
`N
`
`“LL13
`
`N
`N
`
`q;
`
`v\
`as
`
`N.
`o;
`
`'\.
`S
`
`“2
`
`N
`:
`
`“2
`
`N.
`3
`
`‘Q
`
`'\
`:3
`
`<o_
`
`
`
`
`EV:
`N‘Luw‘
`
`:03:
`tn‘LLHo‘
`
`:V‘:
`t\‘
`
`uon°q
`
`-~LuN
`
`’\
`~<
`
`’\
`N“
`
`m
`
`00
`
`M:
`
`N
`"5‘
`
`{a
`
`0:1
`
`v
`
`N.
`V
`
`‘0
`
`ogmuq
`
`LnLLJb
`
`'\.'
`‘0
`
`N.
`<0
`
`‘0
`
`°°N°°
`
`NLLIOG
`
`to
`
`www w
`“Lu“:
`"3‘
`
`% QNQ nfim Q
`v
`toLLHo
`N‘LUOQ‘
`o:
`
`Q 35:
`3
`-Lu-
`
`V-
`N“
`
`"3
`
`V~
`N‘
`
`"3
`
`V-
`~3‘
`
`m
`
`V~
`VP
`
`Nu
`
`V
`Lo‘
`
`N3
`
`V-
`<6
`
`”3
`
`V~
`r\‘
`
`"3
`
`V-
`or:
`
`Na
`
`V-
`o;
`
`”3
`
`V;
`E
`
`"1
`E
`
`174
`
`77,3
`
`72,4
`
`72,5
`
`2 6 2
`
`£22
`
`527
`
`
`
`
`
`
`
`
`
`--.-m
`II
`NNN
`«flow §2N
`
`
`N
`
`-‘
`
`N
`
`N‘
`
`N
`
`M:
`
`K
`
`V:
`
`N
`
`Ln‘
`
`N
`
`to“
`
`N
`
`I\‘
`
`K
`
`a5
`
`N
`
`0;
`
`58
`
`NC.
`
`Page 28 of 66
`
`Page 28 of 66
`
`

`

`US. Patent
`
`Jun. 3, 1997
`
`Sheet 23 of 33
`
`5,636,125
`
`
`
`
`
`72,7272,73
`
`7,77
`
`72,70
`
`
`
`
`7,70
`
`ma a
`
`
`
`
`
`mm 70,707,7770,7270,73
`
`mmmmmmmm
`
`
`2,73 mmmm
`
`
`
`73,7073,7773,7273,73
`mummum
`
`
`
`
`77,8“77,7077,7777,7277,73 am
`mnmmmmmm
`mmmmmm
`
`an
`mananan
`
`numm aan
`anmm
`anan
` nunan
`nan
`ananmum
`an
`mama
`
`
`anana
`anaanan
`an
`anan
`ananan
`mana
`
`
`7, A7 2. E7 3,2 mm 5,2 E6 6,2 la namu
`
`n
`
`n
`
`n
`
`m
`
`m 2,7
`6,7
`5,7
`3,7
`
`
`lam
`
`
`
`
`
`
`
`
`
`73.2
`
`
`
`59
`
`F769.
`
`Page 29 of 66
`
`Page 29 of 66
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 3, 1997
`Jun. 3, 1997
`
`Sheet 29 of 33
`Sheet 29 of 33
`
`5,636,125
`5,636,125
`
`
`
`
`
`
`
`
`
`
`
`77,7077,7777,7277,73
`
`
`
`mam-mamamamamama
`
`
`
`
`mamamamamamamamamamamama
`73,7073,7773,7273,73
`
`
`
`72,7072,7772,7272,73
`
`
`
`ma
`am
`amaaammama
`mm
`amammam
`mam
`mama
`
`
`
`
`mam
`mamamama
`waaaa
`aaaaa
`laaaaa
`aaaaamama
`aaaam
`
`
`mam
`-WEEmam
`s
`mam
`mam
`
`
`mamammam
`_ 7.2
`am
`am
`S.
`s s s s ls s
`s s
`7,7 I ala_a 8,7 m
`
`
`
`
`
`
`
`
`mm
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`am
`
`
`
`
`
`&
`60
`s
`FIG.
`
`Page 30 of 66
`
`Page 30 of 66
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 30 of 33
`
`5,636,125
`
`FIG. 61
`
`
`
`
`
`FIG. 65
`
`Y1
`
`X1,X2
`
`X2
`
`Page 31 of 66
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 3, 1997
`Jun. 3, 1997
`
`Sheet 31 of 33
`Sheet 31 of 33
`
`5,636,125
`5,636,125
`
`
`VA+
`
`CO O § L?
`FIG. 65
`
`
`
`Page 32 of 66
`
`Page 32 of 66
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 3, 1997
`
`Sheet 32 of 33
`
`5,636,125
`5,636,125
`
`
`
`
`
`.:6mmQU‘Emm.©\.K
` VBmum$39ngaVB:2:E8955:EEnf/gn
`
`
`
`Rm0C
`
`MQEKEEmbmkcmmmogkm$3032093&wa
`
`EQE:
`
`SES4%
`
`
`
`
`
`
`
`NR\NQEEKSszzsunfiksEwmfi\msmnémmmustmE
`
`th.MQEEKEmummommmgqmfi
`
`
`
`
`
`
`
`53$:ch\ESQMSQwwm,g.«SEES$3
`
`3m.
`
`$65.:mtuvc
`
`Page 33 of 66
`
`Page 33 of 66
`
`
`
`
`

`

`U.S. Patent
`
`Jun. 3, 1997
`
`Sheet 33 of 33
`
`5,636,125
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`300W 3/10/W3C/
`
`09
`
`099##9
`
`Page 34 of 66
`
`

`

`5,636,125
`
`1.
`COMPUTER IMPLEMENTED METHOD FOR
`PRODUCING OPTIMIZED CELL
`PLACEMENT FOR INTEGRATED CIRCUT
`CHP
`
`15
`
`20
`
`25
`
`30
`
`2
`expected that the feature size can be reduced to 0.1 micron
`within several years. This small feature size allows fabrica
`tion 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 geom
`etries and more circuit elements on an integrated circuit, and
`of course, larger die (or chip) sizes will allow far greater
`numbers of circuit elements.
`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
`Aided Design (CAD) tools, and many phases have already
`been partially or fully automated. Automation of the physi
`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
`ing scheme between the devices to obtain the desired
`functionality. Since space on a wafer is very expensive real
`estate, algorithms must use the space very efficiently to
`lower costs and improve yield.
`Currently available physical design automation systems
`are limited in that they are only capable of placing and
`routing approximately 20,000 devices or cells. Placement of
`larger numbers of cells is accomplished by partitioning the
`cells into blocks of 20,000 or less, and then placing and
`routing the blocks. This expedient is not satisfactory since
`the resulting placement solution is far from optimal.
`An exemplary integrated circuit chip is illustrated in FIG.
`1 and generally designated by the reference numeral 10. The
`circuit 10 includes a semiconductor substrate 12 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) 14, a read-only
`memory (ROM) 16, a clock/timing unit 18, one or more
`random access memories (RAM) 20 and an input/output
`(I/O) interface unit 22. These blocks can be considered as
`modules for use in various circuit designs, and are repre
`sented as standard designs in circuit libraries.
`The integrated circuit 10 further comprises a large
`number, which can be tens of thousands, hundreds of
`thousands or even millions or more of small cells 24. Each
`cell 24 represents a single logic element, such as a gate, or
`several logic elements that are interconnected in a standard
`ized manner to perform a specific function. Cells 24 that
`consist of two or more interconnected gates or logic ele
`ments are also available as standard modules in circuit
`libraries.
`The cells 24 and the other elements of the circuit 10
`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
`ous elements of the circuit 10 are interconnected by elec
`trically conductive lines or traces that are routed, for
`example, through vertical channels 26 and horizontal chan
`nels 28 that run between the cells 24.
`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.
`Partitioning-Achip may contain several million transis
`tors. 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 components into blocks such as subcircuits and
`
`This application is a continuation of U.S. Pat. applioca
`tion Ser. No. 08/229/826, entitled INTEGRATED CIRCUIT
`PHYSICAL DESIGN AUTOMATION SYSTEM UTILIZ
`ING OPTIMIZATION PROCESS DECOMPOSITION
`AND PARALLEL PROCESSING, filed Apr. 19, 1994 by
`10
`Michael D. Rostoker, et al. now U.S. Pat. No. 5,495,419.
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention generally relates to the art of
`microelectronic circuit fabrication, and more specifically to
`an integrated circuit physical design automation system
`utilizing optimization process decomposition and parallel
`processing.
`2. Description of the Related Art
`Contents
`1. Integrated Circuit (IC) Physical Design
`2. Physical Design Algorithms
`a. Overview
`b. Simulated Annealing
`c. Simulated Evolution
`d. Force Directed Placement
`3. Integrated Circuit Cell Placement Representation
`4. Cost Function Computation for IC Physical Design
`5. Parallel Processing Applied to IC Physical Design
`6. Distributed Shared Memory (DSM) Parallel Processing
`Architectures
`a. Overview
`b. Limitations of Basic DSM Architecture
`c. Telecommunications Network Applications
`1. Integrated Circuit (IC) Physical Design
`The automated physical design of a microelectronic inte
`grated circuit is a specific, preferred example of simulta
`neous optimization processing using a parallel processing
`architecture to which the present invention is directed.
`Microelectronic integrated circuits consist of a large num
`ber of electronic components that are fabricated by layering
`several different materials on a silicon base or wafer. The
`45
`design of an integrated circuit transforms a circuit descrip
`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
`design requirements. The result is a set of design files in a
`particular unambiguous representation known as an inter
`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 electronbeam
`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
`process of converting the specifications of an electrical
`circuit into a layout is called the phy