US007 1 8 l 608B2
`
`(12) United States Patent
`Fallon et al.
`
`(10) Patent No.:
`
`(45) Date of Patent:
`
`US 7,181,608 B2
`Feb. 20, 2007
`
`(54)
`
`(75)
`
`SYSTEMS AND METHODS FOR
`ACCELEILATED LOADIN G OF OPERATING
`SYSTEMS AND APPLICATION PROGRAMS
`
`Inventors: James J. Fallon, Arrnonk, NY (US);
`John Buck, Oceanside, NY (US); Paul
`F. Pickel, Bethpage, NY (US); Stephen
`J. MeEerlain, New York, NY (US)
`
`(73)
`
`Assignee:
`
`Realtime 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(b) by 223 days.
`
`(21)
`
`Appl. No.: 09/776,267
`
`(22)
`
`Filed:
`
`Feb. 2, 2001
`
`(65)
`
`(60)
`
`(51)
`
`(52)
`(58)
`
`(56)
`
`Prior Publication Data
`
`US 2002/0069354 A1
`
`Jun. 6, 2002
`
`Related U.S. Application Data
`
`Provisional application No. 60/ 180,114, filed on Feb.
`3, 2000.
`
`Int. Cl.
`G06F 9/24
`
`(2006.01)
`(2006.01)
`G06F 9/00
`(2006.01)
`G06F 13/00
`U.S. Cl.
`.............................. .. 713/2:713/1;711/113
`Field of Classification Search .................. .. 713/2,
`713/], 100; 711/170, 118,113
`See application file for complete search history.
`References Cited
`
`U.S. PA'l'HN'l' ])()(IUMl*',N'l'S
`
`4,302,775 A
`4,394,774 A
`4,574,351 A
`
`ll/1981 Widergren et al.
`7/1983 Widcrgrcn ct al.
`3/1986 Dang et :1].
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`DE
`
`4127518 A1
`
`2/1992
`
`((Ior1tinued)
`OTHER PUBLICATIONS
`
`IBM, Fast Dos Soft Boot, Feb. 1, 1994, vol, 37, Issue 2B, pp.
`185-136.*
`
`(Continued)
`
`Primary E.mn'n’ner—Thon1as Lcc
`Assistant Examz'ner—Suresh K Suryawanshi
`(74) Attorney, Agent, or Fz'rm—Fish & Neave IP Group of
`Ropes & Gray LLP
`
`(57)
`
`ABSTRACT
`
`Systems and methods are provided for accelerated loading
`of operating system and application programs upon system
`boot or application launch. In one aspect, a method for
`providing accelerated loading of an operating system
`includes maintaining a list of boot data used for booting a
`computer system, preloading the boot data upon initializa-
`tion of the computer system, and servicing requests for boot
`data from the computer system using the preloaded boot
`data. The boot data may comprise program code associated
`with an operating system of the computer system, an appli-
`cation program, and a combination thereof. The boot data is
`retrieved from a boot device and stored in a cache memory
`device. The boot data is stored in a compressed format on the
`boot device and the preloaded boot data is decompressed
`prior to transmitting the preloaded boot data to the request-
`ing system.
`
`4,127,518 A
`
`ll/1978 Coy eta].
`
`31 Claims, 13 Drawing Sheets
`
`DATA
`COMPRESSION
`ENGINE
`
`
`
`APPLE 1001
`
`1
`
`APPLE 1001
`
`

`
`US 7,181,608 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`4,593,324
`4,682,150
`4,730,348
`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
`5,028,922
`5,045,848
`5,045,852
`5,046,027
`5,049,881
`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,452,287
`5,461,679
`5,467,087
`5,471,206
`5,479,587
`5,486,826
`5,495,244
`5,506,844
`5,506,872
`5,530,845
`5,533,051
`5,535,356
`
`D>B>>Il>D>I>>>D>>>21>II>iI>>>>I1>D>i>II>D>>>D>>il>>i1>iI>>>>>>il>I1>D>>D>>>>D>il>iI>>.>>>3>I>i>D>I>>>D>>D>il>iI>D>II>>>I1>>D>I1>{I>
`
`6/1986
`7/1987
`3/1988
`6/1988
`2/1989
`9/1989
`10/1989
`10/1989
`12/1989
`3/1990
`5/1990
`9/1990
`10/1990
`7/1991
`9/1991
`9/1991
`9/1991
`9/1991
`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
`9/1995
`10/1995
`11/1995
`11/1995
`12/1995
`1/1996
`2/1996
`4/1996
`4/1996
`6/1996
`7/1996
`7/1996
`
`Ohkubo et al.
`Mathcs ct al.
`MacCrisken
`Wright
`Makansi et a],
`Van Maren et al.
`Tsukiyama et al.
`Storer
`Dinan et al.
`Swanson
`O’l3rien el al.
`Herrmann
`Hori et al.
`Huang
`Fascenda
`Mitchell et al.
`Taalfe et 21].
`Gibson et al.
`Langdon, Jr. et al.
`Dinwiddie, Jr. et al.
`Szymborski
`Chu
`Rabin et al.
`Lantz
`Taalfe et al.
`Keith et al.
`Ilasegawa el al.
`Chevion et al.
`Hiyama et al.
`Normile et al.
`Westaway et al.
`Ett
`Dangi et al.
`Miller et al.
`Hannon, J1‘.
`Seroussi et al.
`Jackson
`O‘Brien et al.
`Osterlund et al.
`Toms et al.
`Balkanski et al.
`Barrett
`Carr
`Fcigenbaum ct 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
`Dicccco
`Normile et al.
`Chu
`Allen et al.
`Campbell et al.
`Remillard
`Jeong et al.
`Rao
`Mohler
`Hiatt et al.
`James
`Kim et al.
`
`........ .. 713/l
`
`5,537,658
`5,557,551
`5,557,668
`5,557,749
`5,561,824
`5,574,952
`5,576,953
`5,583,500
`5,590,306
`5,596,674
`5,604,824
`5,606,706
`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,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,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,832,037
`5,832,126
`5,836,003
`5,838,996
`5,839,100
`5,841,979
`5,847,762
`5,861,824
`5,861,920
`
`>-3>il>>D>B>>>3>>3>B>Il>>D>>>>D>>D>3>>>>>>3>>>D>>>1?->>>Il>>3>>3>>L1>>>B>>>>3>>>D>>>>B>>i1>>>D>>>>3>>>B>>>>
`
`7/1996
`9/1996
`9/1996
`9/1996
`10/1996
`11/1996
`11/1996
`12/1996
`12/1996
`1/1997
`2/1997
`2/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
`7/1997
`7/1997
`7/1997
`7/1997
`8/1997
`8/1997
`9/1997
`9/1997
`9/1997
`10/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
`11/1998
`11/1998
`11/1998
`11/1998
`11/1998
`l 1/1998
`12/1998
`1/1999
`1/1999
`
`Bakke et al.
`Craft
`Brady
`Norris
`Carreiro et al.
`Brady et al.
`Hugentobler
`Allen et al.
`Watanabe et al,
`Bhandari et al.
`Chui et al.
`Takamoto ct al.
`Stone
`Walker
`Choi
`Rynderman et al.
`Kim et al.
`Bakke et al.
`Craft
`Miller et al.
`Moskowitz ct al.
`Carreiro et al.
`Fay et al.
`Shinagawa 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.
`Konno
`Mac I )o11ald ct al.
`Wise et al.
`Kikinis
`Nakano et al.
`Schwartz et al,
`Lee et al.
`Kikinis
`Kirsten
`Frzmaszek et al.
`Huang et al.
`Jericevic et al,
`Nakazato et al.
`DeMoss et al,
`Inoue et al.
`Rostoker et al.
`Hashimoto et al.
`Callahan
`Israelsen et al.
`Kawashima et al.
`Sekine et al.
`Yajima
`
`Canlield et al.
`Dobson et al.
`Canfield et al.
`Park
`Tanaka
`Sadeh
`deCa.rmo
`Wegener
`Schulhof et al.
`Canfield
`Ryu et al.
`Mead et al.
`
`2
`
`

`
`US 7,181,608 B2
`Page 3
`
`5,867,167
`5,870,036
`5,870,087
`5,872,530
`5,883,975
`5,886,655
`5,889,961
`5,915,079
`5,917,438
`5,920,326
`5,936,616
`5,949,355
`5,955,976
`5,960,465
`5,964,842
`5,968,149
`5,973,630
`5,974,471
`5,982,723
`5,991,515
`5,996,033
`6,000,009
`6,002,411
`6,003,115
`6,011,901
`6,014,694
`6,026,217
`6,028,725
`6,031,939
`6,032,148
`6,061,398
`6,073,232
`6,075,470
`6,094,634
`6,097,520
`6,104,389
`6,105,130
`6,128,412
`6,141,053
`6,145,069
`6,169,241
`6,172,936
`6,173,381
`6,182,125
`6,192,082
`6,195,024
`6,226,667
`6,226,740
`6,253,264
`6,272,627
`6,272,628
`6,282,641
`6,309,424
`6,317,714
`6,330,622
`6,345,307
`6,421,387
`6,434,168
`6,434,695
`6,442,659
`6,449,682
`6,452,602
`6,463,509
`6,487,640
`6,489,902
`6,513,113
`6,529,633
`6,539,456
`6,542,644
`
`i>>I1>I1>I>>.>>>I1>>i>iI>I>>>D>>>3>3>i>D>>>D>Cl>3>>D>>D>>>>>il>>D>>
`
`>3
`
`B1
`B1
`B1'’'‘
`B1
`B1
`B1
`B1"‘
`B1*
`B1
`B1
`B1
`B1
`B1
`B1
`B1
`B1
`B1
`B1
`B1"‘
`B1
`B1
`B1
`B1"‘
`B1
`B2
`B1
`B1
`B2""
`B1
`
`2/1999
`2/1999
`2/1999
`2/1999
`3/1999
`3/1999
`3/1999
`6/1999
`6/1999
`7/1999
`8/1999
`9/1999
`9/1999
`9/1999
`10/1999
`10/1999
`10/1999
`10/1999
`11/1999
`11/1999
`11/1999
`12/1999
`12/1999
`12/1999
`1/2000
`1/2000
`2/2000
`2/2000
`2/2000
`2/2000
`5/2000
`6/2000
`6/2000
`7/2000
`8/2000
`8/2000
`8/2000
`10/2000
`10/2000
`11/2000
`1/2001
`1/2001
`1/2001
`1/2001
`2/2001
`2/2001
`5/2001
`5/2001
`6/2001
`8/2001
`8/2001
`8/2001
`10/2001
`11/2001
`12/2001
`2/2002
`7/2002
`8/2002
`8/2002
`8/2002
`9/2002
`9/2002
`10/2002
`11/2002
`12/2002
`1/2003
`3/2003
`3/2003
`4/2003
`
`Deering
`Franaszek et al.
`Chau
`Domyo el al.
`N arita et al.
`Rust
`Dobbek
`Vondran, Jr. et al.
`Ando
`Rentschler et al.
`Torborg, Jr. et al.
`Panaoussis
`Ilealh
`Adams
`Packard
`Jaquette et al.
`Heath
`Belt
`Kamatani
`Fall et al.
`Cl1iu—Hao
`Brady
`Dye
`Spear et al.
`Kirsten
`Aharoni et al.
`Adiletta
`Blumenau
`Gilbert et al.
`Wilkes
`Satoh et al.
`Kroeker et al.
`Little et al.
`Yahagi et al.
`Kadnier
`Ando
`Wu ct al.
`Satoh
`Saukkonen
`Dye
`Shimizu
`Kitazaki
`Dye ............... ..
`Borella et al.
`Moriarty et al.
`Fallon
`Matthews et al.
`
`........ .. 711/137
`
`.... ..
`
`........... .. 713/1
`
`........ .. 711/170
`
`........ .. 709/203
`
`
`
`Aguilar et al.
`Christensen
`Fallon
`Del Castillo et al.
`Schaefer
`Booth
`Rhee
`Kari
`Esfahani et al.
`Blumenau
`Toorians
`Morein
`Teoman et al.
`Lipasti
`Heath
`Kobayashi
`Easwar et al.
`Stewart
`.......... ..
`Satoh
`
`..
`
`........... .. 713/2
`
`........ .. 711/137
`
`........ .. 711/113
`
`6,590,609
`6,601,104
`6,604,158
`6,606,040
`6,606,413
`6,609,223
`6,618,728
`6,624,761
`6,661,839
`6,704,840
`6,711,709
`6,745,282
`6,748,457
`6,856,651
`6,888,893
`7,054,493
`2001/0032128
`2002/0037035
`2002/0104891
`2002/0126755
`2003/0034905
`2003."0084238
`2003/0142874
`
`B1
`B1
`B1
`B2
`B1
`B1
`B1
`B2
`B1
`B2 *
`B1
`B2
`B2
`B2
`B2
`B2
`A1
`Al
`Al
`A1
`A1
`A1
`A1
`
`7/2003
`7/2003
`8/2003
`8/2003
`8/2003
`8/2003
`9/2003
`9/2003
`12/2003
`3/2004
`3/2004
`6/2004
`6/2004
`2/2005
`5/2005
`5/2006
`10/2001
`3/2002
`8/2002
`9/2002
`2/2003
`5/2003
`7/2003
`
`Kitade et al.
`Fallon
`Fallon
`Abdal
`Zeineh
`Wolfgang
`Rail
`Fallon
`Ishida et al.
`Nalawadi et al.
`York
`Okada ct al.
`Fallon
`Singh
`Li et al.
`Schwartz
`Kepecs
`Singh
`Otto
`Li et al.
`Anton ct al.
`Okada et al.
`Schwartz
`
`......... .. 711/118
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`GB
`JP
`JP
`JP
`W0
`W0
`W0
`W0
`
`A3
`
`0164677
`0185098
`0283798
`0405572
`0493130
`0718751
`0587437
`0595406
`0718751
`2162025
`06051989 A *
`9188009
`11149376
`WO 9414273
`WO 9429852
`WO 9502873
`WO 9748212
`
`12/1985
`6/1986
`9/1988
`6/1990
`12/1991
`6/1992
`9/1993
`5/1994
`6/1996
`1/1986
`2/1994
`1/1996
`6/1999
`6/1994
`12/1994
`1/1995
`6/1997
`
`OTHER PUBLICATIONS
`
`Rice, Robert F., “Some Practical Universal Noiseless Coding Tech-
`niques", Jet Propulsion Laboratory, Pasadena, California, JPL Pub-
`licatlon 79-22, Mar. 15, 1979.
`Anderson, J., et al. “Codec squeezes color teleconferencing through
`digital telephone lines”, Electronics 1984, pp. 13-15.
`Venbrux, Jack, “A VLSI Chip Set for High-Speed Lossless Data
`Compression”, IEEE Trans. On Circuits and Systems for Video
`Technology, vol. 2, No. 44, Dec. 1992, pp. 381-391.
`“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 Predetern1ined 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, US., New York,
`IEEE, Sep. 16, 1996, pp. 825-8286.
`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-3263.
`
`* cited by examiner
`
`3
`
`

`
`U.S. Patent
`
`US 7,181,608 B2
`
`
`
`
`
`minWmz_ezm_m_moEmm:z_mxoézo_m$E_2ooF9%:HvaaE3
`
`mm_o<#_Ez_mam
`
`
`
`IIIIICIIIIIIIIIIIIICIIIIIIIIIIIIUIIIIIII.IIIIIIIIIIIIIIIIIIllI.!II|II.IIIIIIIII
`
`—._®_n_
`
`
`
`mammmE:s_oozo_mz<n_xmmo22:
`
`4
`
`
`

