.
`(.2; Umted States Patent
`Dye et al.
`
`(54) SELECTIVE LOSSLESS. LOSSY, OR NO
`COMPRESSION OF DATA BASED ON
`
`W5}
`
`ADDRESS RAI\’GI-Z. DA'l'A TYPE. ANDIOR
`REQUESTING .-KG]-3.-\i'l‘
`I11vent0rs: Thomas A. Dye, 6621 Candle Ridge
`Cove. Austin.
`(US) "F8731: Manuel
`J. .'-\]\"fll‘9Z.. II.
`Pi3'[Jp€l' ROCK Dl'..
`.r\1JSlll‘L TX (US) 73717; PEIOI‘ Geiger.
`[0407 'l_l'i3&.‘iL1n: Island D12, AL]SLl!'1. TX
`(US) 78730
`
`( "'
`
`) Nmice:
`
`Subiccl In any disclaimer. the term Ofllllhi
`patenl is extcxided or adjusled under 35
`A
`~.
`Q
`E
`_
`Uibit I 1‘-“bl by 0 d lyb‘
`
`_
`..
`lg” MP1‘ N“" "M39559
`.
`02> Filed:
`Jan-29-1999
`
`Reimd U-S- APP1i9=“i0fl Data
`(03) Cmliriuatiuall-in-Part nf'applicaLi011 N0. 0Rr‘916.4-6-'1.
`filed cu1Aug. H. 1997. m':\\-' 13:11. No. 6.173.381. which
`is a con1'iuuatio11—in—pzm of application No. (183463.
`‘I06.
`O11 .ll.ll‘l. 5, 1995. l'i{'.|W‘ Elballdflllfid. \’v‘l1iCl'l iii
`0 comintualiun-i11-pan Mapplicutiun N0. 03;’340.6{'w7.
`filed on Nov. 16.
`.1994. now Pat. No. 6.002.411,
`
`(51)
`
`(52)
`
`Int. Cl.
`H()3M 7,39
`G061.“ I.-_a/00
`11.5. (.1.
`
`(3905.01)
`(200501)
`341rs1;340s7;710xes<;
`
`['56)
`
`3822'.’-232.
`(58) Field of Classification Search
`333233.244: 710a’63: 709K247: 341151.
`.-'l4lr’372 7ll/l7U
`See application lile for complete sean:l1 liismry.
`References Cited
`_
`_
`_
`__ _
`‘
`_
`U-5- P“\”=m DC“ U1‘/111“ F5
`='I.(J[l8.460 A
`2:l9'!T Bryant at :0.
`4-688.108 A
`3-1937 Cotton ct 211-
`4375.54! A
`ID-"I939 Slnrer
`
`395.-463
`353-'Jfil-I
`
`|||||||||||||||||||||||||||||||||||l||||||||l|||l||||||||||||||||||||||||||
`
`US007l90284Bl
`
`(10) Patent No.:
`(45; Date of Patent:
`
`US 7,190,284 B1
`Mar. 13, 2007
`
`»l.SSI.0';‘5 A
`4,903,317 A "‘
`
`4337-541 A "'
`Q
`..
`,
`.*
`
`ll-I989 Wang ........................ .. 34l-'8?
`3:‘ |‘)*){}
`l\lishil1:u'n el :Ll.
`..
`353-"I .9
`
`
`701935
`
`F1991 L¢\'_¢{11¢ °1'=I1-
`fgtyns C18}-
`_r
`Illnge .1.
`
`A
`§Il5D_430 A
`_-3_1_-1_-1..-1.3.4 A
`5.13"-".4610 A
`5.237.675 A
`5.347.533 A
`
`9.499; mailing at M:
`94992 Ch“
`[(1.-"mg:
`{-].m_mheI.5_ [V
`8r'I993 Miller El .1].
`Se"l993
`lI:1nnnl'l.Jr.
`'.l"l993 fJ'BriEl'l el :1].
`
`
`
`5«347-545 1*‘
`
`9-"1993
`
`0-‘*'*-’l‘l""d '-" Ell
`
`_'i9S.'S3H
`7ll.lr'68
`395-‘S88
`
`395-333
`
`_
`,
`3.____.
`5.337.275 A
`5.353.024 A
`5.353.425 A
`.-.
`.
`iiiiiii ii
`5.379.035 A
`5.339.022 A
`
`4D6';7q
`5.413339 A
`5414325 A
`5_414‘35u A
`5.410.696 A
`.'7l.4.l'5.'.-"T9 A
`5.455.577 A
`5.455.943 A
`5.4fi::.390 A
`
`,,
`
`e :1.
`|
`S-"I994 Garner ................ .. 365-‘ l39.(l|
`10 I994 Graybill
`10-1994 Malamyvat :0.
`I
`I
`01.
`13.1333 213%?
`I-"I995 Siurer
`2.-I995 Seton-ssi el 0].
`
`7:1--144
`552
`39
`5"
`
`35S"'42fi
`
`358.-"463
`
`4.199‘. A;’:{er;un°cI‘:]
`5_.|g9_; Elmer
`'‘
`5.1995 Whiting el “L
`5.1995 \m,i;j,-,g
`5» I995 Wegeng el al.
`IS-"I995 Chambers. IV
`Ill» 1995 Slivkfl rrl éll.
`............... .. 3-4|-"51
`I0'_l‘)95 <'.‘ha_n_1bers. IV
`lU'l?9:
`\T;1l1llll],g ct .1].
`gmipheil E1 al‘
`
`m__.l_“
`
`5_493_59g A ‘e
`5.506.580 A
`5.5l[.'.ii4U A
`5-535-933 A
`5.53_6.3fi3 A
`5.53.-‘.693 A
`5.532.694 A
`5.539.055 A '
`it
`.,
`S.SS9.9?8 A
`5.563.935 A
`
`3..-"1995 Suzuki .-M1, _____________ H _31(;.-gm
`41990 Whiting eta]
`4-':l‘J9fi Yoncmit.-au ct ill.
`5' ["95 511-518 5'51-
`6-"1996
`\7\-‘bis.-9,81
`.
`T"l99fi Wint::1's cl nl.
`1'-""1996
`.\JIa;.'ers at al.
`T.-‘I996 Gentile
`358.-‘L16
`I‘;;::§n‘;'“]'
`
`9 I996 Spilo ........................ .. m.'20.1
`................ .. 34|-"I05
`Ill-'l‘}‘}6
`S1l'0l'1:lck.eI'
`
`
`
`Illlflll
`Elllélildlwlll
`mfimnm mmm
`
`Pvuliflolllldlhhlespulw
`h'fl|I‘.l.|l!l
`
`Oracle 1039
`
`Oracle 1039
`
`

`
`US 7,190,284 B1
`Page 2
`
`71l"ll4
`700521-1
`.. 358-'1_15
`3587404
`
`
`
`..
`
`......... .. 395-"308
`382232
`
`3584.16
`
`
`
`395-'49’.-".04
`3957170
`
`11.1996 Miller el 3.1.
`5.5'72.206 A
`1171996 Chambers. [V
`5.577.248 A
`1231996 Shitmttlrl et al.
`5.584.008 A
`1251996 Uchara
`5.590.047 A '1'
`2.'l9'-)7 Cooper et al.
`5.602.976 A "'
`31997 I-Ianselrnan
`5.606.428 A
`431997 Rczttik
`5.631.403 A
`451997 Schocnzcit or al. ,.. 375-‘£40.05
`5.625.712 A "'
`5-‘I997 Miller el al.
`5.627.995 A
`7-‘I997 ("rail
`5.653.878 A
`12-‘I997 Bicevskis el al.
`5.606.912 A
`371998 Pclartck ct‘ ttl.
`5.714.582 A "'
`361998 Franaszek cl :1].
`5.729.228 A
`64998 Mssenns
`5.771.011 A
`‘H1993 Clark at al.
`5.773.255 A
`831998 C1‘Itrra.ct al.
`5.793.937 A "‘
`81998 Hatiatly
`5.798.718 A
`971998 Hovis e1 :1].
`5.812.817 A
`10.1998 Pearce cl
`:1].
`5.828.877 A
`1171998 Starlet:
`5.835.003 A
`1171998 Dye
`5.838.334 A
`375..'l40.l5
`131998 Canficlcl eltt].
`5.847.762 A
`12.1998 Vond.nJ.n el al. ............. .. 710.91
`5.351.742 A
`.Z.'1999 (‘ntfl
`5.874.908 A
`391999 (‘rail
`5.877.711 A
`331999 {J1-ttttrturtt
`5.883.588 A
`$1999 Kimura
`5.933.104 A
`871999 Higuchi
`5.936.560 A
`871999 Kalkstein
`5.945.933 A
`91999 Vaman ct :11.
`5.956.372 A
`1021999 Tsang
`5.96l.fii7 A "‘
`101999 I-leatlt
`5.973.630 A
`1251999 Dye
`6,002,411 A
`1251999 Chttdez
`6.002.814 A “‘
`5-“I000 Dye
`6.067.098 A
`11-"3000 Dye
`6.145.069 A
`1-".'£(J0l Dye
`6.170.047 B1
`l.-‘Z1101 Dye
`6.173.381 Bl
`332001 Banton ................ .. 358.-426.02
`6.198.850 B-1*
`3:'.‘.001 Dye
`6.208.373 Bl
`[11
`933001 Powell.
`6.292.194 131*
`1253001 Shitnomtua et al.
`6.333.745 B1
`1-"2004 Kitsugi at al.
`200470017483 A1"'
`FOREIGN PATENT DOCUMENTS
`
`710.4100
`
`3457521
`358.-'l.l5
`
`7.36792 B
`
`3-48.‘J07.*)9
`
`E1’
`JP
`W0
`
`0 702 457
`05204747 A “
`95* 1966.?
`
`3.-"1996
`8.-"1993
`7'1’.-3'95
`
`CDTI 113R PU Bl.l(.'A'l‘lONS
`
`Btenza. "Synonym Avoidance Cache." IBM "technical Disclosure
`Bulletin. vol. 34. No. 1. Jun. 1991. pp. 377381.
`lntemalional Searclt Report for Application No. PCTFIIS 00303355.
`rrtajlcd Jun. 16. 2000.
`1.1.8. Appl. No. 087463.106. filed Jun. 5. 1995. Dye.
`
`U.S. Appl. No. 6071*-14.125. 11ll2t1.11.Il. 16, 1999. Dye.
`[l.S. Appl. 1*-‘o. 097-5191.343. filed Jan. 26. 3000. Dye.
`LKS. App]. No. 093818.283. filed Mar. 27. 2001. Dye.
`‘Yabe at al.. Cot11pression."Decompression DRAM For Unified
`Memory Systems: A 16 Mb. ZUOMHZ. 90% to 50% GFflph1CS~
`Bartdwidtlt Reduction Prototype. IEEE [998 So1id—Sta1e Circuits
`Conference. Feb. 1998. pp. 343-343.
`1'-ijclso er al.. Design and Performance of E Main Memory l‘1.1Ll'€1Wa.l't.T
`Data Cotttpressor. EuroMict'o 96 Conference. IEEE. Sep. 1996. pp.
`423-430.
`
`“ cited by cxzuniner
`
`Prt‘matjt'
`
`.':‘.\-mttmezr-— Ilong Kiru
`
`(57}
`
`ABSTRACT
`
`An integrated mentory controller {IMC} including Memo-
`ryF."X Teciinology which includes data compression and
`decompression engities for
`improved perlonnance. The
`memory con1roller(lM(‘,l ofllie present invention preferably
`selectively uses at combination of lossless.
`lossy. and no
`compression modes. Data transfers to and from the inte-
`grated memory controller of the present‘ invention can thus
`be in a plurality of fornists.
`these being compressed or
`normal (I1t)1'l-Ct)t'tlprE.'SS6(1)_. compressed lossy or lossless. or
`compressed with a combination of lossy and lossless. The
`invention also indicates pl‘E!1iE:t'rEd methods for specific com-
`prcssiou and dccornprcssion of particular data lortnats such
`as digital video. 3D textures and image data using :1 com-
`bination of novel lossy and lossless compression algorithms
`in block or span addressable fomtats. To improve latency
`and reduce per1"orm:mce degradations normally associated
`with compression and decompression techniques,
`the
`Menloryl".-‘X Tee-ltnology encompasses multiple novel tech-
`niques stlch as: 1 1 parallel losslcss t:ompressi0nf¢lecompres'-
`sion; 2) selectable compression modes such as lossless.
`lossy or no compression: 3) priority compression mode: 4]
`data cache toehniqttes; 5) variable compression block sizes:
`6] compression nsortdcring; and 7] unique address transla-
`tion. attribute. and address caches. The parallel compression
`and decompression algorilllut allows ltiglt-speed pawl]:-1
`compression and high speed parallel dccorupression opera-
`tion. The IMC also preferably uses a special memory
`allocation and directory teclmjque tor reduction of table size
`and low latency operation. 'l1:te integrated data contpression
`and decompression capabilities of the [MC remove system
`bottle-necks and increase perlormattcc. This allows lower
`cost systems due to smaller data storage. reduced bandwidth
`reqttirelttcnts. reduced power and !‘lL‘llf-I-.‘.
`
`16 Claims, 34 Drawing Sheets
`
`

