United States Patent (19)
`Agrawal et al.
`
`54) VARIABLE GRAIN ARCHITECTURE FOR
`FPGA INTEGRATED CIRCUITS
`
`75 Inventors: Om P. Agrawal, Los Altos; Herman
`M. Chang, Cupertino; Bradley A.
`Sharpe-Geisler; Giap H. Tran, both of
`San Jose, all of Calif.
`73 Assignee: Lattice Semiconductor Corporation,
`Sunnyvale, Calif.
`
`21 Appl. No.: 08/948,306
`22 Filed:
`Oct. 9, 1997
`51
`Int. Cl." .......................... H03K 19/177; H01L 25/00
`52 U.S. Cl. ................................. 326/41; 326/47; 326/39;
`326/38
`58 Field of Search .................................. 326/41, 40, 39,
`326/38, 47, 101
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4,912,342 3/1990 Wong et al..
`5,212,652 5/1993 Agrawal et al. ........................ 364/489
`5,241.224 8/1993 Pedersen et al..
`5,258,668 11/1993 Cliff et al..
`5,260,610 11/1993 Pedersen et al..
`5,260,611 11/1993 Cliff et al..
`5,455,525 10/1995 Ho et al. ................................... 326/41
`5.537,057 7/1996 Leong et al............................... 326/41
`5,581,199 12/1996 Pierce et al. .............................. 326/41
`5,598,109
`1/1997 Leong et al. .............................. 326/41
`5,644,496 7/1997 Agrawal et al. ........................ 364/489
`5,682,107 10/1997 Tavana et al. ............................ 326/41
`5,815,003 9/1998 Pedersen ................................... 326/39
`OTHER PUBLICATIONS
`Advance Product Brief, Dec. 1996, Lucent Technologies:
`Optimized Reconfigurable
`Cell Array (ORCATM)
`OR3CXXX/OR3TXXX Series Field-Programmable Gate
`ArrayS.
`
`USOO609.7212A
`Patent Number:
`11
`(45) Date of Patent:
`
`6,097,212
`Aug. 1, 2000
`
`Product Brief, Jun. 1997, Lucent Technologies: ORCAGR)
`OR2CXXA (5.0V) and OR2TXXA (3.3V) Series Field-Pro
`grammable Gate ArrayS.
`
`Primary Examiner Michael Tokar
`Assistant Examiner Daniel D. Chang
`Attorney, Agent, or Firm-Fliersler, Dubb, Meyer &
`Lovejoy LLP, Gideon Gimlan
`57
`ABSTRACT
`
`A Variable Grain Architecture is disclosed wherein Variable
`Grain Blocks (VGB's) are wedged together in mirror oppo
`sition to one another to define Super-VGB structures. The
`Super-VGB structures are arranged as a matrix within an
`FPGA device. Each VGB includes progressive function
`Synthesizing layers for forming more complex function
`Signals by folding together leSS complex function Signals of
`preceding layers. A function spawning layer containing a Set
`of function spawning lookup tables (LUTs) is provided near
`the periphery of the corresponding Super-VGB structure. In
`one case, the function spawning layer is L-shaped and
`includes a symmetrical distribution of Configurable Build
`ing Blocks. A Signal-acquiring layer interfaces with adjacent
`interconnect lines to acquire input terms for the LUTs and
`controls. A decoding layer is interposed between the Signal
`acquiring layer and the function Spawning layer for provid
`ing Strapping and intercept functions. Each VGB has a
`common controls Section, a wide-gating Section and a carry
`propagating Section. Each Super-VGB has a centrally-shared
`Section of longline drivers that may be accessed from any of
`the constituent VGB's. A diversified spectrum of intercon
`nect lines, including 2XL, 4XL, 8XL and direct connect
`surround each Super-VGB to provide different kinds of
`interconnect.
`
`112 Claims, 46 Drawing Sheets
`
`y
`
`451
`HIC(O)
`
`WGB-LOCAL
`Feedback 435
`
`400B
`Maxl Long-haul General interconnect
`2xL4xL,8xL Short-haul General Interconnects
`422c
`
`X
`
`N
`S -
`ROW 0 -> 430
`
`461
`vico
`
`421.
`- - - - -
`
`(8)
`ROW 1 -->
`PARED-CBBS
`420
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`452
`HC(1)
`
`Max Long-haul General Interconnect
`17
`2xL4xL,8x. Short-haul General Interconnects
`453
`
`
`
`COLO
`
`a 1.
`SQ
`8XSWBOX
`4XSWBOX
`s-2XSWBOX
`
`WGB(0,0)
`V&E3
`WGB(10)
`WGB(1,1)--
`
`SUPER
`e--vgb
`440
`
`462
`WIC(1)
`
`463
`WC(2)
`SWBOXES
`AREA
`465
`
`Intel Exhibit 1007
`Intel v. Iida
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 1 of 46
`
`6,097,212
`
`
`
`
`
`(LHV »JOIHd) I "OIH
`
`

`

`U.S. Patent
`
`Aug.1, 2000
`
`Sheet 2 of 46
`
`6,097,212
`
`
`
`
`
`‘SHOUNOSSYLOANNOOYSLNIGAWNSNOOL3A-LONONISN(€)
`
`
`
`
`
`
`
`
`
`SANNHOSG3a0V1dSHLNSASAMLAESNOILOSANNOO3LNOY
`
`
`
`$.419TWaNTdAO
`
`S0¢
`
`
`
`
`
`“LNAIVAINOAATIVNOILONN4VTWLNN
`
`
`
`ONILNOY/LNAWAOVId/DNINOILLILYVd
`
`
`
`CIWWILdO‘LSAYSL1L39ONY)
`
`GNNO4SIADSALVYLS
`
`(LYVYOIYd)¢Old
`
`
`
`ONINOIWILYVdYO/UNV
`
`INSAWS9V1dYO/GNV
`
`
`
`ONILNOYALVYALI(y)
`
`MNNHOHOWAdv1d(Z)£0210GAWNSNOODLAA-LON‘O1sIDSdSVOLNI
`
`
`
`
`
`
`
`c0d
`
`
`
`YATIVWSHOG3ZIS-910OLNI
`
`SYNNHO
`
`
`
`
`
`LINDMIOTWNIDIMONOILILYYVd(L)
`
`|O=
`
`dO0O1YANNI
`
`L0¢
`
`902
`
`
`
`dOO1YAaLNO
`
`802
`
`
`
`dOO1SIdGIN
`
`YaLNA
`
`LOc
`
`oO
`
`N
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 3 of 46
`
`6,097,212
`
`350
`
`300
`-
`N V
`
`HORIZONTAL BUS
`SERVING Srow-1/Nrow0. Q
`AXL LONG-HAU GENERAL INTERCONNECT
`2xL SHORT-HAUL GENERAL INTERCONNECT
`
`4-SIDED
`CB
`(0,0)
`
`
`
`
`
`
`
`N
`
`N
`4-SIDED
`CLB
`(0,1)
`S
`
`SWBOX
`
`HBUS
`(Srow0/Nrow1)
`
`4-SIDED
`CLB
`(1,0)
`
`
`
`E
`
`
`
`4-SDED
`CLB
`
`v
`
`f
`|Y VERTICAL BUS
`v.
`} SERVING Eco-1 Wool_0
`|
`H_BUS
`(Srow1/Nrow2)
`f
`
`|
`
`
`
`32O
`
`Y.
`
`y
`- VERTICAL BUS
`\,
`SERVING Ecolo/Wool 1
`Y
`-
`C
`W
`Cis-
`-N
`OS
`W
`\
`W Sk E
`W Sk E.
`W
`14. (C)
`(E)
`4.NEB)NE2DNS1
`TRANSITION
`SW1 SSR,
`LAYER
`
`PERPHERAL
`IMPORT1
`EXPORT
`LAYER
`
`FIG. 3A
`(PRIOR ART)
`
`FUNCTION SYNTHESIZING
`CORE
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 4 of 46
`
`6,097,212
`
`FUNCTION
`SYNTHESIZING
`CORE 369
`
`RASS PERPHERAL
`LAYER 365
`IMPORT/EXPORT
`(PIE)
`LAYER 361
`
`us
`
`- a
`
`m
`
`{-
`
`h
`
`s
`
`e
`
`-)
`
`(PRORART)
`
`TERM
`AQCUISTION
`LAYER 491
`f
`A
`
`492
`
`
`
`DECODNG
`LAYER 493
`
`FUNCTION
`SENS
`
`SESS
`LAYERS
`496
`O -)
`O
`O
`O ->
`N-
`PROGRESSIVE,
`N-N2
`--/N COMPOUND
`1 1/-/- CN FUNCTIONS
`(gers
`SYNTHESZING
`4946
`LAYERS 495
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 1, 2000
`Aug.1, 2000
`
`Sheet 5 of 46
`Sheet 5 of 46
`
`6,097,212
`6,097,212
`
`PIP
`
`TNODT
`
`385
`
`0 K
`
`e
`
`12 3 4
`
`y,388
`{------
`
`387.
`
`386
`
`<-
`
`A! P
`
`— m
`
`ywee)
`
`ee
`
`FIG. 3C
`FIG. 3C
`
`373
`
`STONEDIamannrrnmSSeOEES1=N©wT|88gcoooOoO
`
`370
`
`3
`
`THNOT
`
`PP
`
`_--Sad
`
`384
`eooy
`
`383
`
`A-i8t-,S%oO9
`oOeNO?nQO~““—t
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 6 of 46
`
`6,097,212
`
`
`
`
`
`FIG. 3D
`
`FIG. 3E
`
`

`

`Sheet 7 of 46
`Sheet 7 of 46
`
`6,097,212
`6,097,212
`
`U.S. Patent
`U.S. Patent
`
`XOUMSXBSSya4S}OPULODJO}U|
`XO@MSXvWO07-29A
`
`JEI@USS([NBY-OYSXe‘XP1XZ
`
`
`
`
`yOauUOdJE}U][eJBUSH|NeYy-Bbuo7]7xXey(0)9IH
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LSV
`
`wadns(L'O)DAoev<—0MOx
`XOEMSXe~~seyNOvVaaaaS
`(O‘O)GDA|
`
`Xx
`
`Aug. 1, 2000
`Aug.1, 2000
`
`OrratagDA-O'}gSA
`
`(Z)OIAOr
`
`$,qg0-Gaulvd
`
`(OIA|MO¥
`
`<——
`
`Fr
`
`+O
`
`ago
`
`OlpLor
`
`vauy—(0SaXO8MS
`
`
`
`
`
`SorJOSUUOdJE}U][eJQUSDjNey-Buo77xeW
`
`
`SJIUUODIAJU][E1QUEHD|NEY-WOUS7X8‘1X1XZ5p
`
`
`
`——(L)OIH
`
`
`
`Z100seL1090109
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`Aug.1, 2000
`
`Sheet 8 of 46
`Sheet 8 of 46
`
`6,097,212
`6,097,212
`
`FIG. 4C 9
`
`U.S. Patent
`
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 1, 2000
`Aug. 1, 2000
`
`Sheet 9 of 46
`Sheet 9 of 46
`
`6,097,212
`6,097,212
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 10 of 46
`
`6,097,212
`
`
`
`
`
`10BN NOO? JELLNI
`
`T\/LNOZIPHOH
`
`
`
`
`
`
`Y5)
`
`?AJO
`
`£XITO
`
`TVEIOTS)
`
`LEISERH
`
`TEINNVHO
`
`769
`
`
`
`-lèHIL CIERHVHS
`
`TENN\/HO
`
`| X
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 11 of 46
`
`6,097,212
`
`
`
`
`
`
`
`PROGRESSIVE
`SIGNAL
`CASCADING
`
`am we win in Now
`
`ap H and us
`
`m in
`
`
`
`
`
`W
`
`PROGRESSIVE
`SYNTHESIS
`LAYERS
`
`546
`
`547
`
`- - - - - - - .
`
`FASTER
`- - - - - - - ,
`! --- 4 - -
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug.1, 2000
`Aug. 1, 2000
`
`Sheet 12 of 46
`Sheet 12 of 46
`
`6,097,212
`6,097,212
`
`HIC**
`
`
`
`
`
`
`
`
`
`*(7T) Ny
`SHARED BIG DRIVERS
`A568 ~7-* -
`'
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 13 of 46
`
`6,097,212
`
`
`
`-099
`
`LTT LI8 #79
`
`16 BIT LUT
`FORMING CKT
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 1, 2000
`Aug. 1, 2000
`
`Sheet 14 of 46
`Sheet 14 of 46
`
`6,097,212
`6,097,212
`
`V L 'OIH
`
`isuvadSA
`
`G8Z
`
`S92,~¥SOA
`
`gSZ
`
`Nay10VEDA
`—LbZ
`
`VL‘DIA04a9VADAGZZ
`
`LasVGDABGulFE]121eoeelO)
`
`-(PHSsezVgdDA=4002reeOT440N10
`
`M10WADAe9192x10we
`IS8v9AOe2SanitDWOLXc6Z
`Lasv_ddAiooo=elozoSANTIS8a162
`
`
`:oe_iEEONCREizyon
`—SOLSSN1D2x662OlH
`
`ZS=44010_
`6pHu)OKAeoette
`0SZyz
`aL119
`comle
`bedezLzz,SANIIX8oxSIA
`-fel\Lge,
`
`SINTIXxSANITXZ(9x
`
`
`
`£02€GZ
`
`SSNITWILOL8S\WADA
`
`-WDA
`
`mo
`
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 15 of 46
`
`6,097,212
`
`?XITO
`
`OXTO
`
`
`
`{{L 'OIH
`
`
`
`
`
`999A.
`
`ZT_LO
`
`0T. LO
`
`\/ 89/A
`
`++OXTO
`
`e99/
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 16 of 46
`
`6,097,212
`
`800
`
`
`
`
`
`
`PERIPHERAL, HORIZONTAL CHANNEL
`PERPHERAL VERTICAL CHANNEL
`95 93 91
`89 87 85
`96.94 92
`90 88 86
`
`83 81 79
`84 82V 80
`
`f|\| P|\| t|\p
`D
`II)
`
`O
`
`1
`
`
`
`WGB
`IOB
`77 75 73
`78 76 74
`
`f| \,:
`TD
`
`
`
`rarrrrrrrrr. XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
`
`
`
`XXX
`
`YYYYYYY SXXXXXXXXXXXXXXXX
`
`r
`
`a Y
`
`SSSS &XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
`-0
`1-XL-2
`3-2-4
`5-2-6
`7.2
`
`25 il is
`26 28 30
`
`3. lial 3s
`32 34 36
`
`3. del.
`38 40 42
`
`4. sl.
`44. 46 48
`
`FIG. 8
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug.1, 2000
`Aug. 1, 2000
`
`
`
`
`
`6,097,212
`
`Sheet 17 of 46
`Sheet 17 of 46
`
`6,097,212
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 18 of 46
`
`6,097,212
`
`
`
`
`
`
`
`
`
`s
`
`E E E \ is E. E.
`d we can
`o w
`CN
`S
`S
`9 S 9
`J
`J 1
`Ll
`o o O o O O
`O
`
`f
`
`N V N
`H. H.
`H. H.
`O O O O
`-
`-
`CN ord
`d v
`O O C) O
`
`X
`
`s
`
`:
`
`N
`
`X
`
`i
`
`--Y-O-Y--C-SA
`A--C-4------
`- A --A-C-SA---
`
`- HOHC A---A-C-
`A-d--- s---A-C)
`- SA---------
`
`.."'
`
`-- s f
`
`:
`
`---
`
`ra
`
`re Š s N :
`
`CO
`
`S N
`
`sm"
`
`ad
`
`* S-1-all r
`
`co
`
`N- O
`
`O) O v
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 19 of 46
`
`6,097,212
`
`AQUISTION DECODING
`LAYER
`LAYER
`1121
`1123
`
`LD6
`
`2
`
`3
`
`4.
`
`Mi AIL
`
`1100
`
`11 OOB
`
`
`
`in2
`n3
`
`SelectO
`Select 1
`
`1175
`fa(3T)/fy(4T)
`N-- N--
`O
`Of1
`
`1185
`f(3T)
`
`N--
`1125
`FIRST FUNCTION
`SYNTHESIZNG LAYER
`
`LD3
`
`\
`1124
`FUNCTION
`SPAWNING LAYER
`FIG 11 A
`
`LUT'b'
`
`-
`PIP
`
`FIG. 11B
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 20 of 46
`
`6,097,212
`
`
`
`Ziff
`
`Wf1
`
`Yf1
`
`SelO:1 in4:7
`
`SelO:1 in O:3
`
`W
`
`Y
`
`1275W
`1275Z
`
`4:1
`
`4:1
`
`1275Y
`
`in8:11-D
`
`SelO:1-D
`
`Z
`
`128OB
`
`Y M
`
`8:1
`
`FIG. 11C
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 21 of 46
`
`6,097,212
`
`Bus 1 Bus3
`
`
`
`
`
`
`
`
`
`
`
`
`
`1100D
`
`y
`
`
`
`BO(Bus 1:4) -b.
`
`BO(BusX)
`
`SeO:1
`
`Z
`
`Bus5
`
`N
`
`1181
`
`B1 (BusX)
`S
`
`X
`
`B2(BusX)
`
`1182
`
`B3(BusX)
`
`11.83
`
`Z
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`B1 (Bus 1:4)
`
`SeO:1
`
`B2(Bus 1:4)
`
`SeO:1
`
`B3(Bus 1:4)
`
`SeO:1
`
`Bm(Bus 1:4)
`SelO:1
`
`
`
`FIG. 11E
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 22 of 46
`
`6,097,212
`
`YO-
`
`X)
`
`LSB
`
`LUT
`
`w a
`
`H
`
`\-PIPY5-W5a.
`AIL Sco
`X)
`
`SDPPY5Z2
`
`(3T)
`LSB
`
`f(3T)
`
`DECODNG LAYER 1223
`AOUSITION
`1224
`- N
`SYW SABh
`-N-
`t M" sat
`FTY
`fa(3T)
`FTY2
`set
`O5poil as Pyos
`sea
`5POPE's
`PY14
`Y3 III
`POPY2)
`C-PIPY25 WRAP25 -- sb
`Y
`R
`-
`seezer
`Y4-8 D
`5
`GPPYZ
`MSEY.
`WSS as Pwas
`E.
`CD-PPW14
`W2 III D
`MSB Wo
`III D
`C
`-PPW3XO is
`W
`5
`PPW25
`cise,
`Mos
`CDPPW4x1W
`PPY5-W5b
`Sc f(3T)
`HIC
`VC
`sef
`|
`|PIPW5X2
`20
`D 1.
`LSB
`fe(
`8BIT
`II.
`2 B
`is:
`I
`| LSB
`2P
`|
`8BIT
`POPZ3
`Z4-)HD
`LUT
`Z5 III P-Pipxozos
`Zf
`SSAB --------------------si
`Sgh
`3
`g(3T)
`LSB
`XO-8 D 4M
`X1 III D
`CD
`I
`5
`MSB Xg
`LSB
`X3-
`D X
`IIISPOFX3
`SB 8B
`use; X
`X4- III P
`X5-
`D POPX5
`f(3T) h
`
`F
`|
`
`|
`
`|
`
`C-PPZO3
`| Co-PPZ14
`g-PIPZ25
`
`PPs
`| Co-PIPX25
`
`|
`
`|
`|
`
`|
`|
`
`Z
`
`X
`
`

`

`U.S. Patent
`
`Aug.1, 2000
`
`Sheet 23 of 46
`
`6,097,212
`
`1225
`
`fa(3T)
`Y
`
`f,(3T)
`
`Sab
`[rm
`
`1226
`
`4271 1270Y a ~
`, fy(4T/3T)
`
`12757
`
`1280A
`
`1272
`
`vo
`
`1263Y
`
`fa(5T)
`
`1283A
`
`f(3T)
`
`1270W
`
`SYW
`
`
`
`Ww fyw(4T/3T)C| my
`
`f4(3T)
`
`1275W
`
`SABv
`
`1227
`
`1285}
`
`1200a
`
`
`
`1263WaSed 17
`
`
`
`f(3T)
`
`1270Z
`
`Z
`f(3T)
`
`Sef
`
`f7(4T/3T)
`12752
`
`( 12632
`
`fg(3T)
`
`1270X
`
`1235
`
`1283FWa
`
`16BIT
`
`SBI
`LUT
`
`FIG. 12B
`
`mJ fp(6T/WO)
`fy(4T/3T)
`
`fra)
`
`x " fy(4T/3T)
`Soh
`1263x 2 aman
`im] |)
`Ww
`
`1275X
`
`f7(4T/3T)
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 24 of 46
`
`6,097,212
`
`Select3
`Select2
`
`DyOE A
`Y1-SYW
`
`InO -->
`In 1 - 0
`LSB
`
`PPYO3
`1315
`
`In2
`In3
`
`LUT'b' A
`
`SB
`
`1311
`
`127OY A
`
`E.
`
`1312
`Sab
`
`
`
`1353
`
`PIPY3-W3
`1316 aS
`n4
`5
`
`PIPW03
`1317 CD
`
`ins
`in 7
`
`1320 as
`In8
`In 9
`
`PPYO3
`1325
`
`inA
`InB
`
`PPY3-W3
`N
`1326 - C
`nC
`InD
`
`PPW03
`1327 C
`
`nE
`nF
`W3
`SelectO
`Select1-Y
`
`LUT 'd' A R
`
`PPYO-WO
`1313
`aS
`127OW A
`
`1314
`Scd
`
`1321
`
`127OY B
`
`LUT'b' B
`
`1322
`
`LUT'd' B
`
`PPYO-WO
`1323
`as
`127OW B
`
`1337
`
`LUT'c' B
`
`E.
`
`1324
`
`FIG. 13
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 1, 2000
`Aug. 1, 2000
`
`Sheet 25 of 46
`Sheet 25 of 46
`
`We<ogy,srlarica)eer!
`
`Xp>0W1DaSA|€9¢l
`CcyporOru1xcS6OPL4PpeSbl
`
`coprl
`eeraOLbLmi_LILO
`
`
`gerla(=NaW10GDA
`
`
`
`9erlrSrl
`
`CAAOVL
`
`LZPLAaso
`
`L9v1LSSrl
`
`6,097,212
`6,097,212
`
`1xZ
`
`(gs)
`
`(LN3O0Vf'dV-NON)WVZAaZZrl
`
`(1e)4
`
`WA—aoeSZbL
`B0FLSCrL
`sortOrr
`
`ver
`
`zerl
`
`Joa<|(om19)%
`
`
`
`ZLPLorp)Grrl
`
`(LeyLp)Ay
`
`Ozrlgeri
`
`<<cas
`
`ZSrlLSvL
`dQA=GDA
`iassis
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 1, 2000
`Aug. 1, 2000
`
`Sheet 26 of 46
`Sheet 26 of 46
`
`6,097,212
`6,097,212
`
`1x8Cc>
`
`C—_—Xp<><<éCI5W190ADA
`1WXS—>rfre)Tl0)
`o>0tu)
`8crlLM[uhe1LoCNay10GDA
`
`
`
`GSPLM
`
`LMGLELM
`
`
`
`vSOPLMO”vLMGerLM
`
`100<<os
`
`wou
`
`(Leriy)My
`
`KZom
`VZMZLVLM
`
`aMMOP
`
`LLVLM_
`
`
`
`aptOldGe)Ps
`
`9A=ADA
`15Ssy
`MASO
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 27 of 46
`
`6,097,212
`
`TXZ
`
`| Alfy | ZZTESO
`
`(Lc) } }
`
`[2][1][0
`
`(19/Ly)zy
`
`ONV19)0;
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 28 of 46
`
`6,097,212
`
`XITOTGOA
`
`/TI_LO
`
`
`
`NEXTO TGSDA
`
`(Lc)!!!
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 29 of 46
`
`6,097,212
`
`\/07||
`
`VNATESO
`
`TOC]
`
`ZJAWA
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 30 of 46
`
`6,097,212
`
`STOW©.
`
`LeSl
`
`02S1
`
`ecsh
`
`6L-
`
`8r-
`
`ceSb ee$<oeaaroceannner
`tebePEE!_
`SSeeeSSeS——4eetd
`
`PNhhhRdNNNeaeeleednelargreenrenemerrerrensnrrermarnaendfhertapomaasad-AAh-4-tAkA|
`SSaeaaeeaetteee
`
`(os)atganocd
`
`(sjavno
`
`
`
`OKP
`
`}OKs
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 31 of 46
`
`6,097,212
`
`A31 l Ali:30
`Y VV
`A
`"V
`
`
`
`Ali-39 AL i38
`
`
`
`1610
`
`
`
`O
`
`Ali:28
`Hu 1620
`tai-
`4. AllO5 AL04
`All #07
`AIL#06 7.
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 32 of 46
`
`6,097,212
`
`reyay
`
`aon{alolalv}=r
`
`
`
`ggo--{xX|ZIMIA}=»™Sith
`
`{PLMlerslrraleriNn}=!
`
`mew
`
`ctbelt
`
`CrLL
`
`
`
`OvelS9OZLL
`
`imO¢cZLL
`
`fy)AyCy
`
`68216LZ1()
`
`
`
`ralayay(OSZL)
`
`iampzi1
`
`OeLl
`
`
`
`
`
`OLLL7S9LLf3odns
`
`OLZL
`
`6SZ1ff
`
`69LLuu]
`
`O9LL_
`
`r304d
`
`BSZL
`
`ZLLL
`
`pELt
`
`QLLL
`
`ONI--—0Zy
`
`LNI-~LZPe
`
`@NI----ZZof
`
`
`
`€NI----€Zy
`
`PNI----OfHLA
`
`GNI----LfMLS
`
`ONI----2WLS
`
`ZNI----&.fWLS
`
`=VLIOIAet
`
`ty]
`
`fl6BLLL
`
`

