Lateral castout (LCO) of victim cache line in data-invalid state

• US 8,949,540 B2
• Filed: 03/11/2009
• Issued: 02/03/2015
• Est. Priority Date: 03/11/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Guthrie, Guy L., Le, Hien M., Ng, Alvan W., Siegel, Michael S., Williams, Derek E., Williams, Phillip G.
• Primary Examiner(s): Savla, Arpan P.
• Application Number:
  US12/402,025
• Publication Number:
  US 20100235584A1
• Time in Patent Office: 2,155 Days
• Field of Search: 711/122, 711/133, 711118-120, 711/135, 711/141
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel

Abstract

A victim cache line having a data-invalid coherence state is selected for castout from a first lower level cache of a first processing unit. The first processing unit issues on an interconnect fabric a lateral castout (LCO) command identifying the victim cache line to be castout from the first lower level cache, indicating the data-invalid coherence state, and indicating that a lower level cache is an intended destination of the victim cache line. In response to a coherence response to the LCO command indicating success of the LCO command, the victim cache line is removed from the first lower level cache and held in a second lower level cache of a second processing unit in the data-invalid coherence state.

Claims

1. A method of data processing in a data processing system including a plurality of processing units including a first processing unit and a second processing unit coupled by an interconnect fabric, wherein the first processing unit has a first processor core having an associated first upper level cache and a first lower level cache, and wherein the second processing unit has a second processor core and an associated second upper level cache and second lower level cache, said method comprising:

in response to a need to evict one of a plurality of cache lines in a congruence class of the first lower level cache;

selecting a victim cache line to be evicted from the congruence class of the first lower level cache;

determining, based at least on a coherence state of the victim cache line, whether to perform a lateral castout (LCO) to a lower level cache of another of the plurality of processing units or a castout to a system memory, wherein the determining includes determining to perform a LCO of a coherence state of the victim cache line in response to the victim cache line having a first data-invalid coherence state and determining to perform a castout of the coherence state of the victim cache line to the system memory in response to the victim cache line having a second data-invalid coherence state;

in response to determining to perform the LCO of the coherence state of the victim cache line, the first processing unit issuing a lateral castout (LCO) command on the interconnect fabric, wherein the LCO command identifies an address of the victim cache line to be evacuated from the first lower level cache, indicates the first data-invalid coherence state, and indicates that a lower level cache is an intended destination of the coherence state of the victim cache line; and

in response to a coherence response to the LCO command indicating success of the LCO command, evacuating the victim cache line from the first lower level cache and associating the address of the victim cache line with the first data-invalid coherence state in a directory of the second lower level cache, wherein the LCO command does not transfer data of the victim cache line from the first lower level cache to the second lower level cache.

2. The method of claim 1, wherein the first and second lower level caches are victim caches, and wherein the first processing unit performs the selecting and removing steps.

3. The method of claim 1, wherein:

the victim cache line is a first victim cache line; and

the method further comprises evicting a second victim cache line from the second lower level cache to make room for an entry for the address of the first victim cache line in the directory of the second lower level cache.

4. The method of claim 1, wherein said lateral castout command identifies the second lower level cache as the destination.

5. The method of claim 1, wherein:

the plurality of processing units are grouped in at least a first coherence domain including the first processing unit and a second coherence domain; and

the first data-invalid coherence state indicates that a valid copy of the victim cache line was sourced to a processing unit among the plurality of processing units belonging to the second coherence domain.

15. The method of claim 1, wherein:

the method further comprises recording, in the first lower level cache, an access chronology for the plurality of cache lines and a respective membership of each of the plurality of cache lines in one of a plurality of classes including at least a first class and a second class, wherein the first class includes one or more cache lines of the congruence class more likely to be accessed by a first processor core of the first processing unit than one or more cache lines of the congruence class in the second class, wherein the membership of the plurality of cache lines in the plurality of classes is determined dependent on a type of access made to each of the plurality of cache lines and independent of the recorded access chronology of the plurality of cache lines; and

the selecting includes selecting the victim cache line from among the one or more cache lines in the second class while excluding the one or more cache lines in the first class from the selection.

16. The method of claim 1, wherein the determining further includes determining not to perform an LCO in response to the need to evict one of the plurality of cache lines arising from a cast-in from another lower level cache.

6. A data processing system, comprising:

an interconnect fabric; and

a plurality of processing units coupled to the interconnect fabric, the plurality of processing units including a first processing unit and a second processing unit, wherein the first processing unit has a first processor core and associated first upper and first lower level caches, and wherein the second processing unit has a second processor core and associated second upper and lower level caches;

wherein the first lower level cache includes;

a data array including a plurality of congruence classes including a congruence class containing a plurality of cache lines, and

a directory of the data array;

wherein the first processing unit, responsive to a need to evict one of the plurality of cache lines, selects a victim cache line to be evicted from the congruence class of the first lower level cache and determines, based at least on a coherence state of the victim cache line, whether to perform a lateral castout (LCO) to a lower level cache of another of the plurality of processing units or a castout to a system memory, wherein the first processing unit determines to perform a LCO of a coherence state of the victim cache line responsive to the victim cache line having a first data-invalid coherence state and determines to perform a castout of the coherence state of the victim cache line to the system memory responsive to the victim cache line having a second data-invalid coherence state;

