l|||||||||l|||||I||||l||l||||l|l||||lIlill||l||lllll||||||||l|||||||||l||||
`
`USUUGGUI 104131
`
`(12) United States Patent
`Fallon
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,601,104 B1
`Jul. 29, 2003
`
`(54)
`
`SYSTICM AND Ml£TH()t)S FOR
`ACCELERATED DATA STORAGE AND
`RETRIEVAL
`
`«
`.
`-I,
`.
`,
`-
`James J. lutllon. Brtmxwtle, NY (US)
`lmentor.
`(73)
`(73) Aqsjgnee: Rmmme [jam ]J[‘C_ New Ymk‘ NY
`[US]
`
`( ‘ ) Notice:
`
`Subject to any disclaimer. the term of this
`patcnt
`is extended or adjusted under 3:?
`U-S-C l54(b) byo days’
`
`(31) AFPL N0-3 0949559394
`22)
`Filed:
`Mar. ll. 1999
`
`('51)
`
`Int. (31.7
`
`(S3) U.S. Cl.
`_
`Fleld of Search ..................................
`References Cited
`
`(56)
`
`G06I" l3;’00
`
`709E231
`
`U-S- PATENT DOCUMENTS
`4,5-H351 A
`3r_.-198,6 Dang N “L
`4f3{_]4:_g5t) A
`3193:; Makamd at at‘
`.-;_'3‘,t‘t:p__.-H5 A
`qglogrg van Maren cl "[1
`4_,%5_.-*:‘.r'5 A
`lrtt'ttt9IrI Hori cl al.
`.'j_.U28_..‘J22 A
`?tl'Nl Huang
`v‘.-"4"".-“37 A
`‘-’H‘-’‘-‘'1 W959 9‘ =l'-
`5=l5”-43“ A
`W1992 Ch"
`5,l59,33t'i A
`l{J!I‘J92 Rabin at al.
`5J?q‘65l A
`MW} Taafle at al_
`fialwflffl A
`SHW3 Miner cl :1],
`5’3_1-31,75 A
`3,1993 Hanna": _h_
`5’g4',t_‘(,33 A
`t;-,r1qg3 0 mien cl 3;‘
`5_;4-,r_.«j,4;, A
`t;,'1r;g3 (},;m]l.nd Qta|‘
`5,28'?,-121'! A
`251994 Barrett
`5,;’t57_.t‘:14 A
`lfIt't9'§I4 Pattisant et al.
`5.-‘i1‘i.~35'[' 4"
`5t'1‘='q5 whiting
`R *
`%°"1°l'
`:'.---‘-.‘--
`J
`ITlL‘il.
`S!S3_m53 A
`.1”IWe Bflkkc at “L
`556L834 A
`lwwqfi Cm_mimctnL
`5:514F.;52 A
`Jlflggfi Brad}, ct BL
`5.574.953 A
`ll."l‘-F96 Rust et at.
`5.S9(.|.3<tt‘i A
`l2,ttUUb Walanahc at at.
`
`37-"34"
`
`21-39? 'Takamoto at at.
`5.fitI_:.‘«_'0b A
`-‘:"["’i'7 Chm
`—iv""1—"v"1-"i A
`-'lt‘t9'.3'.I" Rynderman El 3].
`:t,:'J2l_,82Ct A
`4:'t09't Kim cl al.
`5.623.623 A
`4t't§I'J7 Balrkc el al.
`5.63.70] A
`man? Mm“ N “L
`Srfizmgj A
`5t't9'T.F Mnskowitz not al.
`5.629.732 A "
`31997 C'a‘rrt.-ir‘o ct al.
`if.6.ffJ,l'.|‘f2 A
`'r’ft';ifJT Stitmm et at.
`:-_.{u:w."__,3:«'.«‘ A
`THW7 Mtlllpill 6| 3|-
`5.053.917 A
`T_
`1-
`_d
`__ 1
`_
`L-_l
`1:9 eon mun. on De); page.)
`{
`Prftttrtr}-’ t.'xnmt.'t1er—Davi(l Y. Eng
`(74!) Attorney. Ag:-wt, or }"irm—l"rank V. DeRo5a; I3. Chan
`& A-*it'~*~wi=llt*t*»F~l-1’
`(57)
`
`ABSTRACT
`
`348;’?
`
`Systems and methods for providing accelerated data stttrage
`and retrieval utilizing losstess data compression and (Incom-
`preasion. A data storage accelerator incluctes one or a plu-
`rfllily of
`Spccd data compression cncudurs [hm an;
`contigttrcd to simultaneously or scqu-enttally loseilessly corn-
`press data at a rate equivalent to or faster than the Lranst‘t:It.‘.-‘.-
`sinn rate of an input data stream. The compressed data is
`subetequenlly otored in a target
`lTl(.'tTtC-try or other storage
`device whose lIt]‘tuI data storage hanttwtdth IS lower than the
`original
`input data stream batztclwidth. Similarly,
`it. data
`rctriuvat accelerator includes one ora pluralilyuf high speed
`data clccompressiun decoders that are configurccl to simul-
`tancously or sequentially losslessly decompress data at at rate
`réiiluivalerll to or faster than the input data stream from the
`,
`,
`-
`.
`-
`tgrget memory or Sl‘(j)l'3g|_.]:_it.Vt.f.‘C.'I'i1l‘idC;.’(ll'n§?1fE35l§Cd data It:
`1 L-[] output at rate
`ata 1 at is greater I an I ‘e output rats.
`[rum the target rnemory or data storage device. The data
`storage and_retrtc\t:tl accelerator method and system may
`employed:
`in a disk storage adapter to reduce the Lime
`required to store and retrieve data from computer to disk; in
`conjunction with random access memory to reduce the time
`required to store and retrieve data from random access
`memory; in a display controller to reduce the time required
`.,
`'
`.
`-
`.
`‘
`I
`.
`.
`--
`.
`to [!i:¢LD(l -display: tlttltt to the tltsplayueonlrttllerl twrlprfieehattwrt
`an for in an tnputtotttput Lontro er to ruucu.
`t
`t.
`l1n'lL
`required to store. retrieve. or transmit data.
`
`35 Claims, 20 Drawing Sheets
`
`
`
`Oracld 1006
`
`

`
`US 6,601,104 B1
`Page 2
`
`US. PATENT DOCUMENTS
`
`3:199: Kflcinis.
`5,a55,133 A
`9.r'1tJ9? Moeru el al.
`5,acso;‘-6(r A
`9:199? Saliha
`5,cm,339 A
`l22’l‘)§|7 Korma
`5,694-,(:19 A
`13199? Macflouaid clal.
`5,696,927 A
`211998 Kikinis
`5.715.477 A
`3,1998 Kikmis
`5':_.31',958 A
`3199.23 Kirsten
`5,724,475 A
`maos nemuss ..-1 al.
`5,773,411 A
`'r'_a’l9§I8 Haslfimc-to el al.
`5,187,487 A
`i_.8u3_.6(:.n A v wags Sekinc mu.
`5_,3nug_:7 A
`‘#1998 Hannah el 11!.
`5_.81;’_.78*J A
`am.-93 Diaz.
`5,838,096 A
`IIIIWS de(‘.nrn1o
`5,841,933 A "' IUIDUS Schulhof etul.
`5,847,762 A
`12.«1r.~9s Canfield cl al.
`
`345»;
`
`3€|'5!2tJU.f57
`
`5:3-m,L'|S7 A
`5,3a9_.u:»1 A
`5915 079 A
`5 g36’fim A
`,;‘9m‘4fi A
`'_.‘%8’l"‘;’ A
`;"W4’4n A
`"
`-
`5.'§.l96_fl33 A
`”-“."m=“"" A
`‘5*”°2"‘” “‘
`K’:-.fI11__<J(Jl A
`‘‘*°'‘’'{‘,‘’4 A 3‘
`fim0___,-; A
`‘'’--‘?'23-725 A
`5-'"32’”3 A
`
`31999
`331999
`5,1999
`3”m.;.
`W999
`mflgdg
`mnggg
`JIIWW
`'z"°';'°
`13’W9
`l.f2I]fJ[J
`;"§'3"”"
`J~‘_"-"'-7
`3’2"””
`Mom
`
`Chan
`Dohbclc
`Vondran, Jr. at al.
`Turburg, Jr. r.-I
`‘.21.
`Adam
`Jaqucuc et :11.
`Bell
`Chin -lino
`Brady
`Dye
`Kirsten
`Ahmtmi el al.
`Adilclla
`Blumcnau
`Wilkes
`
`* cited by examiner
`
`395110.71
`
`

`
`MM
`
`m.m
`
`SU
`
`1B401M.
`
`MFMKDOE
`
`.mE.mn_EmaEma
`
`
`1._m>m_.__mw_wmeemmmmcflw
`
`
`m,..__.9m.m._muu<838._o=Em_moo<
`
`M83E
`
`8tadPamU
`
`.mEma59:0
`
`
`
`Emmbwm..w_nm._&mnw_c_
`
`
`

`
`U.S. Patent
`
`.101. 29, 2003
`
`sheet 2 of 20
`
`US 6,601,104 B1
`
`
`Receive lnitiai
`Data Block From
`
`
`
`
`Input Data
`Stream
`
`
`
`Compress Data
`Block with
`
`~ 202
`
`Encoder(s)
`
`Store Data
`
`204
`
`More Data Blocks in
`
`Input Stream ?
`
`No
`
`
`
`Terminate Storage
`Acceleration Process
`
`
`
`208
`
`
`
`
`Receive Next Data
`
`
`
`Block From Input
`Stream
`
`FIGURE 2
`
`

`
`U.S. Patent
`
`.lul. 29, 2003
`
`Sheet 3 of 20
`
`US 6,601,104 B1
`
`
`
`
`
`Retrieve Initial
`
`Data Block
`
`From Storage
`Device
`
`~ 300
`
`Decornpress Data
`Block with
`
`—- 302
`
`Decoder(s)
`
`Output Accelerated
`Data Block
`
`"” 304
`
` More Data Blocks
`For Output Stream ?
`
`NO
`
`Terminate Retrieval
`
`Acceleration Process
`
`
`
`308
`
`
`
`Retrieve Next
`
`Data Block
`
`
`
`
`
`From Storage
`Device
`
`FIGURE 3
`
`

`
`..lH8..l3PamU
`
`Jul. 29, 2003
`
`Sheet 4 of 20
`
`I.06.,6SU
`
`.1B40J,
`
`_
`
`_
`
`_________
`
`
`
`
`
`
`
`
`
`UDUOOCMflhoumUEUOUCMm._O.._.wUmzuoocw0._OuwuouoocmScumUDDOOCNfl._OuWZ
`
`:__8_mEma_...8_mEma....xUO_mSunN..8_m_EmaV._8_m_was”oo.mm_mm__wwm.m.w
`
`,H____
`_H______
`mjI...2 _
`
`
`
`mmEn_EoUmmm.&Eo0mmuaeoommoasou
`
`
`2.5._8_m28m._8_m.23N._8_m.28S_uo_m.28%m_.m..__.._m_..mw.._
`
`umuoocwm..o.w
`
`
`
`3-:..oo_mEND
`
`owuoocm22$
`
`Nxugm£3
`
`.H__________
`
`uouoocmm._Bm
`
`rx8_m£8
`
`uoooucw905
`
`,__8_mMED
`
`3m_m3o_u_
`
`___NHoEEomam:_mm0_
`
`___________
`
`mmm._aEoO_mmmEEoo
`
`m>_momm
`
`wxoo_mman
`
`mzwomm
`
`_.«.85£8
`
`_____.__
`
`m>_mu2...._
`
`v_8_m28
`
`_fldofihufl
`
`__._.H0E._n._._N...“E._
`
`__m>§:_oEP
`
`

`
`..lH8..l3PamU
`
`Jul. 29, 2003
`
`Sheet 5 of 20
`
`I.06.,6SU
`
`1B40J,
`
`_._____
`
`___.._____.__
`
`___._____.___..
`
` |____H:.nwe__:aH“xuo_mBunfl_x8_m2.3,%a_m£8_.ao.m£3_@283.__wozmuam_§_$$_"38oz
`_+___ 32:.
`_._..__c__3...:_3+:_"_xuo_m_Ema“"xuo_mSun.“._oo_m_Ema_v_8_mEma
`_E__9+3H322:.
`.mmmaeoo__mmm._uEoo_mmm._aEoo_...$asoo__flfl"__.|.aims.
`
`_
`
`n+3"
`
`«E.»
`
`_
`
`C
`
`omvoocwQ05
`
`._8_m28
`
`E
`
`mmm.aEoo
`
`.ao_m£8
`
`uuuoucmm._Bw
`
`._8_mEND
`
`ATE
`
` |||_._.__c_"fié_3+:H_62mEma_.,_8_mmac_._8_mEma_._8_mEma
`_._fl____._fie.____25_8sun_._8_mEma_"._8_mman_v_3_mman_.__m_.uououcm22w__umuoocmsew_?...u8cm92m_268cm22w
`..___H_.H._H9-5_H:1.___,_8_m5.3_..8_mmfio__xogm£3.,_uo_mEma_mmoasoo_mmmEEo0H“mmm._aEoU“mmmEEo0____.__ldn'maE:
`_uuuoocm22m"¢uouoocm0.65“u%8_.m_222uacoucmsew
`
`avmanor.
`
`

`
`..lH8..l3PamU
`
`Jul. 29, 2003
`
`Sheet 6 of 20
`
`US 6,601,104 B]
`
`_
`
`__H___HHWPHOHEH
`
`H._._.m_._a HHH___._HHHH:H8Hm23HH.3_8HmuseH38.:2.5HN52:
` __H_____H____H_H_.H8_m23HH:.H8Hm28Hm._8_mmanHN,_..Ho_m23HH..H8_m53H:H8_m:5:
`
`H__H_H__HHHHHH__HHHH_H_.Hoo_mSan__..._uo_m28Ha52mEma_N.HuoHmEma_C_8_m3.3_xoo_mEma
`_H__H_H_H___H_
`HHmmE..._EoomoHHmm2aEoumn_Hmmm._nE8mn_Hmmu.aEoowoHmmo.aEouwn_HmmoEEoumoHHHHHHH“loll:
`Hm>o.c.omHHm>mEmmHm>m.EmmHw>mEmmHm>mEwmHu.§:$H
`:5:_C_8_msun_.H8_mwas
`_8:8353:0__uouoomo59:0_8:885:50_8:835:50_uouoooa5:50_Euoomo5:50
`
`_H__H__H_HHHHH__8-:62:«ac_HN._8Hm£3HSH8_m9.3__H.H8_mmanHumuoumo59:0HHuououom59:0Humuoumo39:0HHHuouoooo53:0
`HHHHHHH__HH__HHH_.-_H.H8Hm3.3HHmH8_m33HN:85sunH_..H8Hm23HH._8Hm33
`HHH__H__HHHH_NoH.:.m_sH
`Hmmo5HEoumn__HmmoaEoomn__mmmaE8wn__mmmaEoumDH_39:58::
`
`mmm_m:oE
`
`
`
`

`
`..lHC..l3PamU
`
`Jul. 29, 2003
`
`Sheet 7 of 20
`
`I.06.,6SU
`
`1B40J,
`
`_HHHHHMn_OI._rm__HH_HH ___H._H_:__fim+aHHe+a_HH.H8_m98HH.H8HmSan.HHH8HmmanH.H8HmEma
`norm: HHHHH_HHH._HH8+;H:.+_HH__«.005SunHHxoo_m_EmaH.HuoHm98H._oo_m«an.HHmH6._=omHH@>m_.aumHu>o_._fimHm>uH__Hmm
`HHHHH__HHH.HH75HH9+:HHHH.H8_mEmaHxuoHmEmaHHxooHm_EmaHxoo_mEmaH.Huo_mEmaHmmmaeouooHmwwHaEoomnHHHmmm.aEouon_HmmEaEaomn_Hmmoasoooo
`
`
`HHBu8oo5330HHHuwuoomo53:0_BeaconS&:OHumusao5930HHHHHH._HHH__HcHHH~+HHHHEHHHH.H8_mEmaHH.H8Hm28H.H8_m.28HHH8Hm93
`HH_HHHHHHHH_H.
`HHmmo.aEooon_HHmm$aEouon_HwmmaEouonHHmmwaEoumnH
`
`
`
`H_HHH
`
`
`
`308859:0Hu%oumoH.aH:oHEB8n:HaH:oHHHH.....HH.ouon_=a=HoH8u8unHHHa_HHoHBuooun=.._H=Ho
`HH_HHHcHH75H3.5HHHH:-_HHxuo_m_EmaHH.H....HoHmEmaHxuoHmEmaHHxuo_mEma_xooHm_EmaHv_ooHmEma
`
`A~+::.H9+5»HEHHAm+_H.H.HHEPHHma2c_mE_H.
`
`8wine:
`
`

`
`U.S. Patent
`
`Jul. 29, 2003
`
`Sheet 8 of 20
`
`US 6,601,104 B1
`
`Receive Initial
`
`Data Block From
`
`Input Data
`Stream
`
`~ 600
`
`B
`
`Time & Count
`Data Block
`
`602
`
`Buffer
`Data Block
`
`"' 504
`
`Compress Data
`Block with
`
`Encoder(s)
`
`~ 606
`
`Time 8. Count
`Data Block
`
`W 608
`
`FIGURE 6a
`
`

`
`U.S. Patent
`
`Jul. 29, 2003
`
`sheet 9 of 20
`
`US 6,601,104 B1
`
`-— 510
`
`Determine
`
`Compression Ratio ~ 612
`and Bandwidths
`
`Store Data
`
`~ 614
`
`
`
`Compression
`Ratio and Input
`Bandwidth
`
`Compatible
`9
`
`
`
`
`Modify:
`Input Bandwidth or
`Compression or
`Buffering
`
`
`
`Receive Next Data
`
`Block From Input
`Stream
`
`
`
`
`More Data Blocks in
`Input Stream ?
`~6m
`
`No
`
`
`
`Terminate Storage
`Acceleration Process
`5
`an
`
`
`
`FIGURE 6b
`
`

`
`U.S. Patent
`
`.101. 29, 2003
`
`Sheet 10 0f 20
`
`US 6,601,104 B1
`
`Retrieve Initial
`
`Data Block
`
`From Storage
`Device
`
`-v 700
`
`B
`
`Time 8. Count
`Data Block
`
`”" 702
`
`Buffer
`Data Block
`
`'“‘ 704
`
`Decompress Data
`Block with
`
`- T06
`
`De-coder(s)
`
`Time 8. Count
`Data Block
`
`N 708
`
`FIGURE 7.3
`
`

`
`U.S. Patent
`
`Jul. 29, 2003
`
`Sheet 11 of 20
`
`US 6,601,104 B1
`
`~ 710
`
` Determine
`Decompression
`Ratio and
`Bandwidths
`
`
`
`-— 712
`
`Output Accelerated
`Data Block
`
`~ 714
`
` Modify:
`Output Bandwidth or
`Decompression or
`Buffering
`
`
`
`Decompression
`Ratio and Output
`Bandwidth
`
`Compatible
`?
`
`Yes
`
`Retrieve Next Data
`Block From
`
`Storage Device
`
`
`
`
`
`
`FIGURE 7b
`
`
`
`
`Yes
`
`More Data Blocks
`for Output Stream ?
`
`~ 720
`
`
`
`
`
`No
`
`Terminate Retrieval
`Acceleration Process
`
`
`
`722
`
`

`
`U.S. Patent
`
`Jul. 29, 2003
`
`sheet 12 of 20
`
`US 6,601,104 B1
`
`._2a_.:uumn..xiEmmhwEmQbwuoocm
`
`
`
`.._o_Etomuo:ou__uaEo0
`
`:BE:oo...._ut=m
`
`mmmaoz
`
`A&oo_>on_muatmE_
`mmfloumEma
`BanA£co_>uo
`
`umfifim.
`
`_.$E:oo..._a__._:m
`
`N._2c:oo:ot:m
`
`
`
`uni.....:o__ac_E._3oo
`
`
`
`
`
`co_mmuEEooozmmco_wmoEEoomBucnoototzmEmflm
`
`pan
`
`
`
`

`
`QMU
`
`05.,6S
`
`1B40J,
`
`1mmmnoz
`
`
`m.3950_noun__m.Emason_M..
`
` .jL__..l....2o._:um@Q=32\3EMQn__e___M...__P.I.I.I.I.I.I.I.I.I.I.I.I.I.I.I.I-
`
`Ucm_I.I.I.IuI.I.E.IuI.I.I.I.I.I.I.II-J_8_"_w1..__PI.u_Eu__m..o_“W1m.montage.
`.Ema
`
`Emmhm__323$
`
`_noLououoo.“£00.30
`
`
`

`
`Jul. 29, 2003
`
`Sheet 14 of 2|!
`
`US 6,601,104 B1
`
`mmm._9m
`
`.2m._m_moo<
`
`Smm:o_.._
`
`33:0Ema
`
` U.S.Patent
`Emmhmoo_u_>
`
`
`3.3%.
`
`

`
`P5U
`
`t
`
`m.
`
`m.MBMU1.
`
`SU
`
`I.B4.01M,
`
`
`
`M,_._.mm_:o_u_
`
`3cm:ow:8:on:9:8M....,,..,..
`
`
`M._o..Em_muu<
`...n_..m_m...w..m__,m._u_IQaommmmzI_a>u_:mm
`..28
`
`
`
`nEmmbmm.23§%_o
`
`
`

`
`U.S. Patent
`
`M
`
`M
`
`h5
`
`PI0
`
`W.
`
`SU
`
`01L,
`
`.1B
`
`MEmw._.wW.59:098
`
`mmg89m..,.
`
`
`.o.mcm.muo<
`
`:23x32FomfiewEmaSac.
`
`.moms
`
`I.DI.
`
`_m._m.mn_
`
`
`
`Ema.9_a_o
`
`_u_.am
`
`Sam_9_m_n_
`
`
`
`Emaatom59:
`
`oumtm_c_x:_2
`
`000
`
`4Smanor.
`
`Mmnfi6,.
`
`tU>.._DOX35
`
`:3I3..
`
`O00
`
`Emamo_m:<
`
`..
`
`
`

`
`U.S. Patent
`
`Jul. 29, 2003
`
`sheet 17 of 20
`
`US 6,601,104 B1
`
`
`Select Initial
`Select lnitial
`.
`.
`.
`
`Analog Data with
`Parallel Digital
`53:‘; "::itt':]l:e:ta'
`Input Analog
`Data with Input
`M
`P
`UX
`
`Mux
`Mux
`
`1312
`
`
`
`
`
`
`
`
`
`Convert Serial
`Data Format
`
`131‘
`
`Latch Parallel
`Digital Input Data
`
`
`
`Agaolflgeig E‘-’g:‘a'
`Signal p
`
` Buffer Serial
`Buffer Parallel
`Digital Data
`
`
`Digital Data
`
`1316
`
`
`
`
`
`
`Buffer Digitized
`Analog Data
`
`
`
`
`Compress Input Data Block
`
`
`Output Encoded
`Data Block
`
`
`FIGURE 13
`
`

`
`Jul 29. 2003
`
`‘K...
`
`Bm..H
`
`
`
`_m._m_o_o__Ean_
`
`man
`
`":'-3
`£-3
`O
`
`wEmaME35_m__om
`
`SU
`
`mL,0
`
`.1B
`
`
`
`am,.3;2.3mm:6,
`
`4E.m_m:o_u_
`
`_m_.om_coEo_2M3.2_.mw_.M_._m_wsun.Io_m_._mw.
`
`
`
`_m>_.n__m
`
`_m>m.Eom
`
`.o.Em_aou<
`
`Ema5%.
`
`Emwbw
`
`Sanmo_m:<
`
`000
`
`mo_m:<2_m._m_n_
`
`tm>:oo
`
` U.S.Patent
`
`
`
`

`
`U.S. Patent
`
`Jul. 29, 2003
`
`sheet 19 of 20
`
`US 6,601,104 B1
`
`
`
`Receive Initial
`Data Block
`
`
`
`"“ 1500
`
`
`
`Decompress Data .-.. 1532
`Block
`
`ata Digiiize
`Analog Data
`
` No
`
`
`ls Data
`
`Digital Parallel
`Data ‘?
`
`~ 1510 YES
`
`Analog Data
`
`Buffer Digitized
`
`Buffer Parallel
`Digital Data
`
`Buffer Serial
`Digital Data
`
`FIGURE 15a
`
`

`
`U.S. Patent
`
`.Iul. 29, 2003
`
`Sheet 20 of 20
`
`US 6,601,104 B1
`
`Digital to Analog
`Convert Data
`
`Demux Digital
`Parallel Data
`
`Output Analog
`Data
`
`Output Parallei
`Digital Data
`
`Output Serial
`
`Yes
`
`Receive Next
`
`Data B|0(‘J'l
`
`FIGURE 15b
`
`

`
`US 6,601,104 B1
`
`1
`SYSTEM AND METHODS FOR
`ACCELERATED DATA STORAGE AND
`RETRI EVA] .
`
`-'.n
`
`2
`pressed data. Simply stated, the deco-ded (or reconstructed)
`data is identical
`to the original unencodcdfuncompresscd
`data. I.ossless data compression is also known as reversible
`or noiseless compression. Thus, lossless data compression
`has. as its current limit, a minimum representation defined
`by the ncgcntropy of a given data mt.
`it is well known within the current an that data. compres-
`sion provides several unique benefits. First, data compres-
`sion crtn reduce the time to transmit data by more efliciently
`utilizing low bandwidth data links. Second, data compres-
`sion cconornizes on data storage and allows more informa-
`tion to be stored for a hired me-mory sire by representing
`information more efliciently.
`One problem with the current art is that existing memory
`storage devices severely limit the perfonnance of consumer.
`entertainment. ollice, workstation, servers, and mainframe
`computers for all disk and memory intensive operations For
`example, magnetic disk mass storage devices currently
`employed in a variety of home, business. and scientific
`computing applications sttflfer from significant seek-time
`access delays along with profound reatllwritc data rate
`limitations. Currently the fastest available { |0,0U0) rpm disk
`drives suppon only a l'z'.1 Megabyte per second data rate
`(MBfsec]. This is in stark contrast to the modern Personal
`Computcr’.=-:. Peripheral Component Interconnect (PCl} l3us's
`inputfoutput capability ol"?.6-1 MB,isec and internal local bus
`capability of B00 Mliisec.
`Another problem within the current art is that emergent
`high performance disk interface standards such as the Small
`Computer Systems Interface [SCSI-3) and Fibre Cltanncl
`olfcr only the promise of higher data transfer rates through
`intermediate data buffering in random access memory. ‘These
`interconnect strategies do not address the fundamental prob-
`lem that all modern magnetic disk storage devices for the
`personal computer marketplace are still limited by the same
`physical media restriction of 17.1 MBI-sec.
`I’aster disk
`access data rates are only achieved by the high cost solution
`of simultaneously accessing multiple disk drives with it
`technique known within the art as data striping.
`Additional problems with bandwidth limitations similarly
`occur within the art by all other forms of sequential, pseudo-
`random, and random access mass storage devices. "Typically
`mass storage devices include magnetic and optical tape,
`. magnetic and optical disks. and various solid-state mass
`storage devices. It should be noted that the present invention
`applies to all forms and manners of memory devices includ-
`ing sturage devices utilizing magnetic, optical, and chemical
`techniques. or any combination thereof.
`SUMMARY OF THE INVENTION
`
`BACKGROUND
`
`1. ’l‘echnical Field
`
`'lhe present invention relates generally to data storage and
`retrieval and, more particularly to systems and methods for
`improving data storage and retrieval bandwidth utilizing
`losslcss data eornprcssion and decompression.
`2. Description of the Related An
`Information may be represented in a variety of manners.
`Discrete information such as text and numbers are easily
`represe-nted in digital data. This type of data representation
`is known as symbolic digital data. Symbolic digital data is
`thus an absolute representation of data such as a letter,
`figure, character, mark, machine code, or drawing.
`Continuous infomtation such as speech, music‘, audio,
`images and video frequently exists in the natural world as
`analog information. As is well-known to those skilled in the
`art, recent advances in very large scale integration {\/LS1)
`digital computer technology have enabled both discrete and
`analog information to be represented with digital data.
`Continuous information represented as digital data is often
`referred to as dilluse data.
`l)iITuse digital data is thus a
`representation of data that is of low in formation density and
`is typically not easily recognizable to humans in its native
`form.
`
`There are many advantages associated with digital data
`representation. For instance, digital data is more readily
`processetl, stored. and transmitted due to its inherently high
`noise immunity. In addition. the inclusion of redundancy in
`digital data representation enables error detection andior
`correction. tirror detection antlior correction capabilities are
`dependent upon the amount and type of data redundancy,
`available error detection and correction processing, and
`extent of data corruption.
`One outcome of digital data representation is the continu-
`ing need for increased capacity in data processing, storage.
`and transmittal. This is especially true for dilfuse data where
`increases in fidelity and resolution create exponentially
`greater quantities of data. Data compression is widely used
`to reduce the amount of data required to process, transmit,
`or store a given quantity of inlhnnation. In general, there are
`two types of data compression techniques that may be
`utilized either separately or jointly to enco-defdecode data:
`lossy and lossless data compression.
`lossy data compression techniques provide for an inexact
`representation of the original uncompressed data such that
`the decoded (or reconstructed) data differs from the original
`uncneodedfuncompresscd data. Lossy data compression is
`also known as ineversible or noisy compression. Negent-
`ropy is defined as the quantity ofinformation in :1 given set
`of data. Thus, one obvious ttdvrtntage of lossy data com-
`pression is that the compression ratios can be larger than that
`dictated by the negentropy limit, all at
`the expense of
`informattion content. Many lossy data compression tech-
`niques seck to exploit various traits within the human senses
`to eliminate otherwise imperceptible data. For example.
`Iossy data compression of visual
`irrtagery might seek to
`delete information content in excess of the display resolution
`or contrast ratio of the target display device.
`On the other hand, lossless data compression techniques
`provide an exact representation of the original uncom-
`
`.10
`
`40
`
`St]
`
`The present invention is directed to systems and methods
`for providing accelerated data storage and retrieval by
`utilizing lossless data compression and decompression. The
`present invention provides an elIc-ctive increase of the data
`storage and retrieval bandwidth of at memory storage device.
`In one aspect of the present invention. a method for provid-
`ing accelerated da ta storage and retrieval comprises the steps
`of:
`
`receiving it data stream at an input data transmission rate
`which is greater than a data storage rate of a target
`storage device:
`compressing the data stream at a compression ratio which
`provides a data compression rate that is greater than the
`data storage rate;
`storing the compressed data stream in the target storage
`device;
`
`55
`
`till
`
`55
`
`

`
`US 6,601,104 B1
`
`3
`retrieving the compressed data stream from the target
`storage device at a. rate equal to a data access rate of the
`target storage device; and
`dccomprcssing the compressed data at a decompression
`ratio to provide an output data stream having an output
`transmission rate which is greater than the data access
`rate of the target storage device.
`In another aspect of the present invent ion, the method for
`providing accelerated data storage and retrieval utilizes a
`compression ratio that is at least equal to the ratio of the
`input data transmission rate to the data storage rate so as to
`provide continuous storage of the input data stream at the
`input data transmission rate.
`ln another aspect of the present invention, the method for
`providing accelerated data storage and retrieval utilizes a
`decompression ratio which is equal to or greater than the
`ratio of the data access rate to at maximum accepted output
`data transmission rate so as to provide a continuous and
`optimal data output transmission rate.
`In another aspect of the present invention the data storage.
`and retrieval accelerator method and system is employed in
`a disk storage adapter to reduce the time required to store
`and retrieve data Erom computer to a disk memory device.
`In another aspect of the present invention the data storage
`and retrieval accelerator method and system is employed in
`conjunction with random access memory to reduce the time
`required to store and retrieve data from random access
`memory.
`In another aspect of the present invention a data storage
`and retrieval accelerator method and system is employed in
`a video data storage system to reduce the time required to
`store digital video data.
`In another aspect of the present invention the data storage
`and retrieval accelerator method and system is employed in
`a display controller to reduce the time required to send
`display data to the display controller or processor.
`In another aspect of the present invention the data storage
`and retrieval accelerator method and system is employed in
`an inptttloutput controller to reduce the time required to
`store. retrieve, or transmit data various forms of data.
`The present invention is l't1£lIl.?'£(_l due to recent improve-
`ments in processing speed, inclusive ofdcdicatcd analog and
`digital hardware circuits. central processing units. digital
`signal processors, dedicated linitc state machines (and any
`hyhrid combinations thereof). that. coupled with advanced
`data compression and decompression algorithms, are
`enabling of ultra high hanrlwidth data compression and
`decompression methods that enable improved data storage
`and retrieval bandwidth.
`These and other aspects, features and advantages, of the
`present invention will become apparent from the following
`detailed description of preferred ernhodiments, that is to he
`read in connect ion with the accompanying drawings.
`
`BRlI_7.I"' DliSC‘RIP'I'ION OF THE. DRAWINGS
`
`FIG. 1 is a block diagram of at system for accelerated data
`storage and retrieval according to one embodiment of the
`present invention;
`FIG. 2 is a How diagram ofa method l'or accelerated data
`storage in accordance with one aspect of the present inven-
`tion;
`FIG. 3 is a How diagram of a method for acct:-lcralcd data
`retrieval
`in accordance with one aspect of the present
`invention;
`FIGS. 40 and -lb are timing diagrams of methods for
`accelerated data storage according to the present invention;
`
`.10
`
`30
`
`40
`
`SU
`
`till
`
`65
`
`4
`
`FIGS. Sn and 5b are liming diagrams of methods for
`accelerated data retrieval according to the present invention:
`FIGS. on and 6b com prise a llow diagram of a method for
`accelerated data storage in accordance with a further aspect
`of the present invention;
`FIGS. 7n and 71: comprise a flow diagram of a method for
`accelerated data retrieval in accordance with a further aspect
`of the present invention;
`FIG. 8 is a detailed block. diagram of a system for
`accelerated data storage act.'ot'(ling to a preferred embodi-
`ment of the present invention;
`FIG. 9 is a detailed block diagram of a system for
`accelerated data retrieval according to a preferred embodi-
`ment of the present invention;
`FIG. 10 is a block tliagrarn of a system for accelerated
`video storage according to one c-rnbodirnent of the present
`invention:
`FIG. 11 is a block diagram 01'' a system for accelerated
`retrieval of video data according to one embodiment of the
`present invention;
`FIG. I2 is a block diagram of an inputtoutput controller
`system for accelerated storage of analog, digital, and serial
`data according to one embodiment oftlic present invention;
`FIG. 13 is a flow diagram of a method for accelerated
`storage of analog, digital, and serial data according to one
`aspect of the present invention;
`FIG. 14 is a block diagram of an inputtoutput system for
`accelerated retrieval of analog, digital, and serial data
`according to one embodiment of the present invention; and
`FIGS. 15:? and 15!: comprise a how diagram of method
`for accelerated retrieval of analog, digital, and serial data
`according to one aspect of the present invention.
`Dl_"’l'AIl_ED DlLS(?RIl"l‘lGN OI? PREFERRED
`EM.BODIMEl'*«lTS
`
`The present invention is directed to systems and methods
`for providing improved data storage and retrieval handwidth
`utilizing lossless data compremion and decompression. In
`the following description, it is to be understood that system
`elements having equivalent or similar functionality are des-
`ignated with the same retercnce numerals in the Figures. It
`is to be further understood that the present invention may be
`implemented in various forms of hardware. software,
`firmware. or a combination thereof. Preferably, the present
`invention is implemented on a computer platform including
`hardware such as one or more central processing units
`(CPU) or digital signal processors IIDSP), a random access
`memory (RAM), and l!]ptl1,"0tt1]‘tttl (U0) interfacets}. The
`computer platform may also include an operating system.
`microinstruction code, and dedicated processing hardware
`utilizing combinatorial
`logic or finite state machines. The
`various processes and functions described herein may be
`either part 01' the hardware, microinstruction code or appli-
`cation programs that art: cxccutctl via the operating system.
`or any combination thereof.
`It is to he further understood that, because some of the
`constituent syste-m components described herein are prefer-
`ahly implemented as software modules, the actual system
`connections shown in the Figures may ditfcr depending
`upon the manner in that the systems are programmed. It is
`to be appreciated that special purpose microprocessors,
`digital signal processors, dedicatctl Iztardware, or and com-
`bination thereof may be employed to implement the present
`invention. Given the teachings herein, one of ordinary skill
`in the related art will be able to contemplate these and
`similar implementations or cortligurations of the present
`invention.
`
`

`
`US 6,601,104 B1
`
`10
`
`EU
`
`Jl
`
`5
`:1 block diagram illustrates a
`Rcl"crring now to FIG. 1,
`system for accelerated data storage and retrieval
`in accor-
`dance with an crnbodimcnt of the present invention. The
`system includes tt data storage accelerator 10, operatively
`coupled to a data storage device 45. The data storage 5
`accelerator operates to increase the eliective data storage
`rate of the data storage device 45. It is to be appreciated that
`the data storage device 45 may be any fonn of memory
`device including all fomis of sequential, pseudo-random,
`and random access storage devices. The memory storage
`device 45 may he volatile or non-volatile in nature, or any
`cornbination thereof. Storage devices as known within the
`current an include all forms of random access memory,
`magnetic and optical tape. rttagrietie and optical disks, along
`with various other fonns ol'solid—state mass storage devices.
`Thus it should be noted that the current invention applies to
`all forms and manners of memory devices including, but not
`limited to, storage devices utilizing magnetic, optical, and
`clieniical techniques. or any combination thereof.
`The data storage accelerator ll] receives and processes
`data blocks from an input data stream. The data blocks may
`range in size from individual bits through complete files or
`collections of multiple files, and the data block size may be
`fixed or variable. In order to achieve continuous data storage
`acceleration, the data storage accelerator 10 must be con~ .
`figured to compress it given input data block at a rate that is
`equal to or faster than receipt of the input data.
`'lt1us, to
`achieve optimum throughput, the rate that data blocks from
`the input data stream may be accepted by the data storage
`accelerator 10 is a function of the size of each input data
`block, the compression ratio achieved, and the bandwidth of
`the target storage device. For example, if the data storage
`device 45 (c.g., a typical
`target mass storage device] is
`capable of storing 20 megabytes per second and the data
`storage accelerator III is capable of providing an average
`compression ratio of 3: l . then 60 megabytes per second may
`he accepted as input and the data storage acceleration is
`precisely 3:], equivalent to the average compression ratio.
`lt should be noted that
`it
`is not a requirement of the
`present invention to configure the storage accelerator 10 to
`compress it given input data block at a rate that is equal to
`or faster than receipt of the input data. Indeed, if the storage
`accelerator 10 compresses data at a rate that is less than the
`input data rate. butlering may be applied to accept data from
`the input data stream for subsequent compression.
`Additionally, it is not a requirement that the data storage
`accelerator 10 utilize data compression with :1 ratio that is at
`least the ratio ol’ the input data stream to the data storage
`access rate ol‘ the data storage device 45. Indeed, if the
`cornprcssion ratio is less than this ratio. the input data stream
`may be periodically halted to effectively reduce the rate of
`the input data stream. Alternatively, the input data stream or
`the output of the data accelerator 10 may be buffered to
`temporarily accommodate the mismatch in data bandwidth.
`An additional alternative is to reduce the input data rate to
`rate that is equal to or slower than the ratio of the input data
`rate to the data storage device access rate by signaling the
`data input source and requesting a slower data input rate, if
`possible.
`Referring again to FIG. 1, a data retrieval accelerator 80
`is operative ly connected to and receives data from the data
`storage device 45. 111:: data retrieval accelerator SI] receives
`and processes compressed data from data storage device 45
`in data blocks that may range in size from individual bits
`through complete tiles or collections of multiple files.
`Additionally,
`the input data block size may be lixed or
`variable. The data retrieval accelerator 80 is configured to
`
`4-D
`
`fill
`
`55
`
`6|’!
`
`55
`
`6
`decompress each compressed data block which is received
`from the data storage device 45. In order to achieve con-
`tinuous accelerated data retrieval. the data retrieval accel-
`erator tnust decompress H given input data block at a rate that
`is equal to or faster than receipt of the input data.
`In a manner analogous to the data storage accelerator lfl,
`achieving optimum throughput with the data retrieval accel-
`erator R0 is a function of the rate that compressed data
`blocks are retrieved from the data storage device 45, the
`of each data block, the decompression ratio achieved, and
`the limitation on the bandwidth oithc output data strcant, if
`any. For example, if the data storage device 45 is capable of
`continuously supplying 20 megabytes per second and the
`data retrieval accelerator 80 is capable of providing an
`average decompression ratio of 1:3, then a 60 megabytes per
`second output data stream is achieved, and the correspond-
`ing data retrieval acceleration is precisely 1:3, equivalent to
`the average decompression ratio.
`It is to be understood that it is not required that the data
`retrieval accelerator 8|] utilize data decompression with a
`ratio that is at most equal to the ratio of the retrieval rate of
`the data storage device 45 to the maximum rate data output
`stream. lndecrl. ifthe decompression ratio is greater than this
`ratio, retrieving data from the data storage device may be
`periodically halted to eflcctivel y reduce the rate of the output
`data stream to he at or below its maximum. Alternatively, the
`compressed data retrieved from the data storage device 45 or
`the output of the data dccotrtpressor may be buliererl
`to
`temporarily accommodate the mismatch in data bandwidth.
`An additional alternative is to increase the output data rate
`by signaling or otherwise requesting the data output device
`(5.) receiving the output data stream to accept a higher
`bandwidth. if possible.
`Referring now to FIG. 2, a [low diagram of a method for
`accelerated data storage according to one aspect ol‘ the
`present invention illustrates th