`

`Aug. 1, 2000
`
`Sheet 33 of 46
`
`“ad
`
`U.S. Patent
`
`6,097,212
`
`[oN]ea]OM
`wbaa|acy|
`
`
`a-2xid]G1x14]92x14]91X14|za|zo|za9|og30fa/a04a]es
`@cAld|@1|OALabALs)AeZXa|7A0|zx"|@30%a|&30%13
`(ZND(QNI)(SNI)(pNI)(€N!)(ZND(LND(ON)|.f30dnsjfa0|tan
`
`
`
`
`efMla|ZrMid|PewLa|OFMla|ezMer|czar]baer|omer
`SHONOYHLGASSA88271ISOWOUNOWWOSWOudadc!Ol
`
`
`
`
`
`
`(vZb‘SI4WOU)$892TOULNOD.
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 1, 2000
`Aug. 1, 2000
`
`Sheet 34 of 46
`Sheet 34 of 46
`
`6,097,212
`6,097,212
`
`ada
`
`mxew
`
`
`
`(OSLL)(49)0-¥y
`EZ(12)4omEte a7]
`
`
`
`beate0ZLL
`
`
`
`{rerMlersl¢taletn}=!
`
`aoA{alolalvt=r
`
`gao-{x|ZIMIA}=»
`
`LOZL
`
`Ov
`
`Cel
`
`
`
`GLLL
`
`
`_(woe(Gr-a0ka
`qO9/1
`
`qgsZt
`BOLL
`
`O21
`
`FC]
`
`8921faodng
`
`1
`
`Pell
`
`G6SLLim
`
`LAL
`
`e6SLL
`
`ru]
`
`BQQL1
`
`Lf304d
`
`egS/1
`
`ONI---0Zy
`
`LNI--~-LZfe
`
`ZNI----ZZ
`
`
`
`€NI----€zy
`
`PNIsaanyzyoS
`
`GNI----pZyUS
`
`QNI~---SZlf
`
`LNI~---ZIMal
`
`A)AyOy
`
`
`
`68216ZLL
`
`()suBnoluypeaamit
`
`qocZl
`
`(omg)
`
`ObLb
`
`6PZLL
`
`62Z1
`
`tu)
`
`ebOLTDd
`
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 35 of 46
`
`6,097,212
`
`2 3
`
`N o
`
`o N
`
`3 2
`
`s
`
`- E.
`SensEEEEEEEEEEEEEEEEEEEEEE ver
`s: ?
`-
`I
`-
`T - III
`to
`EEEEEEEEEEEEEEEEra EEEEEEEEEEEEEEEEEEco
`CS
`k s
`V --N
`
`
`
`
`
`
`
`
`
`S2 II.
`s SE
`
`-
`
`L
`
`O
`-
`roo
`CO
`list
`I
`k is
`cN
`X- N
`Siii-HiFEEHFiFi if
`{ EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE lo
`i-PPP.
`& EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEElo
`S look3
`OO
`1,
`NS SP2
`A-
`SR is s
`Y A as
`y'ss
`N- a
`N-
`5 9 5
`X
`F C)
`w
`c
`NZ
`2
`D
`
`-
`X
`
`Y
`
`CN
`
`wr
`
`ty-
`
`-
`X
`s
`
`X v.
`s
`-
`s
`
`O
`
`s
`c
`
`ve
`
`r
`
`CN-9)
`
`vm
`
`N
`-
`
`-
`X
`d
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 36 of 46
`
`6,097,212
`
`Y
`
`lo
`ch
`
`w
`cN OO
`
`cy
`
`w
`op c.
`
`c.
`
`v.
`
`D
`s
`on 2 EiEEEEEEEEEEEEEEEEEEEEEEEEEEE v
`3ID-g
`EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
`kinll||
`||
`|| ||
`sis EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEv
`III (N
`- wer
`
`)
`
`w
`
`|Eil OO
`II is
`S: II
`||
`s||
`22
`S.
`
`
`
`
`
`
`
`
`
`o
`
`- -
`
`-
`
`OO
`
`s
`
`w N!!!!--!!!!N
`N EHEHEEEEEEEEEEEEEEEEEEEEEEE
`g
`Fi
`ii ii
`SEEEEEEEEEEEEEEEEEEEEEEEEEEEE
`h
`wn
`
`Vr
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 37 of 46
`
`6,097,212
`
`v
`
`ld
`c.
`
`v
`cy op
`
`cy
`x -o
`CN g
`
`cN
`-
`X
`s
`
`II
`
`op
`
`I
`
`ILo
`
`53
`
`||| || 22
`
`
`
`{ Nasr
`s s &
`
`II
`II
`NOROn
`
`EEE EEE EE
`
`E: EE EE:
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 38 of 46
`
`6,097,212
`
`g ...
`
`wn
`
`EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
`NHammomammam HaRHoHo
`SNI
`N!!!I-e-IIIl
`t
`y
`S'IIII
`IIII
`
`cy
`
`III is
`||
`
`
`
`
`
`
`
`3: III
`SCII Sl
`
`o
`
`s
`is
`Y
`
`od
`EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
`fini-E!!!N
`EEEEEEEEEEEEEEEE omomo PEEEEEEEEEEEEEEE
`iiii
`Niiii
`stiliili REiiii-3
`-
`EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEL)
`S- EEEEEEEEEEEEEEEOoo BoEEEEEEEEEEEEEEEE
`ge
`ven
`gs
`to
`1,
`N. R.
`QPQ
`an
`\-cy
`NN
`d
`V
`N/\g o s/r-
`-
`v
`N/
`y
`x
`it
`5 9
`O S
`s it
`2
`s
`>
`
`CN
`
`s
`S
`
`ve
`
`GN
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 39 of 46
`
`6,097,212
`
`
`
`
`
`
`
`
`
`
`
`SDNICIO OEC] NOI LISIQO\/
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 1, 2000
`Aug.1, 2000
`
`Sheet 40 of 46
`Sheet 40 of 46
`
`6,097,212
`6,097,212
`
`age86l
`
`qZ861
`
`
`
`
`
`
`
`{{6 I "OIH
`
`dolOla
`
`qbe6bfabtuonwoaese6Lus--o:we
`(9onswos)|abelg°qebO6t
`
`
`
`Z+10
`
`(Za6eis01)fiws(~~
`Z+l5QSc6l
`
`qlS6l€Z6L
`
`ONIGODgAG
`
`YSAVI
`
`Awe
`
`0:uo
`
`owengainStH]|[aflhqOZ6LL+I¥
`:aswCHI
`
`pcan+n7@H+]ez,\PPwans|ltd
`\!|!cont
`[b+rer
`
`, ?Z ,
`
`8 SW
`
`[+g@by)
`
`ST
`
`ppw/ans
`
`b+
`
`
`
`
`

`

`6,097,212
`
`9L86t
`
`(Lpe6e}gwo.)
`
`Ste
`
`Z@ebejis
`
`O6T“DIA
`
`U.S. Patent
`
`Aug.1, 2000
`
`Sheet 41 of 46
`
`(¢aBeys01)
`
`Ctl
`
`[etlg@Cty]
`
`[¢+lg@Cthy|
`
`9GZ61
`
`90261
`
`[uy ppyw/ans
`
`Ln
`
`OM,
`
`9GE6L
`
`gs]
`
`c+lV
`
`Aan
`
`gsw
`Ppw/ans
`
`SONIGODAG
`
`YyaAvI
`
`€c6h
`
`cr
`
`Aaan=|
`
`
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 42 of 46
`
`6,097,212
`
`
`
`
`
`
`
`EST
`
`, GA ,
`8 SW
`
`pp\//qnS
`S.
`A.
`
`A.
`A Ali
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 43 of 46
`
`6,097,212
`
`B1
`
`B
`B15 ;
`;
`
`B12
`
`200OA
`
`;
`:
`
`2006
`2005
`WGB RST
`V B
`GB CLK
`1C16
`ADDER
`STAGE F
`
`
`
`|
`
`7
`
`
`
`Zf1
`
`D
`
`B3 B2 B Bo
`B 't
`-2
`B3
`
`Xf1
`STAGE O FF
`
`2002 2001
`
`
`
`Ekko Q0
`UNITAMoUNTN'
`OF LEFT SHIFT N24
`FIG. 20A
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 44 of 46
`
`6,097,212
`
`
`
`SVGB
`-8FB
`
`/%, T
`
`HC X1
`
`HC XO
`
`DC40
`
`HC301
`
`2023
`
`HC2O1
`
`2022
`
`HC101
`
`VIC X1
`2021
`
`DCOO1
`
`- • •
`
`CO
`
`trì
`
`———”
`
`OUADAMOUNT
`OF LEFT SHIFT
`
`FIG. 20B
`
`2020
`2024
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 45 of 46
`
`6,097,212
`
`2 O O O C
`
`"C": "T" "" " " " " " " " ": "T"
`E.J. E.
`E.I.E.L. E.
`E.
`E.
`E.L.
`"T" "" " " " " " " " " "," "T"
`... . . . . . . . . . . . . . .
`"T" "" " " " " " "
`" " " ""
`E.
`E.
`E.
`E.
`E.
`E.
`E.
`E.
`"T" "" " " " " " ": "T": "T": "T"
`E.
`E.
`E.
`E.
`E.
`E.
`E.
`E.
`"" " " "," "" " " " " "," "T"
`... . . . . . . . . . . . . . .
`"T" "" " " " " " " " " " " "C"
`... ... ... ... E.
`E.
`E.
`E.I.
`Y
`(" "," ""
`
`
`
`FIG. 20O
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 46 of 46
`
`6,097,212
`
`- - - - - -
`
`
`
`--?—LM KHOA KHOA KHWN
`
`
`
`
`
`
`
`
`
`'NEDITOTEISÖÄ
`
`
`LS}} _HSO/\
`LES GASOA
`
`
`IZ "OIH
`
`

