US007415530B2
`
`(12)
`
`United States Patent
`Fallon
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,415,530 B2
`Aug. 19, 2008
`
`(54) SYSTEM AND METHODS FOR
`ACCELERATED DATA STORAGE AND
`RETRIEVAL
`
`(75) Inventor: James J Fallon, Armonk, NY (US)
`
`(73) Asslgnee: Realtlme Data LLC’ New York’ NY
`(US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U'S'C' 154(1)) by 0 days'
`(21) Appl' No‘: 11/553,426
`
`FOREIGN PATENT DOCUMENTS
`
`DE
`
`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:
`
`0a. 26, 2006
`
`(57)
`
`ABSTRACT
`
`(65)
`
`Prior Publication Data
`
`US 2007/0067483 A1
`
`Mar- 22, 2007
`
`Related U-s- Application Data
`(63) Continuation of application NO 10/628,795, ?led on
`Ju1_ 28’ 2003, HOW Pat NO 7,130,913, which is a
`Continuation of application NO_ 09/266,394, ?led on
`Man 11, 1999’ HOW Pat NO_ 6,601,104
`
`(51) Int CL
`(200601)
`G06F 13/00
`(52) US. Cl. .................................................... .. 709/231
`(58) Field of Classi?cation Search n
`_ 709/231
`709033’
`See application ?le for Complete Search history'
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,302,775 A 11/1981 Widergren et al.
`4,394,774 A
`7/1983 Widergren et al.
`4,574,351 A
`3/1986 Danget al.
`4,593,324 A
`6/1986 Ohkubo et al.
`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 con?gured
`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 a target 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 con?gured to simultaneously or sequen
`tiany losslessly decompress data at a rate equivalent to or
`faster than the input data stream from the target memory or
`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
`
`Al
`
`Bullet
`Data am
`
`510
`
`I
`
`Delmrnlm
`m1 Bandwidth:
`
`e12
`
`Manly
`N“ ,1 Input Bandwidth a:
`/ Cnmprunlnn m 1
`EuIferm
`'
`
`we Data Black! in
`InDuk 5mm 7
`
`No
`
`Tanninlto Stmsgs
`Mamba PM!
`
`522
`
`

`

`US. PATENT DOCUMENTS
`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
`
`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
`
`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
`
`US 7,415,530 B2
`Page 2
`
`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 a1.
`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
`Can?eld et al.
`Dobson et al.
`Can?eld et al.
`Kopf
`Park
`
`

`

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

`

`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”, Geekcom [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.serverWorkscom/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
`
`

`

`US. Patent
`
`Aug. 19, 2008
`
`Sheet 1 0f 20
`
`US 7,415,530 B2
`
`
`
`Ema 593G
`
`W 2695
`
`8 $ 8
`
`F mmDGE
`
`_m>wEwm A @9205 A wmEBw
`
`
`636x894 w2>w0 636684‘ \_
`Ema Ema Ema [I
`
`
`
`
`
`2825
`Ema Ens
`
`

`

`US. Patent
`
`Aug. 19, 2008
`
`Sheet 2 0f 20
`
`US 7,415,530 B2
`
`Receive InitiaI
`Data Block From
`Input Data
`Stream
`
`200
`
`I
`
`Compress Data
`Block with
`——->
`Encoder(s)
`
`202
`
`Store Data
`
`204
`
`More Data Blocks in
`Input Stream ?
`
`Terminate Storage
`Acceleration Process
`
`208
`
`YES
`
`I
`
`Receive Next Data
`Block From Input
`Stream
`
`210
`
`FIGURE 2
`
`

`

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

`

