Memory controller including embedded data compression and decompression engines

• US 6,173,381 B1
• Filed: 08/08/1997
• Issued: 01/09/2001
• Est. Priority Date: 11/16/1994
• Status: Expired due to Term

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Interactive Silicon, Inc.
• Inventors: Dye, Thomas A.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): KIM, HONG CHONG
• Application Number:
  US08/916,464
• Time in Patent Office: 1,250 Days
• Field of Search: 395/341, 395/888, 395/133, 395/159, 711/203, 711/170, 711/160, 711/133, 711/134, 711/136, 711/155, 711/159, 711/165, 709/247, 345/521, 345/202, 345/509, 710/68, 714/763, 714/764, 382/232
• US Class Current: 711/170
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G09G 2340/02 Handling of images in compressed format, e.g. JPEG, MPEG
• CPC Class Codes: G09G 2340/0407 Resolution change, inclusive of the use of different resolutions for different screen areas
• CPC Class Codes: G09G 2340/125 wherein one of the images is motion video
• CPC Class Codes: G09G 2360/121 using a cache memory
• CPC Class Codes: G09G 2360/125 using unified memory architecture [UMA]
• CPC Class Codes: G09G 5/02 characterised by the way in which colour is displayed details of colour display specific for CRTs G09G1/28; specific for flat matrix panels other than liquid crystal displays G09G3/2003; specific for liquid crystal displays G09G3/3607
• CPC Class Codes: G09G 5/14 Display of multiple viewports
• CPC Class Codes: G09G 5/363 Graphics controllers
• CPC Class Codes: G09G 5/39 Control of the bit-mapped memory

Abstract

An integrated memory controller (IMC) which includes data compression and decompression engines for improved performance. The memory controller (IMC) of the present invention preferably sits on the main CPU bus or a high speed system peripheral bus such as the PCI bus and couples to system memory. The IMC preferably uses a lossless data compression and decompression scheme. Data transfers to and from the integrated memory controller of the present invention can thus be in either two formats, these being compressed or normal (non-compressed). The IMC also preferably includes microcode for specific decompression of particular data formats such as digital video and digital audio. Compressed data from system I/O peripherals such as the hard drive, floppy drive, or local area network (LAN) are decompressed in the 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 CPU usage in a normal or compressed format, or transmitted and stored on a medium in a normal or compressed format. Internal memory mapping allows for format definition spaces which define the format of the data and the data type to be read or written. Software overrides may be placed in applications software in systems that desire to control data decompression at the software application level. 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 requirements and reduced bandwidth requirements. This also increases system bandwidth and hence increases system performance. Thus the IMC of the present invention is a significant advance over the operation of current memory controllers.

Claims

1. A method for managing memory accesses in a system including a CPU, a system memory for storing data, and a memory controller coupled to the system memory, wherein the memory controller performs memory control functions for the system memory, wherein the memory controller includes a hardware compression and decompression engine, the method comprising:

the CPU initiating an access of data in the system memory, wherein the system memory is a volatile memory which stores uncompressed data currently being used for execution by the CPU, wherein the uncompressed data includes most recently used data;

determining a replacement block of data in the system memory after said initiating;

the memory controller compressing said replacement block of data;

the memory controller storing said compressed replacement block of data in said system memory after said compressing said replacement block of data;

wherein said compressing said replacement block of data and storing said compressed replacement block of data in said system memory operates to free up at least a portion of said system memory;

the memory controller performing said access of data in the system memory.

2. The method of claim 1, wherein the CPU initiating an access of data in the system memory comprises the CPU initiating a read of requested data in the system memory, wherein the memory controller performing said access of data in the system memory includes:

the memory controller providing said requested data to the CPU.

3. The method of claim 2, wherein the requested data resides in the system memory in a compressed format, wherein the memory controller providing said requested data to the CPU includes:

the memory controller decompressing said requested data after the CPU initiating the access to produce uncompressed requested data; and

