US 7,415,530 B2
`(10) Patent No.:
`(12) United States Patent
`
` Fallon (45) Date of Patent: Aug. 19, 2008
`
`
`USOO7415530B2
`
`(54) SYSTEM AND METHODS FOR
`ACCELERATED DATA STORAGE AND
`RETRIEVAL
`
`DE
`
`(75)
`
`Inventor:
`
`James J Fallon, Armonk, NY (US)
`
`.
`( * ) Notlce:
`
`(73) Assignee: Realtime Data LLC, New York, NY
`(Us)
`.
`.
`.
`.
`Subject to any d1scla1mer, the term of this
`patent is extended or adjusted under 35
`U'S'C' 15403) by 0 days'
`,
`.
`..
`(21) App] NO . 11/553 426
`
`FOREIGN PATENT DOCUMENTS
`
`4127518
`
`2/1992
`(Continued)
`OTHER PUBLICATIONS
`
`Rice, Robert F., “Some Practical Universal Noiseless Coding Tech-
`niques”, Jet Propulsion Laboratory, Pasadena, California, JPL Pub-
`lication 79-22, Mar. 15, 1979.
`
`(Continued)
`Primary ExamineriDavidY Eng
`(74) Attorney, Agent, or FirmiRopes & Gray LLP
`
`(22)
`
`Filed:
`
`Oct. 26, 2006
`
`(57)
`
`ABSTRACT
`
`(65)
`
`Prior Publication Data
`
`US 2007/0067483 A1
`
`Mar. 22, 2007
`_
`_
`Related U-S- APPllcatlon Data
`(63) Continuation of application NO. 10/628 795 filed on
`Jul. 28 2003 now Pat. NO. 7130 913 which is a
`continu’ation 05f application No.5 09/266 394 filed on
`Mar. 113 1999, now pat. NO. 6,601,104.
`
`(51)
`
`Int, Cl,
`(2006.01)
`G06F 13/00
`(52) U.S.C1.
`.................................................... .. 709/231
`(58) Field of Classification Search ............... .. 709/231,
`709/233
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`Us PATENT DOCUMENTS
`4,302,775 A
`11/1981 Widergren et 31.
`4,394,774 A
`7/ 1983 Widergren et a1.
`4,574,351 A
`3/ 1986 Dang et al.
`4,593,324 A
`6/ 1986 Ohkubo et a1.
`4,682,150 A
`7/1987 Mathes et al.
`4,730,348 A
`3/1988 MacCrisken
`
`Systems and methods for providing accelerated data storage
`and retrieval utilizing lossless data compression and decom-
`pression. A data storage accelerator includes one or a plurality
`of high speed data compression encoders that are configured
`to simultaneously or sequentially losslessly compress data at
`a rate equivalent to or faster than the transmission rate of an
`input data stream. The compressed data is subsequently
`stored in atarget memory or other storage device whose input
`data storage bandwidth is lower than the original input data
`stream bandwidth. Similarly, a data retrieval accelerator
`includes one or a plurality of high speed data decompression
`decoders that are configured to simultaneously or sequen-
`tially losslessly decompress data at a rate equivalent to or
`faster than the input data Stream from the target memory of
`storage device. The decompressed data is then output at rate
`data that is greater than the output rate from the target
`memory or data storage device. The data storage and retrieval
`accelerator method and system may employed:
`in a disk
`storage adapter to reduce the time required to store and
`retrieve data from computer to disk; in conjunction with ran-
`dom access memory to reduce the time required to store and
`retrieve data from random access memory; in a display con-
`troller to reduce the time required to send display data to the
`display controller or processor; and/or in an input/output
`controller to reduce the time required to store, retrieve, or
`transmit data.
`
`(Continued)
`
`23 Claims, 20 Drawing Sheets
`
`A_
`
`v_,
`
`
`
`Communion Rzna
`
`
`
`8mm Dani
`
`310
`
`alz
`
`eu
`
`No
`
`Tannin-i. smgsAnnular-anon PM:
`
`522
`
`Nempp
`
`Exhibit1001
`
`Page1
`
`
`
`mnpm'
`Ratioand Ian
`Bandwhlh
`Comb-tibia
`
`
`
`
`
`Modify.
`Input El MI"I DI
` ale
`’
`Eulferm
`:
`""1 Compuulnn of
`
`61B
`
`
`
`
`NetApp Exhibit 1001 Page 1
`
`

