United States Patent
`
`[19]
`
`[11] Patent Number:
`
`6,145,069
`
`I||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`USU(l6145ll69A
`
`Dye
`
`I54]
`
`[45] Date of Patent:
`
`Nov. 7, 2000
`
`PARALLEL DECOMPRESSION AND
`C()Ml’RESSlON SYS'I'I'3M AND METHOD
`FOR IMPROVING STORAGE DENSITY AND
`ACCESS SPEED FOR NON-VOLATILE
`MEMORY AND EMBEDDED MEMORY
`DEVICES
`
`5_.37l,499
`5_.3’.“J_.tJ?t6
`5,396,343
`5_.4t}(J,2?8
`5_.4U-t‘J_.2'l".'l
`5,412,429
`5,414,425
`
`l2;"199-1 (jrayhill ct til.
`1:19:95 Storer.
`3.51995
`ilanselman ............................ .. 358.-"-’-$21‘)
`4;'l9‘)5 Grayhill et al.
`.
`—’l,."l9‘l5 Anderson et al.
`$1995 (ilovcr .
`5,.-'t9‘.\}5 Whiting et al.
`
`.
`
`.
`
`.
`
`[75]
`
`Inventor: Thomas A. Dye, Austin, Tex.
`
`I73]
`
`Assignee:
`
`Interactive Silicon, lne., Austin, Tex.
`
`{List continued on next page.)
`
`Printnry i.?xanu'm:r—Eddic P. Chan
`Assistant l;‘xnminer—Hong Kim
`Attorney, Agent, or Ft'rm—Conley, Rose & Tayon PC;
`Jelfrcy C. Hood
`
`[57]
`
`ABSTRACT
`
`A flash memory controller ancllor embedclccl memory con-
`troller including Memoryl-‘EX Technology that uses data
`compression and decompression for improved system cost
`and performance. The Compression Enhanced Flash
`Memory Controller [CET-'MC) of the present invention pref-
`erably uses parallel lossless compression and decompression
`engines embedded into the flash memory controller unit for
`improved memory density and data bandwidth. In addition,
`the invention includes a Compression Enhanced Memory
`Controller (CEMC) where the parallel compression and
`decompression engines are introduced into the memory
`controller of the microprocessor unit. The Compression
`Enhanced Memory Controller (CEMC) invention improves
`system wide memory density and data bandwidth. The
`disclosure also indicates preferred methods for specific
`applications such as usage of the invention for solid—statc
`disks, embedded memory and Systems on Chip (SOC)
`environments. The disclosure also indicates a novel memory
`control method for the execute in place (XIP} architectural
`model. The integrated parallel data compression and decom-
`pression capabilities of the CEFMC and CEMC inventions
`remove system bottle-necks and increase performance
`matching the data access speeds of the memory subsystem
`to that of the microprocessor. Thus, the invention allows
`lower cost systems due to smaller data storage, reduced
`bandwidth requirements, reduced power and noise.
`
`39 Claims, 24 Drawing Sheets
`
`I21]
`
`App}. No; l]9,I"299,966
`
`[22
`
`Filed:
`
`Apr. 26, 1999
`
`[53]
`
`I51]
`[53]
`
`[53]
`
`I55!
`
`Related U.S. Application Data
`
`Continualiomin-part of application No. 09.-’2'39_.é59_. Jan. 29,
`1999.
`
`Int. CL? .................................................... .. G06l" I2;’00
`U.S. Cl. ........................... .. 7111170; 711E103; 710,568;
`382K233; 345521; 34550]
`Field of Search ................................... .. 7111103, 170;
`710368; 714E763, 7'64; 7099247; 382232,
`233; 34-5521, 501, 507, 509
`
`References Cited
`
`U.S. l’A'l'l:INT DOCUMI:IN’l‘S
`
`......................... .. 395,."463
`....................... . 358.-'2()l.l
`
`2,r't‘)7’.F Bryant ct al.
`4_.iIl8,46(l
`8."l‘)8'.-' Cotton el al.
`4_.688,lU8
`l(},"l989 Storer.
`4,376,541
`11,-H989 Wong ...................................... .. 341,-F8?
`4.881.075
`3fl991 Whiting el al. .
`5,t’lt‘t3,3tl7
`531991 Whiting el al. .
`5,(Jl6,(I}9
`6;'1992 Whiting ct al. .
`5,l26,'.»'39
`‘M1992 Whiting Ct at. .
`5.l46,22l
`£155,484 1U,fl992 Chambers, IV .
`395.-“B88
`5,237,460
`S;"l993 Miller el al.
`.. TIUISS
`5,23'r,c575
`sin;-93 Hannon, Jr.
`.. 71U;'68
`5_.24?_.638
`9,-"[993 (Tflrien el al.
`395888
`5_.24?,t')=lv6
`.‘h"l993 Osterlund et al.
`36Sr't89.t]t
`5_.337_.2?5
`SH994 Garner
`8.-‘I994 Wells ................................ . 3(:5,u‘18S.]l
`ltJ;'t‘)‘J4 (irayhill.
`lU;‘t994 Malainy ct at.
`l[),a’t994 Pattisam et at.
`
`
`
`...................... .. TIIII44
`........................ .. ?l['!r'ti8
`
`
`
`Q00 - Flush met:-Iuqr_§ysrom
`
`112
`
`l ECCJEDC
`
`I90
`
`Convener
`
`-
`
`APPLE 1008
`
`APPLE 1008
`
`1
`
`

`
`6,145,069
`Page 2
`
`1
`
`us. PATENT DOCUMENTS
`_
`,_
`_
`358x468
`$911193-t
`§;=:g:)i.-2;?
`.........................
`$19.93 C:-ag;rl1:I:
`%,426_.7?9
`.
`‘
`"
`"
`’_
`........................... .. 7147757
`971995 Wells et 11.
`5,443,577
`-
`_
`,.
`_
`_
`.............................. 341751
`5,455,577 1071995 5114115 51:11.
`5,455,943 1071995 C11am1ms,1v.
`5,459,350 1071995 Ciay 51 51.
`.............................. 7117171
`cl al' v
`5,455,333 1171995 Clay ...................................... .. 7107130
`
`5,477,254 1271995 3515555115515: 51.
`3437231
`........................... .. 7117103
`5,479,533 1271995 75155: et a].
`5,435,525
`171995 ‘ll:-bin.
`5,504,342
`471995 Gentile ................................. .. 35371.15
`5,505,530
`471995 Whiling 5151..
`5,526,363
`671996 Weiss ct al. .
`5,532,693
`"#1996 Winters et al. .
`5,532,594
`771995 Mayers el 51..
`5,543,742
`371995 Wang 5151.
`.......................... .. 7117123
`5,553,251
`971995 11151555 51 .-11.
`........................ .. 7117103
`5,559,973
`971995 Spilo ..................................... .. 7117203
`
`5,553,595
`5,553,423
`5,572,205
`53571243
`5,584,008
`5,505,428
`5621403
`:’
`’
`3'7"“°=539
`5,696,912
`$397333
`3.798.-718
`5,812.31?
`5,323,377
`5,374,903
`5,377,711
`5,883,588
`5,933,104
`5,935,550
`5,945,933
`5,955,372
`5,973,530
`
`............................ .. 3417105
`1071995 31751155115:
`
`..................... ,. 355713533
`1071995 .155 5151.
`1171995 511115151 51..
`
`11“995 Chambers, w_
`.,
`, 7117114
`1271996 Shimada 01 a1.
`271997 11555515155 ............................ .. 3537404
`4,199., R
`ik
`'
`“Z”
`511997 ”_°""""-‘"_ """"""""""""""""""""""117111193
`BiCC\I"-‘ikl-S 913.1.
`.«...................
`311993 F"*'193Z°1< 9191--
`371993 Hadadyv
`971998 Hovis etal.
`1071993 Pearce 1-.151.
`271999 Craft.
`371999 C1511.
`371999 Okamura .
`871999 Kimura .
`371999 Higuchi.
`371999 1011151515.
`971999 Vamzln et 51..
`1071999 1155111.
`
`395749104
`......................... .. 3957570
`
`2
`
`

`
`U.S. Patent
`
`Nov. 7, 2000
`
`Sheet 1 of 24
`
`6,145,069
`
`mm2nv<
`
`
`
`W33NUFND
`
`
`
`m:&_m:m_
`
`%r_
`
`.5=..._:_.
`
`Q._0t._._mEma
`
`_O.5COU
`
`9...:
`
`3
`
`
`
`
`
`

`
`Nov. 7, 2000
`
`Sheet 2 of 24
`
`6,145,069
`
`_2<mw
`
`5.33
`
`.60
`
`Qmm9_uu<
`
`m_._,
`
`OSV
`
`
`
`boEmEc_mS_<N.m_u_
`
`JJ:2._o_._n=
`
`05:2
`
`]_O:COmwI
`Qa20moomaam
`
`m_.__mmmoo.i0hi;mm_n_
`
`«EDm_.._.u:._m"-_o.:.:oO
`8.,»<9L.NH
`
`m:9:
`
`_>_<ma
`
`
`
`boEmE3n=2
`
`olmm
`
`.0s_<mm
`
` U.S.Patent
`
`4
`
`
`
`
`

`
`..lHe4....3P3nu
`
`Nov. 7, 2000
`
`Sheet 3 of 24
`
`6,145,069
`
`5_<~.._D5s_<mw
`
`
`
` E..coEmE_._n=>_
`
`90:2
`
`m:_mmmo9n_
`
`E5
`
`cow
`
`_2<mw
`
`.6
`
`5.55
`
`
`
` E..¢oEwEEms.
`
`
`
`EwanmoEmE:mu...¢.new
`
`USENU-cow
`
`s_<mw
`
`wcumo
`
`8;
`
`co__mmmaEouma
`
`o..__m:m_
`
`mmlm
`
`co_mwmEEoO
`
`§mE_m:m_
`
`9m>>woomaom
`
`mc__w>m.._
`
`2%..
`
`own
`
`N:
`
`we
`
`we
`
`2:
`
`II_9Eoo8..
`
`
`
`
`
` §_.c2om:_n_EmawE5_o._Eoo:o_wmm:aEoo
`
`%W.mtm>cooH09.00
`
`
`
`mmm.U_u<aomu.”_n:._<1:
`
`5
`
`
`
`
`
`
`
`
`