`
`A
`
`Cache E cpu
`195
`E
`
`Local Bus 1o5—-. H A
`
`8vs*emMem°rv11°
`ll
`
`Frame Buffer Memory 114
`
`A
`
`IIF
`
`A
`
`
`
`\ PCIIAGPBus
`
`107
`
`_
`Hard Disk
`go
`
`
`
`
`HO Subsystem
`Controlier
`115
`—
`
`Keyboard
`12
`
`Mouse
`12;‘
`
`_
`Audro DAG
`2.33:
`
`C
`
`A
`
`IIO Bus 113
`
`Fig. 1
`(Prior An‘)
`
`
`
`If]I78Z"[I6I"LSJ]PE1“I-I3-THIS.".l}llZTl‘-WW2|I.l3Z|Bd'S'f1
`
`
`
`
`
`

`
`
`
`
`IIO Subsystem
`Controller
`
`Video Display 142
`
`
`
`|{]p8Z"[]6I"LSJ]I‘-‘CJ02l€|3llSLUIIZTl‘JENJ|I.l3Z|Bd'S'f1
`
`
`
`
`
`Fig. 2
`
`m
`
`flfi
`
` Keyboard
`
`

`
`
`
`I8t’8Z‘06l‘LS11V53J“9WW51-003'51“W31313:]‘ST!
`
`
`
`
`
`
`Local Bus 106
`
`
`
`Local CPUr'RiSC IIF
`(lntegraterzi External)
`
`
`
`Audio 8. Modern
`subswem
`
`
`
`System Memory
`110
`
`
`
`
`Video IIO & Formal
`
`
`Memory Controlier
`Digital Video IIF
`Conversion
`wirh Mem§£yF!X Block
`_U
`E
`
`
`
`
`
`
`
`
`VDRL En ine &
`Display F F0‘s
`2_40.
`
`RGBJNTSC
`
`
`
`I...-......-..._._..-.-___._-.-_..._.-
`
`2DI3D!video Graphics
`Eng. VGA
`M
`
`
`
`Peripheral Bus I30 Interface
`E
`
`Fig. 3
`
`

`
`
`
`
`
`[8fr8Z‘06[‘,'_SflI’-'1.‘J01-‘wellsr'.130Z't'['-WINJIIBJEJ'S'fl
`
`
`
`
`
`29
`
`_______ _ _ _R§'l“E5£3_"§’903153.31
`
`III1
`
`Address Bus 1 215
`
`Data Bus 1 216
`
`Address Bus I1
`
`Data Bus n
`
`
`
`
`Parailel Compression 8. Decompression Unit
`251
`
`110
`
`
`
`
`
`Compression
`Control Unit
`
`_____________ _ _
`
`L3 Data Cache
`
`Compressed Data
`Directory
`E
`
`