`

`US 7,415,530 B2
`
`Page 2
`
`US. PATENT DOCUMENTS
`
`4,754,351
`4,804,959
`4,870,415
`4,872,009
`4,876,541
`4,888,812
`4,906,995
`4,929,946
`4,953,324
`4,965,675
`4,988,998
`5,028,922
`5,045,848
`5,045,852
`5,046,027
`5,049,881
`5,091,782
`5,097,261
`5,113,522
`5,121,342
`5,150,430
`5,159,336
`5,175,543
`5,179,651
`5,187,793
`5,191,431
`5,204,756
`5,209,220
`5,212,742
`5,226,176
`5,227,893
`5,231,492
`5,237,460
`5,237,675
`5,243,341
`5,243,348
`5,247,638
`5,247,646
`5,263,168
`5,270,832
`5,287,420
`5,293,379
`5,307,497
`5,309,555
`5,355,498
`5,357,614
`5,379,036
`5,379,757
`5,381,145
`5,394,534
`5,396,228
`5,400,401
`5,403,639
`5,406,278
`5,406,279
`5,412,384
`5,414,850
`5,420,639
`5,434,983
`5,452,287
`5,461,679
`5,467,087
`5,471,206
`5,479,587
`5,483,470
`5,486,826
`5,495,244
`5,506,844
`5,506,872
`5,530,845
`5,533,051
`
`>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
`
`6/1988
`2/1989
`9/1989
`10/1989
`10/1989
`12/1989
`3/1990
`5/1990
`9/1990
`10/1990
`1/1991
`7/1991
`9/1991
`9/1991
`9/1991
`9/1991
`2/1992
`3/1992
`5/1992
`6/1992
`9/1992
`10/1992
`12/1992
`1/1993
`2/1993
`3/1993
`4/1993
`5/1993
`5/1993
`7/1993
`7/1993
`7/1993
`8/1993
`8/1993
`9/1993
`9/1993
`9/1993
`9/1993
`11/1993
`12/1993
`2/1994
`3/1994
`4/1994
`5/1994
`10/1994
`10/1994
`1/1995
`1/1995
`1/1995
`2/1995
`3/1995
`3/1995
`4/1995
`4/1995
`4/1995
`5/1995
`5/1995
`5/1995
`7/1995
`9/1995
`10/1995
`11/1995
`11/1995
`12/1995
`1/1996
`1/1996
`2/1996
`4/1996
`4/1996
`6/1996
`7/1996
`
`Wright
`Makansi et al.
`Van Maren et al.
`Tsukiyama et al.
`Storer
`Dinan et al.
`Swanson
`O’Brien et al.
`Herrmann
`Hori et al.
`O’Brien
`Huang
`Fascenda
`Mitchell et al.
`Taaffe et al.
`Gibson et al.
`Krause et al.
`Langdon, Jr. et al.
`Dinwiddie, Jr. et al.
`Szymborski
`Chu
`Rabin et al.
`Lantz
`Taaffe et al.
`Keith et al.
`Hasegawa et al.
`Chevion et al.
`Hiyama et al.
`Normile et al.
`Westaway et al.
`Ett
`Dangi et al.
`Miller et al.
`Hannon, Jr.
`Seroussi et al.
`Jackson
`O’Brien et al.
`Osterlund et al.
`Toms et al.
`Balkanski et al.
`Barrett
`Carr
`Feigenbaum et al.
`Akins et al.
`Provino et al.
`Pattisam et al.
`Storer
`Hiyama et al.
`Allen et al.
`Kulakowski et al.
`Garahi
`Wasilewski et al.
`Belsan et al.
`Graybill et al.
`Anderson et al.
`Chang et al.
`Whiting
`Perkins
`Yaso et al.
`Dicecco
`Normile et al.
`Chu
`Allen et al.
`Campbell et al.
`Alur et al.
`Remillard
`Jeong et al.
`Rao
`Mohler
`Hiatt et al.
`James
`
`5,535,356
`5,537,658
`5,557,551
`5,557,668
`5,557,749
`5,561,824
`5,563,961
`5,574,952
`5,574,953
`5,576,953
`5,583,500
`5,590,306
`5,596,674
`5,604,824
`5,606,706
`5,611,024
`5,612,788
`5,613,069
`5,615,017
`5,621,820
`5,623,623
`5,623,701
`5,627,534
`5,627,995
`5,629,732
`5,630,092
`5,635,632
`5,635,932
`5,638,498
`5,640,158
`5,642,506
`5,649,032
`5,652,795
`5,652,857
`5,652,917
`5,654,703
`5,655,138
`5,666,560
`5,668,737
`5,671,389
`5,675,333
`5,686,916
`5,694,619
`5,696,927
`5,703,793
`5,715,477
`5,717,393
`5,717,394
`5,719,862
`5,721,958
`5,724,475
`5,729,228
`5,748,904
`5,757,852
`5,771,340
`5,778,411
`5,781,767
`5,784,572
`5,787,487
`5,796,864
`5,799,110
`5,805,932
`5,808,660
`5,809,176
`5,809,337
`5,812,789
`5,818,368
`5,818,369
`5,818,530
`5,819,215
`5,825,424
`5,825,830
`5,832,037
`
`>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
`
`7/1996
`7/1996
`9/1996
`9/1996
`9/1996
`10/1996
`10/1996
`11/1996
`11/1996
`11/1996
`12/1996
`12/1996
`1/1997
`2/1997
`2/1997
`3/1997
`3/1997
`3/1997
`3/1997
`4/1997
`4/1997
`4/1997
`5/1997
`5/1997
`5/1997
`5/1997
`6/1997
`6/1997
`6/1997
`6/1997
`6/1997
`7/1997
`7/1997
`7/1997
`7/1997
`8/1997
`8/1997
`9/1997
`9/1997
`9/1997
`10/1997
`11/1997
`12/1997
`12/1997
`12/1997
`2/1998
`2/1998
`2/1998
`2/1998
`2/1998
`3/1998
`3/1998
`5/1998
`5/1998
`6/1998
`7/1998
`7/1998
`7/1998
`7/1998
`8/1998
`8/1998
`9/1998
`9/1998
`9/1998
`9/1998
`9/1998
`10/1998
`10/1998
`10/1998
`10/1998
`10/1998
`10/1998
`11/1998
`
`Kim et al.
`Bakke et al.
`Craft
`Brady
`Norris
`Carreiro et al.
`Rynderman et al.
`Brady et al.
`Rust et al.
`Hugentobler
`Allen et al.
`Watanabe et al.
`Bhandari et al.
`Chui et al.
`Takamoto et al.
`Campbell et al.
`Stone
`Walker
`Choi
`Rynderman et al.
`Kim et al.
`Bakke et al.
`Craft
`Miller et al.
`Moskowitz et al.
`Carreiro et al.
`Fay et al.
`Shinagawa et al.
`Tyler et al.
`Okayama et al.
`Lee
`Burt et al.
`Dillon et al.
`Shimoi et al.
`Maupin et al.
`Clark, 11
`Kikinis
`Moertl et al.
`Iler
`Saliba
`Boursier et al.
`Bakhmutsky
`Konno
`MacDonald et al.
`Wise et al.
`Kikinis
`Nakano et al.
`Schwartz et al.
`Lee et al.
`Kikinis
`Kirsten
`Franaszek et al.
`Huang et al.
`JericeVic et al.
`Nakazato et al.
`DeMoss et al.
`Inoue et al.
`Ro stoker et al.
`Hashimoto et al.
`Callahan
`Israelsen et al.
`Kawashima et al.
`Sekine et al.
`Yajima
`Hannah et al.
`Diaz et al.
`Langley
`Withers
`Canfield et al.
`Dobson et al.
`Canfield et al.
`Kopf
`Park
`
`NeMpp
`
`Exhibit 1001
`
`Page 2
`
`NetApp Exhibit 1001 Page 2
`
`

