US 7,190,284 B1
`(10) Patent No:
`a2) United States Patent
`Dyeetal.
`(45) Date of Patent:
`Mar. 13, 2007
`
`
`US007190284B1
`
`(76)
`
`(54) SELECTIVE LOSSLESS, LOSSY, OR NO
`COMPRESSION OF DATA BASED ON
`ADDRESS RANGE, DATA TYPE, AND/OR
`REQUESTING AGENT
`Inventors: Thomas A. Dye, 6621 Candle Ridge
`.
`Cove, Austin, TX (US) 78731; Manuel
`J. Alvarez, II, 8800 Pepper Rock Dr.,
`Austin, TX (US) 78717, Peter Geiger,
`10407 Treasure Island Dr., Austin, TX
`(US) 78730
`
`( ae ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 1540) by 0 days.
`.
`(21) Appl. No.: 09/239,659
`.
`(22)
`Filed:
`Jan. 29, 1999
`
`too.
`Related U.S. Application Data
`(63) Continuation-in-part of application No. 08/916,464,
`:
`filed on Aug. 8, 1997, now Pat. No. 6,173,381, which
`.
`.
`.
`.
`Loe
`is a continuation-in-part of application No. 08/463,
`106, filed on Jun. 5, 1995, now abandoned, whichis
`a continuation-in-part of application No. 08/340,667,
`filed on Nov. 16, 1994, now Pat. No. 6,002,411.
`
`(51)
`
`Int. Cl.
`(2006.01)
`HO3M 730
`(2006.01)
`GOSF 12/00
`:
`.
`.
`(52) US. CM. ceceeeeeees 341/51, 341/87; 710/68;
`711/170; 382/232; 382/233; 382/244
`(58) Field of Classification Search ................ 382/232,
`382/233, 244; 710/68; 709/247; 341/51,
`341/87; 711/170
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,008,460 A
`4,688,108 A
`4,876,541 A
`
`2/1977 Bryantet al. «0... 395/463
`8/1987 Cotton et al. «0.0.0... 358/261.1
`10/1989 Storer
`
`4,881,075 A
`LU/L989 Weng w.eccccccscscseeseees 341/87
`4,903,317 A *
`wee 358/19
`2/1990 Nishihara et al.
`.
`
`4,987,541 A *
`1/1991 Levente etal. on. 701/35
`5,003,307 A
`3/1991 Whiting et al.
`5,016,009 A
`5/1991 Whiting et al.
`een A
`tog niin et al.
`136,
`oshidaet al.
`5,146,221 A
`9/1992 Whitinget al.
`5,150,430 A
`9/1992 Chu
`5,155,484 A
`10/1992 Chambers, IV
`5,237,460 A
`8/1993 Miller et al. we 395/888
`
`5,237,675 A
`a 710/68
`8/1993 Hannon, Jr.
`......
`5,247,638 A
`9/1993 O’Brien et al... 395/888
`5,247,646 A
`9/1993 Osterlund et al.
`.......... 395/888
`ae A : Loot ne aseseeeneaes
`” ee
`
`5325,
`irdetal. we
`veecsssssesseesee 365/189.01
`5,337,275 A
`8/1994 Garner
`5,353,024 A
`10/1994 Graybill
`5,353,425 A
`10/1994 Malamyet al. 0.0.0... 711/144
`5,357,614 A
`10/1994 Pattisam et al.
`............ 395/250
`5,371,499 A
`12/1994 Graybill etal.
`5,379,036 A
`1/1995 Storer
`5,389,922 A
`2/1995. Seroussietal.
`5,396,343 A
`3/1995 Hanselman been eee eeeeeeeeee 358/426
`5,406,278 A
`4/1995 Graybill et al.
`5.406.279 A
`4/1995 And
`406,
`lerson et al.
`5.412.420 A
`5/1995 Glover
`5,414,425 A
`5/1995 Whiting et al.
`5,414,850 A
`5/1995 Whiting
`5,420,696 A
`5/1995 Wegeng et al. 0.0... 358/468
`5,426,779 A
`6/1995 Chambers, IV
`5,455,577 A
`10/1995 Slivka et al. oo... 341/51
`5,455,943 A
`10/1995 Chambers, IV
`s467087 A
`1/1995 Chu
`;
`,
`lu
`5.479.587 A * 12/1995 Campbell et al. css. 358/111
`5.485.596 A
`1/1996 Tobin
`5,493,698 A *
`2/1996 Suzukiet al. .... 370/280
`5,506,580 A
`4/1996 Whiting etal.
`5,510,840 A
`4/1996 Yonemitsu etal.
`5,525,982 A
`6/1996 Cheng etal.
`5,526,363 A
`6/1996 Weisset al.
`5,532,693 A
`7/1996 Winters et al.
`5,532,694 A
`7/1996 Mayerset al.
`5,539,865 A *
`7/1996 Gentile vee. 358/1.16
`...
`5,548,742 A
`8/1996 Wang et al.
`
`9/1996 Dawson .essessessee: 358/426.02
`5,553,160 A *
`5,559,978 A
`9/1996 Spilo .cecccecccsesseeseseeeees 711/203
`5,563,595 A
`10/1996 Strohacker ....c.ceseeeee 341/106
`
`Access campressed data
`
`
`
`Receive a
`
`request for the data
`812
`
`
`
`
`
`
`
`
`
`
`Access the data from the memory
`814
`
`Determine a compression mode
`for the data
`816
`
`
`Selectively decompress the data
`according to the compression mode
`B18
`
`
`Provide the data in response
`fo the request
`820
`
`Commvault Ex. 1028
`Commvault v. Realtime
`
`US Patent No. 9,054,728
`
`Page1
`
`Page 1
`
`Commvault Ex. 1028
`Commvault v. Realtime
`US Patent No. 9,054,728
`
`