`
`“* I
`
`
`‘
`
`E
`
`III
`
`Memo
`_ Switcltny
`,
`§l‘i
`
`~
`
`Compress
`-I switch
`_5_1_6,
`Dat
`
`III
`
`T L
`
`'
`
`I
`
`I
`
`'
`
`-
`Compression
`E""'"° E
`Compression
`Engine
`
`Decompression
`Engine E
`""""fin?
`Decompression
`Engine
`
`'
`
`Memo
`lntenacrzye
`.5511
`
`
`
`mama'S'fl
`
`§
`
`5*‘
`§
`“
`
`"'
`"
`3-;
`
`DRAM
`Controller
`.532.
`
`DRAM
`HOIIF
`E1
`
`CAT
`
`rggg
`
`l
`
`.
`Fr9- 5
`
`u
`
`Key:
`— c
`§-A33?£-"$1"
`T - Tag
`L - Length
`Ty - Type
`
`
`
`S - Status Iflt'8Z‘06l‘LSn
`
`

`
`Inpui Data
`
`Entry
`
`Entry
`
`Entry
`
`Entrysi ss
`ssss 5:?
`snsssssm
`Wsassss
`
`C
`
`n-2
`
`Byte!)
`
`2
`
`5
`
`. 6B
`
`"Art)
`
`
`
`
`
`
`
`
`
`[8|v3Z‘06[‘LSfll'-'}.‘J09Walls’L001‘?!‘WINJIIBJBJ'S'fl
`
`

`
`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 7 of 34
`
`US 7,190,284 B1
`
`Parallel Compression
`
`Maintain a history table
`comprising entries
`4.02
`
`Maintain a current count of prior
`matches for each entry in the
`history table
`
`4%
`
`Receive Uncompressed data
`fl
`
`Compare a plurality of symbols with
`each entry in history table
`
`
`
`Determine match information for each
`of the plurality of symbols based on
`the current cc-untlzland compare results
`
`_1_Q
`
`Output compressed data in response
`to the mattih information
`.__2
`
`Fig. 7
`
`

`
`
`
`
`
`
`
`[flf73Z‘0fi[‘,'_SflIVEJ“813'-HISt‘.00Z't'I'-WWIHIBJBJ'S'fl
`
`
`
`
`
`
`
`Start
`
`‘W U"°°."‘|’"’55°d 35'”"’°'3
`to Hastnnr window
`31
`
` Yes
`
`Ft sh Ramainin
`U
`Matchtgp
`m
`
`revbus
`F
`
`Add Uncompressed Symbots
`to History Window
`m
`
`
`
`°”ft”n".~3fi°l‘e§s‘2‘é”°'
`i_
`
`c°J3§1'§c7aa53{1§§$ 21%”
`at
`
`Any
`Matches?
`
`“°
`
`Output Previous
`Compressed Data Info
`434
`
`
`
`
`
`Output Symbol
`Uncompressed
`ifii
`
`
`
`Output Compressed
`.
`.
`r IS Match Include
`
`the '35‘ Symbol?
`Dagafiénfo
`
`
`
`araltel. Shown
`Performed in
`serially for e-age of Iltuslrahun
`
`Reset Counter to Max of
`Symbol Count In Match
`7.3
`L
`
`r...--—._.....-_-.---..--.------------------------
`
`Increase Counter by
`# of Symbuls
`M
`
`Yes
`
`one match?
`
`442"'7
`
`
`
`
`
`
`Select Largest Match
`-
`-
`Inciudlng Pfimus Match
`
`Output Previous
`Compressed Data Info
`E
`
`Fig. 8
`
`

`
`Entry D Data Byte
`
`610
`
`Data 3
`
`Data 2
`
`Data 1
`
`Data 0
`
`UGO—smt..>
`
`Compare
`Outputs to
`Later
`Entries
`
`Entry D Counter
`511*!
`
`£513.51
`
`Results
`Catcutation
`
`Output Mask
`
`Output Count
`
`Fig. 9
`
`
`
`|{]pSZ'[|6I"LSJ]I‘-"E1°6-l33llSLUIIZTl‘JENJllallfid'S'n
`
`
`
`
`
`

`
`
`
`
`
`[8r3Z‘0fi[‘,'_Sflt-‘EJ9Ill133118L001‘?!'«‘“M.|JIIBJBJ'S'fl
`
`
`
`
`
`
`
`Ent
`
`0 Count & Mask
`
`Entry 1 Count & Mask
`Ent
`2 Count & Mask
`_
`;
`
`Ent
`
`n Count 3. Mask
`
`Ent 0 Count & Mask
`
`1 Count & Mask
`Ent
`Em 2 Cflunt & Mask
`
`Ent
`
`‘
`n Count 8: Mask
`
`Ent
`
`0 Com ress Mask
`
`Prev Count Index
`
`
`
`Output Stream
`
`
`
`
`.51_3
`
`
`:
`
`Combined Comress Mask
`
`En
`
`n Compress Mask
`
`Fig. 10
`
`Output Data Stream
`
`Reset Value
`
`Max Count Index
`
`
`
`To Results Calculation
`
`Data
`0
`
`Data
`1
`
`Data
`2
`
`Pm”
`Data
`3
`
`

`
`
`
`ISt78Z‘06l‘LSf]N31“ll1"‘“|S3-003'*31°“"'WJuaflgd‘ST!
`
`
`
`
`
`Fig. 11
`
`Output
`Counter
`
`Saved +4
`
`Saved+3
`
`Savedi-2
`
`Saved+2
`
`Saved+1
`
`Saved+1
`
`Saved+1
`
`Saved+1
`
`Saved
`
`Saved
`
`Saved
`
`Saved
`
`Saved
`
`Saved
`
`Saved
`
`Saved
`
`Output
`Mask
`
`Reset
`
`Value
`
`10000
`
`10001
`
`10010
`
`10011
`
`10100
`
`10101
`
`10110
`
`10111
`
`11000
`
`01111
`
`11010
`
`11011
`
`11100
`
`11101
`
`11110
`
`11111
`
`It-1:5-I:-43-J3--I3--it-I5!-(.IJ(D(a)(.I)hJ|‘hJ—I$
`
`New Counter
`
`Value
`
`Saved+4
`
`0 |
`
`:J—'-€:lI'\.JC)—ICDLn>l:'J-5CJl\JZ—K
`
`Input Matches
`Iiillifl
`1
`1
`1
`
`1
`
`1
`
`1
`
`1
`
`1
`
`1
`
`1
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`D
`
`1
`
`1
`
`1
`
`D
`
`0
`
`0
`
`0
`
`1
`
`1
`
`1
`
`1
`
`0
`
`0
`
`D
`
`0
`
`1
`
`0
`
`0
`
`1
`
`1
`
`0
`
`0
`
`1
`
`1
`
`U
`
`D
`
`1
`
`1
`
`0
`
`D
`
`1
`
`3-5-$—l§—K§—l§—i-§—|-§—¥CI
`
`

`
`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 12 or 34
`
`US 7,190,284 B1
`
`
`
`Send out
`
`compressed block
`IE
`
`Adjust max count
`to 4 or less
`E
`
` Yes
`
`
`
`Mask — 10000?
`1.23
`
`
`No
`
`Send out
`compressed block
`731
`
`No Yes
`sendou
`
`Z3
`
`No Yes
`
`Send LZ12
`compressed block
`E
`
`
`
`Yes
`
`
`
`CCM(O) = 1?
`
`7_4_9
`
`
`No
`
`Send out data 0
`E
`
`N0
`
`Send out data 0
`Z51
`
`No
`
`Send out data O
`M
`
`Fig. 12
`
`Done
`
`

`
`U.S. Patent
`
`Mar. 13,2007
`
`Sheet 13 of 34
`
`Us 7,190,284 B1
`
`Entry
`
`0‘l2345B?B91D1112131415
`
`smonw EHEEHEEHHEHHEEEE
`cm mmmmmmmmmmmmmmmm
`
`Input D3:U COF?F3F9
`
`mwmmm@@mmmmmmmmmmmm
`Mam"! IEIIEIEEI
`
`sm1om mnflnmflnnflflfinnflflm
`cm @m@@m@@mmmmmmmmm
`
`Input D3:0
`
`FOF1F2B5
`
`wwmm@mmm@mmmmmmm@mm
`mm=nnn@nnflnm@flnnmnm
`I
`OW
`smzvm Efliflflflflflflflflfiflflfifl
`Cow“
`IEIEEIEIEEIIEIIEIEIEIEIEIEIIEIIEIIEJ
`
`InputD3:fl
`
`wmmm@mmmmmmmm@mmmmm
`Maskout |i'l|T_F||l'l
`OW
`mm mm EHHHHHEEHHEHEHEH
`CM IEIIEIIEIIEIIEEIBJIEIEIEJEIEIEIIEIEIEI
`
`|nputD3:O
`
`state»:
`
`mmmmm@mmmmmmmmmmmm@
`mmtflmflwflflnmmflflflnmnfl
`Output
`were IE2!
`001"“
`EEIEIEIEIIEIEIE]lE|[EJ|Ell'£Jl'§lElIEAItema:eoutpu:
`Finaloutput
`
`1 3
`
`Alternate Output
`
`

`
`

`
`
`
`
`
`[HI78Z"{I6I"LS1]175J051133115L002"El‘JENIlllallfid'S'f1
`
`
`
`
`Select Generation
`
`
`
`><—=cv><¢'>EI_
`
`—~¢=r><><I:J._¢'_‘-I_
`
`C3)-(DI:-‘
`
`A!
`C
`0
`X
`1
`X
`
`B.‘
`D
`X
`0
`X
`1
`
`Output
`
`A
`3
`C
`D
`
`A)‘
`
`B 0 1 X X
`
`Fig. 1
`
`Select
`
`
` l._'%flI
`
`2
`Co
`
`re
`
`2 Way
`Compare
`
`

`
`-...-..--._._-.._- .._....__......_.......................................................—..-........_............_........r
`
`Lossy Compression Engine fl
`
`121
`
`r..__........_._._.._.._._...._..................-......-..-..........-....-.....-.-—-.......——-........_........._...._..-...
`Loasy Decompression Engine fl
`
`GmmmC
`
`
`
`Fm.3:2:2»:B.2::2.3.3$3cm.._.E=.~§E
`
`
`

`
`
`
`lIl3J3d‘STI
`
`3 ?
`
`:7»hi
`5
`“'
`
`[Hf*8Z'0(‘-1'1’.S11
`
`
`
`
`
`
`Fig. 19
`
`Amax=Amin = Dxfll]
`--
`3
`Ymax=Ymin
`AmaJ:=Amin=fixFF
`~
`— EDIE
`E
`max = Amin .!= 00 or FF IEEEEIIEE
`;'
`—:EEI[EEE [E1313 413 "5
`-
`Yrnax IEEIEEI 01
`
`15b1'f5 —— if:
`‘"3 bits
`_— HE Bbits EEEEEI 4f3 bits
`_ I@IID%_ 3?-9 B fies
`T WHERE 4:‘?! bits
`418 bits
`32 tilts jj
`IEIEEEIEEIEEIEJEEEIIEEIE ‘NB 3 135
`T E Bblts mmmm 4!8 bits
`4i8bIts [Maj
`9H0 B 195
`
`
`—— 5bitS5bil8 5bit54!3bilS 32bif5
`
`%@
`—_fi
`
`E
`—:@
`IEEI
`
`E
`
`
`
`
`
`
`
`

`
`INPUT Bus
`
`Loss-"Les; Parallal
`Compres§_:%n Engine
`——————— — —
`
`—
`
`Memory Bus
`
`Compressed
`Data
`
`
`
`10913-d'STl
`
`Lossy Compression
`Engine
`£15
`
`_____________ _ .
`
`Lnssy Decompression
`En Ina
`
`fij
`-—- - --uv Decornpressad Data
`
`
`
`Engine
`
`§
`
`5 3’
`
`=
`--I
`
`m='
`FD
`2
`
`ED
`""
`E
`
`W"
`
`:75
`2"
`E
`1:’
`
`g E
`
`— — —FrI'rnaryoompres5ion
`___ _ _ _ '"[9"T‘9°"3°9
`Decompression
`----------- Decompression
`
`Loss-Less Parailel
`Decompression
`
`‘:
`
`fig
`
`E
`
`‘""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
`
`Compressed Data
`"""""""""""""" "
`.
`Fig. 20
`
`

`
`310
`
`320
`
`330
`
`340
`
`350
`
`§§¥\.\§
`
`Texture
`_310_2
`
`3D-DL
`fl
`
`2D-DL
`m
`
`DV-DL
`E
`
`VDRL
`fl
`
`
`KC!’
`
`
`
`-
`
`-
`
`°es=m"°"°ata
`
`Dlcmp
`
`Crnp
`
`.
`
`l—Cmp
`
`-
`
`may
`
`,
`
`Hg. 21
`
`360
`
`370
`
`380
`
`390
`
`396
`
`300
`
`
`
`
`
`[8|v3Z‘06[‘,'_SflHEJ“6!“N181'.Bl]Z'%Tl'«‘“M.|JIIBJBJ'S'fl
`
`
`
`
`
`

`
`U.S. Patent
`
`Mar. 13. 2007
`
`Sheet 20 of 34
`
`US 7,190,284 B1
`
`Compression of received data
`
`Receive uncompressed data
`
`5.0.2
`
` Determine a compression mode
`
`of the data
`QEL4.
`
`Selectively compress the
`uncompressed data according to the
`compression mode
`
`5.0.6.
`
`
`
`Store the data in the memory; store
`compression mode information with
`the data
`flfi
`
`
`
`
`Fig, 22
`
`

`
`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 21 of 34
`
`US 7,190,284 B1
`
`Access compressed data
`
`Receive a request for the data
`812
`
`Access the data from the memory
`.8.1_4
`
`Determine a compression mode
`for the data
`§l§
`
`Selectively decompress the data
`according to the compression mode
`BE
`
`Provide the data in response
`to the request
`
`QZQ
`
`Fig. 23
`
`

`
`Address (31:01
`
`
`
`Compressed Address Translation Table [GATT] Overflow Address Table {OAT}
`?2 bits per entry
`53 bus per entry
`1 entry per oompressed memory range
`256 entry max
`2?1(]
`
`
`
`Note:
`CATT not required for
`single address range
`implementations
`['re frame buffers} Initiai Allocation Area
`
`Memory Block Equal in srze to Memory Range
`
`Srze Divided by Maximum Compression Ratio.
`
`
`Contains one compressed block for each
`uncompressed block.
`
`Zlfl
`
`
`
`
`
`
`
` Ii]f78Z‘{Ifi[‘,’_Sf]H?J“U139115‘r‘.GOZ'€I"WINIIIIGJBJ'S'fl
`
`
`
` Overflow Area
`
`Memory Block Contains all remaining
`
`compressed blocks for each
`
`uncompressed block.
`
`
`E
`
`Decompression Engines
`flf fl
`
`Add! (1110)
`
`Output Formal Switch
`§§§
`
`
`Compressed Data
`
`2'-L9.Q
`
`Header
`
`Deoompressed Data
`
`F,"g_ 24
`
`
`
`

`
`
`
`
`
`IflI?8Z‘|]I6l‘LSflif19£2l93llSL002'5!'~"‘|r\lJIIBJBJ"S'n
`
`
`
`
`
`Memory Allocation Fields
`
`Starting Addr
`20 bits
`
`4GB Addressabllily
`4K Boundry
`
`Ending Addr
`20 bits
`
`Type
`-3- SU!
`'
`
`ala Plr
`0 bits
`
`OAT Ptr
`
`Compressed
`K Boundry
`Blk Size
`4K Boundry
`Overflow Address Table (DAT)-258 Entry Max
`
`4K Boundry
`
`ED bits
`
`24 bits
`
`8 bits
`
`
`
`‘_m E"i-v-
`
`ieaacaressabmw
`axaoundw T
`lnllial Header Description
`Meaning
`I
`
`Value
`
`bits
`
`1oA{2n no
`11 iA{a+20 bins:
`
`Last B|ocldUnusecl
`
`m2
`
`_Z The nexl block follows physically after this one
`10A (8 bits}
`The next block is A blocks before this one {or after?)
`110A [20 bils} E The next block is at offset A in lhe Overflow Area
`11 1 IA {a+2o bits]
`The next block is at offset A in the Overflow Area of DAT entry I
`
`Fig. 25
`
`

`
`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 24 M34
`
`US 7,190,284 B1
`
`@Memory Allocation
`[initialized GATT)
`2709
`
`2.711.
`
`Allocate CATT Ent
`
`Arrange entry order
`(if required basedzofri gtartlend address)
`
`Set the compression type
`271 5
`
`A|locate% of the requested memory
`(Based on block size and compression type)
`2717
`
`Set the data pointer to start at the initial block
`in the CATT
`2719
`
`
`
`Allocate Overflow Address memory (DAM)
`(Set by IMC driver or BIOS)
`Typically 118th original data size
`
`2721
`
`Initialize the OAT pointer in the CATT
`2723
`
`Initialize allocated memory headers to zero
`2725
`
`initialize OAT entries, set overflow
`pointer in DAT
`2727
`
`Fig. 26
`
`

`
`US. Patent
`
`Mar. 13, 2007
`
`Sheet 25 of 34
`
`US 7,190,284 B1
`
`
`
`
` @Compressed
`Memory Store (Addr N)
`MB.
`
`
`
`
`Yes
`
`Check
`Cache for Hit
`While searching CA1T
`
`E11.
`
`No
`
`
`
`
`
`Calculate Initial Address I, continue to
`compress data (Validate present entry)
`ZE
`2?§3
`
`
`
`H = Header
`from Address I
`
`
`
`
`
`Remaining
`Compressed block
`:>Btock Size?
`
`(531 Next
`Add,-955 (U:f(H))
`gfl
`
`
`
`
`
`
`
`Store block of Compressed data at
`address I with header=LAST
`
`2737
`
`Store btock of Compressed data at
`address I with2t1?e:r3a9der(U) Set I=U
`
`
`Q H2=HeaderfromAddress H Set
`
`
`Yes
`
`Store uncompressed btock and header
`at Add N in cache and set most
`recently modified bit for cache
`2_74t§
`
`header of H to UNUSED Set I-i=f(H2)
`2745
`
`Done
`
`Fig. 27
`
`

`
`U.S. Patent
`
`Mar. 13,2007
`
`Sheet 26 of 34
`
`US 7,190,234 B1
`
`-
`Deliver dezztggom cache
`—
`
`
`
`
`@Memory Fetch
`(address N)
`E
`
`Yes
`
`
`
`Search
`Cache Directory HIT?
`
`2_?'5i
`
`No
`
`
`
`Solve for initial address (I) = (Matching
`GATT start address - N){)(
`(X is based on data type)
`
`2753
`
`Fetch from memory
`compressed block I
`2755
`
`Strip the Header bits, and decompress
`the remaining data from I
`2757
`
`
`
`Fetch the overflow block using the
`overflow pointer as base and the
`header as offset
`E
`
`
`
`LAST Biock?
`2&1
`
`Yes
`
`Read compressed overflow blocks
`2756
`
`Send decompressed data to
`requesting agent
`Zlfifi
`
`Update Cache, invalidate LRU, mark
`new block as MRU
`2769
`
`Completed compressed
`read operation
`
`Fig 28
`
`

`
`Get next
`
`
`
`address §R=fiH]}
`
`32.2
`Caiculate next trl-oak adtfress poinnar
`
`A = 1(H2?eoader N:
`___E
`
`
`
`
`
`bmck OAT En1ry{u||'F
`2?93
`
`Read Ouesllovn Header @R
`
`
`
`
`
`
`
`New Overflow pointer from OAT
`@nex1 painter
`E
`
`
`
`is next
`
`overflow pointer uaiid?
`
`
`R = R+B|ocI: S‘ e
`
`Dues
`header ilidlcated Unused '?‘
`£011.
`
`Next address painter = R 0 block size
`
` [HI78Z"[I6I"LSf]PE10L2-l33llSL003"El'-WWI|Il3Z|Bd'S'f1
`
`
`
`
`
`
`
`Atlocate new black afflverflaw memory
`and OAT ann-
`270‘-
`
`
`
`
`Store resulling poinier in
`next address poirler
`ZIQE
`
`Set new OAT painter and valid bit
`EYE
`
`Calculaua new ovadluw block address
`[Fll= ffUVI1Pn1.r, ofiset. block size]
`2705
`
`
`
`
`
`
`

`
`
`
`Header
`
`win OF
`
`02%
`
`o
`
`5%
`6%
`
`
`
`a1%
`
`4-3%
`1- 33%
`13%
`11-5%
`
`
`
`
`
`
`
`Header
`
`WIOF
`
`Fragmented
`4.1%
`4.2%
`4.3%
`
`Fig. 30
`
`4.3% [HI78Z'[I()I"LSJ]ff1082.’133115L002‘El‘JENI|Il3Z|Ud'S'f1
`
`

`
`/- 251D
`
`Comgression block §256b[les)
`
`I
`
`I
`
`g
`
`5
`
`
`
`an“
`Intermediate Bfioclvr Seigrnent (32bytes)
`
`Original
`Order‘
`
`/- 2530
`
`1) Read compressed block from memory
`
`2) Decompress to L3 data cache
`
`New read address
`
`3) Store Position tag (@F) in table
`
`4) Re - compress block out of order
`
`/- 2520
`
`5) Attach header with tag (@F)
`
`' Header tag field is '0' indicating in original order
`
`6) Write compressed block back to memory
`
`New
`Compressed IEIIEIIZE
`Order“
`
`“ Header tag field is '5' indicating out of order
`
`Fig. 31
`
`
`
`
`
`If]I78Z."[lfiI"LSJ]I751"63|33llS.".l}0Z‘£l'-WW§|lI3Z|l3d'S'fl
`
`
`
`
`
`
`
`