the memory controller storing said uncompressed requested data in the system memory.

4. The method of claim 3, further comprising:

marking said uncompressed requested data as most recently used data.

5. The method of claim 2, further comprising:

marking said requested data as most recently used data.

6. The method of claim 2, wherein the computer system includes a non-volatile memory coupled to the memory controller, wherein the requested data resides in the non-volatile memory, wherein the memory controller performing said access of data in the system memory comprises:

the memory controller accessing said requested data from the non-volatile memory; and

the memory controller storing said requested data in the system memory.

7. The method of claim 2, wherein the computer system includes a non-volatile memory coupled to the memory controller, wherein the requested data resides in the non-volatile memory in a compressed format, wherein the memory controller performing said access of data in the system memory comprises:

the memory controller accessing said requested data from the non-volatile memory;

the memory controller decompressing the requested data to produce uncompressed requested data; and

the memory controller storing said uncompressed requested data in the system memory.

8. The method of claim 1, further comprising:

marking said data as most recently used data.

9. The method of claim 1, wherein the CPU initiating an access of data in the system memory comprises the CPU initiating a write of first data to the system memory, wherein the memory controller performing said access of data in the system memory comprises:

the memory controller writing said first data to the system memory after the memory controller compressing said replacement block of data and storing said compressed replacement block of data in said system memory.

10. The method of claim 9, further comprising:

marking said first data as most recently used data.

11. The method of claim 1, wherein the CPU initiating an access of data in the system memory comprises the CPU initiating a write of first data to the system memory, wherein the memory controller performing said access of data in the system memory comprises:

the memory controller compressing the first data to produce compressed first data; and

the memory controller writing said compressed first data to the system memory after the memory controller compressing said replacement block of data and storing said compressed replacement block of data in said system memory.

12. The method of claim 1,

the memory controller determining if the data resides in the system memory in an uncompressed format in response to the CPU initiating the access of data in the system memory;

wherein the memory controller compresses the replacement block of data and stores the compressed replacement block of data in the system memory in response to the memory controller determining that the data does not reside in the system memory in an uncompressed format.

13. The method of claim 12,

wherein the memory controller determining if the data resides in the system memory in an uncompressed format comprises the memory controller determining if a page hit occurs;

wherein the memory controller compresses the replacement block of data and stores the compressed replacement block of data in the system memory in response to the memory controller determining that a page miss has occurred.

14. The method of claim 1, wherein the memory controller compressing said replacement block of data comprises the memory controller performing a lossless compression on said replacement block of data.

15. The method of claim 1, wherein the memory controller compressing said replacement block of data comprises the memory controller performing a lossy compression on said replacement block of data.

16. The method of claim 1, wherein the system memory stores application data used by the CPU for executing one or more applications.

17. The method of claim 16,

wherein the CPU initiating an access of data in the system memory comprises the CPU initiating an access of application data in the system memory;

and

wherein the memory controller performing said access of data in the system memory comprises the memory controller accessing the application data in the system memory.

18. The method of claim 16, wherein the replacement block of data in the system memory comprises application data.

19. The method of claim 1, wherein the computer system includes a display, wherein the system memory stores graphics data used for presenting images on the display;

wherein the CPU initiating an access of data in the system memory comprises the CPU initiating an access of graphics data in the system memory; and

wherein the memory controller performing said access of data in the system memory comprises the memory controller accessing the graphics data in the system memory.

20. The method of claim 1, wherein the computer system includes a display, wherein the system memory stores graphics data used for presenting images on the display;

wherein the replacement block of data in the system memory comprises graphics data.

21. The method of claim 1, wherein said determining a replacement block of data in the system memory comprises determining a least recently used block of data in the system memory.

22. The method of claim 1, wherein said determining a replacement block of data in the system memory comprises determining a true least recently used block of data in the system memory.

