Method and apparatus for mapping memory addresses to corresponding cache entries
View Patent ↗One embodiment of the present invention provides a system for mapping memory addresses to cache entries. The system operates by first receiving a memory request at the cache memory, wherein the memory request includes a memory address. The system then partitions the memory address into a set of word offset bits and a set of higher-order bits. Next, the system maps the memory address to a cache entry by computing a modulo operation on the higher-order bits with respect to an integer and using the result as the cache index.
1. A method for mapping memory addresses to cache entries within a cache memory, comprising:
receiving a memory request at the cache memory, wherein the memory request includes a memory address associated with the memory requested;
partitioning the memory address into word offset bits and higher-order bits; and
mapping the memory address to a cache entry by computing a modulo of the higher-order bits with respect to an integer and using the result as the cache index, wherein the integer used in the modulo operation is (2 N −1), wherein N is an integer; and
wherein computing the modulo of the higher-order bits involves:
dividing the higher-order bits into at least three parts, wherein each part contains at most N bits,
adding only the two lower-order-bit parts to produce a summation, and
using the lower order N bits of the summation as the cache index.
2. The method of claim 1 , wherein the cache memory can be organized as one of a direct-mapped cache, a set-associative cache, and a fully-associative cache.
3. The method of claim 1 , wherein the integer 2 N is equal to the number of sets in the cache memory.
4. The method of claim 1 , wherein the integer used in the modulo operation is a prime number.
5. An apparatus for mapping memory addresses to cache entries within a cache memory, comprising:
a cache memory configured to receive a memory request, wherein the memory request includes a memory address associated with the memory requested;
a partitioning mechanism configured to partition the memory address into word offset bits and higher-order bits; and
a mapping mechanism configured to map the memory address to a cache entry by computing a modulo of the higher-order bits with respect to an integer and using the result as the cache index, wherein the integer used in the modulo operation is(2 N −1), wherein N is an integer; and
wherein the mapping mechanism is configured to compute the modulo of the higher-order bits by:
dividing the higher-order bits into at least three parts, wherein each part contains at most N bits,
adding only the two lower-order-bit parts to produce a summation, and
using the lower order N bits of the summation as the cache index.
6. The apparatus of claim 5 , wherein the cache memory can be organized as one of a direct-mapped cache, a set-associative cache, and a fully-associative cache.
7. The apparatus of claim 5 , wherein the integer 2 N is equal to the number of sets in the cache memory.
8. The apparatus of claim 5 , wherein the integer used in the modulo operation is a prime number.
9. A computer system containing a mechanism for mapping memory addresses to cache entries within a cache memory, comprising:
a processor;
a memory;
a cache memory configured to receive a memory request, wherein the memory request includes a memory address associated with the memory requested;
a partitioning mechanism configured to partition the memory address into word offset bits and higher-order bits; and
a mapping mechanism configured to map the memory address to a cache entry by computing a modulo of the higher-order bits with respect to an integer and using the result as the cache index, wherein the integer used in the modulo operation is (2 N −1), wherein N is an integer; and
wherein the mapping mechanism is configured to compute the modulo of the higher-order bits by:
dividing the higher-order bits into at least three parts, wherein each part contains at most N bits,
adding only the two lower-order-bit parts to produce a summation, and
using the lower order N bits of the summation as the cache index.
10. The computer system of claim 9 , wherein the cache memory can be organized as one of a direct-mapped cache, a set-associative cache, and a fully-associative cache.
11. The computer system of claim 9 , wherein the integer 2 N is equal to the number of sets in the cache memory.
12. The computer system of claim 9 , wherein the integer used in the modulo operation is a prime number.