`

`US 7,190,284 B1
`
`Page 2
`
`U.S. Appl. No. 60/144,125, filed Jul. 16, 1999, Dye.
`U.S. Appl. No. 09/491,343, filed Jan. 26, 2000, Dye.
`U.S. Appl. No. 09/818,283, filed Mar. 27, 2001, Dye.
`Yabe et al., Compression/Decompression DRAM for Unified
`Memory Systems: A 16 Mb, 200MHz, 90% to 50% Graphics-
`Bandwidth Reduction Prototype, IEEE 1998 Solid-State Circuits
`Conference, Feb. 1998, pp. 342-343.
`Kjelso et al., Design and Performance of a Main Memory Hardware
`Data Compressor, EuroMicro 96 Conference, IEEE, Sep. 1996, pp.
`423-430.
`
`..... 375/240.05
`
`* cited by examiner
`
`Primary Examiner—Hong Kim
`
`(57)
`
`ABSTRACT
`
`11/1996 Miller et al.
`5,572,206 A
`11/1996 Chambers, IV
`5,577,248 A
`............ 711/114
`12/1996 Shimadaet al.
`5,584,008 A
`5,590,047 A * 12/1996 Uehara ...... ee eeeeee 700/214
`5,602,976 A *
`2/1997 Cooper et al.
`.
`358/1.15
`
`2/1997 Hanselman ..............04 358/404
`5,606,428 A
`5,621,403 A
`4/1997 Reznik
`5,625,712 A *
`4/1997 Schoenzeit et al.
`5,627,995 A
`5/1997 Milleret al.
`5,652,878 A
`T1997 Craft
`........... 395/308
`5,696,912 A
`12/1997 Bicevskis et al.
`5,724,582 A *
`3/1998 Pelanek et al. oo... 382/232
`5,729,228 A
`3/1998 Franaszek etal.
`5,771,011 A
`6/1998 Masenas
`5,778,255 A
`7/1998 Clark et al.
`5,793,937 A *
`8/1998 Churaet al. oo... 358/1.16
`5,798,718 A
`8/1998 Hadady
`An integrated memory controller (IMC) including Memo-
`.......... 395/497.04
`5,812,817 A
`9/1998 Hovis et al.
`5,828,877 A
`10/1998 Pearce et al... 395/670
`ryF/X Technology which includes data compression and
`5,836,003 A
`11/1998 Sadeh
`decompression engines for improved performance. The
`5,838,334 A
`11/1998 Dye
`memory controller (IMC)of the present invention preferably
`....... 375/240.15
`5,847,762 A * 12/1998 Canfield et al.
`selectively uses a combination of lossless,
`lossy, and no
`5,852,742 A * 12/1998 Vondran etal. .......... T10/1
`compression modes. Data transfers to and from the inte-
`5,874,908 A
`2/1999 Craft
`grated memory controller of the present invention can thus
`5,877,711 A
`3/1999 Craft
`be in a plurality of formats,
`these being compressed or
`5,883,588 A
`3/1999 Okamura
`normal (non-compressed), compressed lossy or lossless, or
`5,933,104 A
`8/1999 Kimura
`compressed with a combination of lossy and lossless. The
`5,936,560 A
`8/1999 Higuchi
`5,945,933 A
`8/1999 Kalkstein
`invention also indicates preferred methods for specific com-
`5,956,372 A
`9/1999 Vaman et al.
`pression and decompression of particular data formats such
`5,961,617 A * 10/1999 Tsang oo... eee 710/100
`as digital video, 3D textures and image data using a com-
`5,973,630 A
`10/1999 Heath
`bination of novel lossy and lossless compression algorithms
`6,002,411 A
`12/1999 Dye wee ee eeeeeeee 345/521
`in block or span addressable formats. To improve latency
`6,002,814 A * 12/1999 Chadez ........ cesses 358/1.15
`and reduce performance degradations normally associated
`6,067,098 A
`5/2000 Dye
`with compression and decompression techniques,
`the
`6,145,069 A
`11/2000 Dye
`MemoryF/X Technology encompasses multiple novel tech-
`6,170,047 Bl
`1/2001 Dye
`niques such as: 1) parallel lossless compression/decompres-
`6,173,381 Bl
`1/2001 Dye
`6,198,850 B1*
`3/2001 Banton................ 358/426.02
`sion; 2) selectable compression modes such as lossless,
`6,208,273 Bl
`3/2001 Dye
`lossy or no compression; 3) priority compression mode; 4)
`6,292,194 B1*
`9/2001 Powell, TI ................ 236/92 B
`data cache techniques; 5) variable compression block sizes;
`6,333,745 Bl=12/2001 Shimomuraetal.
`6) compression reordering; and 7) unique address transla-
`2004/0017483 Al*
`1/2004 Kitsugi et al.
`......... 348/207.99
`tion, attribute, and address caches. The parallel compression
`FOREIGN PATENT DOCUMENTS
`and decompression algorithm allows high-speed parallel
`compression and high speed parallel decompression opera-
`tion. The IMC also preferably uses a special memory
`allocation and directory technique for reduction oftable size
`and low latency operation. The integrated data compression
`and decompression capabilities of the IMC remove system
`bottle-necks and increase performance. This allows lower
`cost systems due to smaller data storage, reduced bandwidth
`requirements, reduced powerand noise.
`
`EP
`JP
`WO
`
`0 702 457
`05204747 A *
`95/19662
`
`3/1996
`8/1993
`T/1995
`
`OTHER PUBLICATIONS
`
`Brenza, “Synonym Avoidance Cache,” IBM Technical Disclosure
`Bulletin, vol. 34, No. 1, Jun. 1991, pp. 377-381.
`International Search Report for Application No. PCT/US 00/02355,
`mailed Jun. 16, 2000.
`USS. Appl. No. 08/463,106, filed Jun. 5, 1995, Dye.
`
`16 Claims, 34 Drawing Sheets
`
`Page 2
`
`Page 2
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 1 of 34
`
`US 7,190,284 B1
`
`
`
`
`
`pLlowesayingewes
`
`Vv
`
`
`
`soydeusPigYONIeOL,Alowayywayshs
`m~pttIJejdepyatioug0,——I
`
`
`201
`
`waysksqns¢/|
`
`Jayjonuo5
`
`
`
`
`
`
`
`sngdOW/l0dV9
`voe90)sng{2907
`AddPG|ayseg
`ZoroO)6m
`
`vqolpnyasno|pieogAeyOL}ysiqpleH
`
`(UVJOM),bly
`
`8€Zvelech—Ozer
`
`8LbSngO/|
`
`v2
`
`Page 3
`
`Page 3
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 2 of 34
`
`US 7,190,284 B1
`
`4SIGPIErelZh__OzT
`
`esnojpueogheyObl
`
`Kejdsiqoap!Ovi
`Y|fo*901sng[e907
`ZridNddldVv
`Vv||I
`
`SLLSngO/|
`
`Vv9
`
`wajsksqngQ/|
`
`Jaj|ouyUuOD
`
`gbig
`
`Page 4
`
`
`
`
`
`
`
`waysksCh}Ae|ASIGOBpiAaN}aya‘pnyOL)Mowe
`
`Page 4
`
`
`