`
`U.S. Patent
`
`Feb. 20,2007
`
`Sheet 2 of 13
`
`US 7,181,608 B2
`
`mamzo_mz<n_xm_moz_<s_
`
`N._U_u_
`
`
`
`O:om._.<o_om_n_8
`
`_
`
`mo<n_mm_._.z_vaa0
`
`._
`
`m:m<s__>_<mmom;
`
`
`
`mo_>m_o200..
`
`m_o<u_E:,__mamm_.
`
`gm!
`
`mowmmoomm
`
`Im
`
`o$9
`
`._<oO._
`
`mam
`
`III
`%
`
`>mos_m__>_m.__._.<._o>.zoz
`E15mozmsazom
`m._._:om_o.5$28
`
`wmam;$5%_8
`
`E
`
`8
`
`5
`
`
`
`

`
`U.S. Patent
`
`Feb. 20,2007
`
`Sheet 3 of 13
`
`US 7,181,608 B2
`
`a%mommwooi
`
`ma._<oo._
`
`monae
`
`mama
`
`ImfiéomE2
`
`9.mm__.:o
`
`m
`
`or.
`
`mo._.n_<o<mazoazém
`
`macawmo
`
`_._m<._n=_>_om
`
`.~
`
`N
`
`5
`
`w._._:om_on5mason.wEma
`mmE:s_ou
`
`6
`
`

