Virtual uncompressed cache size control in compressed memory systems

• US 6,779,088 B1
• Filed: 10/24/2000
• Issued: 08/17/2004
• Est. Priority Date: 10/24/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Franaszek, Peter A., Robinson, John T., Benveniste, Caroline D.
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US09/694,876
• Time in Patent Office: 1,393 Days
• Field of Search: 711/113, 711/118, 711/119, 711/122, 711/117, 711/203, 711/205, 711/207, 711/170, 711/171, 711/156, 711/144, 711/159, 711/160, 711/145, 707/101, 710/68, 709/247
• US Class Current: 711/145
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 2212/401 Compressed data

Abstract

A compressed memory system includes a cache, and compressed memory including fixed size storage blocks for storing both compressed data segments and fixed size storage blocks defining a virtual uncompressed cache (VUC) for storing uncompressed data segments to enable reduced data access latency. The compressed memory system implements a system and method for controlling the size of the VUC so as to optimize system performance in a manner which permits the avoidance of operating system intervention which is required in certain circumstances for correct system operation. The system solves-these problems by implementing one or more thresholds, which may be set by the operating system, but which, after being sets control the size of the VUC independently of the operating system or other system software.

Claims

1. In a compressed memory system including a cache, and compressed memory having fixed size storage blocks for storing both compressed data segments and fixed size storage blocks defining a virtual uncompressed cache (VUC) for storing uncompressed data segments to enable reduced data access latency, a method for controlling the size of said VUC comprising:

a) maintaining a count of free fixed size storage blocks in said compressed memory system;

b) providing directory structure having entries for locating both uncompressed data segments and compressed data segments for handling cache miss events in said compressed memory system, wherein a CPU generated real memory address is translated into a physical memory locations using said directory, each said directory entry including a status flag indicating compressibility status of said segment and a membership status indicator for indicating storage of said data segment in said VUC; and

,

c) for each cache miss event, accessing a corresponding directory entry and checking status of its corresponding data segment to determine whether said entry is already compressed, wherein for a cache miss event requiring access of an uncompressed data segment indicated in said directory as not stored in said VUC, storing said uncompressed data in said VUC when said free storage blocks count is greater than or equal to a first threshold and said cache miss event is a write access, or, removing a segment from said VUC, compressing and storing said removed segment as a compressed data segment and storing said uncompressed data in said VUC when said free storage blocks count is less than said first threshold and said cache miss event is a write access, whereby

the size of the VUC varies dynamically.

2. The method for controlling the size of said VUC as claimed in claim 1, wherein said step c) of accessing a corresponding directory entry further including checking said membership status of said corresponding data segment, wherein for a cache miss event, requiring access of uncompressed data segments indicated as stored in said VUC, terminating flier processing of said uncompressed data segment.

3. The method for controlling the size of said VUC as claimed in claim 2, wherein for a cache miss event requiting access of uncompressed data segments indicated as not stored in said VUC, the steps of:

determining if said cache miss is a read access; and

, if said cache miss is a read access terminating further processing of said uncompressed data segment.

4. The method for controlling the size of said VUC as claimed in claim 2, wherein for a cache miss event requiring access of a compressed data segment, said step d) comprises the steps of:

reading said compressed data segment, decompressing and storing said decompressed data in said VUC when said free storage blocks count is greater than a first threshold in said VUC;

or,

removing another segment from said VUC, compressing and storing said removed segment as a compressed data segment, and decompressing and storing said decompressed data segment in said VUC when said free storage blocks count is less than said first threshold.

5. The method for controlling the size of said VUC as claimed in claim 4, further comprising:

providing a fixed length FIFO data structure comprising a list of directory indexes corresponding to recently accessed uncompressed data segments in said VUC, a corresponding membership status of said data segment being set to indicate membership of said directory index in said FIFO data structure.

6. The method for controlling the size of said VUC as claimed in claim 5, wherein said comparing step d) further comprises the step of:

determining whether said FIFO is full and performing said steps of;

removing another segment from said VUC, compressing and storing said removed segment as a compressed data segment, and reading, decompressing and storing said decompressed data segment in said VUC when said FIFO is not full.

7. The method for controlling the size of said VUC as claimed in claim 5, wherein said step of storing said decompressed data in said VUC further comprises:

inserting said directory entry in said FIFO data structure and setting said membership status indicator to indicate storage in said VUC of its corresponding uncompressed data segment.

8. The method for controlling the size of said VUC as claimed in claim 5, wherein said step of removing another segment from said VUC further comprises:

removing its corresponding directory entry from said FIFO data structure and clearing said membership status indicator.

9. The method for controlling the size of said VUC as claimed in claim 5, wherein prior to said step of removing another segment from said VUC, compressing and storing said removed segment as a compressed data segment, the steps of:

comparing said current count of said free storage blocks against a second threshold for managing a size of said VUC, and performing one of;

removing said another data segment, compressing and storing of said compressed data segment when said current count of said free storage blocks is less data said second threshold, or, removing more than one other data segments from said VUC, compressing and storing each of said more than one compressed data segments when said current count of said free storage blocks is greater than or equal to said second threshold.