`
`
`
`05:2BoEm_>_
`
` U.S.Patent
`
`memo%
`
`w_._.fin:
`
`
`
`:o_mmmEEoomn_02¢.Emwmnflnw
`
`.CoEm_>_
`
`IHg“EDWQmcfimmooi:o_mmm:E00
`
`momtmE_
`
`Nov.7,2000
`
`:o_wmm:aEoo
`
`§m:_m.:m_
`
`Sheet4of24
`
`24%
`
`.0
`
`
`
`Dn:>_uouumnem 0.9“.
`
`6,145,069
`
`
`
`aw.3H>._oEmE:_mE
`
`s_<mo
`
`6
`
`
`
`

`
`U.S. Patent
`
`Nov. 7, 2000
`
`Sheet 5 of 24
`
`6,145,069
`
`m:_mmmoEn_
`
`“ED
`
`Se
`
`2<mw
`
`3
`
`2430B_2<mm
`
`
`
`_.:oEmE3&5.
`
`mm
`
`fifla
`
`
`
`m:em:
`
`Dm:_m:m_
`
`:o_mmmaEo8o
`
`92.2-mam
`
`oaeoommam
`
`usmmo-Sn_
`
` 3>._oEmEEms.
`
`tocm...mflua_2<mn_..n_.3D3:3.Eco:o_mmm:E00
`
`aeuqqaommg.2:
`
`NS.
`
`7
`
`
`
`
`
`
`
`