`

`
`
`
`AilCapijey6iqJEWO49OJ]OAPIAJayjojuogAowayysfowe<i
`
`
` AejasiqYOA“bug'OSLN/GDY9aulbu3TYCAsaiydergoapiyqeiaz||!!43!!
`
`
`
`COee
`S,Od|J
`
`SEC0¢¢771|oIsI@AuogyoolgX/JAIoweY\YIMLec
`
`
`7|sdepaqu|oflsngfereydueg|a“sy
`vez
`
`A
`
`
`
`(jeuJa}x3JOpayes6ayuy)
`
`202
`
`Wapow2Olpny
`
`wajsksqns
`
`
`
`aulbuzuolnoaxy
`
`olz
`
`
`
`Kiowayywaysks
`
`OLL
`
`Page 5
`
`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 3 of 34
`
`US 7,190,284 B1
`
`90}Sng|e907
`
`
`
`
`
`d/lOSTH/Add12907
`
`Page 5
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 4 of 34
`
`US 7,190,284 B1
`
`Kiowej)
`
`BdeHa}
`
`ayoedeed€7
`
`46c
`
`
`
`eBjeqpessaidwo4
`
`uoissasdwos
`
`
`
`UP)[O4}UOD
`
`182
`
`
`
`LZjouog/sng}sanbay
`
`022 ®
`
`
`
`zeTzzabLéO}IM°
`
`
`
`L9¢.
`
`91607Asojoau1qPEs.
`
`
`
`Ob}
`
`rd
`
`
`
`
`
`yup)uolssesdwosag9uoIsseidwiosjayereg
`
`
`
`u)sngSSauppy
`
`u)sngejeq
`
`Page 6
`
`Page 6
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Mar
`
`13, 2007
`
`Sheet 5 of 34
`
`y6S6S
`
`WudLv’
`SiO/lJa||OU0D
`
`
`O
`
`ejeq
`
`qruolssaidwo4
`
`02geulbuy
`
`Asso}
`
`uolssaudwo4
`
`aulbuz
`
`ssaidwiooaq
`
`uolssasdwosaq
`
`06SouibuZ
`
`Asso}
`
`uolsseudwooag
`
`YOYMS
`
`cls
`
`ssaidwoy
`
`YOUIMS
`
`
`
`Moweyseqssou)
`
`vs206
`
`US 7
`
`2
`
`190,284 B1
`
`ssalppy-Vpuewwoy-9‘Aay
`
`adky-AL
`
`snjeig-S
`
`G‘bly
`
`Page 7
`
`Page 7
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 6 of 34
`
`US 7,190,284 B1
`
`v9‘bly
`
`(UY40d)
`
`eyeqyndu|
`eyeqyndu| 0akg
`
`0a}Ag
`
`eyeqyndu|
`
`0ajAg
`
`eyeqyndu|
`
`0aiAg
`
`ejeqyndu|
`
`0alAg
`
`Page 8
`
`Page 8
`
`

`

`U.S. Patent
`
`Mar.13, 2007
`
`Sheet 7 of 34
`
`US 7,190,284 B1
`
`Parallel Compression
`
`402
`
`Maintain a history table
`comprising entries
`
`
`
`
`
`Maintain a current countof prior
`matches for each entry in the
`history table
`404
`
`
`Receive Uncompressed data
`406
`
`Compareaplurality of symbols with
`eachentry in the history table
`
`408
`
`
`
`Determine match information for each
`of the plurality of symbols based on
`
`
`the current count and compareresults
`
`
`410
`
`
`
`Output compresseddata in response
`to the match information
`
`
`
`
`
`Fig. 7
`
`Page 9
`
`Page 9
`
`

`