`
`U.S. Patent
`
`Feb. 20, 2007
`
`Sheet 4 of 13
`
`US 7,181,608 B2
`
`5m§_s_éSE
`
`o_oo._
`
`Em_<_>_s_EooE
`
`
`
`m_o_>m_oo_w9
`
`$15moImséom
`
`
`
`EOE:m._=5o>-zoz
`
`m._.Som_o.5E22wmam$5n__>_8
`
`7
`
`
`

`
`U.S. Patent
`
`5
`
`US 7,181,608 B2
`
`
`
`W.Lmommaog
`
`momma
`
`7am $o§m;__v_w_n_
`
`mm,2m$o§m:z:_m_n_
`
`M3m
`
`3m8209
`
`EHém
`a
`
`.8
`
`m.G_n_
`
`am_§s_§oE
`
`gas
`
`mom
`
`IQ.EEO
`
`152200I£85azomaoog
`amm:
`
`mcama.5$30“.
`
`mm
`
`8
`
`
`
`

`
`U.S. Patent
`
`Feb. 20, 2007
`
`Sheet 6 of 13
`
`Us 7,181,608 B2
`
`
`
`ENSURE ENOUGH 58
`
`DELAY FOR VOLATILE
`|I_I\(I)I'T||AI;Ll|)ZIA\'(f|IT)T\I
`
`
`
`
`TO BE COMPLETE
`
`
`
`LATCH DATA BYTE
`INTO VOLATILE
`LOGIC DEVICE
`
`59
`
`so
`
`CHECK BYTE
`COUNT LESS THAN N0
`
`
`PRE§,,':f8'EF'E°
`
`
`A
`°
`
`YES
`
`3
`
`DSP READS NEXT DATA
`BYTE OF DEVTCE
`PROGRAM DATA
`
`61
`
`so
`
`AS3597 DSP
`RESET 3'G"'AL
`
`51 COPY nsp BOOT LOADER
`FROM NON VOLATILE
`LOGIC DEVICE
`
`52
`
`DSP BEGINS
`EXECUTION
`
`53
`
`CONFIGURE I/O PORTS
`
`FOR VOLATILE LOGIC
`DEVICE PROGRAMMING
`
`54
`
`55
`
`INITIALIZE VOLATILE
`LOGIC DEVICE
`
`READ
`CONFIGURATION
`DATA
`
`A
`
`CLEAN BYTE
`COUNTER
`AND
`READ 1ST
`CONFIGURATION
`
`LOAD 1ST
`CONFIGURATION
`DATA BYTE
`INTO DSP I/O
`
`
`
`
`
`57
`
`62
`
`63
`
`64
`
`'“°%%“IEII‘ILS”E
`
`LOAD DATA BYTE
`INTO DSP IIO
`
`AND
`LATCH INTO
`PROGRAMMABLE
`LOGIC
`
`
`
`
`
`DATA BYTE DELAY 20 nsec
`DEVICE
`
`9
`
`

`
`U.S. Patent
`
`Feb. 20, 2007
`
`Sheet 7 of 13
`
`Us 7,181,608 B2
`
`
`
`
`
`
`
`DSP READ LAST
`DATA BYTE & LATCH INTO
`
`VOLATILE LOGIC
`DEVICE
`AND
`POLL VOLATILE LOGIC
`
`
`DEVICE TO ENSURE
`
`
`PROGRAMMING
`
`
`COMPLETE
`
`
`66
`
`
`SUCCESSFUL
`
`
`PROGRAMMING
`
`
`
`
`CONTINUE DATA STORAGE
`CONTROLLER
`INITIALIZATION
`
`68
`
`FLAG ERROR
`REPEAT
`ENTIRE PROCESS
`
`
`
`FIG. 6b
`
`10
`
`10
`
`