`

`US 7,415,530 B2
`
`Page 3
`
`5,832,126 A
`5,836,003 A
`5,838,996 A
`5,839,100 A
`5,841,979 A
`5,847,762 A
`5,861,824 A
`5,861,920 A
`5,864,342 A
`5,867,167 A
`5,867,602 A
`5,870,036 A
`5,870,087 A
`5,872,530 A
`5,883,975 A
`5,886,655 A
`5,889,961 A
`5,915,079 A
`5,917,438 A
`5,920,326 A
`5,936,616 A
`5,949,355 A
`5,955,976 A
`5,960,465 A
`5,964,842 A
`5,968,149 A
`5,973,630 A
`5,974,235 A
`5,974,471 A
`5,978,483 A
`5,982,723 A
`5,991,515 A
`5,996,033 A
`6,000,009 A
`6,002,411 A
`6,003,115 A
`6,008,743 A
`6,011,901 A
`6,014,694 A
`6,026,217 A
`6,028,725 A
`6,031,939 A
`6,032,148 A
`6,061,398 A
`6,073,232 A
`6,075,470 A
`6,091,777 A
`6,094,634 A
`6,097,520 A
`6,104,389 A
`6,105,130 A
`6,128,412 A
`6,141,053 A
`6,145,069 A
`6,169,241 B1
`6,172,936 B1
`6,173,381 B1
`6,182,125 B1
`6,192,082 B1
`6,195,024 B1
`6,195,465 B1
`6,222,886 B1
`6,225,922 B1
`6,226,667 B1
`6,226,740 B1
`6,253,264 B1
`6,272,178 B1
`6,272,627 B1
`6,272,628 B1
`6,282,641 B1
`6,308,311 B1
`6,309,424 B1
`6,317,714 B1
`
`11/1998 Tanaka
`11/1998 Sadeh
`11/1998 deCarmo
`11/1998 Wegener
`11/1998 Schulhofet a1.
`12/1998 Canfield
`1/1999 Ryu et a1.
`1/1999 Mead et a1.
`1/1999 Kajiya et a1.
`2/1999 Deering
`2/1999 Zandi et a1.
`2/1999 Franaszek et a1.
`2/1999 Chau
`2/1999 Domyo et a1.
`3/1999 Narita et a1.
`3/1999 Rust
`3/1999 Dobbek
`6/1999 Vondran, Jr. et a1.
`6/1999 Ando
`7/1999 Rentschler et al.
`8/1999 Torborg, Jr. et al.
`9/1999 Panaoussis
`9/1999 Heath
`9/1999 Adams
`10/1999 Packard
`10/1999 Jaquette et a1.
`10/1999 Heath
`10/1999 Nunally et a1.
`10/1999 Belt
`11/1999 Thompson, Jr. et al.
`11/1999 Kamatani
`11/1999 Fall et a1.
`11/1999 Chiu-Hao
`12/1999 Brady
`12/1999 Dye
`12/1999 Spear et a1.
`12/1999 Jaquette
`1/2000 Kirsten
`1/2000 Aharoniet a1.
`2/2000 Adiletta
`2/2000 Blumenau
`2/2000 Gilbert et a1.
`2/2000 Wilkes
`5/2000 Satoh et a1.
`6/2000 Kroeker et a1.
`6/2000 Little et a1.
`7/2000 Guetz et a1.
`7/2000 Yahagiet a1.
`8/2000 Kadnier
`8/2000 Ando
`8/2000 Wu et a1.
`10/2000 Satoh
`10/2000 Saukkonen
`11/2000 Dye
`1/2001 Shimizu
`1/2001 Kitazaki
`1/2001 Dye
`1/2001 Borella et a1.
`2/2001 Moriarty et a1.
`2/2001 Fallon
`2/2001 Zandi et a1.
`4/2001 Yogeshwar
`5/2001 Norton
`5/2001 Matthews et a1.
`5/2001 Iga
`6/2001 Sebastian
`8/2001 Nieweglowskiet a1.
`8/2001 Mann
`8/2001 Aguilar et a1.
`8/2001 Christensen
`10/2001 Carmichael et a1.
`10/2001 Fallon
`11/2001 Del Castillo et a1.
`
`.......... .. 375/240.23
`
`6,330,622 B1
`6,345,307 B1
`6,392,567 B2
`6,404,931 B1
`6,421,387 B1
`6,434,168 B1
`6,434,695 B1
`6,442,659 B1
`6,449,682 B1
`6,452,602 B1
`6,463,509 B1
`6,487,640 B1
`6,489,902 B2
`6,513,113 B1
`6,529,633 B1
`6,532,121 B1
`6,539,456 B2
`6,542,644 B1
`6,577,254 B2
`6,590,609 B1
`6,597,812 B1
`6,601,104 B1
`6,604,040 B2
`6,604,158 B1
`6,606,040 B2
`6,606,413 B1
`6,609,223 B1
`6,618,728 B1
`6,624,761 B2
`6,650,261 B2
`6,661,839 B1
`6,661,845 B1
`6,704,840 B2
`6,711,709 B1
`6,717,534 B2
`6,731,814 B2
`6,745,282 B2
`6,748,457 B2
`6,756,922 B2
`6,810,434 B2
`6,856,651 B2
`6,885,316 B2
`6,885,319 B2
`6,888,893 B2
`6,909,383 B2
`6,944,740 B2
`7,054,493 B2
`7,102,544 B1
`7,130,913 B2
`7,161,506 B2
`7,181,608 B2
`7,190,284 B1
`7,321,937 B2
`2001/0031092 A1
`2001/0032128 A1
`2001/0052038 A1
`2002/0037035 A1
`2002/0080871 A1
`2002/0101367 A1
`2002/0104891 A1
`2002/0126755 A1
`2002/0191692 A1
`2003/0030575 A1
`2003/0034905 A1
`2003/0084238 A1
`2003/0142874 A1
`2003/0191876 A1
`2004/0042506 A1
`2004/0073710 A1
`2006/0015650 A1
`2006/0181441 A1
`2006/0181442 A1
`2006/0184696 A1
`
`12/2001 Schaefer
`2/2002 Booth
`5/2002 Satoh
`6/2002 Chen et a1.
`7/2002 Rhee
`8/2002 Kari
`8/2002 Esfahaniet a1.
`8/2002 Blumenau
`9/2002 Toorians
`9/2002 Morein
`10/2002 Teoman et a1.
`11/2002 Lipasti
`12/2002 Heath
`1/2003 Kobayashi
`3/2003 Easwar et a1.
`3/2003 Rustet a1.
`.................... .. 360/8
`3/2003 Stewart
`4/2003 Satoh
`6/2003 Rasmussen
`7/2003 Kitade et al.
`7/2003 Fallon et al.
`7/2003 Fallon
`8/2003 Kawasaki et a1.
`8/2003 Fallon
`8/2003 Abdat
`8/2003 Zeineh
`8/2003 Wolfgang
`9/2003 Rail
`9/2003 Fallon
`11/2003 Nelson et al.
`12/2003 Ishida et a1.
`12/2003 Herath
`3/2004 Nalawadi et a1.
`3/2004 York
`4/2004 Yokose
`5/2004 Zeck et a1.
`6/2004 Okada et a1.
`6/2004 Fallon et a1.
`6/2004 Ossia
`10/2004 Muthujumaraswathy et al.
`2/2005 Singh
`4/2005 Mehring
`4/2005 Geiger et a1.
`5/2005 Li et a1.
`6/2005 Shokrollahiet a1.
`9/2005 Abaliet a1.
`5/2006 Schwartz
`9/2006 Liu
`10/2006 Fallon
`1/2007 Fallon
`2/2007 Fallon et a1.
`3/2007 Dye et a1.
`1/2008 Fallon
`10/2001 Zeck et a1.
`10/2001 Kepecs
`12/2001 Fallon et a1.
`3/2002 Singh
`6/2002 Fallon et a1.
`8/2002 Geiger et a1.
`8/2002 Otto
`9/2002 Li et a1.
`12/2002 Fallon et a1.
`2/2003 Frachtenberg et a1.
`2/2003 Anton et a1.
`5/2003 Okada et a1.
`7/2003 Schwartz
`10/2003 Fallon
`3/2004 Fallon et a1.
`4/2004 Fallon
`1/2006 Fallon
`8/2006 Fallon
`8/2006 Fallon
`8/2006 Fallon
`
`Nempp
`
`Exhibit 1001
`
`Page3
`
`NetApp Exhibit 1001 Page 3
`
`

`