`
`f.HC..laPQMU
`
`Nov. 7, 2000
`
`Sheet 6 of 24
`
`6,145,069
`
`oomawmoasooopaeoo
`
`O9:22E809.8
`
`omCONNn=_Ems__.oom_
`
`
`
`own_o::oommmn-__...m_
`
`mmmzuudBox
`
`
`
`oo_.Em_>_Em:
`
`u.9".
`
`
`
`cm.:23u:_._CoEwS_
`
`mom
`
`._m_ummIw..cBow._o
`
`cozmcwcwo
`
`o_mo._
`
`Sm
`
`mocmzmzoow225
`
`._m__o._Eoo
`
`mm
`
`.m.
`
`:o_mwm._aEoomQ
`
`_o::oo
`
`o_mo._
`
`mm
`
`“EE226oombom
`
`_9Eo0
`
`9...,»
`
`oo<
`
`
`
`_O._uCOO2.00:0DEG._0Um0T_
`
`:o_mmm:n_Eoo
`
`mmm._uu<w.mn_
`
`_._o_mmoaEoo
`
`26_.:m>O
`
`:ozm_w:m.._.
`
`mmm:uu<
`
`Em
`
`n:mEc._oo
`
`:o_§m:n:mE_
`
`%_O._~_._OOnew
`
`_o=:oo
`
`mmm:uu<wmom+_mE_
`
`Lmuoomu
`
`Q8
`
`2.W
`
`‘EL
`wm2_un<
`
`Ema
`
`aim
`
`_9Eoomam
`
`8
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Nov. 7, 2000
`
`Sheet 7 of 24
`
`960.,54_I..,6
`
`mucmseoo
`
`mm89n_
`
`8%
`
`
`ofimmmcmfiEma5$2:
`_mEwE_EcongaEaa5co_aE_m_.__
`mmmooi
`E5»w>_5.3.83
`
`%2.8%$234
`
`...a_..333in2%....._am
`
`
`
`:8:BE%%:mEEoo.=o=o§m:_85mmgm._8_g_._mmEc+uEmo_o
`
`
`
`
`
`SE5522mEm$3200
`%boEoE
`
`mumv.83cofimwaeoo
`%...%_._E8
`
`
`
`mumnewEflmcmo
`
`
`
`_.m._mummE_.6_m8aE8
`
`am2%oB...oom_%§ao
`
`%%mm.in_w.m.m:o_§on_om_
`
`
`
`mmmosumv.83BmmoasooB9_oo_83$co_§m:E_$804
`
`
`
`mmmaumaomfim:mémo
`
`
`
`omomxmtmfig“.3.3new
`
`Bmaom38.5
`
`
`
`
`
`%mama;co_m8.aEoonew
`
`
`
` §swam2v_oo_nmam$55a:.E_._p.52:09_m__Emq:_
`
`
`
`marsmmmaeoomo
`
`§$8_m._,...m_u_gsgoo
`
`awmaceC
`
`
`
`wm8mtmE_mamOH3330m..E_>>
`
`
`
`
`
`EEE5__.,_<mm_.__.€mm:_m
`
`
`
`
`
`mmmfiumx8_ncoammaeoum_
`
`52.2£83£3s_§e$m
`
`E8$3
`
`9
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`v”0N
`
`7..
`
`6,145,069
`
`$ .
`
`é*
`LL
`
`
`
`8%aumcomomwmmsufioEm5
`
`
`
`mmcouxoofiBco_wmm:n_EoomQ
`
`
`
`ommm:ms_55mfimo@333
`
`omwmwmcoo
`
`
`
`
`
`4ommmnmumwzcw.wmmfium2.3EM59:0ncmmcomo9EmuwE>>
`
`
`
`:o_mm.P_aEoomn_%8%2.2»280om83$2.36:82Momwm
`
`
`
`2.,_._o:w_:o_mommm:u_u<Sam:_Emum.:>>5vmmm
`
`|39wW2%yardr_mm_n_E0...Sam.2..om.#w_.4.m..__u%.umo
`
`
`
`
`iulu8%u_mo:_uamaom
`
`
`|3.25%mag:
`
`10
`
`
`
`CommovémwmcwcowwmymOmvm_u:mEEoO.Eo:.o:=.mc_
`
`
`
`
`
`
`
`mu:mEEooEm_ooE_mEmE_Bcozoce
`
`
`mmmooi5&3._oco_.o:=mc_mmmooi
`
`
`
`omvmouoowo
`
`
`
`
`
` mm9%<»OVVMmmwou<>._OEw__2_._mm_n_Hom_mw
`
`
`
`
`
`tO.:.u.W@»...u._._.COUWOW..._fl.OOu¢n=*
`
`10
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Nov. 7, 2000
`
`Sheet 9 of 24
`
`6,145,069
`
`m_u:mEEoo
`
`mmmooi
`
`m.m_"_
`
`
`|l25EmumE2_.m9.m_2amm$1ocomo>»8?,
`
`
`ovrmmmcmcomtflmBm_uoE>omvm.u:mEEoo.Eo=o::w:_
`
`
`
`
`
`
`
`
`
`_m:._wE_2cozocaconga
`
`
`
`LO:O_.._0:.__umC_mmoo9n_
`
`
`
`83w_88n_$9%<
`
`
`
`-ovvmmmooo<>..oEw_2gomfim
`
`
`Duo5naunaaem...mbo$.oak
`
`
`owmmwcomoE.6.:o_fi_:o_momwmE..fi<
`
`
`
`..somotnm$225mmzceExoofiUmmmméum208E3%wE>>598¢
`
`
`
`ohum.€:<cmmiE0:ummm1|
`
`
`
`
`
`
`
`
`S32%E08omvmo_mo._oomaom8%2%28.0
`_.E.E._m__2Emma:3ms_5m._9.23:
`
`owmmEmu.mmm:n_Eo0:.0
`
`mmzonv_ooE.5:o_mmmaEoomn_
`
`
`
`
`
`8%%Bo8mmmm:_u_o<.6Em
`
`
`
`I383E55%::Ilimm$m8<away.2:5m_._.....>
`
`
`
`ommm:ms_5EwfimoBatu:
`
`
`
`
`:umzfimma2m.umw:u_Dm._E0omvmco_mwm:aEoown_8%mmm:_u_um:82
`83.fim_9.ll|
`
`
`
`ommmmmmfiumxooll
`
`|....
`zmmzumzmwfiimc_%,m_uommmuflmmzcm.mmmzuum33EIF.95
`
`
`
`
`
`
`
`33:0ucm.mzomo2Emu25>omvm.on_:
`
`11
`
`11
`
`
`
`
`