`
`
`
`
`
`
`
`
`sjoqwigpasseudwoounppy
`
`
`
`
`
`ALOISI}]0}seyjeyésjoquiAspassaidwoounppysnolaaidBulurewayysnj4oNal0\NMOPUINAOISIH0}
`MOPUIAA
`
`oeseteaduvlp
`
`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 8 of 34
`
`US 7,190,284 B1
`
`HE}S
`
`oecer
`
`
`
`
`
`
`passaidwoounESay}eu807
`
`joquiAsyoe3jndjnoAyuMOpulMyoreYM
`
`kuy
`
`
`
`
`01870}Oyu]eyeqpassaidwogZp
`
`SJQJUNOD{ly}eSeySNOIAagJndjnoEsounrey
`
`
`
`
`
`yeV
`
`{Vv
`
`SO,
`
`
`
`
`
`
`
`joquiAsynduiyoeaaedwioy
`
`
`
`joquiAsyndjno
`
`passeidwaour)
`
`vor
`
`
`
`passaidwogjndjno
`
`jueyeq
`
`89P
`
`
`
`
`
`
`UOHes}SNII!JOaseeJO}Ajeuas
`UMOUS‘Jaljeredulpawwopey
`
`
`
`peeweeewwwenewseeeeeeeweeeweeeeeeeeneeereeeeeeeeeeewwwcrocoeeeeeny
`
`
`
`
`
`yoye|\)UlJUNODjOqUAS
`
`oegbly
`
`ulpapnjou;
`
`éyoyewAuy
`
`c9P
`
`
`
`OpNjoulyoyey|sty
`
`
`
`dloquiAs}se]ay
`
`99P
`
`s30q
`
`
`
`JOXe0}JeJUNODJasay
`
`SNOINA
`
`ESOYOE||
`
`CoP
`
`SO,
`
`Cov
`
`éyayewauo
`
`
`
`
`
`joquiXsyndujyokes404SOA
`
`ulsjoquids
`
`
`
`sjoquiksJo#AqJajunoyeseai0u|
`
`PPP
`
`
`
`
`
`yoyeywjsebue7joajas
`
`
`
`
`
`yojewsnoiadigBuipnjau|
`
`vst
`
`
`
`SNOIAgInd\ing
`
`
`
`ou]eVeQpassaidwo4
`
`9S
`
`Page 10
`
`Page 10
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 9 of 34
`
`US 7,190,284 B1
`
`junodjndjnouoneinse4
`ysewjndingSHNSoY
`
`
`(Ayuysnoinald)19
`
`cd
`
`
`
`aledwo)€d
`
`19e7
`
`0}s}ndinocd
`
`saujuzLd
`
`ayigejeqqAquy
`
`209
`
`809
`
`O19
`
`sayunoygAnuz
`
`709
`
`0d
`
`¢e]eq
`
`cEyeq
`
`|BJeq
`
`0BIeq
`
`6‘bly
`
`
`
`107and909
`
`anjeAjesoy
`
`tv
`
`Page 11
`
`Page 11
`
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 10 of 34
`
`US 7,190,284 B1
`
`eho|elo|eta|elo2raid
`
`
`uolenge4siinseyo|
`J0Je19Ua5)v19
`
`weaysejeqjndjno
`
`YSBWSSaidWopauiquoy
`
`Xapu|JUNOAadSNOIASq
`
`
`Xapu|JUNoDxXeyyZ19
`ASE8JUNOD¢AUR
`
`anjeAJasay
`
`yseWXepy
`
`WwNwixew
`
`
`91607Juno9
`ysey)9yunogzAquy
`
`ysey)9JunodOAquy
`
`yseyQyung|Anuy
`
`yseW9JUNODuAljUS
`
`YSEY8JUNODQAdjuZ
`
`ySEY9JUNOD|ANuZ
`
`819
`
`
`
`Wweadsnding91607yunod
`
`YSEY|8JUNODUAjjUZ
`
`yseWssaidwog¢AjuZ
`
`
`
`yse|sseldwoyuAug
`
`OL“big
`
`Page 12
`
`Page 12
`
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 11 of 34
`
`US 7,190,284 B1
`
`LL‘big
`
`Om NN MOM YO tre tte tT Tt
`
`tT Tt
`
`01001
`Z+P9AeS
`
`LLOO}
`C+POALS
`
`OOLOL
`
`LOLOL
`
`OLLOL
`
`LLLOL
`
`OO001L
`
`LLLLO
`
`OLOLL
`
`LLOLL
`
`OO}
`
`LOLLL
`
`ObLLL
`
`LELLL
`
`|+Pares
`
`|+Ppaaes
`
`[+PoAeS
`
`panes|+Paaes
`
`panes
`
`pares
`
`panes
`
`DoAeS
`
`panes
`
`panes
`
`panes
`
`TOn or TOMO ron ox~ &
`
`josey
`
`anjeA
`
`yndjno
`
`¥SPiA
`
`Jajuno4
`
`anjea
`
`00001
`p+PpaAes
`
`LO001
`¢+panes
`
`07+PeAeS
`
`yndjno
`Ja}UN05MON
`000L000L0LL000LL0L0LLLLL000L000L0LL000L|0L0LLL|L|ev|za|to|sayojewyndu;
`
`=_ Tre Te
`
`ew rw www ee eB oO Oo Oo
`
`lO le
`
`Page 13
`
`Page 13
`
`

`

`
`
`
`
`U.S. Patent Mar. 13,2007—-Sheet 12 of 34 US 7,190,284 B1
`
`
`compressed blockSRSNINOanww
`
`Adjust max count
`to4orless
`
`
`Send out
`
`
`
`No
`
`Yes
`
`—Max
`
`eflask = 100007
`729
`
`Send out
`compressed block
`731
`
`Send out data 0
`733
`
`N
`
`No
`
`Send out data 0
`741
`
`No
`
`Send out data 0
`a
`
`Yes
`
`YeS
`
`Send LZ12
`compressed block
`743
`
`e
`
`‘
`
`o
`
`Send out data 0
`151
`
`
`
`<“CCM(0) = 1?
`749
`
`
`Fig. 12
`
`Tone
`
`Page 14
`
`Page 14
`
`

`

`
`
`
`
`U.S. Patent Mar. 13,2007.—-Sheet 13 of 34 US 7,190,284 B1
`
`Entry
`
`Data
`Count
`
`State 0
`
`Input D3:0
`
`012 3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`14
`
`12
`
`13
`
`14
`
`15
`
`[0](0)[0]
`
`MMMMMOOOoe
`
`CountOut
`MaskOut
`
`MUIMMMM MM a2)
`(0][0)][0]
`[TF] (TF) [1F] (4) (0°) (0) (1) 0F] CF) OF) 7) OF) 6) OF)
`Output
`
`Data
`cont HMMA MOMMOMOOOOe
`
`contout PMU UMMUIAIUMIMOMM2
`MaskOut
`FF] FF] FF) OF] CF]NO
`Output
`oe FROPAPP
`cut OMMUMUMMMEMOAMOMb
`
`State 1
`
`Input D3:0
`
`sae?
`
`Input D3:0
`
`countout UMM UUMUMIOOOOOOO)
`MeskOut
`FF] TEC) CF RF]CF]
`Output|(7,6)
`State3
`Data
`(85) [F7] [E8) [F9) FF3) [Fa] (FS) (BS) (CO) [E7) (F) (FS) FO) Fy 2) 3]
`cunt MOU MMNMMOOMOO e)
`
`Input D3:0
`
`Coumtout DIM MUOMOOIOOOOOOHH
`MaskOut
`[AF] [TF] (07) (0F) (OF) 0) 0] TF) OF) TF) OF) OF) OF) OF) OF OF)
`Output|(9,2}E2(6,1)
`
`Stale 4
`Data
`Count=(0) [0] (0) (0) 9) (0) (C7) (FP)2) BG) attemate output
`Final Output
`
`Fig. 13
`
`[LB]
`Altemate Output
`
`Page 15
`
`Page 15
`
`

`

`
`
`Page 16
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 15 of 34
`
`US 7,190,284 B1
`
`9Lb
`
`ly
`
`
`
`UOIe1BUdS)J99]9S
`
`y09|9§
`
`KeMZ
`
`aedwoy
`
`Page 17
`
`Page 17
`
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 16 of 34
`
`US 7,190,284 B1
`
`ZLbig
`
`eeww ee ewe wwe eeweena ee ene ee
`
`Byep
`
`passaidwo’)
`pyeqAsso7
`
`
`
`
`
`G7geuibuzuotssesdwioyAsso7
`
`
`passaiduon|‘UPeaSayeaiidayDOA
`
`ejep082ANMEYAANMEDe
`
`
`uojeredaguolsianuo9——
`
`Sz,28Z
`
`
`Japoouy
`
`vil
`
`joquos)
`
`}9|9SGyA
`
`YOWMS
`
`edd
`
`ejeqAsso]
`
`Japooseq
`
`822
`
`|8Xlq
`
`jouUoD
`
`AQS
`
`COL
`
`90unoS
`
`JayaAu0y
`
`ga
`
`Page 18
`
`Page 18
`
`
`
`
`
`
`
`
`
`
`

