Cache memory system and method with multiple hashing functions and hash control storage

Claim 2

A cache memory system comprising: a cache memory having a plurality of cache locations, each for storing a cache line of data, separately accessed from a main memory, and having a first tag memory, each cache location being indexed by indexes, taken from memory addresses, through first and second hashing functions such that plural memory addresses having a common index access plural memory locations through the first and second hashing functions and different indexes access common memory locations through the first and second hashing functions; hash control storage storing control data comprising hash data associated with each cache location which indicates the hashing function used to store data in the cache location; and a controller coupled to the cache memory responsive to memory addresses in accesses to the main memory for accessing data in the cache memory through the first and second hashing functions and for replacing data in the cache memory from the main memory responsive to the control data and to comparisons between tags of the memory addresses and tags stored in the first tag memory.

Claim 3

A cache memory system as claimed in claim 1 wherein the controller checks the hash data of the cache location indexed by the first hashing function when there is a miss at that cache location and applies the second hashing function only when said hash data indicates data stored in the cache location was not stored using the second hashing function.

Claim 4

A cache memory system as claimed in claim 1 wherein the controller responds to the hash data to determine whether to replace data stored in a first location indexed through the first cache hashing function or a second cache location indexed through the second hashing function.

Claim 5

A cache memory system as claimed in claim 3 wherein the controller swaps data replaced in a cache location with data in another cache location indexed by a common index.

Claim 6

A cache memory system as claimed in claim 1 further comprising a second tag memory coupled to the controller for storing as control data at least portions of memory addresses that indicate that data stored in a cache location is likely indexed through one of the hashing functions.

Claim 7

A cache memory system as claimed in claim 5 wherein the controller accesses cache memory locations through the first hashing function or the second hashing function dependent on whether at least a portion of a memory address is stored in the second tag memory and, where a miss results at a cache memory location with access through the first hashing function and the second hashing function, the controller replaces the data stored through the first hashing function if said hash data indicates the data accessed through the first hashing function had been stored using the second hashing function, or through the second hashing function if said hash data indicates the data accessed through the first hashing function had been stored using the first hashing function.

Claim 8

A cache memory system as claimed in claim 1 wherein the hash control storage comprises a second tag memory coupled to the controller for storing as control data at least portions of memory addresses that indicate a likely hashing function through which data stored in cache is indexed.

Claim 9

A cache memory system as claimed in claim 7 wherein the second tag memory is a content addressable memory.

Claim 10

A cache memory system comprising: a cache memory having a plurality of cache locations, each for storing a cache line of data, separately accessed from a main memory, and having a first tag memory, each cache location being indexed by indexes, taken from memory addresses, through first and second hashing functions such that plural memory addresses having a common index access plural memory locations through the first and second hashing functions and such that different indexes access common memory locations through the first and second hashing functions; hash data associated with each of the plurality of cache locations for indicating the hashing function used to store data therein; and a controller coupled to the cache memory for accessing data in the cache locations through the first and second hashing functions and for replacing data in the cache locations from main memory, the controller being responsive to the hash data and a comparison of tags of the memory address and stored tags in cache memory in determining whether to replace data in a first location accessed through the first hashing function or in a second location accessed through the second hashing function.

Claim 11

A cache memory system comprising: a cache memory having a plurality of cache locations, each for storing a cache line of data, separately accessed from a main memory, and having a first tag memory, each cache location being indexed by indexes, taken from memory addresses, through first and second hashing functions such that plural memory addresses having a common index access plural memory locations through the first and second hashing functions and such that different indexes access common memory locations through the first and second hashing functions; hash data associated with each of the plurality of cache locations for indicating the hashing function used to store data therein; and a controller coupled to the cache memory for accessing data in the cache locations through the first and second hashing functions and for replacing data in the cache locations from main memory, the controller being responsive to the hash data and a comparison of tags of the memory address and stored tags in cache memory in determining whether to replace data in a first location accessed through the first hashing function or in a second location accessed through the second hashing function.

