Data processing system and method for efficient L3 cache directory management

• US 20060179250A1
• Filed: 02/10/2005
• Published: 08/10/2006
• Est. Priority Date: 02/10/2005
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Starke, William John, Williams, Derek Edward, Guthrie, Guy Lynn, Williams, Philip G.
• Granted Patent: US 7,337,280 B2
• Time in Patent Office: Days
• US Class Current: 711/143
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 2212/2542 Non-uniform memory access [NUMA] architecture

Abstract

A system and method for cache management in a data processing system having a memory hierarchy of upper memory and lower memory cache. A lower memory cache controller accesses a coherency state table to determine replacement policies of coherency states for cache lines present in the lower memory cache when receiving a cast-in request from one of the upper memory caches. The coherency state table implements a replacement policy that retains the more valuable cache coherency state information between the upper and lower memory caches for a particular cache line contained in both levels of memory at the time of cast-out from the upper memory cache.

Claims

1. A method for cache management in a data processing system, wherein the data processing system includes a memory hierarchy including at least an upper memory cache and a lower memory cache, the method comprising:

comparing a first coherency data related to cache data indicated in the lower memory cache to second coherency data related to the cache data indicated in the upper memory cache;

determining a coherency state of the cache data in the lower memory cache in response to the comparison of the first coherency data and the second coherency data; and

replacing a coherency value associated with the cache data within the lower memory cache with the determined coherency state.

2. The method of claim 1, further comprising the step of determining, in response to a request to copy the cache data from the upper memory cache to the lower memory cache, whether the lower memory cache indicates the first coherency data related to the cache data.

3. The method of claim 2, wherein the step of comparing is performed in response to determining that the first coherency data is indicated in the lower memory cache.

4. The method of claim 1, wherein the first coherency data and second coherency data are compared by accessing a coherency state table indicating the coherency state in response to a request for cast-in to the lower memory cache.

5. The method of claim 1, wherein comparing includes comparing relative priority of the first coherency data and the second coherency data.

6. The method of claim 5, wherein the relative priority between coherency data is defined as:

(Mx|Tx)→

Ig→

S1→

S→

In→

I, wherein coherency data to the left of particular coherency data has priority over the particular coherency data.

7. The method of claim 5, wherein coherency data indicating modified cache data has priority over coherency data indicating shared or invalid cache data.

8. The method of claim 5, wherein coherency data indicating shared cache data has priority over coherency data indicating invalid cache data.

9. The method of claim 1, wherein the determined coherency state is equal to the second coherency data when the second coherency data indicates the cache data is modified.

10. The method of claim 1, wherein the determined coherency state is equal to the second coherency data when the second coherency data indicates the cache data is shared and the first coherency data does not indicate the cache data is modified in the lower memory cache.

11. The method of claim 1, further comprising the step of copying the cache data from the upper memory cache in the lower memory cache only when the second coherency data indicates the cache data value is modified.

12. The method of claim 1, wherein the determined coherency state is equal to the first coherency data when the first coherency data indicates the cache data value stored in the lower memory cache is modified.

14. The system of claim 12, wherein the memory controller overwrites in response to a request to store the particular sub-block from an upper cache memory.

15. The system of claim 12, wherein the memory controller overwrites the portion as a function of the first coherency metadata related to the particular sub-block indicated in the metadata storage only if such first coherency metadata is contained in the metadata storage.

16. The system of claim 12, wherein the memory controller accessing a coherency state table indicating the coherency state.

17. The system of claim 12, wherein the memory controller determines a relative priority of the first coherency metadata and the second coherency metadata.

18. The system of claim 17, wherein the relative priority between coherency metadata is defined as:

(Mx|Tx)→

Ig→

S1→

S→

In→

I, wherein all coherency metadata to the left of a coherency metadata has priority over that coherency metadata.

19. The system of claim 12, wherein the coherency state is equal to the second coherency metadata when the second coherency metadata indicates the sub-block is modified.

20. The system of claim 12, wherein the coherency state is equal to the first coherency metadata when the first coherency metadata indicates the sub-block is modified in the lower cache memory.

21. The system of claim 12, wherein the coherency state is equal to the second coherency metadata when the second coherency metadata indicates the sub-block is shared and the first coherency metadata does not indicate the sub-block is modified in the lower cache memory.

22. The system of claim 12, wherein the memory controller stores the sub-block in a storage location of the lower cache memory only when the second coherency metadata indicates the sub-block is modified.

13. A cache coherent data processing system, comprising:

a plurality of processing units each having at least an associated upper cache memory;

a lower cache memory associated with the plurality of processing units;

a memory controller that is coupled to and controls access to the lower cache memory;

wherein the lower cache memory includes;

a plurality of storage locations for storing a memory block of data, wherein each of the plurality of storage locations is sized to store a sub-block of data;

metadata storage for storing metadata describing the memory block; and

wherein the memory controller overwrites at least a portion of the metadata in the metadata storage associated with a particular sub-block of data with a coherency state determined as a function of;

(1) first coherency metadata related to the particular sub-block indicated in the metadata storage, and (2) second coherency metadata related to the particular sub-block of data indicated in the upper memory cache.

23. A cache memory for a cache coherent data processing system including a hierarchy of cache memory devices, said cache memory comprising:

a cache controller;

a data array including a data storage location for caching a memory block;

a cache directory including;

a tag field for storing an address tag in association with said memory block;

a coherency state field associated with said tag field and said data storage location, wherein said coherency state field has a plurality of possible coherency states;

wherein said cache controller sets a coherency state of the coherency state field as a function of a received coherency state for the memory block and a current coherency state for the memory block in the coherency state field.

24. The cache memory of claim 23, wherein the memory controller sets the coherency state in response to receiving a request to cache the memory block from a cache memory device at a higher level of the hierarchy of cache memory devices, wherein the request contains the received coherency state.

25. The cache memory of claim 23, wherein the cache controller accesses a coherency state table indicating the coherency state as a function of the received coherency state for the memory block and the current coherency state for the memory block in the coherency state field.

26. The cache memory of claim 23, wherein the cache controller determines a relative priority of the received coherency state and the current coherency state.

27. The cache memory of claim 26, wherein the relative priority between coherency states is defined as:

(Mx|Tx)→

Ig→

S1→

S→

In→

I, wherein all coherency states to the left of a coherency state has priority over that coherency state.

28. The cache memory of claim 23, wherein the coherency state is equal to the current coherency state when the current coherency state indicates the memory block is modified in the data array.

29. The cache memory of claim 23, wherein the coherency state is equal to the received coherency state when the received coherency state indicates the memory block is shared and the current coherency state does not indicate the memory block is modified in the data array.

30. The cache memory of claim 23, wherein the cache controller stores the memory block in the data storage location only when the received coherency state indicates the memory block is modified.