`U.S. Patent
`
`Aug. 19,2008
`
`Sheet 4 of 20
`
`US 7,415,530 B2
`
`.28_v_8_m3.3_w>_mumm__“mzmomm__wzmomm_wzmomm_m>m_omm“mzmowm.__,____________._HC.nuE."3HE.uE._522:.me:
`__.n_o_.:.m_s_ _HH“Huu_:_8_m_98u_§oo_m$8_$85$3.Nv_8_m£8_C_8_m
`
`
`
`
`
`
`
`-__.—.-__._....——_.-.—_.—._—
`
`_______________
`
`
`
`
`
`wmm.qEoowwmEEo0mmmEEo0mmm:aEoommmEEoommmasoo
`
`
`
`
`
`C_8_m_3.3$_8_m_Ema38_m_EmaNx8_m28285San.x8_m98
`
`
`
`
`
`umvoocm93wvmuoocm98wUwuoocmSSWvwuoocw98mcwuoocw92m882$22m
`
`C_oo_mEmavv_8_m98Nv_8_m98Nx8_mEma.x8_mEmaN8598
`
`T‘J|
`
`_IINoo._._l+l.um_>_
`
`
`
`wmmaEoommmaEoommmafioomwmafioom$aEoo
`
`.——.—.—_..—_._.—._._——..———-
`
`—._—..———.._...._——_.——_—-
`
`
`
`3-;x8_m28Nx8_mEmaNx8_m.28FN8538x8_m38
`
`uwnoocm99$
`
`
`
`AN-_Vv_8_mEma
`
`uwuoocm28m
`
`Nv_8_mEma
`
`umvoocm29$
`
`Fx8_msun.
`
`9»manor.
`
`uwuoocmm._9m
`
`V_8_m_Ema
`
`
`
`
`
`
`
`.———.__.—....—_——._._—._——-
`
`

`

`U.S. Patent
`
`1
`
`Sheet 5 of 20
`
`5»51
`
`2B
`
`m3mmswi
`
`4,::-58-5_:-_.Mv_8_mEmax8_m9.8x8_m98,_8_m_Ema
`
`
`
`
`
`
`x8_m£86o_m98Uumuoocm92mvmcoocm9.05umuoocmm_o..mumcoocm905umuoocwm._2wUmuoocm205
`
`
`
`
`
`
`
`0Ne3+:Mv_oo_m98xoo_m_Emav_oo_mEmavwMwnw__mmfi__.m._~.,um%_
`
`
`
`9,m$_n_Eoowmo._aEoowmmEEoo
`m..._4,Q:o.:...Hm_..s_.A_HuHH_H____c._3+:_3+:_xoo_m_Ema33Tv_oo_m_Emaj3v_0O_mEmaflv_OO_mEwe
`@>_®O®W______.________
`
`
`
`
`
`@>_@UmKmzwomm0>®_00./._
`
`c:-53+;_
`
`
`
`
`mmmircoomwm:aEoowwm._aEoommwaEoo
`
`V_8_mEmaV_8_mEmax8_m98v_8_m.28wmoaEoo
`
`
`
`x8_mEma
`
`c
`
`umuoocm905
`
`x8_m£8
`
`vmuoocm92m
`
`v_0o_mEND
`
`6+;
`
`_________._____
`
`3+;
`
`v_oo_m_Ema
`
`nwvoocm92m
`
`
`Umnoocm92m
`
`fio_m£8
`
`NDO_._._..n.=>_
`
`a“+
`
`5I
`
`-
`
`if
`-
`
`5E
`
`:._.
`
`6?
`.1
`F’
`
`E F
`
`-’
`
`
`
`_m>.m.E_mE_._.
`
`_______.________
`
`
`

`