`
` U.S.Patent
`
`Nov. 7, 2000
`
`Sheet 10 of 24
`
`6,145,069
`
`wmEI
`9598.2:c85
`
`omum
`
`bum.EEma=55
`Nmomam
`
`B85%.
`
`Eng._a___o25
`
`12
`
`12
`
`

`
`SU
`
`Llun6Ale3P
`
`Nov. 7, 2000
`
`Sheet 11 of 24
`
`6
`
`w
`
`
`
`
`
`
`
`
`
`.I..,EmuummmmaEoo.5930Bb__mS_Qm56E8.2co=mE.oE__._3mEoc__E$mn_
`09NS..9|m.3.
`
`
`.%:o_Hm=_mm.w_%._a_Mo%m%9:9B__..m22mn_EooucmEsauE850mp:coEmmammoazim_._.
`
`
`
`
`
`.cowmmmaeoo_m__£mm
`
`:22;mc_mE_m_>_
`
`
`
`
`
` QmmE:mm:_m.:aEou23$
`
`.5b__E=_amemaaoo
`
`
`g28.
`
`r2m_,_9:5‘Samsumo£__sm_B_.E$
`
`38mm
`
`
`
`Emuummmmasoocz
`
`mam
`
`
`
`BE.5E38EmE3m.c_mE_m_2
`
`§E359%Emmma9:§mofime
`
`13
`
`13
`
`
`
`

`
`U.S. Patent
`
`Nov. 7, 2000
`
`Sheet 12 of 24
`
`6,145,069
`
`
`
`
`
`m_o£§mnommmaeoocb2%
`
`.82?:22:2
`
`
`
`m:_c_mEmm;m:_”..
`
`
`
`393mm§w_2mzosma
`
`_s_.§mE3528
`
`Bmmmasoocs
`
`mm
`
`=4.23%
`
`
`
` acan232..560
`
`
`
`m=o__..§n_.350
`
`25£3Bmmwaeoo
`
`fl
`
`_oe_;mseas
`
`
`
`
`
`
`
`§.QQ22%....=<5EmmaEou_._:.wu=_oc__onExm
`
`
`uowmoaeoo59:025mwoo
`
`ea.582....%:_u:_gum:
`
`I3§n.._B=;mas
`
`$>
`
`:o=E_m:___B38.2ax28E6.93EE5o__.5_o__.8tn_cams.
`
`c_E=on:B=;mEE52_2__=oo
`
`Emma
`
`
`
`.cEm_2033some53,_onE.$
`
`
`
`
`
`52commm:mqEoo
`
`3...,
`
`uowmmaeoefiE4
`
`8...?age:22355
`
`2.9”.
`
`2,.
`
`m:o__$.i
`
`n..mo;2m_2
`
`Wm
`
`mm;
`
`£262m=o___§mm:_n.:_o:_
`
`
`
`
`
`
`gems.fimm._m._aofiw
`
`§
`
`am25£3uwmmmaeoo
`m=o_>m_n_53:0
`
`mm»
`
`
`
`somemm8§__
`
`maeimBu.3.550
`
`Em
`
`14
`
`14
`
`
`
`
`
`
`
`
`
`
`
`

`
`aPamU
`
`..mB2:930W93500
`
`._9m._mo
`
`mm_._Em__.n_
`
`mM
`
`m.1,
`
`mS
`
`0
`
`4
`
`6
`
`mv.825930
`
`HEsoo39:0
`
`
`
`m_.._m>xw_>_
`
`Qm:
`
`mgzmmm
`
`a:o=m_:o_mo
`
`Emm:o_>m.n__.o
`
`
`
`v_mmS_Uw_.__n_EoO
`
`mm
`
`9.
`
`15
`
`a
`
`_...,2.2".
`
`9069
`
`15
`
`

`
`
`
`mco_..m_:u_momzsmmmoH
`
` U.S.Patent
`
`
`
`m:_m>Emma
`
`xmms.X92
`
`Ems.w.560abum.
`
`in:wE80_.Em.
`
`xwszwE300Nbum.
`
`
`
`EmaEmaEmaEma>m:n_
`
`mNwomflmo
`
`
`
`x2E_Ezooxm_>_
`
`Nov.7,2000
`
`v_mm_>_M.E300ombcw
`
`
`
`xmm5_.mEzoocBEm
`
`v_mms_wE30_Ecm
`
`m:o_>m._n_
`
`E930
`
`Emmbm
`
`
`
`xm_E_Ezoo>m:m
`
`Ezoo
`
`2%..
`
`fin:wE300NEcm
`
`16
`
`6,145,069
`
`E.5
`
`EmmzwSan.53:0
`
`
`
`v_mm_2ummmm:aEoOCm._Em
`
`
`
`mmm:QEoo_um:_n_EoO
`
`Sheet14of24xmm_>_
`
`aEoymficwo
`
`ma
`
`xmflzwEsooC&Em
`
`
`
`v_mms_ummmm:EcooEEw
`
`16
`
`

