System and method for managing compression and decompression of system memory in a computer system

Abstract

A method and system for allowing a processor or I/O master to address more system memory than physically exists are described. A Compressed Memory Management Unit (CMMU) may keep least recently used pages compressed, and most recently and/or frequently used pages uncompressed in physical memory. The CMMU translates system addresses into physical addresses, and may manage the compression and/or decompression of data at the physical addresses as required. The CMMU may provide data to be compressed or decompressed to a compression/decompression engine. In some embodiments, the data to be compressed or decompressed may be provided to a plurality of compression/decompression engines that may be configured to operate in parallel. The CMMU may pass the resulting physical address to the system memory controller to access the physical memory. A CMMU may be integrated in a processor, a system memory controller or elsewhere within the system.

1. A method for compressing memory in a system comprising a plurality of compression engines and a physical memory, wherein the physical memory comprises system memory, the method comprising:
 locating a page translation entry in a page translation table, wherein the page translation entry references an uncompressed page in the physical memory; 
 providing the referenced uncompressed page to the plurality of compression engines, wherein each of the plurality of compression engines implements a different compression algorithm; 
 the plurality of compression engines each compressing the uncompressed page using the compression algorithm implemented by the particular compression engine to produce a plurality of compressed pages each compressed by a different compression algorithm; 
 selecting the compressed page with the highest compression ratio of the plurality of compressed pages; and 
 writing the selected compressed page to the physical memory. 
 
     
     
       2. The method of  claim 1 , further comprising marking the page translation entry associated with the selected compressed page to indicate the particular compression algorithm used in said compressing the page. 
     
     
       3. The method of  claim 1 , further comprising:
 determining that the compressed page needs to be decompressed:
 examining the page translation entry to determine the particular compression algorithm used to compress the page; 
 selecting a decompression engine from a plurality of decompression engines, wherein the selected decompression engine implements a decompression algorithm for decompressing data compressed using the particular compression algorithm; 
 providing the page to the selected decompression engine; and 
 the selected decompression engine decompressing the page using the decompression algorithm to produce the decompressed page. 
 
 
     
     
       4. The method of  claim 1 , wherein the compression of pages of the memory in the system is operable to increase the effective size of the system memory by keeping least recently used data as compressed data in the physical memory and most recently and frequently used data as uncompressed data in the physical memory. 
     
     
       5. The method of  claim 4 , wherein the system further comprises an operating system, wherein the operating system is not aware of the increased effective size of the system memory. 
     
     
       6. A method for managing compression of pages of memory in a computer system comprising physical memory, wherein the physical memory comprises system memory, the method comprising:
 receiving a system memory access;   locating a page translation entry for the system memory access in a page translation table, wherein the page translation table comprises a plurality of page translation entries;   in response to determining that a page in the physical memory referenced by the page translation entry is uncompressed, the computer system:
 determining that the uncompressed page is to be compressed; 
 selecting one of a plurality of compression engines based at least in part on a compression ratio associated with using a compression algorithm implemented by the selected compression engine to compress the uncompressed page, wherein individual ones of the plurality of compression engines are configured to implement different compression algorithms; 
 compressing the uncompressed page to produce a compressed page, wherein said compressing is performed using the selected compression engine; and 
 writing the compressed page to the physical memory. 
   
     
     
       7. The method of claim 6, wherein said compressing comprises:
 a Direct Memory Access (DMA) channel reading the uncompressed page from the physical memory; and   the DMA channel writing the uncompressed page to the selected compression engine.   
     
     
       8. The method of claim 6, wherein said writing the compressed page to the physical memory comprises:
 a Direct Memory Access (DMA) channel reading the compressed page from the selected compression engine; and   the DMA channel copying the compressed page into one or more linked compressed blocks in the physical memory.   
     
     
       9. The method of claim 6, wherein said compressing comprises:
 a plurality of Direct Memory Access (DMA) channels reading the uncompressed page from the physical memory; and   the plurality of DMA channels writing the uncompressed page to the selected compression engine.   
     
     
       10. The method of claim 6, wherein said writing the compressed page to the physical memory comprises:
 a plurality of Direct Memory Access (DMA) channels reading the compressed page from the selected compression engine; and   the plurality of DMA channels copying the compressed page into one or more linked compressed blocks in the physical memory.   
     
     
       11. The method of claim 6, wherein said selecting one of a plurality of compression engines comprises:
 compressing the uncompressed page using two or more of the plurality of compression engines to produce two or more compressed pages compressed using different compression algorithms; and   selecting the selected one of the plurality of compression engines based at least in part on the selected one producing a compressed page having the highest compression ratio of the two or more compressed pages.   
     
     
       12. A method for managing compression of pages of memory in a system comprising physical memory, wherein the physical memory comprises system memory, the method comprising:
 receiving a system memory access;   locating a page translation entry for the system memory access in a page translation table, wherein the page translation table comprises a plurality of page translation entries; and   in response to determining that a page in the physical memory referenced by the page translation entry is uncompressed:
 determining that the uncompressed page is to be compressed; 
 compressing the uncompressed page to produce a compressed page; and 
 writing the compressed page to physical memory; 
 wherein said compressing the uncompressed page comprises:
 providing the uncompressed page to a plurality of compression engines, wherein individual ones of the plurality of compression engines implement different compression algorithms; 
 individual ones of the plurality of compression engines compressing the uncompressed page using the compression algorithm implemented by the particular compression engine to produce a plurality of compressed pages compressed by different compression algorithms; and 
 selecting the compressed page from the plurality of compressed pages, wherein the selected compressed page has the highest compression ratio of the plurality of compressed pages. 
 
   
     
     
       13. The method of claim 12, further comprising:
 providing a different portion of the compressed page to individual ones of a plurality of decompression engines; and   the individual ones of the plurality of decompression engines decompressing the portion of the compressed page provided to the particular decompression engine.   
     
     
       14. The method of claim 13,
 wherein the individual ones of the plurality of decompression engines implement a same data decompression algorithm.   
     
     
       15. The method of claim 13,
 wherein the plurality of decompression engines decompresses the portions of the compressed page in parallel.   
     
     
       16. The method of claim 13, further comprising:
 combining the decompressed portions of the page to produce the decompressed page.   
     
     
       17. A method for managing compression of pages of memory in a system comprising physical memory, wherein the physical memory comprises system memory, the method comprising:
 receiving a system memory access;   locating a page translation entry for the system memory access in a page translation table, wherein the page translation table comprises a plurality of page translation entries;   determining if a page in the physical memory referenced by the page translation entry is compressed or uncompressed; and   in response to determining indicates the page is compressed:
 decompressing the compressed page to produce a decompressed page; 
 writing the decompressed page to the physical memory; 
 providing a first physical memory address of the decompressed page in the physical memory to fulfill the system memory access; and 
 prior to said providing the page to a decompression engine:
 examining the page translation entry to determine a compression algorithm used to compress the page; and 
 selecting the decompression engine from a plurality of decompression engines, wherein the decompression engine is configured to decompress data compressed using the determined compression algorithm; 
 
   wherein said decompressing the compressed page comprises:
 providing the page to a decompression engine; and 
 the decompression engine decompressing the page to produce the decompressed page. 
   
     
     
       18. An article of manufacture including a computer-readable medium having instructions stored thereon that, responsive to execution by a computing device, cause the computing device to perform operations comprising:
 receiving a system memory access;   locating a page translation entry for the system memory access in a page translation table, wherein the page translation table comprises a plurality of page translation entries; and   in response to determining that a page in physical memory of the computing device referenced by the page translation entry is compressed:
 examining the page translation entry to determine a compression algorithm used to compress the page; 
 selecting a decompression engine from a plurality of decompression engines, wherein the selected decompression engine is configured to decompress data compressed using the determined compression algorithm; 
 decompressing the compressed page using the selected decompression engine to produce a decompressed page; 
 writing the decompressed page to the physical memory; and 
 providing a first physical memory address of the decompressed page in the physical memory to fulfill the system memory access. 
   
     
     
       19. A method for managing compression of pages of memory in a computer system comprising physical memory, wherein the physical memory comprises system memory, the method comprising:
 receiving a system memory access;   locating a page translation entry for the system memory access in a page translation table, wherein the page translation table comprises a plurality of page translation entries; and   in response to determining that a page in the physical memory referenced by the page translation entry is compressed, the computer system:
 examining the page translation entry to determine a compression algorithm used to compress the page; 
 selecting a decompression engine from a plurality of decompression engines, wherein the selected decompression engine is configured to decompress data compressed using the determined compression algorithm; 
 decompressing the compressed page using the selected decompression engine to produce a decompressed page; 
 writing the decompressed page to the physical memory; and 
 providing a first physical memory address of the decompressed page in the physical memory to fulfill the system memory access. 
   
     
     
       20. An article of manufacture including a computer-readable medium having instructions stored thereon that, responsive to execution by a computing device, cause the computing device to perform operations comprising:
 locating a page translation entry in a page translation table, wherein the page translation entry references an uncompressed page in physical memory of the computing device, and wherein the page translation table comprises a plurality of page translation entries;   determining whether the uncompressed page is to be compressed; and   in response to determining that the uncompressed page is to be compressed:
 compressing the uncompressed page to produce a compressed page; and 
 writing the compressed page to the physical memory, wherein the compression of pages of the memory in the system is operable to increase the effective size of the system memory by keeping least recently used data as compressed data in the physical memory and most recently and frequently used data as uncompressed data in the physical memory; 
 wherein said compressing the uncompressed page comprises:
 selecting one of a plurality of compression engines based at least in part on a compression ratio associated with using a compression algorithm implemented by the selected compression engine to compress the uncompressed page, wherein individual ones of the plurality of compression engines are configured to implement different compression algorithms; and 
 using the selected compression engine to produce the compressed page; 
 
   wherein an operating system of the computing device is not aware of the increased effective size of the system memory.   
     
     
       21. The article of manufacture of claim 20, wherein the plurality of compression engines compress portions of the uncompressed page in parallel to produce the compressed page. 
     
     
       22. A method for managing compression of pages of memory in a system comprising an operating system and physical memory, wherein the physical memory comprises system memory, the method comprising:
 locating a page translation entry in a page translation table, wherein the page translation entry references an uncompressed page in the physical memory, wherein the page translation table comprises a plurality of page translation entries;   determining whether the uncompressed page is to be compressed; and   in response to determining that the uncompressed page is to be compressed:
 compressing the uncompressed page to produce a compressed page; and 
 writing the compressed page to the physical memory, wherein the compression of pages of the memory in the system is operable to increase the effective size of the system memory by keeping least recently used data as compressed data in the physical memory and most recently and frequently used data as uncompressed data in the physical memory; 
 wherein said compressing the uncompressed page comprises:
 providing the uncompressed page to a plurality of compression engines, wherein individual ones of the plurality of compression engines implement different compression algorithms; 
 the individual ones of the plurality of compression engines compressing the uncompressed page using the compression algorithm implemented by the particular compression engine to produce a plurality of candidate compressed pages compressed by different compression algorithms; and 
 selecting the compressed page from the plurality of candidate compressed pages 1 based at least in part on the selected compressed page having the highest compression ratio of the plurality of candidate compressed pages; 
 
   wherein the operating system is not aware of the increased effective size of the system memory.   
     
     
       23. The method of claim 22, further comprising:
 marking the page translation entry associated with the compressed page to indicate the particular compression algorithm used in said compressing the page.   
     
     
       24. A system comprising:
 one or more processors;   a physical memory comprising a system memory;   a system memory controller;   a plurality of compression/decompression engines, wherein at least two of the plurality of compression/decompression engines implement different compression/decompression algorithms; and   a compressed memory management unit (CMMU), configured to:
 receive from a first processor of the one or more processors a system memory access comprising a system memory address; 
 translate the system memory address into a first physical memory address, wherein the first physical memory address references compressed data; 
 cause decompression of the compressed data at the first physical memory address in the physical memory to produce decompressed data; 
 write the decompressed data to a second physical memory address; and 
 pass the second physical memory address to the system memory controller; 
 prior to said writing the compressed data to the compression/decompression engine:
 determine a particular compression algorithm used to compress the compressed data; and 
 select the compression/decompression engine from the plurality of compression/decompression engines, wherein the selected compression/decompression engine is configured to decompress data compressed using the particular compression algorithm; 
 
   wherein the system memory controller is configured to fulfill the system memory access from the decompressed data at the second physical memory address; and   wherein the CMMU is operable to increase the effective size of the system memory by keeping least recently used data as compressed data in the physical memory and most recently and frequently used data as uncompressed data in the physical memory.   
     
     
       25. The system of claim 24,
 wherein said translating comprises locating a page translation entry for the system memory address in a page translation table and determining the first physical memory address from the page translation entry for the system memory address, wherein the page translation table comprises a plurality of page translation entries.   
     
     
       26. A system comprising:
 one or more processors;   a system memory controller;   a physical memory comprising a system memory;   a plurality of compression/decompression engines, wherein individual ones of the plurality of compression/decompression engines implement different compression algorithms; and   a compressed memory management unit (CMMU), configured to:
 translate a system memory address into a first physical memory address, wherein the first physical memory address references uncompressed data; 
 select a compression/decompression engine based at least in part on a compression ratio associated with compressing the referenced uncompressed data using the compression algorithm implemented by the selected compression/decompression engine; 
 cause compression of the referenced uncompressed data using the selected compression/decompression engine to produce compressed data; and 
 write the compressed data to a second physical memory address; 
   wherein the system is operable to increase the effective size of system memory by keeping least recently used pages compressed in the physical memory and most recently and frequently used pages uncompressed in the physical memory.   
     
     
       27. The system of claim 26,
 wherein the CMMU selects the compression/decompression engine that implements an compression algorithm that provides a highest compression ratio for the referenced uncompressed data.   
     
     
       28. The system of claim 26,
 wherein the system further comprises a page translation table comprising one or more page translation entries;   wherein one of the one or more page translation entries references a page of physical memory at the second physical memory address; and   wherein the CMMU is further configured to mark the page translation entry to indicate the particular compression algorithm used in said compressing the uncompressed data.   
     
     
       29. The system of claim 26,
 wherein the plurality of compression/decompression engines is configured to compress the uncompressed data in parallel.