23. The method of claim 1, wherein said determining a replacement block of data in the system memory comprises determining a pseudo least recently used block of data in the system memory.

24. The method of claim 1, wherein the memory controller comprises a hardware compression engine and a hardware decompression engine.

25. The method of claim 1, wherein the data includes application code and application data.

26. A method for managing memory accesses in a system a system including a CPU, a system memory for storing data, and a memory controller coupled to the system memory, wherein the memory controller performs memory control functions for the system memory, wherein the memory controller includes a hardware compression and decompression engine, the method comprising:

the CPU requesting data from the memory controller, wherein the data resides in the system memory in a compressed format, wherein the system memory is a volatile memory which stores uncompressed data currently being used for execution by the CPU, wherein the uncompressed data includes most recently used data;

determining a replacement block of data in the system memory after said requesting;

the memory controller compressing said replacement block of data;

the memory controller storing said compressed replacement block of data in said system memory after said compressing said replacement block of data;

the memory controller decompressing said requested data after said requesting to produce uncompressed requested data; and

the memory controller providing said uncompressed requested data to the CPU.

27. The method of claim 26, further comprising:

marking said uncompressed requested data as most recently used data.

28. The method of claim 26, wherein the memory controller comprises a hardware compression engine and a hardware decompression engine.

29. The method of claim 26, wherein the data includes application code and application data.

30. A method for managing data accesses in a system including a CPU, a system memory for storing data, a memory controller coupled to the system memory, and a non-volatile memory coupled to the memory controller, wherein the memory controller performs memory control functions for the system memory, wherein the memory controller includes a hardware compression and decompression engine, the method comprising:

the CPU initiating an access of data in the system memory, wherein the system memory is a volatile memory which stores uncompressed data currently being used for execution by the CPU, wherein the uncompressed data includes most recently used data;

determining a replacement block of data in the system memory after said initiating;

the memory controller compressing said replacement block of data;

the memory controller transferring said compressed replacement block to the non-volatile memory for storage after said compressing said replacement block of data;

wherein said compressing said replacement block of data and transferring said compressed replacement block of data to the non-volatile memory operates to free up at least a portion of said system memory;

the memory controller performing said access of data in the system memory.

31. The method of claim 30, further comprising:

marking said data as most recently used data.

32. The method of claim 30, wherein the CPU initiating an access of data in the system memory comprises the CPU initiating a read of requested data in the system memory, wherein the memory controller performing said access of data in the system memory includes:

the memory controller providing said requested data to the CPU.

33. The method of claim 32, further comprising:

marking said requested data as most recently used data.

34. The method of claim 32, wherein the requested data resides in the system memory in a compressed format, wherein the memory controller providing said requested data to the CPU includes:

the memory controller decompressing said requested data after the CPU initiating the access to produce uncompressed requested data; and

the memory controller storing said uncompressed requested data in the system memory.

35. The method of claim 32, wherein the requested data resides in the non-volatile memory, wherein the memory controller providing said requested data to the CPU includes:

the memory controller accessing said requested data from the non-volatile memory; and

the memory controller storing said requested data in the system memory.

36. The method of claim 32, wherein the requested data resides in the non-volatile memory in a compressed format, wherein the memory controller providing said requested data to the CPU includes:

the memory controller accessing said requested data from the non-volatile memory;

the memory controller decompressing the requested data to produce uncompressed requested data; and

the memory controller storing said uncompressed requested data in the system memory.

37. The method of claim 30, wherein the CPU initiating an access of data in the system memory comprises the CPU initiating a write of first data to the system memory, wherein the memory controller performing said access of data in the system memory comprises:

the memory controller writing said first data to the system memory after the memory controller compressing said replacement block of data and storing said compressed replacement block of data in said system memory.

38. The method of claim 37, further comprising:

marking said first data as most recently used data.

39. The method of claim 30, wherein the CPU initiating an access of data in the system memory comprises the CPU initiating a write of first data to the system memory, wherein the memory controller performing said access of data in the system memory comprises:

the memory controller compressing the first data to produce compressed first data; and

the memory controller writing said compressed first data to the system memory after the memory controller compressing said replacement block of data and storing said compressed replacement block of data in said system memory.

40. The method of claim 30,

the memory controller determining if the data resides in the system memory in an uncompressed format in response to the CPU initiating the access of data in the system memory;

wherein the memory controller compresses the replacement block of data and transfers the compressed replacement block of data to the non-volatile memory in response to the memory controller determining that the data does not reside in the system memory in an uncompressed format.

41. The method of claim 40,

wherein the memory controller determining if the data resides in the system memory in an uncompressed format comprises the memory controller determining if a page hit occurs;

wherein the memory controller compresses the replacement block of data and transfers the compressed replacement block of data to the non-volatile memory in response to the memory controller determining that a page miss has occurred.

42. The method of claim 30, wherein the memory controller compressing said replacement block of data comprises the memory controller performing a lossless compression on said replacement block of data.

43. The method of claim 30, wherein the memory controller compressing said replacement block of data comprises the memory controller performing a lossy compression on said replacement block of data.

44. The method of claim 30, wherein the system memory stores application data used by the CPU for executing one or more applications.

45. The method of claim 44,

wherein the CPU initiating an access of data in the system memory comprises the CPU initiating an access of application data in the system memory;

and

wherein the memory controller performing said access of data in the system memory comprises the memory controller accessing the application data in the system memory.

46. The method of claim 44, wherein the replacement block of data in the system memory comprises application data.

47. The method of claim 30, wherein the computer system includes a display, wherein the system memory stores graphics data used for presenting images on the display;

wherein the CPU initiating an access of data in the system memory comprises the CPU initiating an access of graphics data in the system memory; and

wherein the memory controller performing said access of data in the system memory comprises the memory controller accessing the graphics data in the system memory.

48. The method of claim 30, wherein the computer system includes a display, wherein the system memory stores graphics data used for presenting images on the display;

wherein the replacement block of data in the system memory comprises graphics data.

49. The method of claim 30, wherein said determining a replacement block of data in the system memory comprises determining a least recently used block of data in the system memory.

50. The method of claim 30, wherein said determining a replacement block of data in the system memory comprises determining a true least recently used block of data in the system memory.

51. The method of claim 30, wherein said determining a replacement block of data in the system memory comprises determining a pseudo least recently used block of data in the system memory.

52. The method of claim 30, wherein the memory controller comprises a hardware compression engine and a hardware decompression engine.

53. The method of claim 30, wherein the data includes application code and application data.

54. A method for managing memory accesses in a system including a CPU, a system memory for storing data, a memory controller coupled to the system memory, and a non-volatile memory coupled to the memory controller, wherein the memory controller performs memory control functions for the system memory, wherein the memory controller includes a hardware compression and decompression engine, the method comprising:

the CPU requesting data from the memory controller, wherein the data resides in the system memory in a compressed format, wherein the system memory is a volatile memory which stores uncompressed data currently being used for execution by the CPU, wherein the uncompressed data includes most recently used data;

determining a replacement block of data in the system memory after said requesting;

the memory controller compressing said replacement block of data;

the memory controller transferring said compressed replacement block of data to the non-volatile memory after said compressing said replacement block of data;

the memory controller decompressing said requested data after said requesting to produce uncompressed requested data; and

the memory controller providing said uncompressed requested data to the CPU.

55. The method of claim 54, further comprising:

marking said uncompressed requested data as most recently used data.

56. The method of claim 54, wherein the memory controller comprises a hardware compression engine and a hardware decompression engine.

57. The method of claim 54, wherein the data includes application code and application data.

58. A system with improved memory access management, the system comprising:

a CPU;

a system memory, wherein the system memory is a volatile memory for storing data, wherein the data includes uncompressed data currently being used for execution by the CPU, wherein the uncompressed data includes most recently used data; and