`

`Ymax! Ymax!
`
`P4ebits[4ebits[|||Amax|Amin|Pbits|[6/7Bytes|48bits|4/Bbits|bits}||Amax_[Amin[Pbits|{8/9Bytes|Shits|2bits|48bits|aebits|s2bis||||Bmax|10|
`
`9/10Bytes|Amin|Pbits|7/8BytesPTCUTCC“‘C‘®CC#C#”dCCCCCT6hits[6bits[Sbits[|Sbits[Sits|Sbits|4/8bits|4/8bits|16bits|488bits|32bits
`[Ymax|Rmax]Rmin|Bmax]Bmin|Amax|Amin_|Pbits
`Ymax|Ymax|Rmax|PTUTC*d2Alphasbits[6bits|5bits||>2colors|Ymin_|PBits|Sits|Shits|Shits|Sits|Sbits|4/8bits|1color_|
`
`
`
`
`2Alphas|6bits|6bits|5bits|5bits|2bits|[2colors[Ymax|Ymin[Bmax|Bmin_|[Rmax[RminAmax_||1color_|
`
`
`
`|Bmax|Bmin|Pbits|8Bytes|
`
`
`Ymax|ymax_|PTSits|Sits
`Ymin|toolor_|
` 6pits
`
`|____]
`
`
`
`
`
`
`U.S. Patent Mar. 13,2007.—-Sheet 17 of 34 US 7,190,284 B1
`
`
`
`Fig.18
`
`iz)
`=
`fs
`I~
`
`a—
`
`-> #[
`
`oO
`lo
`
`Ymin
`
`Ymin
`
`Ymin
`Ymax
`
`Ymin
`Ymax
`
`Page 19
`
`&£< x
`
`<
`oO
`
`<«
`
`ss
`© |:
`
`a *|
`
`:
`
`or
`
`><
`co
`
`> xo
`
`D >
`
`Amin!=00orFF
`
`Amax
`Ymin
`Ymax
`
`”
`<=
`
`5c
`
`o
`
`Ymax
`
`£
`e
`>
`
`Ymax
`
`&
`Ee
`>
`
`Ymax
`
`Page 19
`
`

`

`U.S. Patent
`
`13Mar.
`
`, 2007
`
`Sheet 18 of 34
`
`US 7,190,284 B1
`
`passaldwo9
`yndjno
`
`ejeq
`
`yeuo4
`
`YOUMS
`
`98¢
`
`ozs
`
`
`
`
`
`—--------suibuzuoissasdwog
`
`sngAioway
`
`sngLAdNI
`
`
`
`[aleSS8}-SSOJ
`
`
`
`
`
`uolssaidwio7Asso7
`
`
`
`—~-------~-aulpuy}nduy
`
`
`
`ejyeqpassaidwo4
`
`
`
`
`
`Bjeqpassaidwoseq~#--------
`
`aiedwo4
`
`Kel
`
`yun]
`
`yesmeemewmeemwweseesee
`
`yndjno
`
`yeuo4
`
`YoIMS
`
`ggcOc}
`
`soneescescenneceeeeenensceeceeseeeeseeaulbuysoronsecdanos
`
`
`
`
`
`
`uolsseidwiosaqAsso7jeulbuQ
`
`
`
`88S|A||E124$$8]-SSO7]
`
`__ucissasduiosagq
`
`sulbuj
`
`
`
` SJEIPSU}U]!ogsuolssaidwooAwd——-
`
`
`
`
`
`veveceeeeeeeeeeceeeeeeeeeeeeqeeceeeeeeeceeeeeeeeeneenenatensennesesemesnesnneenesneeacssesuessessentnescueceveneeeeveeeeseeeneyuolssasdwosagq
`
`
`
`uolssaJdui0da(--------------
`
`Page 20
`
`
`
`—19GZSYOUMS
`
`Page 20
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 19 of 34
`
`US 7,190,284 B1
`
`Lebly
`
`00¢9
`
`6€
`
`0
`
`alewitel
`
`dw-|
`
`aul)
`
`LANXAg0€
`Ae\dsig THQAASS
`COveOfte02
`6O8eOLEO9E
`J1d-d¢Idde|aunyxeL
`
`duiggin|2aeunog
`
`OS
`
`Jeaurq
`
`OLE
`
`Page 21
`
`Page 21
`
`
`
`€
`
`

`

`U.S. Patent
`
`Mar.13, 2007
`
`Sheet 20 of 34
`
`US 7,190,284 B1
`
`Compression of received data
`
`802
`
`Receive uncompressed data
`
`
`
`Determine a compression mode
`of the data
`804
`
`
`
`
`
`
`Selectively compress the
`uncompressed data according to the
`
`compression mode
`806
`
`
`
`
`
` Store the data in the memory; store
`compression modeinformation with
`the data
`
`808
`
`Fig. 22
`
`Page 22
`
`Page 22
`
`

`

`
`
`
`
`U.S. Patent Mar. 13,2007—-Sheet 21 of 34 US 7,190,284 B1
`
`Access compressed data
`
`Receive a requestfor the data
`
`Accessthe data from the memory
`
`iSiS>ho
`
`
`
`Determine a compression mode
`for the data
`816
`
`
`
`
`selectively decompress the data
`according to the compression mode
`
`
`
`Provide the data in response
`to the request
`820
`
`Fig. 23
`
`Page 23
`
`Page 23
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 22 of 34
`
`US 7,190,284 B1
`
`
`
`JO}pauinbeyjou119
`
`‘@}ON
`
`4d1VO
`
`Jdeeq
`
`08Z¢
`
`
`
`
`
`abuesssauppe9j6uls
`
`suolje}uawajduut
`
`
`
`(ssayngawed)al)
`
`abueyAoway0}azisuljenbyyoojgLowey)
`
`
`
`
`
`"oeyUoIsseudwogwnwixeyAqpapiaigazis
`
`
`
`
`
`
`
`Balyudhesol|y[eltu|
`
`ObLZ¢
`
`
`
`"yO0\qpasseidwiooun
`
`O12
`
`
`
`eyeqpassaidwo9
`
`0622
`
`
`
`
`
`yoreJO}syo0|qpassaudwioo
`
`
`
`
`
`Buiulewar|eSule}uODyoo}gows
`
`
`
`BalMOIAAO
`
`
`
`‘yoo|qpassesdwooun
`
`Ole
`
`ejeqpassaidwo5
`
`0G2¢
`
`
`
`saulbuuoisseudwo29q
`
`GSS/0SS
`
`
`
`
`
`
`
`yoedJO}4D0]qpassaidiwodauosule}Uu05
`
`AujuaJadsyiqeg
`
`
`
`xewAqua96Z
`
`
`
`
`(1'VO)e121SSauppyMOLeAG
`
`
`
`
`(LLWO)alqe,uoe|suel)ssaippypasseidwo5
`abuesAiowswpassaidiuooJadAujue|AquaJadsqZ7/
`
`
`
`
`
`
`
`
`
`(0:L¢)sseuppy
`
`
`
`pz‘bl4e1eqpasseidwosaq
`
`gS
`
`Page 24
`
`
`
`
`
`YOHMSJeWOSjndjnQ(0b)spp
`
`
`
`
`
`Page 24
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 23 of 34
`
`US 7,190,284 B1
`
`GC b
`
`i-+
`
`Page 25
`
`$}!enFFuondis9s9q
`AipunogMyAipunogyy82IS419AipunogypAipunogyp
`PresetFioyrpage|sugoe|SHAYsud02S1902
`
`€5+Fatslidgsid$2sud02Aujua\xau0}sjulogAuliqesseippy
`PIIEALY¥O}XONNdLVOXenyoalgXenJdMO|LSAQ
`
`
`
`MO|L9AO|Aqua10JoBalyMOWIAAGa4)UlYJasyoesiyooxeuayL|Of(suiq02+8)¥I11
`
`idLYOadereq|sad||appyBuipussppyBuners
`|Aqua10JOBayMOYIACAY}UI¥asoJeS|4O0/q}xaUYL
`
`
`
`
`
`
`
`
`yu]uBisagAujuygZ}-(LLW9)aigeLuolje|sues)Ssasppypassaiduio9
` Pez|(sugoz)vor|(,Jayje10)auSiN)310709\X@uOUTor{|(sia)vor|auOSiuJayesyo01g¥SI0019
`
`
`BallyMOUIAAGaU}UiYJasyoIesiyooqyxauay)|Zz|(sq02)vOL
`
`
`AyeaisAudSMoj[o}yO0\q}Xeuaypefo
`
`
`
`
`
`
`
`xewAnjuy962-(1V0)a1qe21SSeuppyMo}IaAQ
`
`
`
`Jepeay
`
`
`uondydsagJapeap[el}1u]
`
`qqsmur}Aipunogip
`re|(sug0Z+8)WILLL
`
`spjal4uonesolyAowey
`
`Nd
`
`
`
`Page 25
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 24 of 34
`
`US 7,190,284 B1
`
`Memory Allocation
`(Initialized CATT)
`2709
`
`Allocate CATT Entry
`— —_
`7INO
`
`Arrange entry order
`(if required pasedon start/end address)
`
`713
`
`Set the compression type
`Sba! — on
`
`Allocate% of the requested memory
`(Basedon block size and compression type)
`2717
`
`Set the data pointerto start at the initial block
`in the CATT
`2719
`
`
`Allocate Overflow Address memory (OAM)
`(Set by IMC driver or BIOS)
`Typically 1/8th original data size
`
`2721
`
`
`
`
`Initialize the OAT pointerin the CATT
`
`Initialize allocated memory headersto zero
`
`INORO—~~NOINO[oa]Oo
`
`
`
`
`
`Initialize OAT entries, set overflow
`pointer in OAT
`2727
`
`Fig. 26
`
`Page 26
`
`Page 26
`
`

`