`
`U.S. Patent
`
`Feb. 20, 2007
`
`Sheet 8 of 13
`
`Us 7,181,608 B2
`
`
`
`
`
`RETREIVE REQUESTED
`BOOT DATA FROM DISK
`
`
`
`BOOT PROCESS
`
`COMPLETE
`
`?
`
`
`
`11
`
`

`
`U.S. Patent
`
`Feb. 20, 2007
`
`Sheet 9 of 13
`
`Us 7,181,608 B2
`
`75
`
` POWEFI-UP
`OR SYSTEM
`
`RESET
`
`YES '
`75
`
`
`
`77 RETRIEVE & READ LIST
`
`PREFETCH DATA BLOCKS
`SPECIFIED IN LIST
`
`78
`
`79 COMMENCE BOOT PROCESS
`
`RECEIVE READ REQUEST
`FOR BOOT DATA
`
`0
`
`IS
`REQUESTED
`
`BOOTDATA
`
`PRELQADED
`N0
`
`2
`
`FIETFIIEVE REQUESTED BOOT
`DATA FROM BOOT DEVICE
`
`3
`
`UPDATE LIST TO INCLUDE
`BOOT DATA NOT PREVIOUSLY
`SPECIFIED IN LIST
`
`FIG. 7b
`
`12
`
`
`
`‘°’§§é’I%'§\§Eé"é5?aTT%S;II'f
`
`84
`
`
`IS ANY BOOT
`
`DATA NOT REQUESTED N0
`DURING BOOT
`PROCESS
`
`9
`
`
`
`UPDATE LIST TO EXCLUDE
`BOOT DATA NOT PREVIOUSLY
`SPECIFIED IN LIST
`
`12
`
`

`
`U.S. Patent
`
`Feb. 20, 2007
`
`Sheet 10 of 13
`
`Us 7,181,608 B2
`
`
`
`RECEIVE REQUEST FOR APPLICATION
`
`DATA ASSOICATED WITH
`
`LAUNCHED APPLICATION
`
`
`
`LAUNCH
`
`PROCESS
`
`
`
`
`
`
`COMPLETE
`
`?
`
`STORE LIST
`
`FIG. 8a
`
`13
`
`13
`
`