`U.S. Patent
`
`Aug. 19,2008
`
`Sheet 6 of 20
`
`US 7,415,530 B2
`
`umuoomo59:0
`
`_v_oo_m28
`
`vv_oo_mEma
`
`mxuo_m_28
`
`Nxoo_m28
`
`.....>o_.aow_
`
`_v_oo_m_98
`
`m>oEwm
`
`wv_8_mman.
`
`m>e_.:ow_
`
`w>o_=om_
`
`mx8_mEma
`
`NV_8_m9.3
`
`m>oEmm_
`
`wv_8_m$8
`
`mmmafioooo
`
`_v_oo_m98
`
`mmmEEoomn_
`
`vxoo_m_98
`
`mmmznécoome
`
`mx8_m£8
`
`mwm3Eooon_
`
`NV_oo_m£8
`
`mmwEEoomn_
`
`Vv_8_m_Ema
`
`—_.—_._.—..—_..—.-—.__.—_.——
`
`_______NDOI._.m__>_
`
`mmmaEooon_
`
`
`
`2-;x8_mEma
`
`mmmaeoomn
`
`mv_8_mEma
`
`umcoomo59:0
`
`asv_8_mEma
`
`umuoomo59:0
`
`Nxoo_m.28
`
`m".L_8_mEma_
`
`mmmmnwz
`
`vmuoomn_S9.:O___~v_8.mEma_C_8_m£8
`mmmEEoomn__mmmEEoomo__
`
`.______.________
`
`mmmEEoomn_
`
`x8_m_Ema
`
`umnoomoS330
`
`x8_msac
`
`nmfioomoS930
`umfioomo5320
`umuoooo5330
`umnoomo3930
`_.x8_m£8
`uwuoowoS930
`
`.———.__._..._——.__.__.___.._
`
`
`
`_mZmE_®C..__._-
`
`o>m_=mm
`
`V_8_m98
`
`_.m_dI._..u.=>_
`
`mmm.aEoomQ
`
`x8_m£8
`
`x8_m98
`
`

`

`U.S. Patent
`
`Aug. 19,2008
`
`Sheet 7 of 20
`
`US 7,415,530 B2
`
`. HHHHHHHHHHHHHH_c_HAN+_HH3+:HvHoo_mHEma
`_HHxoo_mEmaHHv_OO_mMHNQHv_uO_mNEDHm>0_.5@W_HHHm>mEomHHHm>mEmmHm>mE®m_HHHHHH
`
`.23HH8HmEmaHHv_ooHm9.50HxooHm28_wmm.HQEoo¢n_HHmmmafiooooHwmmaeoomoHHmmmHaEooonHHmmmHaEoomoHHHHHHHHNol.|o:EH>H1 HHH:HHHHHHHHm+HIHH8HmHEmaHHHH85S8HHH8HmH
`HHHHHHHHHHHHHHH-_HHH_HH.HH2.5HH3+:_HHvHooHmHEmaHHHooHmH
`«SQSOHHHHHHHHHHHoocmmHHAN+_HH3+:HvHoo_mH
`_HHmmm.HaEoooQHHmwmHnHEoownHHmwmEEoowQHH,HHHHHHVnHoI.EH>H
`
`.23HH85EmaHumuoooo=aH:HoHHHuwuoomo59:0HHnmuoowo5330Humvoomo
`«Han.HHHVHHmH0HHxooHmHSan.HvHooHmHEmaHmmmafioowo
`
`HHHHHHHH:H3.5H3.5HHHH:-_HHHvHoO_mEmaHx8HmH3.8HH8HmHEmaHHH8HmHman.HH8HmHEmaHvH8HmHEma
`
`HUmHooomnHS&:OHnmuoowofifiaoHumuoomo58:0HHu.wUoooQS&H.HOHUmuoomn:H.HBH._OHB88nHHHaH:Ho
`
`gmm_w_DO_nH
`
`
`
`
`
`Hfi+c:.$+5»r:.H.HHHN+_H.FH¢+_H.H.H_m>HmEHmE_._.
`
`

`

`US. Patent
`
`Aug. 19, 2008
`
`Sheet 8 0f 20
`
`US 7,415,530 B2
`
`Receive Initial
`Data Block From
`Input Data
`Stream
`
`600
`
`Time & Count
`Data Block
`
`602
`
`l
`
`Buffer
`Data Block
`
`604
`
`l
`
`Compress Data
`Block with
`Encoder(s)
`
`606
`
`i
`
`Time & Count
`Data Block
`
`608
`
`i
`
`A
`
`FiGURE 6a
`
`

`

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

`