`
`
`
`No
`
`Calculate Initial Address |, continue to
`compressdata (Validate presententry)
`2733
`
`Store block of Compressed data at
`address| with header=LAST
`2737
`
`
`
`
`
`U.S. Patent Mar. 13,2007—-Sheet 25 of 34 US 7,190,284 B1
`
` @Compressed
`
`Memory Store (Addr N)
`
`2749
`
`
`
`
`
`
`Check
`CacheforHit
`
`While searching CATT
`2731
`
`Yes
`
`
`
`
`H = Header
`from Address|
`2159
`
`
`
`
`
`
`Remaining
`Get Next
`
`Compressed block
`Address (U=f(H))
`
`
`>Block Size?
`2799
`
`2735Ne
`
`
`
`
`Store block of Compressed data at
`address | with header(U) Set I=U
`
`2739
`
`a H2=HeaderfromAddressHSet
`
`header of H to UNUSED Set H=f(H2)
`2745
`
`Yes
`
`
`
`
`
`
`Store uncompressed block and header
`at Add N in cache and set most
`recently modified bit for cache
`
`Done
`
`Fig. 27
`
`Page 27
`
`Page 27
`
`

`

`
`
`
`
`U.S. Patent Mar. 13,2007—-Sheet 26 of 34 US 7,190,284 B1
`
`
`@Memory Fetch
`(address N)
`
`2759
`
`
`
`Cache search HIT?
`
`ee
`
`
`
`Solve forinitial address(I) = (Matching
`CATTstart address - N)/X
`(X is based on data type)
`
`2753
`
`
` Fetch from memory
`compressed block|
`2755
`
`Deliver data from cache
`2752
`
`Strip the Headerbits, and decompress
`the remaining data from |
`2757
`
`
`Fetch the overflow block using the
`
`overflow pointer as base and the
`LAST Block?
`headerasoffset
`2761
`
`
`2754
`
`
`
`
`
`
`
`
`
`Read compressed overflow blocks
`2756
`
`Send decompressed data to
`requesting agent
`2765
`
`
`
`Update Cache, invalidate LRU, mark
`new block as MRU
`2769
`
`
`Completed compressed
`read operation
`
`Fig. 28
`
`Page 28
`
`Page 28
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 27 of 34
`
`US 7,190,284 B1
`
`
`
`
`
`
`
`(NJ8peaH)=¥Jajuladssaippeyoo|qKauayeingjeD
`
`COL.
`
`}XOU85)
`
`
`
`((HyJ=u)sseuppe
`
`662¢
`
`Pld1SW]
`
`L622
`
`SA
`
`EINANUSLOyO0\q
`
`e6le
`
`1XaUS|
`
`
`
`
`
`YOsapeaymo|paagpesy
`
`
`
`
`JajulodSsauppeyxau
`
`
`
`ujJayuredBunjnsasa0}
`
`9022
`
`auo0g
`
`
`
`
`
`OZISYOO|q+y=Jajulodsseuppe}xaN
`
`a90/¢
`
`
`
`
`
`8215J901G+Y=4
`
`W902
`
`
`
`
`
`
`
` bOL¢épesnunpeleoipulsapeay
`
`5300
`
`S622
`
`}xOuS|
`
`
`
`
`
`AIOWALUMOWSAQJCYOO}MAUALBEDO]
`
`Agua1yopue
`
`LOL¢
`
`
`
`11dpljeapuesayulod1¥OMeuJag
`
`£022
`
`L62¢
`
`
`
`
`
`éplleasa}u:odMoyaAO
`
`
`
`Jaquiodyxeu@)
`
`Z0LE
`
`
`
`LVOwou)sayu}od
`
`62‘614
`
`GOLZ
`
`Page 29
`
`
`
`(aZIsYO01q‘JesHO“NUUAO))=(4)
`
`
`
`
`
`
`
`SSoppeYOO}MOWPBAOMAUayE(Ng|eD
`
`
`
`
`
`MOIWaAGMAN
`
`Page 29
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Mar
`
`13, 2007
`
`Sheet 28 of 34
`
`US 7,190,284 B1
`
`
`
`
`
`dwosxey
`MO|L8AQ
`
`oney
`
`a2Ig49018
`
`aZzig490/g
`
`40|MJO/MdOojmuOHeO||V
`
`reniuy
`
`pajuswbelj|6es4-uon
`
`
`
`JapeayJepeayJapeayjeriuy
`
`og‘big
`
`Page 30
`
`Page 30
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 29 of 34
`
`US 7,190,284 B1
`
`O12/
`
`O€Sc/
`
` sa}hqg¢z)
`
`yo0|qucIssaidwio
`
`
`
`
`
`AJOWSWWOY0]qpassaidwospeay
`
`
`
`ayoedeyep¢70}ssaidwiosag(Z
`
`
`
`
`
`a1qe}ul(JO)Be}uontisogaiojs(¢
`
`Japs0JOJNOyoo|qssaidwod-ay(Pp
`
`CeTeTstsTototaTypa]0 ssauppepealMON
`
`
`
`
`
`
`
`(seyAqze)juawtiegyoolgS}elpawsa}u
`
`
`
`
`
`(4@)Be)yimsapeayyoeny(s
`
`0cS2/
`
`A1owaw0}yoeqYOO}|GpassasdwiosaA,(9
`
`
`
`
`
`
`JapsojeulbuoulBuyeoiput,O,s!pjayBe}sapeay,
`
`Le‘bi4
`
`
`PastTatToTatTvTHI95[4[apesy]pesseidwog
`,,
`JapioJojnoBuyeoipul¢,s!playBe}sapeay
`
`
`+/9P0
`
`MON
`
`Page 31
`
`Page 31
`
`
`

`