a memory controller coupled to the CPU and to the system memory, wherein the memory controller performs memory control functions for the system memory, wherein the memory controller includes a hardware compression/decompression engine;

wherein the CPU is operable to initiate an access of data in the system memory;

wherein, in response to the access, the memory controller is operable to access a replacement block of data in the system memory, compress said replacement block of data, and store said compressed replacement block of data in said system memory, wherein said compression of said replacement block of data and storage of said compressed replacement block of data in said system memory operates to free up at least a portion of said system memory;

wherein the memory controller is operable to perform said access of data in the system memory after freeing up said at least a portion of said system memory.

59. The system of claim 58,

wherein said data is marked as most recently used data.

60. The system of claim 58, wherein the CPU is operable to initiate a read of requested data in the system memory;

wherein, in performing said access of data in the system memory, the memory controller is operable to provide said requested data to the CPU.

61. The system of claim 60, wherein the requested data resides in the system memory in a compressed format;

wherein, in providing said requested data to the CPU, the memory controller is operable to decompress said requested data and store said uncompressed requested data in the system memory.

62. The system of claim 60, wherein the system further includes:

a non-volatile memory coupled to the memory controller, wherein the requested data resides in the non-volatile memory;

wherein, in providing said requested data to the CPU, the memory controller is operable to access said requested data from the non-volatile memory and store said requested data in the system memory.

63. The system of claim 60, wherein the system further includes:

a non-volatile memory coupled to the memory controller, wherein the requested data resides in the non-volatile memory in a compressed format;

wherein, in providing said requested data to the CPU, the memory controller is operable to access said requested data from the non-volatile memory, decompress the requested data to produce uncompressed requested data, and store said uncompressed requested data in the system memory.

64. The system of claim 58, wherein the CPU is operable to initiate a write of first data to the system memory;

wherein, in performing said access of data in the system memory, the memory controller is operable to write said first data to the system memory.

65. The system of claim 58, wherein the CPU is operable to initiate a write of first data to the system memory;

wherein, in performing said access of data in the system memory, the memory controller is operable to compress the first data to produce compressed first data and write said compressed first data to the system memory.

66. The system of claim 58,

wherein, in response to the access, the memory controller is operable to determine if the data resides in the system memory in an uncompressed format;

wherein the memory controller is operable to access the replacement block of data, compress the replacement block of data, and store the compressed replacement block of data in the system memory in response to the memory controller determining that the data does not reside in the system memory in an uncompressed format.

67. The system of claim 66,

wherein the memory controller is operable to provide the data to the CPU in response to the memory controller determining that the data resides in the system memory in an uncompressed format.

68. The system of claim 66,

wherein, in determining if the data resides in the system memory in an uncompressed format, the memory controller is operable to determine if a page hit occurs;

wherein the memory controller accesses the replacement block of data, compresses the replacement block of data, and stores the compressed replacement block of data in the system memory in response to the memory controller determining that a page miss has occurred.

69. The system of claim 58, wherein the compression/decompression engine comprised in the memory controller is operable to perform a lossless compression on said replacement block of data.

70. The system of claim 58, wherein the compression/decompression engine comprised in the memory controller is operable to perform a lossy compression on said replacement block of data.

71. The system of claim 58, wherein the system memory stores application data used by the CPU for executing one or more applications;

wherein the data comprises application data.

72. The system of claim 58, wherein the system further includes a display;

wherein the system memory stores graphics data used for presenting images on the display;

wherein the data comprises graphics data.

73. The system of claim 58, wherein the replacement block of data comprises a least recently used block of data in the system memory.

74. The system of claim 58, wherein the replacement block of data comprises a true least recently used block of data in the system memory.

75. The system of claim 58, wherein the replacement block of data comprises a pseudo least recently used block of data in the system memory.

76. The system of claim 58, wherein the system comprises a computer system.