`US. Patent
`
`Aug. 19, 2008
`
`Sheet 10 0f 20
`
`US 7,415,530 B2
`
`700
`
`Retrieve Initial
`Data Block
`From Storage
`Device
`
`l
`
`Time & Count
`Data Block
`
`702
`
`i
`
`Buffer
`Data Block
`
`704
`
`1
`
`Decompress Data
`Btock with
`Decoder(s)
`
`706
`
`i
`
`Time & Count
`Data Block
`
`708
`
`l
`
`A
`
`FIGURE 7a
`
`

`

`US. Patent
`
`Aug. 19, 2008
`
`Sheet 11 0f 20
`
`US 7,415,530 B2
`
`Al
`
`Buffer
`Data Block
`
`1
`
`Determine
`Decompression
`Ratio and
`Bandwidths
`
`t
`
`710
`
`712
`
`Output Accelerated
`Data Block
`
`714
`
`[__
`
`Retrieve Next Data
`Block From
`Storage Device
`
`724
`
`Decompression
`Ratio and Output
`Bandwidth
`Compatible
`'2
`
`Yes 4
`
`Modify:
`Output Bandwidth
`No>
`or Decompression
`or Buffering
`
`716
`
`718
`
`More Data Blocks
`for Output Stream ?
`
`Terminate Retrieval
`Acceleration Process
`
`720
`
`722
`
`FIGURE 7b
`
`

`

`U.S. Patent
`
`Aug. 19,2008
`
`Sheet 12 of 20
`
`US 7,415,530 B2
`
`sunSnoocm
`
`xiE35
`
`..8m.=oww.u
`
`:o_mmoEEo0
`
`ma>._.
`
`cozatomwo
`
`
`
`ozmm:o_mmmaEoo
`
`Eo=m:_E..m.oo
`
`:om_._mqEoO
`
`r._Ec:on<._mt_._m_
`
`N._9c:oO\._wt:m_
`
`mEczootwtsm
`
`x8_mman
`
`._wE:oo
`
`sun
`
`Emuhw
`
`@oo_>momomtwE_
`mmmhoamEma
`
`39.
`
`mmmnwi
`
`
`
`Emawafloum
`
`Awvmo_>wn_
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 19,2008
`
`Sheet 13 of 20
`
`US 7,415,530 B2
`
`EBuoowo
`
`NO350000
`
`
`
`u8Q.tumaQ=32\§Emu
`
`sun53:0omesm
`
`._ot:mxoo_m_EmamEmwbm9833:0mo_%88Ema5%.@.8_>mn_om%..mnr«w.oE_._ommo
`Etzmcozomzxm
`
`
`
`
`Awvmu_>wn_
`
`a.O_..._
`
`co._ouoomn_
`
`S9.
`
`00wt0%.:
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 19,2008
`
`Sheet 14 of 20
`
`US 7,415,530 B2
`
`S930Ema
`
`Emwhw
`
`wmm..o..m
`
`.99.w_moo<
`
`.ommmo8n_
`
`_s_m_n_9mo_m:<
`
`tm>coo
`
`O
`
`$59.582>
`
`3
`
`83
`
`9.2
`
`82
`
`owe.
`
`ox:
`
`Smmaor.
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 19,2008
`
`Sheet 15 of 20
`
`US 7,415,530 B2
`
`
`
`>m_Qm_n_o._.
`
`mo_>mD
`
`>m_am_n_
`
`.m£mE.o.._
`
`END
`
`_m>mEm~_
`
`.Bm.m_moo<
`
`Ema3&5
`
`Emmbm
`
`om:
`
`ow:
`
`om:
`
`ow
`
`_%manor.
`
`
`

`

`U
`
`m
`
`2
`
`00
`
`1m
`
`pl
`
`US 7,415,530 B2
`
`ttm>coom_£_m_o.55.Mt59..o
`
`
`
`S.Emamo_m:<
`
`
`
`L,man.my_£_m_o_m__2mn_Amom.
`
`
`
`
`
`«Vnu._O0moo
`
`W1
`
`
`
`Emwbwwmm_E_2w<_._o“_m:_“ow59:038E80
`
`
`
`Mmum.cum?
`
`
`
` 98m_9_m_a_m_.mm
`
`Nem_m:o_.._
`
`mvm.9589
`
`momtmE_o2.8_m__mwW
`
`
`

`

`U.S. Patent
`
`Aug. 19,2008
`
`Sheet 17 of 20
`
`US 7,415,530 B2
`
`
`.
`.
`.
`Select Initial Serail
`.
`Data
`Input
`
`
`1 12
`3
`
`1306
`
`Latch Parallel
`
`
`.
`.
`
`Digital Input Data
`
`
`Select Initial
`.
`.
`Parallel Digital
`Data With Input
`
`Mux
`
`
`
`
`
`Buffer Parallel
`Digital Data
`
`Select lnitial
`
`.
`Analog Data With
`Input Analog
`Mux
`
`1300
`
`Analog to Digital
`Convert lnput
`Signal
`
`1302
`
`
`
`Buffer Digitized
`Analog Data
`
`1304
`
`
`
`New Analog
`ata Availabl —
`
`
`No
`
`New Parallel
`
`
`I ata Availabl -
`
`
`Convert Serial
`Data Format
`
`1303
`
`
`
`1310
`
`Buffer Serial
`Digital Data
`
`
`
`New Serial
`
`No
`I ata Availabl -
`
`
`
`
`
`
`1314
`
`1316
`
`A
`
`N”
`
`1320
`
`1322
`
`Compress lnput Data Block
`
`1 324
`
`Output Encoded
`Data Block
`
`1326
`
`FIGURE 13
`
`

`

`U
`
`
`
`S.San.mo_m:<
`
`P
`
`00002
`
`hS
`
`2f0001W...
`
`01,33my_m._m_o
`_m__m._mn_A23
`
`totw>coOwomo_m:<
`to2_9a_oa..
`
`
`
`0_E_m_o_m__mm
`
`28
`
`OOO
`
`£8_m_.mm
`
`oomtmt:
`
`US 7,415,530 B2
`
`
`
`mi:031.33
`
`3mm_:w_n_
`
`_m>mEm~.._
`
`._8m.m_woo<
`
`Ema3%.
`
`Emmbw
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 19,2008
`
`Sheet 19 of 20
`
`US 7,415,530 B2
`
`Receive lnitial
`
`Data Block
`
`1500
`
`
`
`Decompress Data
`Block
`
`1502
`
`ata Digitize
`Analog Data
`9
`
`
`
`
`
`
`
`1510 Yes
`Digital Data
`
`No
`
` ls Data
`Digital Parallel
`Data ?
`
`
`
`
`
`Yes
`
`
`
`1508
`
`Buffer Digitized
`Analog Data
`
`Buffer Parallel
`Digital Data
`
`Buffer Serial
`
`FIGURE 15a
`
`

`

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

`

`US 7,415,530 B2
`
`1
`SYSTEM AND METHODS FOR
`ACCELERATED DATA STORAGE AND
`RETRIEVAL
`
`This application is a continuation of U.S. patent applica-
`tion Ser. No. 10/628,795, filed on Jul. 28, 2003, now U.S. Pat.
`No. 7,130,913, which is a continuation of U.S. patent appli-
`cation Ser. No. 09/266,394 filed on Mar 11, 1999, now U.S.
`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 efiiciently 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 efiiciently.
`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 invention, a method for providing
`accelerated data storage and retrieval comprises the steps of:
`receiving a data stream at an input data transmission rate
`which is greater than a data storage rate of a target storage
`device;
`
`

`

`US 7,415,530 B2
`
`3
`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;
`retrieving the compressed data stream from the target stor-
`age device at a rate equal to a data access rate of the target
`storage device; and
`decompressing the compressed data at a decompression
`ratio to provide an output data stream having an output trans-
`mission rate which is greater than the data access rate o