`
`
`
`
`U.S. Patent Mar. 13,2007.—-Sheet 30 of 34 US 7,190,284 B1
`
`
`BitsUsed
`
`_
`
`wee ce mm ee te Me
`
`POY
`
`
`
`
`
`
`Compressed
`
`Data
`
`Count
`
`~<
`
`To
`=
`
`1100
`
`Fig.32
`
`Page 32
`
`™—
`
`_—
`
`Page 32
`
`

`

`
`
`
`
`U.S. Patent Mar. 13,2007.—-Sheet 31 of 34 US 7,190,284 B1
`
`25503 ~.
`
`25505 ~.
`
`25507 ~,
`
`25609 ~
`
`Pipe Register (168 bits
`
`Stage 2: Calculate Initial Selects and Overflows
`Partial Selects and Overflows
`0 ...04., 15
`
`Pipe Register (144 bits
`
`
`
`25513 ~. Input Data 8 Bytes
`
`25511
`
`Pipe Register (128 bits
`
`Stage 4: Data Selection
`Data Out
`
`0
`
`Data
`Valids
`
`Page 33
`
`Page 33
`
`

`

`
`
`
`
`U.S. Patent Mar. 13,2007—-Sheet 32 of 34 US 7,190,284 B1
`
`DO: D8:|D9:| B10:} D13:) D25:
`
`
`D24
`D63y
`D634
`D634
`D634,
`DéE3
`[demir }
`E55
`
`Data Index
`
`25523
`[E10 ETS] 2s:
`
`8:
`
`Byte
`
`cou
`
`
`E55) E55a,
`25525
`oi
`fasaan
`Dal F9:|F10:|Index F13:| F25:
`
`FA71 F47py,F47
`
`25527
`me
`tT
`[Decoders=)A
`
`JO:
`
`J23 25531
`Count
`Jo]
`Jto:]
` J13:
`Data Index
`J23a,J23
`4|Decoder5|Byte
`Kt8—Bite Index ft
`
`
`
`
`
`Data Index G9:|Gi0:} G13:1 G25:
`
`Byte
`G394 G39) G39) G39
`
`Count
`
`Count
`Data Index
`Byte
`
`4
`
`HO:
`25529
`H31
`H13:
`H10]
`H9:|
`H31
`H31
`H31
`[Decodert PN
`
`
`
`
`Start Counts
`
`Data Index
`Byte
`
`Data Index
`Byte
`
`25535
`
`Fig. 34
`
`Page 34
`
`Page 34
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 33 of 34
`
`US 7,190,284 B1
`
`GE
`Big
`
`|a0|
`
`Byeq
`
`
`
`ayelauas)SNOIAGd
`
`ayAgB]eq
`
`
`
`eyeqjndu|
`
`¢é0-00
`
` yoa|aS
`
`abb<
`
`BY
`
`9G55S¢
`
`yO8yD
`
`PGGSS¢
`
`49949
`
`9GGSSC
`
`
`
`49949
`
`45652
`
`g0
`
`yy
`
`BGGSS¢
`
`
`
`PIIEA498Y4O
`
`ES5S¢
`
`pectoO
`
`SNOIAald
`
`pajag
`
`juno)
`
`puexepu|
`
`
`
`
`
`LG6S¢juno)
`
`Page 35
`
`Page 35
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 34 of 34
`
`US 7,190,284 B1
`
`
`0010Z0108001399]9S
`
`
`xXcId-:LdcIG:Ld6d:7dxLd:¢cdxopuy
`
`
`
`
`xXOdt¥7a:cId §=$+0d+9C:rd=7+0d+¢€d'°7dI+0dI+0dyunoy)
`xXxXxXxX8d:1dxXaigved
`
`OOHIdldidi
`
`00OfdraIdi
`
`0000000080
`
`BOEIINSIY
`
`q9¢IANS
`
`Page 36
`
`|SSSSSSSSE
`
`dtdtdtdldi
`
`dTAldtdldi
`
`O
`
`Stdldldi
`
`HIdldldl
`
`41dtldtdtdi
`
`S
`
`10cdww30OI
`
`SNOLAdI
`
`3919S
`
`Page 36
`
`
`
`
`