`

`6,097,212
`
`1
`WARIABLE GRAN ARCHITECTURE FOR
`FPGA INTEGRATED CIRCUITS
`
`BACKGROUND
`
`2
`U.S. Pat. Nos. 4,642,487; 4,706,216; 4,713,557; and 4,758,
`985; each of which is originally assigned to Xilinx, Inc.
`An FPGA device can be characterized as an integrated
`circuit that has four major features as follows.
`(1) A user-accessible, configuration-defining memory
`means, such as SRAM, EPROM, EEPROM, anti-fused,
`fused, or other, is provided in the FPGA device so as to be
`at least once-programmable by device users for defining
`user-provided configuration instructions. Static Random
`Access Memory or SRAM is of course, a form of repro
`grammable memory that can be differently programmed
`many times. Electrically Erasable and reprogrammable
`ROM or EEPROM is an example of nonvolatile reprogram
`mable memory. The configuration-defining memory of an
`FPGA device can be formed of mixture of different kinds of
`memory elements if desired (e.g., SRAM and EEPROM).
`(2) Input/Output Blocks (IOB's) are provided for inter
`connecting other internal circuit components of the FPGA
`device with external circuitry. The IOB's may have fixed
`configurations or they may be configurable in accordance
`with user-provided configuration instructions Stored in the
`configuration-defining memory means.
`(3) Configurable Logic Blocks (CLB's) are provided for
`carrying out user-programmed logic functions as defined by
`user-provided configuration instructions Stored in the
`configuration-defining memory means. Typically, each of
`the many CLB's of an FPGA has at least one lookup table
`(LUT) that is user-configurable to define any desired truth
`table, to the extent allowed by the address space of the
`LUT. Each CLB may have other resources such as LUT
`input signal pre-processing resources and LUT output Signal
`post-processing resources. Although the term CLB was
`adopted by early pioneers of FPGA technology, it is not
`uncommon to See other names being given to the repeated
`portion of the FPGA that carries out user-programmed logic
`functions. The term, LAB is used for example in U.S. Pat.
`No. 5,260,611 to refer to a repeated unit having a 4-input
`LUT
`(4) An interconnect network is provided for carrying
`signal traffic within the FPGA device between various
`CLB's and/or between various IOB's and/or between vari
`ous IOB's and CLB's. At least part of the interconnect
`network is typically configurable So as to allow for
`programmably-defined routing of Signals between various
`CLB's and/or IOB's in accordance with user-defined routing
`instructions Stored in the configuration-defining memory
`means. Another part of the interconnect network may be
`hard wired or nonconfigurable such that it does not allow for
`programmed definition of the path to be taken by respective
`Signals traveling along Such hard wired interconnect. A
`version of hard wired interconnect wherein a given conduc
`tor is dedicatedly connected to be always driven by a
`particular output driver, is Sometimes referred to as 'direct
`connect.
`Modern FPGA's tend to be fairly complex. They typically
`offer a large spectrum of user-configurable options with
`respect to how each of many CLB's should be configured,
`how each of many interconnect resources should be
`configured, and how each of many IOB's should be config
`ured. Rather than determining with pencil and paper how
`each of the configurable resources of an FPGA device
`should be programmed, it is common practice to employ a
`computer and appropriate FPGA-configuring Software to
`automatically generate the configuration instruction signals
`that will be Supplied to, and that will cause an unpro
`grammed FPGA to implement a specific design.
`FPGA-configuring Software typically cycles through a
`Series of phases, referred to commonly as partitioning,
`
`15
`
`25
`
`1. Field of the Invention
`The invention is generally directed to integrated circuits,
`more specifically to architectural and physical layouts for
`Programmable Logic Devices (PLD’s), and even more spe
`cifically to a subclass of PLD’s known as Field Program
`mable Gate Arrays (FPGA's).
`2a. CroSS Reference to Related Applications
`The following copending U.S. patent application(s) is/are
`assigned to the assignee of the present application, and
`its/their disclosures is/are incorporated herein by reference:
`(A) U.S. Ser. No. 08/828,520 filed Apr. 1, 1997 by
`Bradley A. Sharpe-Geisler and originally entitled,
`“MEMORY BITS USED TO COUPLE LOOK UP
`TABLE INPUTS TO FACILITATE INCREASED
`AVAILABILITY TO ROUTING RESOURCES PAR
`TICULARLY FOR VARIABLE SIZED LOOK UP
`TABLES FOR A FIELD PROGRAMMABLE GATE
`ARRAY (FPGA)”;
`(B) U.S. Ser. No. 08/931,798 filed Sept. 16, 1997 by
`Bradley A. Sharpe-Geisler and originally entitled,
`“CIRCUITRY TO PROVIDE FAST CARRY and
`(C) U.S. Ser. No. 08/700,616 filed Aug. 16, 1996 by Om
`Agrawal et al (as a continuing divisional with chained
`cross referencing back to U.S. Ser. No. 07/394,221 filed
`Aug. 15, 1989).
`2b. Cross Reference to Related Patents
`The following U.S. patent(s) are assigned to the assignee
`of the present application, and their disclosures are incor
`porated herein by reference:
`35
`(A) U.S. Pat. No. 5,212,652 issued May 18, 1993 to Om
`Agrawal et al., (filed as Ser. No. 07/394.221 on Aug. 15,
`1989) and entitled, PROGRAMMABLE GATE
`ARRAY WITH IMPROVED INTERCONNECT
`STRUCTURE;
`40
`(B) U.S. Pat. No. 5,621,650 issued Apr. 15, 1997 to Om
`Agrawal et al, and entitled, PROGRAMMABLE
`LOGIC DEVICE WITH INTERNAL TIME
`CONSTANT MULTIPLEXING OF SIGNALS FROM
`EXTERNAL INTERCONNECT BUSES; and
`45
`(C) U.S. Pat. No. 5,185,706 issued Feb. 9, 1993 to Om
`Agrawal et al.
`3. Description of Related Art
`Field-Programmable Logic Devices (FPLD's) have con
`tinuously evolved to better serve the unique needs of dif
`ferent end-users. From the time of introduction of simple
`PLDS Such as the Advanced Micro Devices 22V10TM
`Programmable Array Logic device (PAL), the art has
`branched out in several different directions.
`One evolutionary branch of FPLD’s has grown along a
`paradigm known as Complex PLD’s or CPLD’s. This para
`digm is characterized by devices Such as the Advanced
`Micro Devices MACHTM family. Examples of CPLD cir
`cuitry are seen in U.S. Pat. No. 5,015,884 (issued May 14,
`1991 to Om P. Agrawal et al.) and U.S. Pat. No. 5,151,623
`(issued Sep. 29, 1992 to Om P. Agrawal et al.).
`Another evolutionary chain in the art of field program
`mable logic has branched out along a paradigm known as
`Field Programmable Gate Arrays or FPGAs. Examples of
`Such devices include the XC2000TM and XC3000TM families
`of FPGA devices introduced by Xilinx, Inc. of San Jose,
`Calif. The architectures of these devices are exemplified in
`
`50
`
`55
`
`60
`
`65
`
`

`

