SYSTEM AND METHOD FOR CONTENT REPLICATION DETECTION AND ELIMINATION IN MAIN MEMORY

• US 20090287901A1
• Filed: 05/16/2008
• Published: 11/19/2009
• Est. Priority Date: 05/16/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Banikazemi, Mohammad, Abali, Bulent
• Granted Patent: US 8,074,047 B2
• Time in Patent Office: Days
• US Class Current: 711/206
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 2212/151 Emulated environment, e.g. virtual machine

Abstract

A system and method for effectively increasing the amount of data that can be stored in the main memory of a computer, particularly, by a hardware enhancement of a memory controller apparatus that detects duplicate memory contents and eliminates duplicate memory contents wherein the duplication and elimination are performed by hardware without imposing any penalty on the overall performance of the system.

Claims

1. A memory controller apparatus for controlling computer memory input [and output] operations in a computing system, said apparatus comprising:

a translation table for implementing translation of processor issued real memory block addresses to one or more physical memory block address corresponding to physical memory locations that receive input memory content for storage or output stored memory content;

means for calculating the hash value of a memory block content when a block of memory is accessed for content storage at a physical memory location, said translation table mapping all references for real memory blocks whose hashing values are identical to a single shared reference corresponding to a shared block of physical memory;

wherein, only one copy of content is stored at said shared block in physical memory for identical content thereby eliminating duplicate memory blocks in a computer memory system.

2. The memory controller apparatus as claimed in claim 1, wherein said physical memory comprises a cache for storing frequently used blocks addressable by said processor issued real addresses, said shared block of physical memory comprising a cache line.

3. The memory controller apparatus as claimed in claim 2, further comprising:

a hash table, provided in said cache, for storing hash values of each real memory contents stored in said physical memory;

a means for comparing a calculated hash value against said cache hash table when a block of said memory is accessed, said comparing means comparing said calculated hash value against said cache hash table values to determine if a block of identical content already exists in said physical memory, and, when a matching hash value is found, said translation table provides said single reference of said identical content to said shared physical memory location for accessing said identical content,

said comparing of hash values being performed seamless to a user or computer system operations.

4. The memory controller apparatus as claimed in claim 3, further comprising:

a means for maintaining a reference count for each physical block indicating the number of references in the translation table, said reference count of a physical memory block being incremented by one whenever a new reference to the block is added and, the reference count of a physical memory block being decremented by one when a reference to a physical block is removed.

5. The memory controller apparatus as claimed in claim 4, further comprising:

means for maintaining a list of free memory blocks in said physical memory, wherein when a reference count of a physical memory block is zero, said controller adding said physical memory block to said list of free physical memory blocks.

6. The memory controller apparatus as claimed in claim 4, further comprising:

means implementing one or both of compression and encryption of memory block contents when storing said block in said shared physical memory location.

7. The memory controller apparatus as claimed in claim 4, further comprising:

means implementing one or both of decompression and decryption of memory block contents when accessing said block from said shared physical memory location.

8. The memory controller apparatus as claimed in claim 1, wherein said means for calculating a hash value implements a SHA-1 or SHA-2 hashing algorithms.

9. A method for controlling computer memory input and output operations in a computing system, said method comprising:

implementing, via a translation table, translation of processor issued real memory block addresses to one or more physical memory block addresses corresponding to physical memory locations to receive input memory content for storage or output stored memory content; and

,

calculating a hash value of a memory block content when a block of memory is being input for storage at a physical memory location, said translation table mapping all references for real memory blocks whose hashing values have been previously identified as identical, to a single shared reference corresponding to a shared block of physical memory;

wherein, only one copy of content is stored at said shared block in physical memory for identical content thereby eliminating duplicate memory blocks in a computer memory system.

10. The method as claimed in claim 9, wherein said physical memory comprises a cache for storing frequently used blocks addressable by said processor issued real addresses, said shared block of physical memory comprising a cache line.

11. The method as claimed in claim 10, further comprising:

storing, in a hash table provided in said cache, hash values of each real memory contents stored in said physical memory;

comparing, when a block of said memory is accessed, its calculated hash value against said cache hash table values to determine if a block of identical content already exists in said physical memory, and,

when a matching hash value is found,

modifying said translation table to provide said single reference of said identical content to said shared physical memory location for accessing said identical content,

wherein said comparing of hash values being is performed seamless to a user or computer system operations.

12. The method as claimed in claim 11, further comprising:

maintaining a reference count for each physical block indicating the number of references in the translation table, and one of;

incrementing said reference count by one of a physical memory block whenever a new reference to the block is added or, decrementing the reference count of a physical memory block by one when a reference to a physical block is removed.

13. The method as claimed in claim 12, further comprising:

maintaining a list of free memory blocks in said physical memory, wherein when a reference count of a physical memory block is zero, said controller adding said physical memory block to said list of free physical memory blocks.

14. The method as claimed in claim 12, further comprising:

implementing one or both of compression and encryption of memory block contents when storing said block in said shared physical memory location.

15. The method as claimed in claim 12, further comprising:

implementing one or both of decompression and decryption of memory block contents when accessing said block from said shared physical memory location.

16. A computer memory system for a computing device comprising a memory controller and one or more types of memory, wherein the content of main memory is cached in a caching unit, said system comprising:

means for writing to a real memory block,

a hash calculator for calculating a hash value of each real memory block content to be stored in said physical memory for a memory write operation;

a memory storage cache indexible by said memory controller for storing a first table including stored hash values of some or all of the blocks stored in said physical memory;

a means for comparing said calculated hash value against said stored hash values when performing said write operation, to determine if a block of identical content already exists in said physical memory; and

,

means for directing the memory controller such that references to real memory blocks whose contents are identical are substituted by single reference to a single set of physical blocks stored in physical memory, said directing means performing at real memory block level granularity,

means for directing the memory controller such that a single physical memory block can be mapped on to one or more real blocks in real memory.

17. The computer memory system as claimed in claim 16, wherein said table of hash values stored in said memory storage cache is indexed by a set of bits found in the hash value, wherein each row in the hash table is addressed by a subset of the hash value'"'"'s bits, and remaining bits of the hash value is stored in that particular row.

18. The computer memory system as claimed in claim 16, wherein the memory storage cache is a direct mapped or fully associative cache and size of the cache is such that hashes being searched are found with high probability.