`

`US 7,190,284 B1
`
`1
`SELECTIVE LOSSLESS, LOSSY, OR NO
`COMPRESSION OF DATA BASED ON
`ADDRESS RANGE, DATA TYPE, AND/OR
`REQUESTING AGENT
`
`CONTINUATION DATA
`
`This applicationis a continuation-in-part (CIP) of Ser. No.
`08/916,464, filed Aug. 8, 1997, and now U.S. Pat. No.
`6,173,381, issued on Jan. 9, 2001;
`which is a continuation-in-part (CIP) of Ser. No. 08/463,
`106, filed Jun. 5, 1995, now abandoned;
`which is a continuation-in-part (CIP) of Ser. No. 08/340,
`667, filed on Nov. 16, 1994, which is now U.S. Pat. No.
`6,002,411, issued on Dec. 14, 1999.
`
`FIELD OF THE INVENTION
`
`The present invention relates to computer system archi-
`tectures, and moreparticularly to a memory controller which
`includes an embedded data compression and decompression
`engine for the reduction of system bandwidth and improved
`efficiency.
`
`DESCRIPTION OF THE RELATED ART
`
`Since their introduction in 1981, the architecture of per-
`sonal
`computer
`systems
`has
`remained
`substantially
`unchanged. The current state of the art in computer system
`architectures includes a central processing unit (CPU) which
`couples to a memory controller interface that in turn couples
`to system memory. The computer system also includes a
`separate graphical interface for coupling to the video dis-
`play. In addition, the computer system includes input/output
`(I/O) control
`logic for various I/O devices,
`including a
`keyboard, mouse, floppy drive, hard drive, etc.
`In general, the operation of modern computerarchitecture
`is as follows. Programs and data are read from a respective
`I/O device such as a floppy disk or hard drive by the
`operating system, and the programsand data are temporarily
`stored in system memory. Once a user program has been
`transferred into the system memory, the CPU begins execu-
`tion of the program by reading code and data from the
`system memory through the memory controller. The appli-
`cation code and data are presumed to produce a specified
`result when manipulated by the system CPU. The CPU
`processes the code and data, and data is provided to one or
`more of the various output devices. The computer system
`may include several output devices, including a video dis-
`play, audio (speakers), printer, etc. In most systems,
`the
`video display is the primary output device.
`Graphical output data generated by the CPU is written to
`a graphical interface device for presentation on the display
`monitor. The graphical interface device may simply be a
`video graphics array (VGA)card, or the system may include
`a dedicated video processor or video acceleration card
`including separate video RAM (VRAM). In a computer
`system including a separate, dedicated video processor, the
`video processor includes graphics capabilities to reduce the
`workload of the main CPU. Modern prior art personal
`computer systemstypically include a local bus video system
`based on the Peripheral Component Interconnect (PCI) bus,
`the Advanced Graphics Port (AGP), or perhaps anotherlocal
`bus standard. The video subsystem is generally positioned
`on the local bus near the CPU to provide increased perfor-
`mance.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`Therefore, in summary, program code and data are first
`read from the hard disk to the system memory. The program
`code and data are then read by the CPU from system
`memory, the data is processed by the CPU, and graphical
`data is written to the video RAMin the graphical interface
`device for presentation on the display monitor.
`The system memory interface to the memory controller
`requires data bandwidth proportional to the application and
`system requirements. Thus,
`to achieve increased system
`performance, either wider data buses or higher speed spe-
`cialty memory devices are required. These solutions force
`additional side-effects such as increased system cost, power
`and noise. FIG. 1 illustrates the data transfer paths in a
`typical computer memory controller and system memory
`using prior art technology.
`The CPU typically reads data from system memory across
`the local bus in a normal or non-compressed format, and
`then writes the processed data or graphical data back to the
`I/O busor local bus where the graphical interface device is
`situated. The graphical interface device in turn generates the
`appropriate video signals to drive the display monitor. It is
`noted that prior art computer architectures and operation
`typically do not perform data compression and/or decom-
`pression during the transfer between system memory and the
`CPU or between the system memory andthe local I/O bus.
`Prior art computer architecture also does nothing to reduce
`the size of system memory required to run the required user
`applications or software operating system. In addition, soft-
`ware controlled compression and decompression algorithms
`typically controlled by the CPU for non-volatile memory
`reduction techniques can not be applied to real time appli-
`cations that require high data rates such as audio, video, and
`graphics applications. Further, CPU software controlled
`compression and decompression algorithms put additional
`loads on the CPU and CPU cache subsystems.
`Certain prior art systems utilize multiple DRAM devices
`to gain improved memory bandwidth. These additional
`DRAMdevices may cost the manufacturer more due to the
`abundance of memory that is not fully utilized or required.
`The multiple DRAM devicesare in many instances included
`primarily for added bandwidth, and when only the added
`bandwidth is needed, additional cost is incurred due to the
`multiple DRAM packages. For example, if a specific com-
`puter system or consumer computing appliance such as a
`Digital TV set-top box uses DRDRAM memory and requires
`more than 1.6 Gbytes/sec of bandwidth, then the minimum
`amount of memory for this bandwidth requirement will be
`16 Mbytes. In such a case the manufacture pays for 16
`Mbytes even if the set-top box only requires 8 Mbytes.
`Computer systems are being called upon to perform larger
`and more complex tasks that require increased computing
`power. In addition, modern software applications require
`computer systems with increased graphics capabilities.
`Modern software applications include graphical user inter-
`faces (GUIs) which place increased burdens on the graphics
`capabilities of the computer system. Further, the increased
`prevalence of multimedia applications also demands com-
`puter systems with more powerful graphics capabilities.
`Therefore, a new system and methodis desired to reduce the
`bandwidth requirements required by the computer system
`application and operating software. A new system and
`method is desired which provides increased system perfor-
`mance without specialty high speed memory devices or
`wider data I/O buses required in prior art computer system
`architectures.
`
`Page 37
`
`Page 37
`
`

`

`US 7,190,284 B1
`
`3
`SUMMARY OF THE INVENTION
`
`The present invention comprises a memory controller,
`also referred to as the integrated memory controller TMC),
`which provides improved data efficiency and bandwidth.
`The memory controller includes a compression/decompres-
`sion engine, preferably parallel data compression and
`decompression slices, that are embedded into the memory
`control logic of the memory controller. Further, the present
`invention does not require specialty memory devices or
`system software changes for operation. The memory con-
`troller logic of the present invention preferably interfaces to
`the system CPU either external or internal to the memory
`controller. Further, the memory controller interfaces to the
`main s