`
`U.S. Patent
`
`Feb. 20, 2007
`
`Sheet 11 of 13
`
`Us 7,181,608 B2
`
`
`
`APPLICATION
`LAUNCHED
`?
`
`
`
`SERVICE REQUEST USING
`PRELOADED
`
`
`
`
`
`REQUESTED
`APPLICATION DATA
`PRELOADED
`?
`
`
`
`
`
`101
`
`N0
`
`
`
`APPLICATION DATA
`
`RETRIEVE REMAINDER OF
`
`APPLICATION DATA
`FROM DISC
`
`
`
`
`
`
`
`UPDATE LIST TO INCLUDE
`APPLICATION DATA NOT
`
`PREVIOUSLY SPECIFIED IN LIST
`
`
`
`UPDATE LIST TO EXCLUDE
`
`APPLICATION
`
`DATA PREVIOUSLY
`
`SPECIFIED IN LIST
`
`
`
`FIG. 8b
`
`14
`
`14
`
`

`
`U.S. Patent
`
`Feb. 20, 2007
`
`Sheet 12 of 13
`
`Us 7,181,608 B2
`
`SE38%
`
`%z_s§§55%
`
`l"—'_'_'—'—'
`
`'_'-"—'
`
`Q2m:E,_=§Eu_=m
`
`E58%
`
`mgooozmS5
`
`
`.m$8o_,m_._§___§oo
`
`
`
`._o_H,%_W_,M._¢_m<Mmw.%smgooozmv_.,§Eas§2z_.35
`
`L-_.__....-__.-__-
`
`I'I‘I|IIIUIIIIIIIIIII‘IIIIIIIIIIIIIIIIIIIII|I|IIINIIIIIin
`
`m._®_u_&:
`
`
`
`
`
`15
`
`15
`
`
`
`

`
`U.S. Patent
`
`Feb. 20, 2007
`
`US 7,181,608 B2
`
`___
`
`
`
`¢oE_$$o._.=._zE<._.<n_
`
`
`
`
`
` !.._m5Easeweflm.._m_Eu_..5m..._s_>_<m...E.._Ea5&8sfigoaamo:_5ma§Ea_,___,_§_5
`EaSE5_gfiooogommmmmmzoo_afiooomo
`_:...................................
`
`
`
`16
`
`
`
`2GE\2:
`
`16
`
`
`