`
`QMU
`
`tH84|.3D1
`
`Nov. 7, 2000
`
`Sheet 15 of 24
`
`(0
`
`0/60.,541..,
`
`Emma
`
`o=_a>
`
`53:0
`
`fin:
`
`
`
`33:0.2550252
`
`m2_2m_2S._.__
`
`
`.3580m=_m>
`HERE
`
`i.'LD1—(\£C\J(V'JC"JC"JC"J'fil'1"‘=1"=1"El"‘i1"‘=!"d‘
`
`2.9".
`
`oooo_
`
`S2:
`
`22:
`
`:2:
`
`8::
`
`5::
`
`8::
`
`E2
`
`89:
`
`:_.5
`
`So:
`
`5:
`
`8:.
`
`2::
`
`0::
`
`E:
`
`m+_.m>mm
`
`m+u9.,mw
`
`Y.um_..mw
`
`$B>mm
`
`Yémpmm
`
`$_§.mm
`
`ugmw
`
`Baum
`
`umamm
`
`um>mm
`
`Bpmw
`
`umsmw
`
`umpmm
`
`_§mm
`
`1—$C'\.|(:>\--<:)(“"}$1-'ZC'\IC:TJ‘I—Z
`
`
`
`m+um>mmo.3um....mwq+um>m.w
`
`avoFaFcPoVeFoFo—
`
`V
`
`1—$¢~¢-1-5&1-1-6%!-1-56
`
`1-1-1-1—2$$@'I-1-1—\—§$$$
`
`1-1-1--u--r--1-1-1‘-%$$$C3$¢.".'I$
`
`17
`
`17
`
`

`
`U.S. Patent
`
`Nov. 7, 2000
`
`Sheet 16 of 24
`
`6,145,069
`
`No
`
`Prev Cnt= 0?
`721
`
`Yes
`
`Send out
`Compressed
`
`BlockQ3 I .
`Adjust Max Count ‘
`
`to 4 or Less
`
`E
`
`Send out Compressed
`Block E
`
`
`
`
`Send LZ12
`
`Compressed
`Biock E
`
`NoYes
`
`
`
`
`
`Done
`
`
`
`Send out
`Data 0 E
`
`L0 .
`Send out M
`Data 0Z4].
`
`Fig. 16
`
`18
`
`18
`
`

`
`U.S. Patent
`
`Nov. 7, 2000
`
`Sheet 17 of 24
`
`6,145,069
`
`
`
`EHn:_E__$_u__.__£7.;&__&__n:mr_EEEEso,.mms_
`
`
`
`
`
`m_.Em_‘~::9mmNomV«N_.oism
`
`SIBQ_E_o3__o3Z=9__HHEH_E_HE8
`EHEEEJLEEEEEEEEEEE2.802%
`
`
`
`fl_W_HE_o|E_m|Eo|_E_o|E_Eo|__o|_E3oE8
`
` pmaH_.._:_
`
`
`
`u:Q.._:_O2mE£_<
`
`H29".
`
`%__aso
`
`
`3320__o.10__o__o_o__o_oo_Eo|__o|_E2:8
`@Em|“___lm|¢__H_m|u__fl__vl“_:|“___M__fl_o|“__E@EE28Ema
`
` _.._”mo._.&__
`
`
`
`
`
`HEEEEEEEHEHEEHEHso,_w§o_o|_o|__.o|:__o|_fl§§o|__o|=o|o|__o|_H_fl_oI_50580
`
`Eggso
`
`
`
`EEEEWEEEEIEEEEEE59.58
`
`
`
`EHEEWEEEEEEHEEEHso0.02
`
`fl__fl_fl_fi__flfl__fl_@_fl_fl__m_fl__fl_fl__H_H28
`HEHEEHEEHIWEEHEEE383%
`
`
`
` 2.3.3..
`
`
`
`E5930.2”.
`
`as§_amamm%nama111%
`
`mmmmadEEE8mmBEEEEEEHananEma
`
`H5.5
`
`
`MEHEEHHEEEEHHEEEsoxwmg
`
`
`b:_Ho|__oI_:.|o|__o|__o|_o|__o|_WEEH__H_Eaoéao
`
` D”mo.._n_,._
`
`
`o|_o|_o|__o|__o|_o|__fl_o|_H_o|_o|=o|__o|_H_o|_§=58
`Mflmflflflfiflflflflfiflmflflfio0%
`
`19
`
`19
`
`
`

`
`U.S. Patent
`
`Nttttttttttt0
`
`Sheet 18 of 24
`
`6,145,069
`
`20
`
`

`
`m3P3U
`
`2f0011.M...
`
`0/60.,5M
`
`6.,.swam2E
`
`45m_mw
`
`cozfiwcmw
`
`%Q0m__..<
`
`QmQB
`
`w._maEo0MisN.63NNNENisN.63N3.5NNIIll.“LIll“!
`020?.mM23500m:mo_EoQm:mnEo0m:mn_Eoom_maEoo
`
`
`
`
`
`21
`
`
`

`
`QMU
`
`tHC4....3D1
`
`N
`
`3.9”.
`
`o:xQ_xxox:xO:xmoxxxQ:4xQ:xxD
`
`
`
`.....m.ucam:£_mSun.550.82..mm:uommuaeoowmoim
`
`
`
`
`
`Iw--no2:Mman--QQ
`
`S2--85:m2.-88:N
`
`.m9.-no52::om.2.-no89::mM2-.62:...
`
`cm,2--8o::::2--85:::22..302::m2.-8:o::wM:--829::~.
`
`9
`
`M.5,5mmM3-9:Ha::_.::5
`
`22
`
`22
`
`
`

`
`U.S. Patent
`
`Nov. 7, 2000
`
`Sheet 21 of 24
`
`6,145,069
`
`mmsmm93s%_
`
`:58
`
`23
`
`23
`
`

`
`U.S. Patent
`
`Nov. 7, 2000
`
`Sheet 22 of 24
`
`6,145,069
`
`Fig.23
`
`
`
`E5.-'K15% DataIndexBe25535
`
`
`
`
`
`
`DataIndex'
`
`
`
`DataIndex
`
`
`StanCounts
`
`E_%_5
`L
`
`-‘25523
`
`4Decoder‘!
`
`
`
`Count
`
`gagIndex3
`
`InutData 0:D
`
`:i9:I 36?.
`
`DecoderGI
`
`24
`
`24
`
`

`
`U.S. Patent
`
`Nov. 7, 2000
`
`Sheet 23 of 24
`
`6,145,069
`
`m:o_>En_
`
`fim_mw
`
`m=o_>o_n_
`
`E300
`
`25
`
`25
`
`

`
`QMU
`
`toHC4....3D1
`
`Nov. 7, 2000
`
`Sheet 24 of 24
`
`6,145,069
`
`5.8E
`
`m_.oMQx
`
`x
`
`NFQKQ
`
`83x
`
`omiofio
`
`m+8$Ea
`
`w+o%8S
`
`_.+on_x35
`
`__.....~.5
`
`$'CDC2>i3CD<:JC:3C.'>
`C)C)$(2')$$C:3C'.'>
`
`...:.
`
`HZ.
`
`u:.
`
`n__.
`
`n:.
`
`m:
`
`8o_.
`
`u:&&H:
`
`n__.
`
`m:
`
`8m:
`
`HZ.
`
`H2.5H2.
`
`H:
`
`m:
`
`8m_.
`
`n__.
`
`H:
`
`H:
`
`..:.
`
`m:
`
`8w_.
`
`None5509,2
`
`309,2
`
`2095309,2
`
`3095Eng5Run:>2
`
`m=o_>En_
`
`50.8
`
`26
`
`26
`
`

`
`6, '1 45,069
`
`1
`PARALLEI. DECOMPRESSION AND
`COMPRESSION SYSTEM AND METHOD
`FOR IMPROVING S’I‘ORAGE l)ENSI'l‘Y AND
`ACCESS SPEED FOR NON-VOLATILE
`MEMORY AND I£MBl‘ll)I)l£I) MEMORY
`DEVICES
`
`CONTINUATION DAFA
`
`This is a continuation-in-part (CIP) of U.S. patent appli-
`cation Ser. No. 09}239,(>59 titled “Bandwidth Reducing
`Memory Controller Including Scalable Embedded Parallel
`Data Compression and Decompression Engines" and filed
`Jan. 29, I999 (5143-01700).
`
`FIELD OF THE INVENTION
`
`ID
`
`15
`
`invention relates to computer system
`The present
`architectures, and more particularly to a Non-volatile
`"Flash” memory and embedded memory controllers, which
`includes embedded data Decompression andfor Compres-
`sion engines for increased effective memory density and
`improved bandwidth.
`
`DESCRIPTION OF THE RELATED ART
`
`30
`
`35
`
`40
`
`45
`
`50
`
`Non-volatile storage devices such as Ill-‘ROMS {Erasable A-I
`Programmable Read Only Memories), and EEPROMS
`(Electrically Erasable Programmable Read Only Memories)
`have stored computer instruction code and data since their
`introduction. The architecture ofnon-volatile semiconductor
`devices has remained substantially unchanged over recent
`years. Flash memory semiconductors have recently surfaced
`as the more modern non-volatile storage device allowing fast
`in circuit re-programmability. Flash memory devices are
`becoming more popular because of fast read and write
`response,
`low cost and higher density. Still, the cost per
`storage bit of Flash memory exceeds that of volatile DRAM
`(Dynamic Random Access Memory) or SRAM (Static Ran-
`dom Access Memory) devices. Flash memory devices cur-
`rently are sold into two major marketplaces, the “solid-state
`dis '” and "embedded systems” for program and data stor-
`age. Additionally, system on a chip (SOC) shows promise
`for embedded flash memory coupled to embedded MPU,
`(Micro Processor Unit) SRAM, DRAM, and analog circuits
`for execution of programs stored in such non-volitile flash
`memory circuits. While solid—state disks are used widely for
`"rugged” non-mechanical, non-volatile storage and lower
`power, embedded systems use flash memory for program
`and data storage typically for software field upgrades that
`reduce the cost of support and maintenance. Some embed-
`ded flash systems use the XlP{execute in place) architecture.
`Here, the instructions and data are read directly from the
`Flash memory device by the embedded Central Processing
`Unit (CPU) or MPU for direct execution. In prior art, the top
`end frequency of operation was slaved to the bandwidth
`(instruction and data read rate) of the flash memory .sub-
`system. ‘thus, higher speed embedded processors, in order to
`read from the flash directly (XII-‘ model), had to lower their
`clocking rate due to slow read and write timing from the
`Flash Memory Array 100. To avoid low frequency operation
`some systems will copy flash data for execution to DRAM
`or SRAM allowing for faster execution at increased cost due
`to additional subsystem memory devices. The current state
`of the art of Flash memory devices include a central pro-
`cessing unit (CPU) cottpled to optional error correction
`controller (ECC}, Flash Memory Array 100 for storage, and
`charge-pumps for program voltage derivation. Non-
`monolithic Flash memory devices typically comprise two or
`
`.
`
`60
`
`65
`
`27
`
`2
`three devices, such as the Flash Memory Array, the Flash
`controller, and DC to DC converter and supply voltage
`generator. These Flash controllers typically couple to a bus
`interface such as PCMCIA (Personal Computer Memory
`Card International Association),
`ISA (Industry Standard
`Architecture) or a proprietary CPU bus, and also to the Flash
`memory storage array with an address, data, and control bus
`interface. For monolithic or non-monolithic, devices the
`purpose of the Flash memory controller is for orchestration
`of read and write transfers of data between the main CPU
`
`and the memory subsystem. Typically the program running
`on the embedded CPU, in prior art flash memory controller
`circuits.
`includes control
`functions (Sleep, Wake, Seek.
`Compare,
`load and store) for proper Flash memory pro-
`gramming and “wear” balancing. Wear balancing is due to
`the limit of writes that flash can handle before faults begin
`to occur. Thus, for solid-state disks where data is written
`more often, a “wear balancing" program running on the
`embedded CPU will optimally write data to areas that have
`less access, thus prolonging the effective life of the flash
`device.
`
`Certain prior art systems utilize multiple Flash memory
`devices with parallel combined data output pins to gain
`improved memory bandwidth. The multiple Flash devices
`are in many instances included primarily for added
`bandwidth, and when only the added bandwidth is needed,
`additional cost is incurred due to the multiple Itlash memory
`packages required. Additionally, prior art Flash memory
`systems have proven too expensive (cost per hit storage) for
`high density mass market applications and thus have not
`sold in substantial volumes to warrant dramatic cost reduc-
`tions. ‘therefore, a new system and method is desired to
`increase the etfective read bandwidth requirements required
`by the Execute In Place model and the solid state disk
`market for embedded applications and operating system
`software, while reducing the cost per hit of non—volatile
`Flash memory storage, thus establishing a new price per bit
`and read access performance for non-volatile Flash memory
`data and program storage.
`SUMMARY OF TIIIE. INVI_-'.N'I‘ION
`
`The present invention comprises a Flash Memory Con-
`troller with embedded parallel compression andfor decom-
`pression capability, also referred to as the Compression
`Enhanced Flash Memory Controller (CEFMC), which pro-
`vides improved data density, efficiency and bandwidth. To
`enhance the X11’ performance of the CEFMC, the present
`invention uses a decompression engine coupled to an SRAM
`memory bu ll‘er, optionally configured as a data cache which
`is coupled to an interface bus such as the ISA, PCMCIA,
`PCI, Card—Bus or MPU proprietary bus. The memory con-
`troller also couplcs either directly, or through a temporary
`data latch,
`to the Flash Memory Array. In the preferred
`embodiment
`the parallel decompression engine couples
`through a data latch to a wide row of the Flash Memory
`preferably embedded on the same silicon device. The wide
`Flash Memory Array is typically the row-width of the
`normal memory array such as 256 or 512 data bits. This
`array is preferably coupled through a storage latch, which
`preferably allows the next read address to pre—t'etch data
`from the Flash Memory Array prior to completion of the
`decompression stage. Further,
`in one embodiment of the
`present invention, data has been pre—compre.ssed by a soft-
`ware compiler tool prior to the write of such data into the
`Flash Memory Array. Alternatively, for systems that require
`dynamic write capability to the Flash Array, as in tile system
`or solid state disk operation, a compression engine is added
`
`27
`
`

`
`6, '1 45,069
`
`I0
`
`15
`
`30
`
`40
`
`3
`"in-line” with data also preferably located within the Flash
`memory control circuit
`The CEFMC is designed for the reduction of data band-
`width and is located between the main memory andfor
`system memory and the flash memory controller. The
`CEFMC Technology reduces the bandwidth requirements
`while increasing the memory eficiency for almost all data
`types within the computer system. Thus, conventional stan-
`dard Flash Memory cells can achieve higher bandwidth,
`more elfective density, with less system power and noise
`than when used in conventional systems without
`the
`CEFMC technology.
`The CEFMC transfers data between the Flash Memory
`Array and the system MPU and its optional execution and
`data memories. Therefore, the CEFMC technology of the
`present invention typically resides between the MPU, main
`memory and the Flash Memory Array.
`In an alternate
`embodiment,
`the compression andfor decompression
`engines may reside in the MPU memory control unit, thus all
`memory data including flash memory can make use of lower
`pin-out
`interconnect buses, more elfcctive memory
`performance. and increased effective memory density for all
`types of memory coupled to the MPU device.
`The CEFMC technology is designed to embed into prior
`art
`flash memory oontrol circuits. Thus,
`the current
`invention, using the novel parallel architecture to compress A-1
`and decompress data streams. substantially improves band-
`width and ellective storage density within the computing
`system. In addition, the CE-FMC Technology has a “scal-
`able" architecture designed to function in a plurality of
`memory configurations or compression modes with a plu-
`rality of performance requirements as indicated in US.
`patent application Ser. No. 09,239,659 titled “Bandwidth
`Reducing Memory Controller Including Scalable [Embedded
`Parallel Data Compression and Decompression Engines"
`and filed Jan. 29, 1999 (S143-01700). Scalability allows for y
`a non-symmetric compression rate as compared to the
`decompression rate. Write data can match the effective write
`speed of the Flash Memory Array, using fewer input sym-
`bols in parallel during compression,
`thus reducing gate
`count and size. Read data can be decompressed with a
`different number of input symbols per clock or access, thus
`allowing the read data to be decomprcssed at an alternate
`rate. Thus, the non—symmetric nature of the invention during
`reads and writes allows tuning of the memory access time
`vs. gate count to greatly improve performance and cost.
`When configured for “execute in place” (XIP model),
`compressed data is programmed in to the flash memory for
`execution by the system MPU. The CEF-MC invention
`decompresses the data as it is read by the MPU from the
`flash memory. In an alternate embodiment a DMA device
`can also be used to read data in a parallel fashion from the
`flash memory device.
`In the preferred embodiment, data
`presented at the output bus of the Flash Memory system is
`retrieved when the "rcady” output (ready is a control signal
`associated with the MPU and Flash controller interface)
`transitions state during a read data request. The "‘ready"
`output
`indicates that the data has been successfully read
`from the Flash Memory Array and decompressed for con-
`sumption by the MPU. Any form of ready output indication
`can be used, as the "wait" is due to the decompression of a
`new block of data not previously stored in the SRAM buffer
`or cache. Alternatively, the timing specifications can include
`delay time specification indicating a “maximum delay” such
`that the MPU ofsystem device waits for some period of time
`in order to process the decompressed requested data.
`The CEFMC technology allows data to be stored in
`multiple compression formats and blocks sizes, as indicated
`
`50
`
`55
`
`60
`
`65
`
`28
`
`4
`in U.S. patent application Ser. No. 09t'239,659 titled "Band-
`width Reducing Memory Controller
`Including Scalable
`Embedded Parallel Data Compression and Decompression
`Engines”, referenced above. Thus, data can be saved in
`either a normal or compressed format. retrieved from the
`Flash Memory Array for MPU execution in a normal or
`compressed format, or transmitted and stored on a medium
`in a normal or compressed format.
`To improve latency and reduce performance degradations
`normally associated with compression and decompression
`techniques the CIZFMC encompasses multiple novel tech-
`niques such as: 1) Compiler directives for data types and
`block sizes for optimal compression and access speeds; 2)
`parallel
`lossless compressionfdecomprcssion; selectable
`compression modes such as losslcss, tossy or no compres-
`sion; 3) data caching techniques; 4) unique address
`translation, attribute, and address directory structures, as
`illustrated in U.S. patent application Scr. No. 09,239,659,
`referenced above.
`
`The CEFMC Technology preferably includes novel par-
`allcl compression and decompression engines designed to
`process stream data at more than a single byte or symbol
`(character) at one time. These parallel compression and
`decompression engines modify the single stream dictionary
`based {or history table based} data compression method
`described by Lempel and Ziv to provide a scalable, high
`bandwidth compression and decompression operation. The
`parallel compression method examines a plurality of sym-
`bols in parallel, thus providing greatly increased compres-
`sion performance. The CEFMC technology, in an alternate
`embodiment, reduces latency further by use of multiple
`compiler hooks to distinguish program data space from table
`look—up data. Thus, if indicated, a bypass of the decompres-
`sion engine will send data directly to the output interface bus
`without delay. A priority scheme can be applied such that
`compression and decompression operations are suspended
`as higher priority noncompressed data is transferred. Thus,
`reduction of latency and improved elficiency can be
`achieved at the oost of additional parallel bullets and com-
`parison Iogic. Compiler directives interpreted by the decom-
`pression controller, can be embedded within the compiled
`XIP code for notification ol’ compressionldecompression
`bypass.
`In summary, the integrated data compression and decom-
`pression capabilities of the present invention removes sys-
`tem bottlenecks allowing a higher frequency MPU clock by
`de-coupling the Flash Memory access time from MPU clock
`frequency. In addition, the present invention reduces the data
`storage size allowing more storage per Flash Memory Array.
`This lower Cost system is due to reduced data storage
`requirements and improved bandwidth results. This also
`increases system bandwidth and hence increases system
`perfomtance. Thus the compression based Flash Memory
`Controller of the present invention is a significant advance
`over the operation of current memory controllers.
`BRIILF DESCRII-"l'ION OF Tllli DRAWINGS
`
`A better understanding of the present invention can be
`obtained when the following detailed description of the
`preferred embodiment is considered in oonjunction with the
`following drawings, in which:
`FIG. 1 illustrates a typical embodiment for the prior art
`Flash Memory Controller architecture without Compression
`Enhancement for the solid-state disk;
`FIG. 2 illustrates a typical embodiment for the prior art
`Flash Memory Controller without Compression Enhance-
`ment for the execute in place (XIP) model;
`
`28
`
`

`
`6,1 45,069
`
`I0
`
`15
`
`30
`
`5
`FIG. 3 illustrates the Flash Memory Controller with
`embedded parallel Compression and Decompression
`engines;
`FIG. 4 illustrates the embedded parallel Compression and
`Decompression Engines embedded into the MPU for the
`system memory control interface;
`the
`for
`FIG. 5 illustrates the preferred embodiment
`execute in place (XIP) model when only real—time data
`decompression is necessary;
`FIG. 6 is a detailed block diagram illustrating the internal
`architecture of the control logic embedded within the Com-
`pression Enhanced Flash Memory Controller (CEFMC)
`invention;
`FIG. 7 shows the compression block read and write
`process flow for the solid state disk embodiment of the
`Compression Enhanced Flash Memory Controller invention;
`FIG. 8 illustrates the process ilow for Execute In Place
`(XIP) mode cl‘ operation for the Compression Enhanced
`Flash Memory Controller invention;
`FIG. 9 is the process flow diagram for the Compression
`Enhanced Memory Controller {CEMC)
`invention when
`embedded into the MPU as the system memory controller.
`FIG. 1l]A illustrates the sequential compression technique
`of the prior art dictionary-based LZ serial compression “
`algorithm;
`FIG. 10B illustrates the parallel compression algorithm
`according to the present invention;
`FIG. 11 is a high-level flowchart diagram illustrating
`operation of the parallel compression;
`FIG. 12 is a more detailed flowchart diagram illustrating
`operation of the parallel compression;
`FIG. 13 illustrates the entry data history and input data
`compare and results calculation for the parallel compression
`and decompression unit;
`FIG. 14 shows the parallel selection and output generation
`block diagram;
`FIG. 15 shows the operation of the counter values, output
`counter and output mask used for output selection during the
`parallel compression operation of the present invention;
`FIG. 16 illustrates the Output Generator Flow diagram;
`FIG. 1'? illustrates an example of the parallel compression
`operation indicating the data flow through multiple cycles;
`FIG. 18 illustrates a high speed parallel comparison
`circuit used to find the largest count of matching entries to
`the history table;
`FIG. 19 further illustrates the select generation logic and
`entry compare logic designed for high data clocking rates;
`FIG. 20 illustrates the logic table for the high speed
`parallel comparison;
`FIG. 21 is a table illustrating the header information
`presented to the lossless decompression engine;
`FIG. 22 illustrates the four stages used for the parallel
`lossless decompression algorithm;
`FIG. 23 illustrates the eight decoder stages required to
`generate the start counts used for the parallel decompression
`process according to one embodiment of the invention;
`FIG. 24 illustrates a single decoder block used by the
`stage 1 input selector and byte counter of FIG. 22;
`FIG. 25:: is a table indicating the check valid results table
`of the decode block; and
`FIG. 25b is a table describing the Data Generate outputs
`based on the Data Input and the Byte Check Select logic.
`
`35
`
`40
`
`45
`
`50
`
`60
`
`65
`
`6
`DETAII.ED DESCRIPTION OF THE
`PREFERRED EMIiODlMI_-'.NT
`
`Incorporation by Reference
`U.S. patent application Ser. No. {l9,=’239,659 titled "Band-
`width Reducing Memory Controller
`Including Scalable
`Embedded Parallel Data Compression and Decompression
`Engines”, which was filed on Jan. 29, 1999 (5143