`6,097,212
`
`15
`
`25
`
`35
`
`40
`
`3
`placement, and routing. This Software is Sometimes
`referred to as a place and route program. Alternate names
`may include, synthesis, mapping and optimization tools.
`In the partitioning phase, an original circuit design (which
`is usually relatively large and complex) is divided into
`Smaller chunks, where each chunk is made Sufficiently Small
`to be implemented by a single CLB, the single CLB being
`a yet-unspecified one of the many CLB's that are available
`in the yet-unprogrammed FPGA device. Differently
`designed FPGA's can have differently designed CLB's with
`respective logic-implementing resources. AS Such, the maxi
`mum size of a partitioned chunk can vary in accordance with
`the specific FPGA device that is designated to implement the
`original circuit design. The original circuit design can be
`Specified in terms of a gate level description, or in Hardware
`Descriptor Language (HDL) form or in other suitable form.
`After the partitioning phase is carried out, each resulting
`chunk is virtually positioned into a specific, chunk
`implementing CLB of the designated FPGA during a sub
`Sequent placement phase.
`In the ensuing routing phase, an attempt is made to
`algorithmically establish connections between the various
`chunk-implementing CLB's of the FPGA device, using the
`interconnect resources of the designated FPGA device. The
`goal is to reconstruct the original circuit design by recon
`necting all the partitioned and placed chunkS.
`If all goes well in the partitioning, placement, and routing
`phases, the FPGA configuring software will find a workable
`Solution comprised of a specific partitioning of the original
`circuit, a specific Set of CLB placements and a specific Set
`of interconnect usage decisions (routings). It can then deem
`its mission to be complete and it can use the placement and
`routing results to generate the configuring code that Will be
`used to correspondingly configure the designated FPGA.
`In various instances, however, the FPGA configuring
`Software may find that it cannot complete its mission Suc
`cessfully on a first try. It may find, for example that the
`initially-chosen placement Strategy prevents the routing
`phase from completing Successfully. This might occur
`because Signal routing resources have been exhausted in one
`or more congested parts of the designated FPGA device.
`Some necessary interconnections may have not been com
`pleted through those congested parts. Alternatively, all nec
`essary interconnections may have been completed, but the
`FPGA configuring software may find that simulation
`predicted performance of the resulting circuit (the
`So-configured FPGA) is below an acceptable threshold. For
`example, Signal propagation time may be too large in a
`speed-critical part of the FPGA-implemented circuit.
`In either case, if the initial partitioning, placement and
`routing phases do not provide an acceptable Solution, the
`FPGA configuring software will try to modify its initial
`place and route choices So as to remedy the problem.
`Typically, the Software will make iterative modifications to
`its initial choices until at least a functional place-and-route
`Strategy is found (one where all necessary connections are
`completed), and more preferably until a place-and-route
`strategy is found that brings performance of the FPGA
`implemented circuit to a near-optimum point. The latter Step
`is at times referred to as 'optimization. Modifications
`attempted by the Software may include re-partitionings of
`the original circuit design as well as repeated iterations of
`the place and route phases.
`There are usually a very large number of possible choices
`in each of the partitioning, placement, and routing phases.
`FPGA configuring programs typically try to explore a mul
`titude of promising avenues within a finite amount of time
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`to see what effects each partitioning, placement, and routing
`move may have on the ultimate outcome. This in a way is
`analogous to how chess-playing machines explore ramifi
`cations of each move of each chess piece on the end-game.
`Even when relatively powerful, high-speed computers are
`used, it may take the FPGA configuring Software a signifi
`cant amount of time to find a workable Solution. Turn around
`time can take more than 8 hours.
`In Some instances, even after having spent a large amount
`of time trying to find a solution for a given FPGA
`implementation problem, the FPGA configuring Software
`may fail to come up with a workable Solution and the time
`spent becomes lost turn-around time. It may be that, because
`of packing inefficiencies, the user has chosen too Small an
`FPGA device for implementing too large of an original
`circuit.
`Another possibility is that the internal architecture of the
`designated FPGA device does not mesh well with the
`organization and/or timing requirements of the original
`circuit design.
`Organizations of original circuit designs can include
`portions that may be described as random logic (because
`they have no generally repeating pattern). The organizations
`can additionally or alternatively include portions that may be
`described as “bus oriented’ (because they carry out nibble
`wide, byte-wide, or word-wide, parallel operations). The
`organizations can yet further include portions that may be
`described as matrix oriented (because they carry out
`matrix-like operations Such as multiplying two, multidimen
`Sional vectors). These are just examples of taxonomical
`descriptions that may be applied to various design organi
`Zations. Another example is control logic which is leSS
`random than fully random logic but leSS regular than bus
`oriented designs. There may be many more taxonomical
`descriptions. The point is that some FPGA structures may be
`better Suited for implementing random logic while others
`may be better Suited for implementing bus oriented designs
`or other kinds of designs.
`If the FPGA configuring software fails in a first run, the
`user may choose to try again with a differently-Structured
`FPGA device. The user may alternatively choose to spread
`the problem out over a larger number of FPGA devices, or
`even to Switch to another circuit implementing Strategy Such
`as CPLD or ASIC (where the latter is an Application Specific
`hardwired design of an IC). Each of these options invariably
`consumes extra time and can incur more costs than origi
`nally planned for.
`FPGA device users usually do not want to suffer through
`Such problems. Instead, they typically want to See a fast
`turnaround time of no more than, Say 4 hours, between the
`time they complete their original circuit design and the time
`a first-run FPGA is available to implement and p