l|||||||||[|||||l||||l|||||||l|l||||lIlill||l||lllll||||||||1|||||||||l||||
`
`USUUGGUI 104131
`
`(12) United States Patent
`Fallon
`
`(in) Patent No.:
`(45) Date of Patent:
`
`US 6,601,104 B1
`Jul. 29, 2003
`
`(54)
`
`SYSTICM AND Ml£TH()l)S FOR
`ACCELERATED DATA STORAGE AND
`RETRIEVAL
`
`«
`.
`-I,
`.
`,
`-
`James J. lutllon. Brtmxwllc, NY (US)
`lmentor.
`(73)
`(73) Aqsjgnee: Rmmme [jam ]J[‘C_ New Ymk‘ NY
`[US]
`
`( ‘ ) Notice:
`
`Subject to any disclaimer. the term of this
`palcnt
`is extended or adjusted under 3:?
`U-S-C l54(b) byo days’
`
`(31) AFPL N0-3 0949559394
`22)
`Filed:
`Mar. 11. 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 al‘
`.1,_'3‘,t‘[p__.-H5 A
`qglogcg van Maren cl "[1
`4_,%5_.-*:‘.r'5 A
`lrIt'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',I'_‘(,33 A
`t;-,r1qg3 0 mien e, at
`5_;4-,r_.«j,4;, A
`t;,'1r;g3 (},;m]l.nd Qta|‘
`5,28'?,-121'! A
`251994 Barrett
`5,;i57_.I‘:14 A
`lfIt't9'§I4 Pattisant at 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 ul.
`5.S9(.|.3<ifi A
`l2,tlUUb Walanahc at at.
`
`37-"34"
`
`21-39? 'I‘aka_.mntn el al.
`5.fitI_:.‘«_'0b A
`-“"07 Chm
`—iv""1—"v"1-"i A
`-'lt‘t9'.3'.I" Rynderman el 3].
`:t,:'J2l_,82i'] A
`43109’? 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';".F Muskowitz ct al.
`5.629.732 A "
`31997 C'a‘rrt.-ir‘u cl al.
`if.6.ffJ,l'.|‘f2 A
`'r’ft';ifJTr’ Shtmm at al.
`:-_.{u:w."__,3:«'.«‘ A
`THW7 Mtlllpill 6| 3|-
`5.053.917 A
`T_
`1-
`_d
`__ 1
`_
`L-_l
`1:9 eon mun. on near page.)
`{
`Prftttrtr}-’ t.'xnmt.'t1er—Davi(l Y. Eng
`(74!) Atmrney. 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 losstcss data compression and (Incom-
`preseion. A data storage accelerator incluclcs one or a plu-
`rfllily of
`Spccd data compression cncudurs [hm an;
`cnnligttrcd to simultaneously or scqu-enttally lnsetlessly corn-
`pruss data at a rate Eql.ll\-"ll.1L'-Ell to nr faster than the LI‘ltl]Sl‘l]l.‘:‘u-
`sinn rate of an input data stream. The cnmpressed data is
`subetequenlly attired in a target mcrrtc-try or other storage
`device whose lI1]‘tuI data storage handwtdt I) Is lower than the
`original
`input data stream batztclwidth. Similarly, a data
`retrieval accelerator includes one nra pluralilyuf high speed
`data clccnmpressiun deenders that are ccnligurecl to simul-
`tancously or sequentially losslessly decompress data at at rate
`réiiluivalenl to or faster than the input data stream from the
`,
`,
`-
`.
`-
`tgrgct memory nr Sl‘(j)l'il.gl_.]:_it.\’t.f.‘C.Ti1l‘idCk:.'0rn!?1fE35l‘§Cd data It:
`1 L-[] output at rate
`ata 1 at is greater I an I
`‘la nutptll rats.
`[rum the target rnemory or data storage device. The data
`storage and_ru1rIc\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 rncmnry to reduce the time
`required tn store and retrieve data from random access
`memory; in a display controller to reduce the time required
`.,
`'
`.
`-
`.
`‘
`I
`.
`.
`--
`.
`lD[!15t.D(l -LllS‘pld}: tlttltt to the tltsplayueonlrtrllerl twrlprfieehettwrt
`an for in an tnputtotltput Lnntro er to recucu.
`t
`t.
`l1n'lL
`required to store. retrieve. or transmit data.
`
`35 Claims, 20 Drawing Sheets
`
`
`
`Oradle 1 108
`Oracle 1108
`
`

`
`US 6,601,104 B1
`Page 2
`
`US. PATENT DOCUMENTS
`
`3-‘I997 Kfl“'J"“*
`5»555»13”3 A
`971997 Moeru el al.
`5,a3o_53n A
`971997 Saliha
`5,371,339 A
`l22’l‘)§|7 Korma
`5,694-,(1l9 A
`1271997 Macflouaid m1.
`5,393,927 A
`271993 Kikinis
`5.7-15.477 A
`3,1998 Kikmis
`5'!.’_.21"958 A
`371993 Kirsten
`3,724,475 A
`771993 I):-Mnzuss 1-1a|.
`5.773.411 A
`7.71993 Ha-sl1imc-to 31111.
`5.737437 A
`9.11998 Sekim: etnl.
`5,313,631 A 1*
`W998 Hannah El at
`sfimfifl A
`971993 Diaz:
`5,312,739 A
`“NW8 decmmo
`53333396 A
`5,341,979 A r 1171993 schuumr at 111.
`5,8«1‘I-‘J62 A
`1211998 Canfield at al.
`
`3-4313
`
`39-572119.37
`
`5:3-m,L'|S'7' A
`5,339,931 A
`5,915 979 A
`’
`E
`"_.‘%8’l"‘§ A
`:9 43* 1
`" 7 ' 7
`“‘
`5.'§.I9fi_fl33 A
`”-m°=“"“‘ A
`‘5’”“3"“1 “‘
`51011-90‘ A
`'5+°""*f‘_"4 A ,
`o,02o_...17 A
`‘’--‘?'33-725 A
`fi_.(I32,l43 A
`
`211999 Chan
`371999 Dohbck
`311999 Vnndmn Jr. 1-.131.
`.
`’
`,
`,
`31333 Igmg‘ 1"" “I”
`“M909 J3 Hem: elm
`'1
`‘
`1”’ “'99 3”.‘
`]l!1§l9l'.I Clnu-[inn
`'z"°'3’° B"““5'
`13’“"°° 53'”
`“,3[’“[’
`I‘"""”'.
`‘°"‘t"°"”“’1‘
`_r-0t:n.f1 Ad1h:Ila
`323?’ 3'?‘"‘°""“
`2.32
`I] Wxlkes
`
`‘ cited by examiner
`
`1 _..J
`.957_t1o.77
`
`

`
`MM
`
`m..m
`
`SU
`
`1B401M.
`
`MFmmnoz
`
`M83E
`
`EmaEma1._m>m_.__mm_mmeemmmmcflmmE.mn_
`
`
`
`
`
`m,...9m._m._muo<838._2Em_moo<
`
`8tonPamU
`
`.mEma53:0
`
`
`
`Emmfiwm.~w_nm._o«mnw_c_
`
`
`

`
`U.S. Patent
`
`Jul. 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
`-210
`
`
`
`Block From Input
`Stream
`
`FIGURE 2
`
`

`
`U.S. Patent
`
`Jul. 29, 2003
`
`Sheet 3 of 20
`
`US 6,601,104 B1
`
`
`
`
`
`Retrieve Initial
`
`Data Block
`
`From Storage
`Device
`
`-— 300
`
`Decompress 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
`
`

`
`..lHC..laPamU
`
`Jul. 29, 2003
`
`Sheet 4 of 20
`
`I.06.,6SU
`
`1B40J,
`
`.______________
`
`__._."“E._n._._m..._E._
`
`_
`
`________________
`
`N%o_mman
`
`mzwoom
`
`_.«.85£8
`
`m>_mum~.._
`
`v_8_m28
`
`____H_.DGIHME
`_.________________m>_3mm"__.__maoE_oEF
`
`__.___v_8_mEma_fiemEND_vx8_mEma_n..8_mEmaN._8.mwan.rxoo_mEma
`
`
`
`mmoEEoo_mmm.aEoo_mmmEEoommm:nEoommE_uEoUmmm.aEoo
`
`:__8_m£8
`
`_
`
`umuoocm99w
`__.____H
`uououcmm._Q.w
`
`w..8_mEND
`
`umuoocm9.9%
`mxuo_m£8
`
`
`
`umuoocmScum
`
`m..8_m_Ema
`
`
`
`umuoocmScum
`
`r._8_m_was
`
`omuoucm22w
`
`._8_m.28
`
`__
`
`umuoucwm..o.w
`
`
`
`3-:._oo_mEND
`
`owuoocm93$
`
`Nxugmsun.
`
`umuoocmBaum
`
`rfio_m£8
`
`9.m_m.._o_u_
`
`
`
`
`amazonmmm.6Eo0mmuaeoommen_Eou
`
`
`
`2.:._8_m23m._8_m.23N62m.28S_uo_m.28.mw_m_n..m_
`..2_.___________.__.____________+......_______
`
`mjI...2
`
`uoooucwEouw
`
`,__8_mEND
`
`

`
`..lH8..l3PSU
`
`Jul. 29, 2003
`
`Sheet 5 of 20
`
`I.06.,6SU
`
`IB40J,
`
`_.___H_
`
`___.H_____.__
`
`__.___._
`
`___
`
`H._8_m28
`_3.85esm
`uuuoocmm._Bw
`
`._8_mEma
`
`c
`
`2-5
`
`E
`
`mmmEEoo
`
`.ao_m.28
`
`_HH__ _E__9+3H_mz2c_mE:r
`_____H:HHfix.H3+:H_xugmsun__x8_m.23,5o_m£8_._uo.m.28H.m>_momm_HHozmuamHmzmummHmzmowm
`
`n+3H
`
`_H__.__c__3+;H:+_.HH62mEmaHH,_8_mmac_fio_m.23.._3_mman
`_._H__c__8+;_3+;__H._8_m38HHxuo.mEmaH._oo_mEmaHv_8_mEma
`__.________nlran».2
`.mmmaeoo._mmm._uEoo_mmm.aEoo_aaasoo
`
`
`__oououcmEflwHHuovoocm...u.._2mHuouoocm29mHuauoucm29w
`
`awmm30_n_
`
`.___.___H__H____H__H___._________H.____H_H_
`
`
`
`mmmaeoommm._aEoummmacboH
`
`._8_mmfio._8_mEma,_8_mmanH.%..w_.mn__..m.mnn._
`9-5:1.__
`
`__ldn'moE:
`
`uououcm32wumuoocm22wumuoocm92mHuououcwm._2w
`8.5_2.;H._8_m23._8_mmanx8_mman_._u2msun
`
`_..
`
`_
`
`

`
`ndPamU
`
`..lHC..l
`
`Jul. 29, 2003
`
`Sheet 6 of 20
`
`US 6,601,104 B1
`
`__H____HWPHEHEH
`
`IE2 HH__H_.__H_H_.H8_m23H_H;_8_muse.N._8_m2.5_N,_8_m£3_C_8_msun_.H8_mwas
` __H_____HH___H_H_..8_m28HHVx8_m98HN._8_m.23HN,_8_m23HH.._8_m53H,_8_m2.3
`
`H__H_H__HHHHHHHHHHH__._8_mSan__v._uo_m23_m185Ema_N..uoHmmac_C_8_m3.3_xoo_mEmaHmmE..._EoomoHHmmoEEoomn_Hmmm._nEoomn_Hmmu.aEoowoHmmm.aEouwn_HmmmEEouaoHHHHHHHnlollo
`_H__H_H__H_HH_
`Hm>u.cHmmHHm>oEa¢Hm>m.EmmHw>mEmmHm>m_._EmHufisam
`_umuoumo53:0__Buoomo59:0_8_u8ooH350__.%8on_5930_BuoomoS930_uwuoooo59:0
`
`__..HHHHH__HH__HHH_.-_H..8_mmamHHNv_3_mmanHNH8593H_..H8_m93HH._8_m23
`_H__H___H_H__HH__H___HN-_H
`HHH__H____H__No.._._.m_s_
`62mEma__N._o2mE3_SH8_m3.3___.Huo_mEmaHuwuoooo59:0HHHumuouom59:0Humuouoo3930HHHuouoooo53:0
`Hmmoieouoo_Hmmo:HEoomn__mmmaEoown__mmmaEouonHH_m$aE8on_
`
`mmm_m:o_“_
`
`
`

`
`..lH8..l3PamU
`
`Jul. 29, 2003
`
`Sheet 7 of 20
`
`I.06.,6SU
`
`IB40J,
`
`_________Moozpmz ___H.___:__fim+a_He+a_HH,_8_mEmaHH._8_mSan.Hx8_mmanH._8_mEma
`._____._______.norm: ______HHcHH3+;H:.+uH__v_oO_mmama_Hxoo_mEND_xuo_mEND_xoo_mENDHHo>m.5omHHw>m_.aumH9.65amHm..a___.mm
`_.HHHH__.HcH:-5HH2+;H_H_._8_mmacHxuo_mEma__xoo_m_Ema_xoo_mEma_._8_msun
`
`..358853:0__uwuoumo53:0_38085930.Enema59:0._H__._HH_____._._8+:H2+;_HH..8_m58HH._8_msun.H._8_msun.Hxosm«.8
`_mmuaeouooHmw9nEoomn_H_mmm.aEouon__mm2aEcomn_Hmmoasouoo
`__mma.aEooon___mmEqEouon__wmmaEoumo_mmEaEoumn_
`
`H_H__
`
`
`
`
`umo8an_5310H_umuoumn_5&_._OHuonoomnzzafioHHumuouonzafisoHuwuoumnzznfioHuouoomn53:0
`_.___HcH.75H3.5HH_H:._HHxuo_m_Ema_xuo_mEma_xuofiEmaH_xuo_mEma_xoo_mEma_v_oo_mEma
`
`pmmmaoz
`
`
`
`5...:H:3:HEHHAw+_H._.HHE:H_aa2.__E:
`
`

`
`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
`
`-- 610
`
`Determine
`
`Compression Ratio ~ 612
`and Bandwidths
`
`Store Data
`
`~ 514
`
`
`
`Compression
`Ratio and input
`Bandwidth
`
`Compatible
`9
`
`
`
`
`Modify:
`Input Bandwidth Dr
`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
`
`Jul. 29, 2003
`
`Sheet 10 of 20
`
`US 6,601,104 B1
`
`Retrieve Initial
`
`Data Block
`
`From Storage
`Device
`
`~ 700
`
`Time 8- Count
`Data Block
`
`"‘ 702
`
`
`
`
`
`
`De-coder(s)
`
`Time & Count
`Data Block
`
`N 708
`
`FIGURE 7.3
`
`Decompress Data
`Block with
`
`

`
`U.S. Patent
`
`Jul. 29, 2003
`
`Sheet 11 of 2.0
`
`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 211
`
`US 6,601,104 B1
`
`
`
`._2a_.:ummn..xiEmm.____mEmabwnoocm.
`
`
`
`.._o_Etomuo:ou__maEo0
`
`:.£::oo.:ut=m
`
`mmmaoz
`
`mmfloumA£oo_>uo
`
`
`.Ema
`
`Baaumfifim.
`
`H3oo_>on_
`
`mu.atmE_
`
`_.Eucnootatzm
`
`N._2c:oo:ot:m
`
`
`
`2;.....:o__ac_E_3oo
`
`
`
`
`
`:o_mmuEEooozmmco_wmoEEo0mBucnoototzmEmflm
`
`Ego.
`
`
`
`
`

`
`amU
`
`05,6S
`
`1B40J,
`
`1mmN_D0_n_
`
`
`m.3950_Novn__m.Emason_M..
`
` .jL__..I......2n.._:um@Q=32\EE3n__E___M...__PII!IIIIIIIII1IIIIIOIlII!IIIIOIIII
`
`Ucmi||IaIIIUIIIIIoIII|IIIII1IIIOIIallIJ_8_"_m2__PI.u_Eu__m..o_“W1m.montage.
`.Ema
`
`Emohm__unflouw
`
`_noLououoo.n£uo_>o.u
`
`
`

`
`Jul. 29, 2003
`
`Sheet 14 of 2|!
`
`US 6,601,104 B1
`
`mmm._9m
`
`8fi._m_moo<
`
`Smmzom
`
`33:0Ema
`
` U.S.Patent
`Emmhm32>
`
`
`3.3%.
`
`

`
`Jul. 29, 2003
`
`Sheet 15 of 20
`
`US 6,601,104 B1
`
`on:03...8:ONE.05;.8..¢¢¢,..
`
`
`
`.m=mE._on_boEm__2I_§%_n_S330
`
`END
`
`_m>m.5.....w_
`
`_Bm.m_muu<
`
`
`
`_._.m_«=._o_u_
`
` U.S.Patent
`
`£3.§%_o
`
`Emmbm
`
`
`
`

`
`U
`
`t
`
`M
`
`h
`
`0
`
`SU
`
`011.‘.
`
`.1B
`
`..m_£_a_oImPm_.ESEmao_m<
`%t....>.._ooo
`
`.95.mos.
`
`mmm?89m..,.
`..,.I.o.mE.muo<x:oI%%MMI:3.M
`MEmwamIm,.59:098£3§_m_oM_m._mam
`
`oumtw_c_x:_2cSunatomSq:_n0use_S_m_n_H_~_am
`
`,..
`
`
`
`4N_.mm_:o_n_
`
`6,.
`
`mmmmfi
`
`
`

`
`U.S. Patent
`
`Jul. 29, 211113
`
`sheet 17 of 211
`
`US 6,601,104 B1
`
`
`Select Initial
`Select lnitial
`.
`.
`.
`
`Analog Data with
`Parallel Digital
`53:: ";:;tt':]l?:ta'
`Input Analog
`Data with Input
`M
`P
`UX
`
`Mux
`Mux
`
`1312
`
`
`
`
`
`
`
`
`
`Latch Parallel
`Digital Input Data
`
`Convert Serial
`Data Format
`
`
`131‘
`
`
`
`Agifigeig g'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
`
`Q...
`
`Bmufl
`
`
`
`_m._m_o_o__Ean_
`
`man
`
`":'-3
`E-3
`0
`
`
`
`mEmaM§_2o_m__om
`
`SU
`
`m1.‘.0
`
`.1B
`
`6.,mg:9.1mm:5,
`
`4E.manor.
`
`
`
`_m>_.n_.m
`
`_m__om_coEoEM3.2_..mm_.M._._,..”._m33Io_m_._mw.
`
`_m>m.Eom
`
`.o.Em_auu<
`
`Ema5%.
`
`Emmbw
`
`Sanmo_m:<
`
`O00
`
`mo_m:<2_m._m_n_
`
`tm>:oo
`
` U.S.Patent
`
`
`
`
`

`
`U.S. Patent
`
`Jul. 29, 2003
`
`Sheet 19 of 211
`
`US 6,601,104 B1
`
`
`
`Receive Initial
`Data Block
`
`"‘ 1500
`
`
`
`Decompress Data .-.. 1532
`Block
`
`ata Digitize
`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
`
`Jul. 29, 2003
`
`Sheet 20 of 20
`
`US 6,601,104 B1
`
`Digital to Analog
`Convert Data
`
`Demux Digital
`Parallel Data
`
`Output Analog
`Data
`
`Oulput Parallel
`Digital Data
`
`Output Serial
`
`Yes
`
`Receive Next
`
`Data Block
`
`FIGURE 15b
`
`

`
`US 6.6il1_.l04 B1
`
`1
`SYSTEM AND METHODS FOR
`ACCIIZLERATED DATA STORAGE AND
`RETRI EVA] .
`
`BACKGROUND
`
`1. Technical Field
`
`The present invention relates generally to data storage and
`retrieval and, more particularly to systems and methods for
`improving data storage and retrieval bandwidth utilizing
`Iosslcss data compression and decompression.
`2. Description of the Related An
`Information may be represented in it variety of manners.
`Discrete inforntation such as text and numbers are easily
`represented 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 information 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 reprcsenterl as digital data is often
`referred to as dilluse data. Ditfuse digital data is thus a
`representation of data that is of low information density and
`is typically not easily recognizalile 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 ofrcdttndancy in
`digital data representation enables error detection andror
`correction. Error detection andior 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 dilluse 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 inlbnnatiort. In general, there are
`two types of data compression techniques that may be
`utilized either separately or jointly to enco-deidecode data:
`Iossy and losslcss data compression.
`lios-sy data compression techniques provide for an inexact
`representation of the original uncompressed data such that
`the decoded (or reconstructc.-cl) data dilfers from the original
`uncncodedruncompresscd data. Lossy data compression is
`also known as in'evers1"hle or noisy oompression. Negent-
`ropy is defined as the quantity ofinformation in a given set
`of data. Thus, one obvious advantage. of tossy data com-
`pression is that the compression ratios can be larger than that
`dictated by the negentropy limit, all at
`the expense of
`information content. Many lossy data compression tech-
`niques seek to exploit various traits within the human senses
`to eliminate otherwise imperceptible data. For example.
`Iossy data compression of visual
`irnagery 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
`
`10
`
`J
`
`Ian
`
`40
`
`St]
`
`55
`
`Evil
`
`55
`
`2
`pressed data. Simply stated, the decoded (or reconstructed)
`data is identical
`to the original uncncodcdfuncompressed
`data. I.ossle.~:s data compression is also known as reversible
`or noiseless compression. Thus, losslcss 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 art that data. compres-
`sion provides several unique benefiLs. First, data compres-
`sion can reduce the time to transmit data by more elliciently
`utilizing low bandwidth data links. Second, data compres-
`sion econontizes on data storage and allows more inf'orrna-
`[ion to be stored for a liired memory sire by representing
`information more efficiently.
`One problem with the current art is that existing memory
`storage devices severely limit the pcrforrnance of consumer.
`entertainment. ollicc, 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 suller from sigttilicattt seek-time
`access delays along with profound reacliwritc data rate
`limitations. Currently the fastest available { |0,0tl0) 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’s Peripheral Component Interconnect (PCl} Buss
`in putfoutput capability ol"Z'.6-1 MBr’sec and internal local bus
`capability of B00 Mlirsec.
`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
`oifcr 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.] MBi'sec.
`1’aster disk
`access data rates are only achieved by the high cost solution
`of simultaneously accessing multiple disk drives with a
`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 storage deviccs utilizing magnetic, optical, and chemical
`techniques. or any combination thereof.
`SUMMARY OF THE INVENTION
`
`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 eiIc-ctive increase of the data
`storage and retrieval bandwidth of :1 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 at 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;
`
`

`
`US 6_.6(l1_.104 B1
`
`3
`retrieving the contpncssed data stream from the target
`storage device at a rate equal to a data access rate of the
`target storage device; and
`dccornprcssing 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 invention. 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.
`in 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 Erorn 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 inputloutput controller to reduce the time required to
`store. retrieve, or transmit data various forms of data.
`The present invention is realized due to recent improve-
`ments in processing speed. inclusive ofdeclicatcd analog and
`digital hardware circuits. central processing units. digital
`signal processors, dedicated finite state machines (and any
`hybrid combinations thercol’), that. coupled with advanced
`data compression and decompression algorithms, are
`enabling of ultra high bandwidth 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 horn the following
`detailed description of preferred ernbodiments, that is to he
`read in connect ion with the accompanying drawings.
`
`BRlI_i["' l)l£SC‘RIP'I'lON OF THE. DRAWINGS
`
`FIG. 1 is a block diagram of a system for accelerated data
`storage and retrieval according to one embodiment of the
`present invention;
`FIG. 2 is a How diagram oft] method for accelerated data
`storage in accordance with one aspect of the present inven-
`non;
`FIG. 3 is a How diagram of a method for accelerated data
`retrieval
`in accordance with one aspect of the present
`invention;
`FIGS. 40 and -1b are timing diagrams of methods for
`accelerated data storage according to the present invention;
`
`or
`
`.10
`
`15
`
`40
`
`SU
`
`6i!
`
`65
`
`4
`FIGS. Sn and 5b are liming diagrams of methods for
`accelerated data retrieval according to the present invention:
`FIGS. 6n and 6b cont prise a flow diagram of a method for
`accelerated data storage in accordance with a further aspect
`of the present invention;
`FIGS. 7n and 7b comprise a How diagram of a method for
`accelerated data retrieval in accordance with a further aspect
`of the present invention;
`FIG. 8 is a detaj led block. diagram of a system for
`accelerated data storage according 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 diagram of a system for accelerated
`video storage according to one embodiment of the present
`invention:
`FIG. 11 is a block diagram oi’ a system for accelerated
`retrieval of video data according to one embodiment oi’ the
`present invenLion;
`FIG. 12 is a block diagram of an inputtoutput controller
`system for accelerated storage of analog, digital, and serial
`data according to one emborliinunt ofihc 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 flow diagram of method
`for accelerated retrieval of analog, digital, and serial data
`according to one aspect of the present invention.
`Dl_"’l'AlLED DES(?RlP'FlGN Oi? PREFERRED
`EMBODIMENTS
`
`The present invention is dtrcctetl to systems and methods
`for providing improved data storage and retrieval bandwidth
`utilizing lossless data compremaion 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 reference 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 ioputfoutput (U0) interface{s}. The
`computer platform may also include an operating system.
`microinstruction code, and dedicated processing hardware
`utilizing combinatorial
`logic or finite state niachines. The
`various processes and functions described herein may be
`either part 01' the hardware, microinstruction code or appli-
`cation programs that are executed via the operating system.
`or any combination thereof.
`It is to he further understood that. because some of the
`constituent syste-In components described herein are prefer-
`ahly implemented as software modules, the actual system
`connections shown in the Figures may differ depending
`upon the manner in that the systems are programmed. It is
`to be appreciated that special purpose microprocessors,
`digital signal processors, dedicated hardware, or and com-
`bination thereof may be employed to implement the present
`invention. Given the teachings herein. one of ordirtary skill
`in the related art will be able to contemplate these and
`similar implerncntations or conligurations ol‘ the present
`invention.
`
`

`
`US 6,601,104 B1
`
`.10
`
`EU
`
`Jl
`
`30
`
`5
`Relicrring now to FIG. 1, a block diagram illustrates a
`system for accelerated data storage and retrieval
`in accor-
`dance with an embodiment ct‘ the present invention. The
`system includes ti data storage accelerator 10, operatively
`coupled to a data storage device 45. The data storage 5
`accelerator operates to increase the eflective data storage
`rate of the data storage device 45. It is to be appreciated that
`the data storage device 45 may be any tonrt of memory
`device including all fonns of sequential, pseudo-random,
`and random ttcccss storage devices. The memory storage
`device 45 may he volatile or non-volatile in nature, or any
`combination thereof. Storage devices as known within the
`current an include all
`fontrts of random access memory,
`magnetic and optical tape. ntagnetie and optical disks, along
`with various other fonns ot'solid—state mass storage devices.
`Thus it should he 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
`chemical 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 a given input data block at a rate that is
`equal to or faster than receipt of the input data. ‘thus, to
`achieve optimum throughput, the rate that data blocks from
`the input data stream may be accepted by the data storage
`accelerator 10 is at 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 (t:.g., a typical
`target mass storage device] is
`capable of storing 20 megabytes per second and the data
`storage accelerator II} is capable of providing an average
`compression ratio of3: t . then 60 megabytes per second may
`be accepted as input and the data storage acceleration is
`precisely 3:], equivalent to the average compression ratio.
`It should be noted that
`it
`is not
`:1 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.
`accelcralor 10 utilize data compression with :1 ratio that is at
`least the ratio ol’ the input data stream to the data storage
`access rate of the data storage device 45. Indeed,
`it" the
`compression 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
`dttta 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. The data retrieval accelerator 8|] receives
`and processes compressed data from data storage device 45
`in data blocks that may range in size from individual hits
`through complete tiles or collections of multiple files.
`Additionally,
`the input data block size may he lixed or
`variable. The data retrieval accelerator 80 is configured to
`
`40
`
`5t]
`
`55
`
`6t]
`
`65
`
`6
`decompress each compressed data block which is received
`from the data storage device 45. In order to achieve con-
`tinuous acceleratcd data retrieval. the data retrieval accel-
`erator rnust decompress a 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 It},
`achieving optimum throughput with the data retrieval accel-
`erator R0 is a function of the rate that compressed data
`blocks are retrieved Erom the data storage device 45, the
`of each data block, the decompression ratio achieved, and
`the limitation on the bandwidth oithe 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 dccomprtssion ratio.
`It is to be understood that it is not required that the data
`retrieval accelerator 80 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. Indeed. ifthe decompression ratio is greater than this
`ratio, retrieving data from the data storage device may be
`periodically halted to eflectively reduce the rate of the output
`data stream to be at or below its maximum. Alternatively, the
`compressed data retrieved from the data storage device 45 or
`the output of the data decompressor may be bullerecl
`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 accordirtg to one aspect ol‘