77. The system of claim 58, wherein the memory controller comprises a hardware compression engine and a hardware decompression engine.

78. The system of claim 58, wherein the data includes application code and application data.

79. A system with improved memory access management, the system comprising:

a CPU;

a system memory, wherein the system memory is a volatile memory for storing data, wherein the data includes uncompressed data currently being used for execution by the CPU, wherein the uncompressed data includes most recently used data;

a memory controller coupled to to the CPU and to the system memory, wherein the memory controller performs memory control functions for the system memory, wherein the memory controller includes a hardware compression/decompression engine; and

a non-volatile memory coupled to the memory controller;

wherein the CPU is operable to initiate an access of data in the system memory;

wherein, in response to the access, the memory controller is operable to access a replacement block of data in the system memory, compress said replacement block of data, and transfer said compressed replacement block of data to the non-volatile memory, wherein said compression of said replacement block of data and transfer of said compressed replacement block of data to the non-volatile memory operates to free up at least a portion of said system memory;

wherein the memory controller is operable to perform said access of data in the system memory after freeing up said at least a portion of said system memory.

80. The system of claim 79,

wherein said data is marked as most recently used data.

81. The system of claim 79, wherein the CPU is operable to initiate a read of requested data in the system memory;

wherein, in performing said access of data in the system memory, the memory controller is operable to provide said requested data to the CPU.

82. The system of claim 81, wherein the requested data resides in the system memory in a compressed format;

wherein, in providing said requested data to the CPU, the memory controller is operable to decompress said requested data and store said uncompressed requested data in the system memory.

83. The system of claim 81,

wherein the requested data resides in the non-volatile memory;

wherein, in providing said requested data to the CPU, the memory controller is operable to access said requested data from the non-volatile memory and store said requested data in the system memory.

84. The system of claim 81,

wherein the requested data resides in the non-volatile memory in a compressed format;

wherein, in providing said requested data to the CPU, the memory controller is operable to access said requested data from the non-volatile memory, decompress the requested data to produce uncompressed requested data, and store said uncompressed requested data in the system memory.

85. The system of claim 79, wherein the CPU is operable to initiate a write of first data to the system memory;

wherein, in performing said access of data in the system memory, the memory controller is operable to write said first data to the system memory.

86. The system of claim 79, wherein the CPU is operable to initiate a write of first data to the system memory;

wherein, in performing said access of data in the system memory, the memory controller is operable to compress the first data to produce compressed first data and write said compressed first data to the system memory.

87. The system of claim 79,

wherein, in response to the access, the memory controller is operable to determine if the data resides in the system memory in an uncompressed format;

wherein the memory controller is operable to access the replacement block of data, compress the replacement block of data, and transfer the compressed replacement block of data to the non-volatile memory in response to the memory controller determining that the data does not reside in the system memory in an uncompressed format.

88. The system of claim 79, wherein the compression/decompression engine comprised in the memory controller is operable to perform a lossless compression on said replacement block of data.

89. The system of claim 79, wherein the compression/decompression engine comprised in the memory controller is operable to perform a lossy compression on said replacement block of data.

90. The system of claim 79, wherein the system memory stores application data used by the CPU for executing one or more applications;

wherein the data comprises application data.

91. The system of claim 79, wherein the system further includes a display;

wherein the system memory stores graphics data used for presenting images on the display;

wherein the data comprises graphics data.

92. The system of claim 79, wherein the replacement block of data comprises a least recently used block of data in the system memory.

93. The system of claim 79, wherein the replacement block of data comprises a true least recently used block of data in the system memory.

94. The system of claim 79, wherein the replacement block of data comprises a pseudo least recently used block of data in the system memory.

95. The system of claim 79, wherein the system comprises a computer system.

96. The system of claim 79, wherein the memory controller comprises a hardware compression engine and a hardware decompression engine.

97. The system of claim 79, wherein the data includes application code and application data.