10. The method for controlling the size of said VUC as claimed in claim 1, wherein said steps of removing, compressing and storing the removed data segment is performed in parallel with the step of storing said uncompressed data in said VUC when said free storage blocks count is less than said first threshold.

11. The method for controlling the size of said VUC as claimed in claim 10, wherein the steps of removing, compressing and storing a removed data segment is performed in parallel with the steps of reading, decompressing and storing said decompressed data segment when said free storage blocks count is less than said first threshold.

12. The method for controlling the size of said VUC as claimed in claim 1, further comprising:

providing a fixed length FIFO data structure comprising a list of directory indexes corresponding to recently access uncompressed data segments in said VUC, a corresponding membership status indicator of said data segment being set to indicate membership of said directory index in said FIFO data structure.

13. The method for controlling the size of said VUC as claimed in claim 12, wherein said comparing step d) further comprises the step of:

determining whether said FIFO is full and performing said steps of;

removing, compressing and storing the removed data segment and said storing said uncompressed data in said VUC for a cache write access when said FIFO is not full.

14. The method for controlling the size of said VUC as claimed in claim 12, wherein said step of storing said uncompressed data in said VUC further comprises:

inserting said directory entry in said FIFO data structure and setting said membership status indicator to indicate storage in said VUC of its corresponding uncompressed data segment.

15. The method for controlling the size of said VUC as claimed in claim 12, wherein said step of removing another segment from said VUC further comprises:

removing its corresponding directory entry from said FIFO data structure and clearing said membership status indicator.

16. The method for controlling the size of said VUC as claimed in claim 12, wherein prior to said step of removing another segment from said VUC, compressing and storing said removed segment as a compressed data segment, the steps of:

comparing said current count of said free storage blocks against a second threshold for managing a size of said VUC, and performing one of;

removing said another data segment, compressing and storing of said compressed data segment when said current count of said fee storage blocks is less than said second threshold, or, removing more than one other data segments from said VUC, compressing and storing each of said more than one compressed data segments when said current count of said free storage blocks is greater than or equal to said second threshold.

17. The method for controlling the size of said VUC as claimed in claim 15, wherein said steps of removing another data segment or more than one data segments includes:

removing their corresponding directory entries from said FIFO data structure and clearing each respective said membership status indicator.

18. The method for controlling the size of said VUC as claimed in claim 15, wherein said steps of removing another data segment or more than one data segments includes:

removing their corresponding directory entries from said FIFO data structure and clearing each respective said membership status indicator.

19. The method for controlling the size of said VUC as claimed in claim 12, wherein after said steps of removing another segment from said VUC, compressing and storing said removed segment as a compressed data segment, performing the further step of comparing said current count of said free storage blocks against said first threshold and repeating said steps of removing another segment from said VUC, compressing and storing said removed segment as a compressed data segment until said count of said free storage blocks is less than said first threshold.

20. The method for controlling the size of said VUC as claimed in claim 1, wherein said VUC size management occurs without operating system interruption.

21. A compressed memory system for reducing data access time in a computer system including a cache and having a compressed main memory in which the unit of compression is a memory segment, the system comprising:

a common memory area including fixed size storage blocks for storing both compressed data segments and fixed size storage blocks defining a virtual uncompressed cache (VUC) for storing uncompressed data segments;

a mechanism for maintaining a count of free fixed size storage blocks in said compressed memory system;

a directory mechanism having entries for locating both uncompressed data segments and compressed data segments for handling cache miss events, wherein CPU generated real memory addresses are translated into one or more physical memory locations using said directory, each said directory entry including a status flag indicating compressibility status of said segment;

control device for accessing said directory entries and checking status indication of a data segment to be accessed for said cache miss event, and enabling processing of said data segment from said common memory area according to said status indication, said control device further comparing a current count of said free storage blocks against one or more thresholds for managing a size of said VUC when handling said cache miss event, wherein for a cache miss event requiring access of an uncompressed data segment indicated in said directory as not stored in said VUC, storing said uncompressed data in said VUC when said free storage blocks count is greater than or equal to a first threshold and said cache miss event is a write access, or, removing a segment from said VUC, compressing and storing said removed segment as a compressed data segment, and storing said uncompressed data in said VUC when said free storage blocks count is less than said first threshold and said cache miss event is a write access, whereby the size of the VUC varies dynamically.

22. The compressed memory system as claimed in claim 21, wherein said control device includes one or VUC size control registers, for controlling a size of said VUC upon receipt of a cache miss event.

23. The compressed memory system as claimed in claim 22, further comprising a fixed length FIFO data structure including a list of directory indexes corresponding to recently accessed uncompressed data segments in said VUC, a corresponding membership status of said data segment being set to indicate membership of said directory index in said FIFO data structure.

24. The compressed memory system as claimed in claim 23, wherein said control device continuously updates said FIFO data structure and said status indication in a corresponding directory entry when uncompressed data segments are processed.

25. The compressed memory system as claimed in claim 21, wherein said control device enables VUC size management without operating system interruption.