Home node aware replacement policy for caches in a multiprocessor system

• US 20070156964A1
• Filed: 12/30/2005
• Published: 07/05/2007
• Est. Priority Date: 12/30/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Sistla, Krishnakanth
• Granted Patent: US 7,502,889 B2
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/2542 Non-uniform memory access [NUMA] architecture

Abstract

A home node aware replacement policy for a cache chooses to evict lines which belong to local memory over lines which belong to remote memory, reducing the average transaction cost of incorrect cache line replacements. With each entry, the cache stores a t-bit cost metric (t≧1) representing a relative distance between said cache and an originating memory for the respective cache entry. Responsive to determining that no cache entry corresponds to an access request, the replacement policy selects a cache entry for eviction from the cache based at least in part on the t-bit cost metric. The selected cache entry is then evicted from the cache.

Claims

1. A system having comprising:

a plurality of processor nodes that share distributed memory, each processor node including

a processor core;

at least one interconnect interface, each interconnect interface to provide a path from the respective processor node to at least one other processor node of said plurality of processor nodes; and

a cache to store copies of data used by the processor core, the cache to write-back a cache entry selected for eviction from the cache to a memory of the distributed memory from which the cache entry originated,

each cache entry to be associated with a t-bit cost metric representing a relative distance between said cache and the originating memory of the cache entry, where t≧

1, said cache to select which cache entry to evict based at least in part on the t-bit cost metric.

2. The system of claim 1, wherein a replacement policy of the cache is biased to evict a first cache entry having a t-bit cost metric representing a shorter relative distance before a second cache entry having a t-bit cost metric representing a longer relative distance.

3. The system of claim 1, at least one of the processor nodes of said plurality of processor nodes further comprising:

a local memory;

a memory controller connected to said local memory, said cache to access the local memory through the memory controller,

wherein the local memory is assigned the t-bit cost metric representing a shortest distance to the cache.

4. The system of claim 3, wherein t=1 for at least one of the processor nodes having the local memory, the 1-bit cost metric having a first state representing the local memory within the respective processor node and having a second state representing remote memory accessible via said at least one interconnect interface.

5. The system of claim 3, wherein t>

1 for at least one of the processor nodes having the local memory, the t-bit cost metric having a first state representing the local memory within the respective processor node, and having a plurality of other states representing relative distances to remote memory accessible via said at least one interconnect interface.

6. The system of claim 5, wherein the t-bit cost metric has 2^t states, encoded to represent up to 2^t relative distances.

7. The system of claim 5, wherein the t-bit cost metric has t states, to represent up to t relative distances.

8. The system of claim 1, each processor node further comprising:

a system address decoder to map memories of the distributed memory into a globally shared memory space, the processor core of the processor node to address the globally shared memory space.

9. The system of claim 8, wherein each cache entry is tagged based on a source address in the globally shared memory space.

10. The system of claim 9, each processor node further comprising:

a cost metric encoder to translate an identity of the originating memory into the t-bit cost metric.

11. The system of claim 8, wherein each cache entry is tagged based on a source address in the originating memory, the processor core to access the cache through the system address decoder.

12. The system of claim 1, wherein the relative distance between said cache and the originating memory corresponds to a relative latency time between said cache and the originating memory.

13. A device comprising:

a cost metric encoder, to translate addresses into t-bit cost metrics, where t≧

1 and each t-bit cost metric corresponds a relative latency for completion of at least one data request to a respective address; and

a cache including

a plurality of storage locations, each storage location to store data associated with an address together with the t-bit cost metric corresponding to the respective address; and

an interface to receive access requests;

wherein data in a storage location of the plurality of storage locations is to be selected for eviction based at least in part on the t-bit cost metric stored by said storage location, to be replaced by data associated with a requested address, if the cache receives an access request for the requested address and the requested address is not associated with data stored in the cache.

14. The device of claim 13, wherein a replacement policy of the cache is biased to evict data from a first storage location storing a t-bit cost metric corresponding to a shorter relative latency before a second storage location storing a t-bit cost metric corresponding to a longer relative latency.

15. A method comprising:

storing, with each entry in a cache, a t-bit cost metric (t≧

1) representing a relative distance between said cache and an originating memory for the respective cache entry;

responsive to determining that no cache entry corresponds to an access request, selecting a cache entry for eviction from the cache based at least in part on the t-bit cost metric; and

evicting the selected cache entry from the cache.

16. The method of claim 15, wherein said selecting the cache entry for eviction is in accordance with a replacement policy biased to evict a first cache entry having a t-bit cost metric representing a shorter relative distance before a second cache entry having a t-bit cost metric representing a longer relative distance.

17. The method of claim 16, further comprising:

determining the relative distance between said cache and each originating memory based on a latency for completion of at least one data request from the cache to the respective memory.

18. A machine-readable medium storing instructions adapted to implement a cache replacement policy, the cache replacement policy comprising:

storing, with each entry in a cache, a t-bit cost metric (t≧

1) representing a relative distance between said cache and an originating memory for the respective cache entry;

responsive to determining that no cache entry corresponds to an access request, selecting a cache entry for eviction from the cache based at least in part on the t-bit cost metric; and

evicting the selected cache entry from the cache.

19. The machine-readable medium of claim 18, wherein the cache replacement policy is biased to evict a first cache entry having a t-bit cost metric representing a shorter relative distance before a second cache entry having a t-bit cost metric representing a longer relative distance.

20. The machine-readable medium of claim 19, the cache replacement policy further comprising:

determining the relative distance between said cache and each originating memory based on a latency for completion of at least one data request from the cache to the respective memory.