`US 7,415,530 B2
`Page 4
`
`2006/0190644 A1
`2006/0195601 A1
`2007/0043939 A1
`2007/0050514 A1
`2007/0050515 A1
`2007/0083746 A1
`2007/0109154 A1
`2007/0109155 A1
`2007/0109156 A1
`2007/0174209 A1
`
`8/2006 Fallon
`8/2006 Fallon
`2/2007 Fallon et al.
`3/2007 Fallon
`3/2007 Fallon
`4/2007 Fallon et al.
`5/2007 Fallon
`5/2007 Fallon
`5/2007 Fallon
`7/2007 Fallon et al.
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`GB
`JP
`JP
`JP
`W0
`W0
`W0
`W0
`
`0164677
`0185098
`0283798
`0405572
`0493130
`0587437
`0595406
`0718751
`2162025
`6051989
`9188009
`11149376
`W0 9414273
`W0 9429852
`W0 9502873
`W0 9748212
`
`12/1985
`6/1986
`9/1988
`1/1991
`7/1992
`3/1994
`5/1994
`6/1996
`1/1986
`2/1994
`7/1997
`6/1999
`6/1994
`12/1994
`1/1995
`12/1997
`
`OTHER PUBLICATIONS
`
`Anderson, J., et al. “Codec squeezes color teleconferencing through
`digital telephone lines”, Electronics 1984, pp. 113-115.
`Venbrux, Jack, “A VLSI Chip Set for High-Speed Lossless Data
`Compression”, IEEE Trans. On Circuits and Systems forVideo Tech-
`nology, vol. 2, No. 44, Dec. 1992, pp. 381-391.
`“Fast Dos Soft Boot”, IBM Technical Disclosure Bulletin, Feb. 1994,
`vol. 37, Issue No. 2B, pp. 185-186.
`“Operating System Platform Abstraction Method”, IBM Technical
`Disclosure Bulletin, Feb. 1995, vol. 38, Issue No. 2, pp. 343-344.
`
`Murashita, K., et al., “High-Speed Statistical Compression using
`Self-organized Rules and Predetermined Code Tables”, IEEE, 1996
`Data Compression Conference.
`Coene, W., et al. “A Fast Route For Application of Rate-distortion
`Optimal Quantization in an MPEG Video Encoder” Proceedings of
`the International Conference on Image Processing, Lausanne, Swit-
`zerland, IEEE, Sep. 16, 1996, pp. 825-828.
`Rice, Robert, “Lossless Coding Standards for Space Data Systems”,
`IEEE 1058-6393/97, pp. 577-585.
`Yeh, Pen-Shu, “The CCSDS Lossless Data Compression Recom-
`mendation for Space Applications”, Chapter 16, Lossless Compres-
`sion Handbook, Elsevier Science (USA), 2003, pp. 311-326.
`Millman, Howard, “Image and video compression”, Computerworld,
`vol. 33, Issue No. 3, Jan. 18, 1999, pp. 78.
`“IBM boosts your memory”, Geek.com [online], Jun. 26, 2000
`[retrieved on Jul. 6, 2007], <URL: http://wwwgeek.com/ibm-boosts-
`your-memory/> .
`“IBM Research Breakthrough Doubles Computer Memory Capac-
`ity”, IBM Press Release [online], Jun. 26, 2000 [retrieved on Jul. 6,
`2007], <URL: http://WWW-03.ibm.com/press/us/en/pressrelease /
`1653.Wss>.
`“ServerWorks To Deliver IBM’s Memory eXpansion Technology in
`Next-Generation Core Logic for Servers”, ServerWorks Press
`Release [online], Jun. 27, 2000 [retrieved on Jul. 14, 2000], <URL:
`http://WWW.serverworks.com/news/press/ 000627.html>.
`Abali, B., et al., “Memory Expansion Technology (MXT) Software
`support and performance”, IBM Journal of Research and Develop-
`ment, vol. 45, Issue No. 2, Mar. 2001, pp. 287-301.
`Franaszek, P A., et al., “Algorithms and data structures for com-
`pressed-memory machines”, IBM Journal of Research and Develop-
`ment, vol. 45, Issue No.2, Mar. 2001, pp. 245-258.
`Franaszek, P. A., et al., “On internal organization in compressed
`random-access memories”, IBM Journal of Research and Develop-
`ment, vol. 45, Issue No.2, Mar. 2001, pp. 259-270.
`Smith, T.B., et al., “Memory Expansion Technology (MXT) Com-
`petitive impact”, IBM Journal of Research and Development, V0. 45,
`Issue No. 2, Mar. 2001, pp. 303-309.
`Tremaine, R. B., et al., “IBM Memory Expansion Technology
`(MXT)”, IBM Journal of Research and Development, vol. 45, Issue
`No. 2, Mar. 2001, pp. 271-285.
`
`* cited by examiner
`
`NeMpp
`
`Exhibit 1001
`
`Page 4
`
`NetApp Exhibit 1001 Page 4
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 1 of 20
`
`US 7,415,530 B2
`
`Ema59:0
`
`Emobw
`
`
`
`3mm.:55
`
`Emmbm
`
`9ND
`
`55:61
`
`“89.90094
`
`END
`
`mmfioum
`
`wo_>wn_
`
`Ema
`
`$9.2m
`
`85068.1
`
`ow
`
`mv
`
`OF
`
`FmmDOE
`
`Nempp
`
`Exhibit 1001
`
`Page 5
`
`NetApp Exhibit 1001 Page 5
`
`
`
`
`
`

`

`US. Patent
`
`Aug. 19, 2008
`
`Sheet 2 0f 20
`
`US 7,415,530 B2
`
`Receive Initial
`
`Data Block From
`
`Encoder(s)
`
`Input Data
`Stream
`
`Compress Data
`Block with
`
`200
`
`202
`
`Store Data
`
`204
`
`No
`
`
`
`Terminate Storage
`Acceleration Process
`
`
`
`208
`
`210
`
`
`
`
`More Data Blocks in
`Input Stream ?
`
`
`
`206
`
`YES
`
`Receive Next Data
`
`Stream
`
`Block From Input
`
`FIGURE 2
`
`Nempp
`
`Exhibit1001
`
`Page6
`
`NetApp Exhibit 1001 Page 6
`
`

`

`US. Patent
`
`Aug. 19, 2008
`
`Sheet 3 0f 20
`
`US 7,415,530 B2
`
`Retrieve Initial
`
`Data Block
`
`From Storage
`Device
`
`Decompress Data
`Block with
`
`
`
`Decoder(s)
`
`Output Accelerated
`
`Data Block
`
`300
`
`302
`
`304
`
`
`
`N0
`
`Terminate Retrieval
`
`Acceleration Process
`
`
`
`308
`
`310
`
`
`
`306
`
`Yes
`
`Retrieve Next
`
`Data Block
`
`Devnce
`
`From storage
`
`
`
`More Data Blocks
`For Output Stream ?
`
`
`
`FIGURE 3
`
`Nempp
`
`ExhibitiOOl
`
`Page7
`
`NetApp Exhibit 1001 Page 7
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 4 of 20
`
`US 7,415,530 B2
`
`3mm"028mm.""magma__memomm"mzwomm“92001“mamon.__,____________._nFnuEn2uEuEn322:.95
`.Ill'JlJllIlJlullllllwllllJlllllJ}"uuunuu_3.02m.
`END__vonmEma._axoemEma_NonmEma_$605San._x005
`
`_rQOIhmE
`
`
`
`
`
`
`
`
`
`
`
`wmmiEoowmeEoommmanommmEEoo$032.00$23.00
`
`———..._—..._—-——_——
`
`_———-——-————.————
`
`:85£8:85$8302m98$85$8:8558x8598
`
`
`
`
`
`
`
`vmvoocm93w360269onUwuonucwSSWUwuoocw99mkuoocw98mvmvoocw22m
`
`E8598vv.8598mv.85.28mx8538Fx85Emax8598
`
`TIIIIIIJITIIIIIITIIJIITIIIJIII
`
`
`
`_IIIIIIN90:52
`
`_-——_—~——_—_—_——-
`
`———.———.—_-___.____-
`
`
`
`
`
`
`
`
`
`39980$05800305500899.503035.00
`
`
`
`3-;v.8538mx8538Nx8528Fx8528x8538
`
`uwnoocm905
`
`atv.85Ema
`
`uwuoocm22m
`
`
`
`Nxoo_m9mm—
`
`.838529m
`
`_‘onmEND
`
`mvMEDOE
`
`uwuoocmSSW
`
`V32m.NED
`
`Nempp
`
`Exhibit 1001
`
`Page 8
`
`.—_——_.—_——____.___-
`
`____—————-__._—
`
`NetApp Exhibit 1001 Page 8
`
`

`

`U.S. Patent
`
`u
`
`0.5
`
`00
`
`Sheet 5 of 20
`
`2B
`
`
`
`
`0cA0m+c3+:0H,v.85Emav.85EmaxogmEmaHmwmmfiwo
`
`
`1wwwanowmoaeoo899:8o
`
`A.lfil‘IJlllllTi'IalAll'lJ'ILan—IE
`__.________
`_nunun____c._3+:_3+;__..00mmummx005Ema“"xoemEma“xoo_m_Emaxwhmmohmo
`
`8?+
`
`5I
`
`...
`
`1:
`
`5E
`
`—
`
`c...
`
`a?
`.i'
`I:
`
`E r
`
`:
`
`329:.08:.
`
`
`
`mamomm920mm
`
`038mm
`
`_.____—____.._—___
`
`_________~_____
`
`—,._.———_——.——.~-———
`
`_______.________
`
`_______________
`
`
`Sx005Emaxoo_mEmaxoo_m9mmx005Emaxoo_m_Emax005SmomUumuoocm
`
`
`
`
`
`93mUwconucw9.9mUmuoocm23wumboocw98wvmvoocw92wUmuogm.0..onMc:.53+:_v.85Ema
`v.85Emax8593v.85Emav.8528
`
`$2950$9925$9950$9950$9360
`
`
`
`
`
`m£#59”.m5,m5mMm7,:9-58-5_3-:E
`
`Page 9
`
`:
`
`
`
`vmnoocw92w
`
`xoo_m_Ema
`
`
`
`Umuoocm93m
`
`xoo_mEma
`
`Amiv
`
`2+;
`
`v.85Ema
`
`vmfioocm98m
`
`
`Umnoocm92m
`
`x005Ema
`
`NDOI._.m=>_
`
`NetApp Exhibit 1001 Page 9
`
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 6 of 20
`
`US 7,415,530 B2
`
`368353:0
`
`_v_oo_mEma
`
`VxoofiEma
`
`mxoo_m_Ema
`
`Nxoo_mEma
`
`92.50”.
`
`_xoo_mEma
`
`@533“.
`
`wxoo_mENG
`
`92th
`
`m>mEom
`
`mx85ES
`
`Nx005Ema
`
`905$.
`
`wv_oo_m_m.ng
`
`mama—touch.
`
`
`
`_x005.mqu
`
`mmmEEoowo
`
`vxoo_m_Ema
`
`mmmanomQ
`
`m505Ema
`
`mwmanooo
`
`N1005Sac
`
`mmwanomo
`
`_.x005Ema
`
`__.__._.—-.__.__——.—_.__
`
`mmmanomn.
`
`2-;v.85Ema
`
`wmmanomQ
`
`mx85Ema
`
`88qu59:0
`
`3-:v.85£3
`
`888059:0
`
`Nx85Ema
`
`m"rxoemEma_38803930“._“NxosmEma":859mm.
`mmmanomo_mmmEEoomo__
`
`mmmmDGE
`
`_______NDOIHwS—
`
`.______.________
`
`mmmEEoomD
`
`v‘oo_m_Ema
`
`umnoomn.53:0
`
`x005Ema
`
`NeMpp
`
`Exhibit 1001
`
`Page 10
`
`833039:0
`umnoomo5330
`368333:0
`uonoomo53:0
`
`_.x005mumm—
`83835930
`
`_~____._________
`
`.529505:.
`
`$2.5m
`
`x8593
`
`PQQIFME
`
`$032.83.
`
`x85Ema
`
`xooEEma
`
`NetApp Exhibit 1001 Page 10
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 7 of 20
`
`US 7,415,530 B2
`
`
`
`_ANEVF:3:c...__Amifi_3+3_
`
`322:.35.
`
`jljlllillllljiwlllljlll_________________c__AN+c_3+:_xoo_mEma““"x8598unv.85£8"x85£8“96:6”.___m>2bom._®>®Emm_®>mEQZ________
`
`Ilillxllllllllllllllllllllwllllulllllllllllii__________c__Amiv_3+;_______._xooaEma___:85Ema__x85.23_x8528_880853:0___@288059:0__8303053:_830mm32:_.____O_O.uununuu.__c__AN+5.3+5______._._comm___V.005Ema__xoo_m_Ema_xoofimama_mMermEhoMmnu"mmmzanooQ"“mmEQEoowQ“805E080"_?nunuun50:52
`
`___-_____c_S5u_3+;___xoo_m_Ema__x8593_x8538__v.8598_62m98_wmmaeoomo““wmeEoomo"$038080““mmEanomo"mmmEEoomo"uuunnnnN.no.
`Ill.me
`
`sagap_880859:0.888059:0.38085930__880853:0_8889350_880mm550m_______euu"uauuN
`1mmmmmmmW_______m_c_3-5_ANICV____CH;_:x_“x8538“x8538“x85Ema"nx85man."x85Ema"v.85
`
`amHEDGE
`
`Page 11
`
`NetApp Exhibit 1001 Page 11
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 8 of 20
`
`US 7,415,530 B2
`
`Receive Initial
`
`Data Block From
`
`600
`
`Input Data
`Stream
`
`Time & Count
`
`Data Block
`
`Buffer
`
`Data Block
`
`Data Block
`
`Compress Data
`Block with
`
`Encoder(s)
`
`Time & Count
`
`602
`
`604
`
`606
`
`608
`
`FIGURE 6a
`
`NeMpp
`
`Exhibit 1001
`
`Page 12
`
`NetApp Exhibit 1001 Page 12
`
`

`

`US. Patent
`
`Aug. 19, 2008
`
`Sheet 9 0f 20
`
`US 7,415,530 B2
`
`
`
`A
`
` Buffer
`Data Block
`
`
`
`
`
`Determine
`
`Compression Ratio
`and Bandwidths
`
`Store Data
`
`614
`
`610
`
`612
`
`
`
`
`
`Modify:
`Input Bandwidth or
`
`Compression or
`Buffering
`
`Nov
`
`
`
`ompression
`Ratio and Input
`Bandwidth
`
`Compatible
`
`
`
`
`Receive Next Data
`
`Yes
`
`Block From input
`Stream
`
`Yes
`
`
`
`ore Data Blocks in
`Input Stream ?
`
`618
`
`622
`
`No
`
`Terminate Storage
`Acceleration Process
`
`FIGURE 6b
`
`NeMpp
`
`ExhibitIOOI
`
`Page13
`
`NetApp Exhibit 1001 Page 13
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 10 of 20
`
`US 7,415,530 B2
`
`Retrieve Initial
`
`Data Block
`
`From Storage
`Device
`
`Time & Count
`
`Data Block
`
`Buffer
`
`Data Block
`
`Data Block
`
`Decompress Data
`Biock with
`
`Decoder(s)
`
`Time & Count
`
`700
`
`702
`
`704
`
`706
`
`708
`
`FIGURE 7a
`
`NeMpp
`
`Exhibit 1001
`
`Page 14
`
`NetApp Exhibit 1001 Page 14
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 11 0f 20
`
`US 7,415,530 B2
`
`A
`
`710
`
`712
`
`
`
` Buffer
`Data Block
`
`
`
`Determine
`
`
`
`Decompression
`Ratio and
`
`Bandwidths
`
`
`
` Output Accelerated
`Data Block
`
`714
`
`
`
`Decompression
`Ratio and Output
`Bandwidth
`
`Compatible
`7
`
`
`
`
`
`Modify:
`Output Bandwidth
`or Decompression
`or Buffering
`
`718
`
`No
`
`Terminate Retrieval
`
`Acceleration Process
`
`
`
`722
`
`
`
`
` More Data Blocks
`
`for Output Stream ?
`
`
`
`720
`
`Retrieve Next Data
`
`Block From
`
`Storage Device
`
`FIGURE 7b
`
`NeMpp
`
`Exhibit 1001
`
`Page 15
`
`NetApp Exhibit 1001 Page 15
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 12 0f 20
`
`US 7,415,530 B2
`
`3.3baboocm
`
`\35.225
`
`L838me
`
`:o_mm2ano
`
`mg...
`
`5.320me
`
`go
`
`«I\
`
`ozmmcofimmano
`
`Beamsgfloo
`
`
`
`v.Eczogmtsm.Fm..wuoocw
`
`N52:09.thm
`
`
`
`m.quoocm
`
`cemtmqsoo
`
`:m5.805
`
`mEczogmfizm£8«:9:
`
`v.85mama
`
`5:150
`
`@0250mommMEE
`
`mmwhogm#o@8300
`
`
`Sunmaflofi
`
`mvow
`
`mHEDGE
`
`Sun
`
`Eugen
`
`NeMpp
`
`Exhibit 1001
`
`Page 16
`
`NetApp Exhibit 1001 Page 16
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 13 of 20
`
`US 7,415,530 B2
`
`Sun533
`
`Emobm
`
`E8830
`
`No.25qu
`
`
`
`51.53....:32E53
`
`wow
`
`
`Ema53:0no.638385:0meEmaSac.@0250m6$9on#o
`
`
`
`555:ozombxmhotamxoo_m_Emammmhoww
`
`
`
`
`:95@832“.
`
`cohmuoomn
`
`
`
`ommv
`
`m.OE
`
`NeMpp
`
`Exhibit 1001
`
`Page 17
`
`NetApp Exhibit 1001 Page 17
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 14 0f 20
`
`US 7,415,530 B2
`
`wmmhoflm
`
`Swgflmco/x
`
`or
`
`59:0END
`
`Emwbw
`
`
`
`Eras8Q>
`
`05?
`
`Lowmwoohn.
`
`.355
`
`5500
`
`omov
`
`ovow
`
`omow
`
`omov
`
`ormmDOE
`
`NeMpp
`
`Exhibit 1001
`
`Page 18
`
`NetApp Exhibit 1001 Page 18
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 15 of 20
`
`US 7,415,530 B2
`
`3:50o._.
`
`0250
`
`
`
`Ema>mam5
`
`Emmbm
`
`>335
`
`525
`
`>m_aw_o
`
`5:555...
`
`om:
`
`0v:
`
`om:
`
`Ema
`
`_m>mEmm
`
`5292891
`
`ow
`
`:MMDOE
`
`NeMpp
`
`Exhibit 1001
`
`Page 19
`
`NetApp Exhibit 1001 Page 19
`
`
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 16 of 20
`
`US 7,415,530 B2
`
`59:0Ema
`
`Emwbw
`
`mmEBm
`
`85568.1
`
`o_‘
`
`NrMMDOE
`
`mVNF
`
`
`
`ovwvmmmv
`
`tw>coo
`
`.355Ian.mSmo_mc<H_0
`
`«Ed@2591
`
`on:88
`
`.955Ewan.
`
`3mm.
`
`
`
`mum.cum?
`
`:234w380
`
`
`
`60$:qu0Ban..mtmwm
`
`.3655:8
`
`Ema
`
`NeMpp
`
`Exhibit 1001
`
`Page 20
`
`NetApp Exhibit 1001 Page 20
`
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 17 of 20
`
`US 7,415,530 B2
`
`1312
`
`1314
`
`1316
`
`A
`
`salad Inmal
`Parallel Digital
`Data With Input
`Mux
`
`
`Select Initial Serail
`.
`Data thlth Input
`ux
`
`1306
`
`Latch Parallel
`
`Digital Input Data
`
`Convert Serial
`
`1303
`
`Data Format
`
`Buffer Parallel
`
`
`
`Buffer Serial
`
`Digital Data
`
`1310
`
`Digital Data
`
`
`
`
`
`
`
`
`
`Select Initial
`
`Analog Data With
`input Analog
`Mux
`
`Analog to Digital
`Convert Input
`Signal
`
`
`
`1300
`
`1302
`
`Buffer Digitized
`Analog Data
`
`1304
`NO
`
`New Serial
`
`ata Availabl N”
`?
`
`N0
`
`Yes
`
`Yes
`
`1322
`
`
`
`
`
`Compress Input Data Block
`
`1324
`
`Output Encoded
`Data Block
`
`1326
`
`FIGURE 13
`
`NeMpp
`
`Exhibit 1001
`
`Page 21
`
`NetApp Exhibit 1001 Page 21
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 18 of 20
`
`US 7,415,530 B2
`
`Emamo_m:<
`
`o525mw20:
`mo_mc<
`
`8:232.955
`
`52.60
`
`o82.5w0szmo0Bram
`
`
`
`Ema.mtmm
`
`oomth.
`
`m3;
`
`031‘
`
`mmi‘
`
`3‘mmDOE
`
`55538m
`
`«ED
`
`3ng_m__m._mn_
`
`3mm.
`
`mI;
`
`4r
`525w295..
`53:0
`
`END
`
`091‘
`
`$8565
`
`.5530”...
`
`mm:
`
`ONE.
`
`ow .Smhw_woo<
`
`EmaSac.
`
`Emwbw
`
`NeMpp
`
`Exhibit 1001
`
`Page 22
`
`NetApp Exhibit 1001 Page 22
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Aug. 19, 2008
`
`Sheet 19 0120
`
`US 7,415,530 B2
`
`1500
`
`
`
`Receive initial
`
`Data Block
`
`
`
`Decompress Data
`Block
`
`1502
`
`
` ls Data
`
`
`Digital Parallel
`Data ?
`
`
`No
`
`
`
`1510
`
`Yes
`
`No
`
` ls
`Data Serial
`Data
`
`1512
`
`
`
`?
`
`Yes
`
`
`
`
`
`1508
`
`ata Digitize
`Analog Data
`7
`
`
`
`Yes
`
`Buffer Digitized
`Analog Data
`
`Buffer Parallel
`Digital Data
`
`Digital Data
`
`Buffer Serial
`
`FIGURE 153
`
`NeMpp
`
`ExhibitiOOi
`
`Page 23
`
`NetApp Exhibit 1001 Page 23
`
`

`

`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 20 of 20
`
`US 7,415,530 B2
`
`1524
`
`1526
`
`Format
`
`Serial Data
`
`1528
`
`Output Serial
`
`Digital Data
`
`1530
`
`
`
`Output Parallel
`Digital Data
`
`Demux Digital
`Parallel Data
`
`1520
`
`1522
`
`No
`
` More Data
`Blocks in Input
`Stream ?
`
`1532
`
`
`
`Yes
`
`Receive Next
`
`Data Block
`
`1534
`
`FIGURE 15b
`
`NeMpp
`
`Exhibit 1001
`
`Page 24
`
`Digital to Analog
`Convert Data
`
`Data
`
`Output Analog
`
`NetApp Exhibit 1001 Page 24
`
`

`

`US 7,415,530 B2
`
`1
`SYSTEM AND METHODS FOR
`ACCELERATED DATA STORAGE AND
`RETRIEVAL
`
`This application is a continuation of US. patent applica-
`tion Ser. No. 10/628,795, filed on Jul. 28, 2003, now US. Pat.
`No. 7,130,913, which is a continuation of US. patent appli-
`cation Ser. No. 09/266,394 filed on Mar 11, 1999, now US.
`Pat. No. 6,601,104, both ofwhich are hereby incorporated by
`reference herein in their entirety.
`
`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 loss-
`less data compression and decompression.
`2. Description of the Related Art
`Information may be represented in a variety of manners.
`Discrete information 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 (VLSI)
`digital computer technology have enabled both discrete and
`analog information to be represented with digital data. Con-
`tinuous information represented as digital data is often
`referred to as diffuse data. Diffuse digital data is thus a rep-
`resentation of data that is of low information 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 pro-
`ces sed, stored, and transmitted due to its inherently high noise
`immunity. In addition, the inclusion of redundancy in digital
`data representation enables error detection and/or correction.
`Error detection and/or correction capabilities are dependent
`upon the amount and type of data redundancy, available error
`detection and correction processing, and extent of data cor-
`ruption.
`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 diffuse 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 ofinformation. In general, there are two
`types of data compression techniques that may be utilized
`either separately or jointly to encode/decode data: lossy and
`lossless data compression.
`Lossy data compression techniques provide for an inexact
`representation ofthe original uncompressed data such that the
`decoded (or reconstructed) data differs from the original
`unencoded/uncompressed data. Lossy data compression is
`also known as irreversible or noisy compression. Negentropy
`is defined as the quantity of information in a given set of data.
`Thus, one obvious advantage oflossy data compression 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 techniques seek to exploit vari-
`ous traits within the human senses to eliminate otherwise
`
`imperceptible data. For example, lossy data compression of
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`visual imagery 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 uncompressed
`data. Simply stated, the decoded (or reconstructed) data is
`identical to the original unencoded/uncompressed data. Loss-
`less data compression is also known as reversible or noiseless
`compression. Thus, lossless data compression has, as its cur-
`rent limit, a minimum representation defined by the negent-
`ropy of a given data set.
`It is well known within the current art that data compres-
`sion provides several unique benefits. First, data compression
`can reduce the time to transmit data by more efficiently uti-
`lizing low bandwidth data links. Second, data compression
`economizes on data storage and allows more information to
`be stored for a fixed memory size by representing information
`more efficiently.
`One problem with the current art is that existing memory
`storage devices severely limit the performance of consumer,
`entertainment, office, 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 com-
`puting applications suffer from significant seek-time access
`delays along with profound read/write data rate limitations.
`Currently the fastest available (10,000) rpm disk drives sup-
`port only a 17.1 Megabyte per second data rate (MB/sec).
`This is in stark contrast to the modern Personal Computer’s
`Peripheral Component Interconnect (PCI) Bus’s input/output
`capability of 264 MB/sec and internal local bus capability of
`800 MB/sec.
`
`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 Channel
`offer 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 MB/sec. Faster disk access
`data rates are only achieved by the high cost solution of
`simultaneously accessing multiple disk drives with a tech-
`nique 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, mag-
`netic 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 including stor-
`age devices utilizing magnetic, optical, and chemical tech-
`niques, 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 utiliz-
`ing lossless data compression and decompression. The
`present invention provides an effective increase of the data
`storage and retrieval bandwidth of a memory storage device.
`In one aspect ofthe present inventi