`
`US 7,181,608 B2
`
`1
`SYSTEMS AND METHODS FOR
`ACCELERATED LOADING OF OPERATING
`SYSTEMS AND APPLICATION PROGRAMS
`
`(IR()SS-RlCl"lLRIINCH 'l'() Rll,I.A'l'|",])
`APPLICATION
`
`This application is based on a U.S. provisional application
`Ser. No. 60/180,114, filed on Feb. 3, 2000, which is fully
`incorporated herein by reference.
`
`BACKGROUND
`
`1. Technical Field
`
`The present invention relates generally to systems and
`methods for providing accelerated loading of operating
`system and application programs upon system boot or
`application launch and, more particularly, to data storage
`controllers employing lossless and/or lossy data compres-
`sion and decompression to provide accelerated loading of
`operating systems and application programs.
`2. Description of the Related Art
`Modern computers utilize a hierarchy of memory devices.
`To achieve maximum performance levels, modem proces-
`sors utilize onboard memory and on board cache to obtain
`high bandwidth access to both program and data. Limita-
`tions in process technologies currently prohibit placing a
`sufiicient quantity of onboard memory for most applications.
`Thus, in order to olfer suflicient memory for the operating
`system(s), application programs, and user data, computers
`often use various forms of popular oif-processor high speed
`memory including static random access memory (SRAM),
`synchronous dynamic random access memory (SDRAM),
`synchronous burst static ram (SBSRAM). Due to the pro-
`hibitive cost of the high-speed random access memory,
`coupled with their power volatility, a third lower level of the
`hierarchy exists for non-volatile mass storage devices.
`Furthermore, mass storage devices olfer increased capac-
`ity and fairly economical data storage. Mass storage devices
`(such as a “hard disk”) typically store the operating system
`of a computer system, as well as applications and data and
`rapid. access to such data is critical l.o system performance.
`The data storage and retrieval bandwidth of mass storage
`devices, however, is typically much less as compared with
`the bandwidth of other elements of a computing system.
`Indeed, over the last decade, although computer processor
`performance has improved by at
`least a factor of 50,
`magnetic disk storage performance has only improved by a
`factor of 5. Consequently, memory storage devices severely
`limit the performance of consumer, entertainment, ofiice,
`workstation, servers, and mainframe computers for all disk
`and memory intensive operations.
`The ubiquitous lntemet combined with new multimedia
`applications has put tremendous emphasis on storage volu-
`metric density, storage mass density, storewidth, and power
`consumption. Specifically, storage density is limited by the
`number olibits that are encoded in a mass storage device per
`unit volume. Similarly mass density is defined as storage bits
`per unit mass. Storewidth is the data rate at which the data
`may be accessed. There are various ways of categorizing
`storewidth in terms, several of the more prevalent metrics
`include sustained continuous storewidth, burst storewidth,
`and random access storewidth, all typically measured in
`megabytes/sec. Power consumption is canonically defined in
`terms of power consumption per bit and may be specified
`under a number of operating modes including active (While
`data is being accessed and transmitted) and standby mode.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`Hence one fairly obvious limitation within the current art is
`the need for even more volume, mass, and power eflicient
`data storage.
`Magnetic disk mass storage devices currently employed
`in a variety of home, business, and scientific computing
`applications suffer from significant seek-time access delays
`along with profound read/write data rate limitations. Cur-
`rently the fastest available disk drives support only a sus-
`tained output data rate in the tens of megabytes per second
`data rate (MB/sec). This is in stark contrast to the modern
`Personal Computer’s Peripheral Component Interconnect
`(PCI) Bus’s low end 32 bit/33 Mhz input/output capability
`of 264 MB/sec and the PC’s 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), Fibre Channel, AT
`Attachment UltraDMA/66/ 100, Serial Storage Architecture,
`and Universal Serial Bus ofler only higher data transfer rates
`through intermediate data buJ.lering in random access
`memory. These interconnect strategies do not address the
`fundamental problem that all modem magnetic disk storage
`devices for the personal computer marketplace are still
`limited by the same typical physical media restrictions. In
`practice, faster 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 and redundant array of independent disks (RAID).
`RAID systems often afl°ord the user the benefit of
`increased data bandwidth for data storage and retrieval. By
`simultaneously accessing two or more disk drives, data
`bandwidth may be increased at a maximum rate that is linear
`and directly proportional to the number of disks employed.
`Thus another problem with modem data storage systems
`utilizing RAID systems is that a linear increase in data
`bandwidth requires a proportional number of added disk
`storage devices.
`Another problem with most modem mass storage devices
`is their inherent unreliability. Many modem mass storage
`devices utilize rotating assemblies and other types of elec-
`tromechanical components that possess failure rates one or
`more orders of magnitude higher than equivalent solid-state
`devices. RAID systems employ data redundancy distributed
`across multiple disks to enhance data storage and retrieval
`reliability. In the simplest case, data may be explicitly
`repeated on multiple places on a single disk drive, on
`multiple places on two or more independent disk drives.
`More complex techniques are also employed that support
`various trade-ofi°s between data bandwidth and data reliabil-
`
`ity.
`Standard types of RAID systems currently available
`include RAID Levels CI, 1, and 5. The configuration selected
`depends on the goals to be achieved. Specifically data
`reliability, data validation, data storage/retrieval bandwidth,
`and cost all play a role in defining the appropriate RAID data
`storage solution. RAID level 0 entails pure data striping
`across multiple disk drives. This increases data bandwidth at
`best linearly with the number of disk drives utilized. Data
`reliability and validation capability are decreased. A failure
`of a single drive results in a complete loss of all data. Thus
`another problem with RAID systems is that
`low cost
`improved bandwidth requires a significant decrease in reli-
`ability.
`1 utilizes disk mirroring where data is
`RAID Level
`duplicated on an independent disk subsystem. Validation of
`data amongst the two independent drives is possible if the
`data is simultaneously accessed on both disks and subse-
`
`17
`
`17
`
`