wherein the first processing unit, responsive to determining to perform the LCO of the coherence state of the victim cache line, issues a lateral castout (LCO) command on the interconnect fabric, wherein the LCO command identifies an address of the victim cache line to be evacuated from the first lower level cache, indicates the first data-invalid coherence state, and indicates that a lower level cache is an intended destination of the coherence state of the victim cache line; and

wherein responsive to a coherence response to the LCO command indicating success of the LCO command, the first processing unit evacuates the victim cache line from the first lower level cache and a directory of the second lower level cache associates the address of the victim cache line with the first data-invalid coherence state, wherein the LCO command does not transfer data of the victim cache line from the first lower level cache to the second lower level cache.

7. The data processing system of claim 6, wherein the first and second lower level caches are victim caches.

8. The data processing system of claim 6, wherein:

the victim cache line is a first victim cache line; and

the second lower level cache evicts a second victim cache line from the second lower level cache to make room for the address of the first victim cache line in the directory of the second lower level cache.

9. The data processing system of claim 6, wherein said lateral castout command identifies the second lower level cache as the destination.

10. The data processing system of claim 6, wherein:

the plurality of processing units are grouped in at least a first coherence domain including the first processing unit and a second coherence domain; and

the first data-invalid coherence state indicates that a valid copy of the victim cache line was sourced to a processing unit among the plurality of processing units belonging to the second coherence domain.

17. The data processing system of claim 6, wherein:

the directory includes an access chronology for the plurality of cache lines and a respective membership of each of the plurality of cache lines in one of a plurality of classes including at least a first class and a second class, wherein the first class includes one or more cache lines of the congruence class more likely to be accessed by a first processor core of the first processing unit than one or more cache lines of the congruence class in the second class, wherein the membership of the plurality of cache lines in the plurality of classes is determined dependent on a type of access made to each of the plurality of cache lines and independent of the recorded access chronology of the plurality of cache lines; and

the first processing unit selects the victim cache line from among the one or more cache lines in the second class while excluding the one or more cache lines in the first class from the selection.

18. The data processing system of claim 6, wherein the first processing unit determines not to perform an LCO in response to the need to evict one of the plurality of cache lines arising from a cast-in from another lower level cache.

11. A processing unit for a data processing system including a plurality of processing units coupled by an interconnect fabric, the processing unit comprising:

a first processor core and associated first upper and first lower level caches, wherein the first lower level cache includes;

a data array including a plurality of congruence classes including a congruence class containing a plurality of cache lines, and

a directory of the data array;

wherein the processing unit, responsive to a need to evict one of the plurality of cache lines, selects a victim cache line to be evicted from the congruence class of the first lower level cache and determines, based at least on a coherence state of the victim cache line, whether to perform a lateral castout (LCO) to a lower level cache of another of the plurality of processing units or a castout to a system memory, wherein the first processing unit determines to perform a LCO of a coherence state of the victim cache line responsive to the victim cache line having a first data-invalid coherence state and determines to perform a castout of the coherence state of the victim cache line to the system memory responsive to the victim cache line having a second data-invalid coherence state;

wherein the processing unit, responsive to determining to perform the LCO of the coherence state of the victim cache line, issues a lateral castout (LCO) command on the interconnect fabric, wherein the LCO command identifies an address of the victim cache line to be evacuated from the first lower level cache, indicates the first data-invalid coherence state, and indicates that a lower level cache is an intended destination of the coherence state of the victim cache line; and

wherein responsive to a coherence response to the LCO command indicating success of the LCO command, the processing unit evacuates the victim cache line from the first lower level cache for association by a directory of a second lower level cache with the first data-invalid coherence state, wherein the LCO command does not transfer data of the victim cache line from the first lower level cache to the second lower level cache.

12. The processing unit of claim 11, wherein:

the first lower level cache is a victim cache; and

the processing unit is a single integrated circuit chip.

13. The processing unit of claim 11, wherein said lateral castout command identifies the second lower level cache as the destination.

14. The processing unit of claim 11, wherein:

the plurality of processing units are grouped in at least a first coherence domain including the first processing unit and a second coherence domain; and

the first data-invalid coherence state indicates that a valid copy of the victim cache line was sourced to a processing unit among the plurality of processing units belonging to the second coherence domain.

19. The processing unit of claim 11, wherein:

the directory includes an access chronology for the plurality of cache lines and a respective membership of each of the plurality of cache lines in one of a plurality of classes including at least a first class and a second class, wherein the first class includes one or more cache lines of the congruence class more likely to be accessed by a first processor core of the first processing unit than one or more cache lines of the congruence class in the second class, wherein the membership of the plurality of cache lines in the plurality of classes is determined dependent on a type of access made to each of the plurality of cache lines and independent of the recorded access chronology of the plurality of cache lines; and

the first processing unit selects the victim cache line from among the one or more cache lines in the second class while excluding the one or more cache lines in the first class from the selection.

20. The processing unit of claim 11, wherein the processing unit determines not to perform an LCO in response to the need to evict one of the plurality of cache lines arising from a cast-in from another lower level cache.