`
`B hasE
`
`ZZZZTEZZZ
`Ijflflijjj
`Ztfilwflijj
`Ziflmjjjtfl
`jfiijj
`jfijj
`Zijjj
`jjjj
`jfijj
`Zifijj
`jtfljj
`jfiijj
`Eflj
`
`Fig. 32
`
`
`
`
`
`rt100:-|'v3-3115L130:‘El'4'-‘«'w1uaJc.,['g'f1
`
`
`
`
`
`
`
`I8P8Z'[i6I':‘.SJ1
`
`

`
`U.S. Patent
`
`Mar. 13,2007
`
`Sheet 31 or 34
`
`Us 7,190,284 B1
`
`Input Data 8 Bytes
`
`Stage 1: initial lnput Selector and Byte Counter
`
`Stage 2: Calculate Initial Selects and Overflows
`Partial Selects and Overflows
`0
`.
`.
`.
`.
`.
`. 15
`
`25501 —\,~
`
`25503 «X
`
`25505 \
`
`25507 —\
`
`25509 -\
`
`Stage 3: Calculate Final Selects
`Final Selects
`.
`.
`.
`.
`.
`
`. 15
`
`0
`
`T
`
`Pie Reister 128 bits
`
`Stage at: Data Selection
`D
`ata ut
`
`Data
`
`History Window
`
`

`
`U.S. Patent
`
`Mar. 13, 2007
`
`Sheet 32 or34
`
`US 7,190,284 B1
`
`Input Data
`D0:D63
`
`D0:
`D24
`
`D9: D10:
`D8:
`D63 D63 D63
`
`25521
`
`D25:
`D63
`
`IE0:
`
`E10: E13:
`E55 E55
`
`—F
`
`0:
`
`E55
`
`Data Index
`Byte
`
`Count
`
`F47
`
`25525
`
`Data mdex
`Byte
`
`F9:
`F10: F13: F25:
`F4?
`F4?
`F4?
`F4?
`4 T
`2
`Count
`Go:
`639
`
`25527
`
`Data max
`Byte
`
`4
`
`Count
`
`°°"“‘
`Data index
`
`(39: G10: G13: G25:
`G39 G39 G39 G39
`—
`H0:
`H31
`H10:
`H31
`
`25529
`H13:
`H31
`
`H9:
`H31
`
`We
`
`Start Counts
`
`
`
`
`4 —
`
`
`Count
`
`J9:
`J23
`
`J0:
`J23 25531
`J10:
`J13:
`J23
`J23
`
`— K
`
`0:
`K15 25533
`
`Data Index
`Byte
`
`K33
`K15
`
`Deooderfi
`
`Data |ndex
`Byte
`
`Data Index
`Byte
`
`25535
`
`Fig. 34
`
`

`
`
`
`1|131l3r[‘SW1
`
`2 F
`
`3
`
`'5CD
`--I
`
`:"
`
`.J1
`
`3
`3
`a
`,3A
`
`I8P830611Sfl
`
`Fig. 35
`
`I
`
`I
`
`I
`
`D0:6
`
`DB
`Check
`2&6:
`
`5115
`243
`113
`Check
`Check
`Check
`2% 2% 255$:
`
`>113
`Check
`151%
`
`4 T
`
`1
`1-1
`111 Generate
`—_—_'II
`
`T
`
`

`
`Previous
`Select
`
`10
`
`08
`
`04
`
`02
`
`
`
`IF
`IF
`IF
`IF
`IF
`IF
`IF
`IF
`
`
`
`01
`
`
`IF
`IF
`IF
`
`IF
`IF
`IF
`
`IF
`IF
`IF IF
`IF
`IF
`
`IF
`IE
`IE
`
`IE IE IE IE 00
`
`IE IE IE 1C 00
`
`08
`
`00
`
`00
`
`00
`
`00
`
`Figure 36a
`
`X
`D2:D7
`PC+I
`
`D1 :D3
`X
`PC+I
`
`X
`D7:D12
`D4:D9
`D2:D3+PC+2 D4:D6+ PC+5 D13 :D24+PC
`
`Figure 36b
`
`
`IF
`IF
`
`888888888
`
`
`
`
`
`lfl'|78Z"[)fi["LSf]ff.19ITJ-93llSL003‘fl'-WWIIIIBJE‘-I'S'fl
`
`
`
`
`
`

`
`US ?,190,284 El
`
`2
`
`1
`SELECTIVE LOSSLESS, LOSSY, OR NO
`COMPRESSION OF DATA BASED ON
`ADDRESS RANGE. D.-i.'l'A ’l'YI’E. AN DIOR
`REQUESTING AGENT
`
`(.'D1\ITlNU_I\'l‘ION IJATA
`
`This application is a continuation-in—part' (ClPl ol'Ser. No.
`0-$916,464,
`tiled Aug. 8, 1997, and now US. Pat. No.
`6,17?-.331, issued on Jan. 9, 2001;
`which is a continuation-in-part (C'.[P] of Ser. No. 08.-’-163.
`106. liled Jim. 5. 1995. now abandoned:
`
`which is a continuation-in-part (_C'lP) ol‘Ser. No. US$40,
`667. liled on Nov. 16, 1994, which is now ll.S. Pat. No.
`6.002.411, issued on Dec. 14. 1999.
`
`FIELD OF THE INVENT ION
`
`The present invention relates to computer system archi-
`tectures. and more particularly to a memory controller which
`includes an cmboided data compression a11d decotnpression
`engine for the reduction oi‘ system bandwidth and improved
`elIiciency_
`
`DESCRJ PTION OF Tl-IE RELATED ART
`
`Since their introduction in 1981. the £tl'Cl‘IilBCTtIDe of per-
`sonal
`computer
`systems
`has
`remained
`substantially
`unclianged. 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 :1
`separate graphical ihter1'ace tor coupling to the video dis-
`play. in addition, the computer system includes input!output
`(IEO) control
`logic for various l2'(J devices.
`including a
`keyboard. mouse. lloppy drive. hard drive, etc.
`In general. the operation of modern computer architecture
`is as follows. lirogratrts and data are read from a respective
`U0 device such as a floppy disk or hard drive by the
`operating system. and the progrants and 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 tttattipttlaled 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 WRAM}. 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 systems typically include a local bus video system
`based on the Peripheral Componcnt Interconnect (PCI} bus.
`the Advanced Graphics Port {AGP), or perhaps another local
`bus standard. The video subsystem is generally positioned
`on the local bus near the C‘ PU to provide increased perfor-
`mancc.
`
`Jr
`
`lll
`
`15
`
`30
`
`40
`
`43
`
`:2: 'Jr
`
`6|]
`
`Tlterefore, in summary. program code and data are first
`read l.l‘0l1‘t. the hard disk to the system memory. The program
`code and data are then read by the CPU liont system
`memory. the data is processed by the CPU. and graphical
`data is written to the video RAM in the graphical interface
`device for presentation on the display monitor.
`The systcnt memory interface to the nternory controller
`requires data bandwidth proportional to the application and
`system requirements. Thus.
`to achieve increased system
`perl'ormancc, either wider data buses or higher speed spe-
`cially memory devices are required. These solutions Force
`additional side-etfects 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 btts in a normal or non-compressed format, and
`then writes the processed data or grapltical data back to the
`U0 btts or local bus where the graphical hiterface device is
`situated. The graphical itttet‘li3ce device in lt.n'n generates the
`appropriate video signals to drive the display monitor. It is
`noted that prior art‘ computer architectures autd operation
`typically do not perform data compression artdfor decont-
`pression during the tmttsfer between system tnctnory and the
`CPU or between the system memory and the local IEO bus.
`Prior art contputer architecture also does nothing to reduce
`lltc size of system memory required to l'1.1l't the required user
`applications or so liwarc operating system. In addition. soft-
`ware control led compression and decompression algoritluns
`typically controlled by the CPU [or 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 soliware controlled
`compression and tlecottlpression algoritlitns put additional
`loads on the CPU and CPU cttcltc subsystems.
`Certain prior art systems utilize multiple DRAM devices
`to gain improved memory bandwidth. These additional
`Dl{.=\M devices may cost the manufacturer more due to the
`abundance of memory that is not fully utilized or required,
`The multiple DRAM devices are in many instances included
`primarily for added bandwidth. and when only the added
`banclwidllt is ttecded. additional cost is incutted due to the
`tttttltiplc DILAM packages. For example. if a specific com-
`puter system or consuiner computing appliance such as a
`Digital TV" set-top box uses DRDRAM memory and requires
`more than 1.6 tibyteslsec ol’ bandwidth, then the minimum
`amount of memory tor this bandwidth requirement will be
`16 Mbytes. In such a case the manufacture pays for ]6
`Mbytcs even if the set-top box only rcqtlirtzs S Mbytcs.
`Computer systems are being called upon to perform larger
`mid more complex tasks that require increased computing
`power. In addition. modern soliware applications require
`computer systems with increased graphics capabilities.
`Modern software applications include graphical user inter-
`faces [_GUls] which place increased burdens on the graphics
`capabilities of the computer system. Further. tlte increased
`prevalence of multimedia applications also demands com-
`putcr systems with more powerful graphics capabilities.
`Therefore. :1 new system and method is 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 U0 buses required itt prior art cornputer syslcnt
`architectures.
`
`

`
`3
`SUMMARY OF THE INVENTION
`
`US ?,190,284 El
`
`4
`
`5
`
`ll.l
`
`15
`
`NJ
`
`As mentioned above, according to the present invention
`the McmoryI’)'X Technology embedded within the IMC
`includes one or more compression and decompression
`engines for compressing and decornpressing. data within the
`system. In the preferred embodiment the MeraoryF/‘X Tech-
`nology comprises separate compression and decompression
`engines.
`In an altentate embodiment. a single combined
`compression/decompression engine can be Implemented.
`Tlte JMC preferably. primarily uses a lossless data compres-
`sion and decompression scheme. Data transfers to and front
`the intcgmted memory controller of the present invention
`can thus be in either two formats, these being compressed or
`normal t_non—cornprcsscd}. The IMC‘ may also include one or
`more lossy compression schemes for audiolvidcofgraphjcs
`data.
`
`Thus cotnpresscd data front system lr‘O peripherals such
`as the non-volatile mentory.
`floppy drive. or local area
`network ("LAN") arc decompressed in thc IMC‘ and stored
`into system memory or saved in the system memory in
`compressed format. Thus. data can be saved in either a
`normal or compressed format. retrieved from the system
`memory for C‘PU usage in a normal or compressed formal‘.
`or transmitted and stored on a medium in a normal or
`compressed l‘onnat.
`To improve latency and reduce performance degradations
`normally associated with compression and decompression
`techniques. the Memoryliffii Technology encompasses tutti-
`tiple novel techniques such as: 1] parallel lossless compres-
`sionfdecornpre-ssion; 2) selectable compression modes such
`as lossless. loss-y or no compression: 3) priority compression
`mode: 4) data cache techniques: 5] variable compression
`block sizes; 6] compression reordering; and 7) unique
`address translal ion. attribute. and address caches.
`
`The present invention comprises a memory controller.
`also referred to as the integrated memory controller (IMC).
`which provides improved data efliciency and batldwidth.
`The rnemory controller includes a compression!'decon‘tpres-
`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 soliware changes for operation. The memory con-
`troller logic of the present invention preferably interliaccs to
`the system CPU either external or internal to the memory
`controller. Further. the memory controller interfaces to the
`main system mem