`
`US 7,181,608 B2
`
`3
`quently compared. This tends to decrease data bandwidth
`from even that of a single comparable disk drive. In systems
`that offer hot swap capability, the failed drive is removed and
`a replacement drive is inserted. The data on the failed drive
`is then copied in the background while the entire system 5
`continues to operate in a performance degraded but fully
`operational mode. Once the data rebuild is complete, normal
`operation resumes. Hence, another problem with RAID
`systems is the high cost of increased reliability and associ-
`ated decrease in performance.
`RAID Level 5 employs disk data striping and parity error
`detection to increase both data bandwidth and reliability
`simultaneously. A minimum of three disk drives is required
`for this technique. In the event of a single disk drive failure,
`that drive may be rebuilt from parity and other data encoded
`on disk remaining disk drives. In systems that offer hot swap
`capability, the failed drive is removed and a replacement
`drive is inserted. The data on the failed drive is then rebuilt
`
`l0
`
`15
`
`in the background while the entire system continues to
`operate in a performance degraded but fully operational
`mode. Once the data rebuild is complete, normal operation
`resumes.
`
`Thus another problem with redundant modem mass stor-
`age devices is the degradation of data bandwidth when a
`storage device fails. Additional problems with bandwidth
`limitations and reliability similarly occur within the art by
`all other forms of sequential, pseudo-random, and random
`access mass storage devices. These and other limitations
`within the current art are addressed by the present invention.
`
`SUMMARY OF THE INVENTION
`
`The present invention is directed to systems and methods
`for providing accelerated loading of operating system and
`application programs upon system boot or application
`launch and, more particularly, to data storage controllers
`employing lossless and/or
`lossy data compression and
`decompression to provide accelerated loading of operating
`systems and application programs.
`In one aspect of the present invention, a method for
`providing accelerated loading of an operating system coni-
`prises the steps of: maintaining a list of boot data used for
`booting a computer system; preloading the boot data upon
`initialization of the computer system; and servicing requests
`for boot data from the computer system using the preloaded
`boot data. The boot data may comprise program code
`associated with an operating system ofthe computer system,
`an application program, and a combination thereof. In a
`preferred embodiment, the boot data is retrieved from a boot
`device and stored in a cache memory device.
`In another aspect, the method for accelerated loading of
`an operating system comprises updating the list of boot data
`during the boot process. The step of updating comprises
`adding to the list any boot data requested by the computer
`system not previously stored in the list and/or removing
`from the list any boot data previously stored in the list and
`not requested by the computer system.
`In yet another aspect, the boot data is stored in a com-
`pressed format on the boot device and the preloaded boot
`data is decompressed prior to transmitting the preloaded
`boot data to the requesting system.
`In another aspect, a method for providing accelerated
`launching of an application program comprises the steps of:
`maintaining a list of application data associated with an
`application program; preloading the application data upon
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`launching the application program; and servicing requests
`for application data from a computer system using the
`preloaded application data.
`In yet another aspect, a boot device controller for provid-
`ing accelerated loading of an operating system of a host
`system comprises: a digital signal processor (DSP); a pro-
`grammable logic device, wherein the programmable logic
`device is programmed by the digital signal processor to (i)
`instantiate a first interface for operatively interfacing the
`boot device controller to a boot device and to (ii) instantiate
`a second interface for operatively interfacing the boot device
`controller to the host system; and a non-volatile memory
`device, for storing logic code associated with the DSP, the
`first interface and the second interface, wherein the logic
`code comprises instructions executable by the DSP for
`maintaining a list of boot data used for booting the host
`system, preloading the boot data upon initialization of the
`host system, and servicing requests for boot data from the
`host system using the preloaded boot data. The boot device
`controller fiirther includes a cache memory device for stor-
`ing the preloaded boot data.
`The present invention is realized due to recent improve-
`ments in processing speed, inclusive of dedicated analog and
`digital hardware circuits, central processing units, (and any
`hybrid. combinations thereof), 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 from the following
`detailed description of preferred embodiments that is to be
`read in connection with the accompanying drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of a data storage controller
`according to one embodiment of the present invention;
`FIG. 2 is a block diagram ol‘ a data storage controller
`according to another embodiment of the present invention;
`FIG. 3 is a block diagram of a data storage controller
`according to another embodiment of the present invention;
`FIG. 4 is a block diagram of a data storage controller
`according to another embodiment of the present invention;
`FIG. 5 is a block diagram of a data storage controller
`according to another embodiment of the present invention;
`FIGS. 6a and 61) comprise a flow diagram of a method for
`initializing a data storage controller according to one aspect
`of the present invention;
`FIGS. 7a and 7b comprise a flow diagram of a method for
`providing accelerated loading of an operating system and/or
`application programs upon system boot, according to one
`aspect of the present invention;
`FIGS. 8a and 8b comprise a flow diagram of a method for
`providing accelerated loading of application programs
`according to one aspect of the present invention;
`FIG. 9 is a diagram of an exemplary data compression
`system that may be employed in a data storage controller
`according to the present invention; and
`FIG. 10 is a diagram of an exemplary data decompression
`system that may be employed in a data storage controller
`according to the present invention.
`
`18
`
`18
`
`

`
`US 7,181,608 B2
`
`5
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`In the following description, it is to be understood that
`syste1n elements having equivalent or similar l'uncLionalily
`are designated 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 hard-
`ware, software, firmware, or a combination thereof. Prefer-
`ably, the present invention is implemented on a computer
`platform including hardware such as one or more central
`processing units (CPU) or digital signal processors (DSP), a
`random access memory (RAM), and input/output
`(I/O)
`interface(s). The computer platform may also include an
`operating system, microinstruction code, and dedicated pro-
`cessing hardware utilizing combinatorial logic or finite state
`machines. The various processes and functions described
`herein may be either part of the hardware, microinstruction
`code or application programs that are executed via the
`operating system, or any combination thereof.
`It is to be further understood that, because some of the
`constituent system components described herein are prefer-
`ably implemented as software modules, the actual system
`connections shown in the Figures may dilfer depending
`upon the manner in that the systems are programmed. It is
`to be appreciated that special purpose microprocessors,
`dedicated hardware, or and combination thereof may be
`employed to implement the present invention. Given the
`teachings herein, one of ordinary skill in the related art will
`be able to contemplate these and similar implementations or
`configurations of the present invention.
`
`1. System Architectures
`The present invention is directed to data storage control-
`lers that provide increased data storage/retrieval rates that
`are not otherwise achievable using conventional disk con-
`troller systems and protocols to store/retrieve data to/from
`mass storage devices. The concept of “accelerated” data
`storage and retrieval was introduced in U.S. patent applica-
`tion Ser. No. 09.:"266,394,
`filed Mar. 11, 1999, entitled
`“System and Methods For Accelerated Data Storage and
`Retrieval”, which is now U.S. Pat. No. 6,601,104 and U.S.
`patent application Ser. No. 09/481,243, filed Jan. 11, 2000,
`entitled “System and Methods For Accelerated Data Storage
`and Retrieval,” which is now U.S. Pat. No. 6,604,158, both
`of which are commonly assigned and incorporated herein by
`reference. In general, as described in the above-incorporated
`applications, “accelerated” data storage comprises receiving
`a digital data stream at a data transmission rate which is
`greater than the data storage rate of a target storage device,
`compressing the input stream at a compression rate that
`increases the elfective data storage rate of the target storage
`dev