Claim 12

A cache memory system according to claim 9, wherein the first hashing function is a bit selection operation.

Claim 13

A cache memory system according to claim 9, wherein the controller checks the hash data of a cache location indexed by the first hashing function when there is a miss to determine whether to apply the second hashing function.

Claim 14

A cache memory system according to claim 9, wherein the second hashing function is a bit selection and flipping operation.

Claim 15

A cache memory system according to claim 9, wherein the controller removes the data from the cache location indexed by the second hashing function after a miss and retrieves new data from the main memory in place therefor.

Claim 16

A cache memory system according to claim 13, wherein the controller swaps the new data in the cache location indexed by the second hashing function with the data in the cache location indexed by the first hashing function.

Claim 17

A cache memory system according to claim 9, wherein the controller responds to a miss at a cache location through the first hashing function, and to hash data indicating data is stored at that cache location through the second hashing function, to remove data from that cache location and retrieve data from main memory in place therefor.

Claim 18

A cache memory system as claimed in claim 15 wherein the controller swaps data replaced in a cache location with data in another cache location indexed by a common index.

Claim 19

A cache memory system according to claim 9, further comprising a second tag memory coupled to the controller for storing at least portions of addresses that indicate that data stored in a cache location is likely to be indexed through the second hashing function, the controller using the second hashing function in the initial cache indexing where an address is found in the second tag memory.

Claim 20

A cache memory system comprising: a cache data memory having a plurality of cache locations for storing plural cache lines of data, each cache location being referenced by a memory address having an index field and a tag field, and each cache location being indexed by indexes, taken from memory addresses, through first and second hashing functions such that plural memory addresses having a common index access plural memory locations through the first and second hashing functions and such that different indexes access common memory locations through the first and second hashing functions; a first tag memory coupled to the cache data memory for storing the tag fields of the data stored in the plurality of cache locations; hash data coupled to the cache data memory for indicating hashing functions used to index data in the cache locations; a second tag memory coupled to the cache data memory for storing at least portions of memory addresses that indicate that data stored in a cache location is likely indexed through one of the hashing functions; and a controller responsive to the hash data, the first tag memory and the second tag memory for indexing memory addresses according to at least one of the plural hashing functions.

Claim 21

A cache memory system comprising: a cache data memory having a plurality of cache locations for storing plural cache lines of data, each cache location being referenced by a memory address having an index field and a tag field, and each cache location being indexed by indexes, taken from memory addresses, through first and second hashing functions such that plural memory addresses having a common index access plural memory locations through the first and second hashing functions and such that different indexes access common memory locations through the first and second hashing functions; a first tag memory coupled to the cache data memory for storing the tag fields of the data stored in the plurality of cache locations; hash data coupled to the cache data memory for indicating hashing functions used to index data in the cache locations; a second tag memory coupled to the cache data memory for storing at least portions of memory addresses that indicate that data stored in a cache location is likely indexed through one of the hashing functions; and a controller responsive to the hash data, the first tag memory and the second tag memory for indexing memory addresses according to at least one of the plural hashing functions.

Claim 22

A cache memory system according to claim 18, wherein the controller applies first and second hashing functions to a memory address, the second hashing function being a bit selection and bit flipping operation.

Claim 25

A method according to claim 20, further comprising the steps of connecting a content addressable memory to the cache data memory for storing portions of memory addresses, each portion indicating that data stored in a cache location is likely indexed through one of plural hashing functions, and checking the content addressable memory for a match with a portion of the memory address.

Claim 26

A method as claimed in claim 20 further comprising swapping the replaced data in a cache location with data in another cache location indexed by a common index.

Claim 29

A method as claimed in claim 23 further comprising determining from a second tag memory a hashing function through which data stored in a cache location is likely indexed and selects that hashing function for indexing the cache location.

Claim 30

A method as claimed in claim 23 further comprising swapping data in the cache location indexed by the second hashing function with the data in the cache location indexed by the first hashing function when replacing data.