Empirically based dynamic control of transmission of victim cache lateral castouts

• US 8,347,036 B2
• Filed: 04/09/2009
• Issued: 01/01/2013
• Est. Priority Date: 04/09/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cargnoni, Robert A., Guthrie, Guy L., Helterhoff, Harmony L., Starke, William J., Stuecheli, Jeffrey A., Williams, Phillip G.
• Primary Examiner(s): CHOE, YONG J
• Application Number:
  US12/421,180
• Publication Number:
  US 20100262778A1
• Time in Patent Office: 1,363 Days
• Field of Search: 711/122, 711/133, 711/118, 711/141, 711/E12.017
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

In response to a data request, a victim cache line is selected for castout from a lower level cache, and a target lower level cache of one of the plurality of processing units is selected. A determination is made whether the selected target lower level cache has provided more than a threshold number of retry responses to lateral castout (LCO) commands of the first lower level cache, and if so, a different target lower level cache is selected. The first processing unit thereafter issues a LCO command on the interconnect fabric. The LCO command identifies the victim cache line to be castout and indicates that the target lower level cache is an intended destination of the victim cache line. In response to a successful coherence response to the LCO command, the victim cache line is removed from the first lower level cache and held in the second lower level cache.

Claims

1. A method of data processing in a data processing system including a plurality of lower level caches and a plurality of architecturally distributed system memories coupled by an interconnect fabric, wherein the plurality of lower level caches includes first, second and third lower level caches, wherein the first lower level cache is associated with a first processing unit having a first processor core and an associated first upper level cache and the second lower level cache is associated with a second processing unit having a second processor core and an associated second upper level cache, said method comprising:

in response to a data request, the first processing unit;

selecting a victim cache line to be castout from the first lower level cache;

selecting a target lower level cache among the plurality of lower level caches, wherein said selecting a target lower level cache comprises selecting a target lower level cache based upon architectural proximity of the target lower level cache to a home system memory among the plurality of system memories to which an address of the victim cache line is assigned;

the first processing unit thereafter issuing a lateral castout (LCO) command on the interconnect fabric, wherein the LCO command identifies the victim cache line to be castout from the first lower level cache and indicates that the target lower level cache is a single intended destination of the victim cache line among the plurality of lower level caches; and

in response to a coherence response to the LCO command indicating success of the LCO command, removing the victim cache line from the first lower level cache and holding the victim cache line in the second lower level cache.

2. The method of claim 1, wherein the first and second lower level caches are victim caches.

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

4. The method of claim 3, 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 the first victim cache line in the second lower level cache.

5. The method of claim 1, and further comprising:

in response to a coherence response to the lateral castout (LCO) command indicating success of the LCO command, the first processing unit transmitting the victim cache line to the second lower level cache.

6. The method of claim 1, and further comprising determining whether the selected target lower level cache has provided more than a threshold number of retry responses to lateral castout (LCO) commands of the first lower level cache, and if so, selecting a different target lower level cache.

7. The method of claim 1, wherein selecting a target lower level cache comprises:

determining a pool containing multiple lower level caches architecturally proximate to the home system memory; and

selecting the target lower level cache from the pool.

8. The method of claim 1, wherein selecting a target lower level cache comprises:

selecting the target lower level cache utilizing a base address register facility.

9. A data processing system, comprising:

an interconnect fabric;

a plurality of processing units coupled to the interconnect fabric, wherein the plurality of processing units are supported by a plurality of lower level caches including first, second and third lower level caches, wherein the first lower level cache is associated with a first processing unit having a first processor core and an associated first upper level cache and the second lower level cache is associated with a second processing unit having a second processor core and an associated second upper level cache; and

a plurality of architecturally distributed system memories coupled to the interconnect fabric, wherein the plurality of architecturally distributed system memories includes a home system memory that is assigned a plurality of addresses including an address;

wherein the first processing unit, in response to a data request, selects a victim cache line associated with the address to be castout from the first lower level cache, selects a target lower level cache among the plurality of lower level caches based upon architectural proximity of the target lower level cache to the home system memory to which the address of the victim cache line is assigned, and thereafter issues a lateral castout (LCO) command on the interconnect fabric, the LCO command identifying the victim cache line to be castout from the first lower level cache and indicating that the target lower level cache is a single intended destination of the victim cache line among the plurality of lower level caches; and

wherein responsive to a coherence response to the LCO command indicating success of the LCO command, the first processing unit removes the victim cache line from the first lower level cache and the second lower level cache holds the victim cache line.

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

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

12. The data processing system of claim 11, wherein:

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

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

13. The data processing system of claim 9, wherein the first processing unit transmits the victim cache line to the second lower level cache in response to a coherence response to the lateral castout (LCO) command indicating success of the LCO command.

14. The data processing system of claim 9, wherein the first processing unit, prior to issuing the LCO command, determines whether the selected target lower level cache has provided more than a threshold number of retry responses to lateral castout (LCO) commands of the first lower level cache, and if so, selects a different target lower level cache.

15. The data processing system of claim 9, wherein the first processing unit selects the target lower level cache by determining a pool containing multiple lower level caches architecturally proximate to the home system memory and selecting the target lower level cache from the pool.

16. The data processing system of claim 9, wherein the first processing unit includes a base address register facility and select the target lower level cache utilizing the base address register facility.

17. A processing unit for a data processing system including a plurality of architecturally distributed system memories including a home system memory, a plurality of processing units coupled by an interconnect fabric, and a plurality of lower level caches supporting the plurality of processing units, wherein the home system memory is assigned a plurality of addresses including an address, the processing unit comprising:

the processing unit has a first processor core and associated first upper and first lower level caches;

wherein the processing unit, in response to a data request, selects a victim cache line associated with the address to be castout from the first lower level cache, selects a target lower level cache among the plurality of lower level caches based upon architectural proximity of the target lower level cache to the home system memory to which the address of the victim cache line is assigned, and thereafter issues a lateral castout (LCO) command on the interconnect fabric, the LCO command identifying the victim cache line to be castout from the first lower level cache and indicating that the target lower level cache is a single intended destination of the victim cache line among the plurality of lower level caches; and

wherein responsive to a coherence response to the LCO command indicating success of the LCO command, the first processing unit removes the victim cache line from the first lower level cache for storage in a second lower level cache.

18. The processing unit of claim 17, wherein the first and second lower level caches are victim caches.

19. The processing unit of claim 17, wherein said lateral castout command identifies the second lower level cache as the target lower level cache.

20. The processing unit of claim 17, wherein the first processing unit transmits the victim cache line to the second lower level cache in response to a coherence response to the LCO command indicating success of the LCO command.

21. The processing unit of claim 17, wherein the first processing unit, prior to issuing the LCO command, determines whether the selected target lower level cache has provided more than a threshold number of retry responses to lateral castout (LCO) commands of the first lower level cache, and if so, selects a different target lower level cache.

22. The processing unit of claim 17, wherein the processing unit selects the target lower level cache by determining a pool containing multiple lower level caches of the data processing system that are architecturally proximate to the home system memory and selecting the target lower level cache from the pool.

23. The processing system of claim 17, wherein the processing unit includes a base address register facility and select the target lower level cache utilizing the base address register facility.

24. A method of data processing in a data processing system including a plurality of processing units and a system memory coupled by an interconnect fabric, wherein each of the plurality of processing units includes a processor core and associated upper and lower level caches, said method comprising:

in response to a data request of the processor core of a first processing unit among the plurality of processing units, selecting a victim cache line to be removed from the lower level cache of the first processing unit;

selecting among a lateral castout (LCO) from the lower level cache of the first processing unit to another lower level cache and a castout (CO) from the lower level cache of the first processing unit to the system memory, wherein the selecting comprises selecting based upon empirical success of the upper level cache of the first processing unit in obtaining requested data by intervention from cache memories of other of the plurality of processing units rather than the system memory;

in response to selecting an LCO, performing an LCO of the victim cache line to a lower level cache of one of the plurality of processing units by issuing a LCO command on the interconnect fabric; and

in response to selecting a CO, performing a CO of the victim cache line to the system memory.

25. The method of claim 24, wherein:

selecting among the LCO and the CO comprises preferentially selecting LCOs for victim cache lines in a home LCO address region of the lower level cache of the first processing unit, wherein the home LCO address region spans multiple congruence classes of the lower level cache;

the method further comprises;

empirically measuring success of the upper level cache of the first processing unit in obtaining requested data within the home LCO address region by intervention from cache memories of other of the plurality of processing units rather than the system memory; and

disabling LCOs for victim caches line outside the home LCO address region of the lower level cache based upon lack of success of the upper level cache of the first processing unit in obtaining requested data within the home LCO address region by intervention from cache memories of other of the plurality of processing units rather than the system memory.

26. The method of claim 25, wherein empirically measuring success comprises comparing to at least one threshold a metric indicative of success of the upper level cache of the first processing unit in obtaining requested data within the home LCO address region by intervention from cache memories of other of the plurality of processing units rather than the system memory.

27. The method of claim 26, wherein said at least one threshold comprises a lower LCO threshold and an upper LCO threshold.

28. The method of claim 25, wherein empirically measuring success comprises computing an average amount of data requests of the first processing unit in the home LCO address region satisfied by cache-to-cache intervention.

29. The method of claim 24, wherein the LCO command identifies the victim cache line to be castout from the lower level cache of the first processing unit and indicates a target lower level cache is an intended destination of the victim cache line;

and

in response to a coherence response to the LCO command indicating success of the LCO command, removing the victim cache line from the lower level cache of the first processing unit and holding the victim cache line in a lower level cache of another of the plurality of processing units.

30. The method of claim 24, wherein the lower level cache in each of the plurality of processing units is a victim cache.

31. A data processing system, comprising:

a plurality of processing units and a system memory coupled by an interconnect fabric, wherein each of the plurality of processing units includes a processor core and associated upper and lower level caches, said plurality of processing units including a first processing unit;

wherein the lower level cache of the first processing unit, responsive to a data request of the processor core of a first processing unit, selects a victim cache line to be removed from the lower level cache of the first processing unit and selects among a lateral castout (LCO) to another lower level cache and a castout (CO) to the system memory, wherein the lower level cache of the first processing unit selects either the LCO or CO based upon empirical success of the upper level cache of the first processing unit in obtaining requested data by intervention from cache memories of other of the plurality of processing units rather than the system memory; and

wherein the lower level cache of the first processing unit, responsive to selecting an LCO, performs an LCO of the victim cache line to a lower level cache of one of the plurality of processing units by issuing a LCO command on the interconnect fabric and, responsive to selecting a CO, performs a CO of the victim cache line to the system memory.

32. The data processing system of claim 31, wherein:

the lower level cache of the first processing unit preferentially selects LCOs for victim cache lines in a home LCO address region of the lower level cache of the first processing unit, wherein the home LCO address region spans multiple congruence classes of the lower level cache;

the lower level cache of the first processing unit empirically measures success of the upper level cache of the first processing unit in obtaining requested data within the home LCO address region by intervention from cache memories of other of the plurality of processing units rather than the system memory; and

the lower level cache of the first processing unit disables LCOs for victim cache line outside the home LCO address region of the lower level cache based upon lack of success of the upper level cache of the first processing unit in obtaining requested data within the home LCO address region by intervention from cache memories of other of the plurality of processing units rather than the system memory.

33. The data processing system of claim 32, wherein the lower level cache of the first processing unit empirically measures success by comparing to at least one threshold a metric indicative of success of the upper level cache of the first processing unit in obtaining requested data within the home LCO address region by intervention from cache memories of other of the plurality of processing units rather than the system memory.

34. The data processing system of claim 33, wherein said at least one threshold comprises a lower LCO threshold and an upper LCO threshold.

35. The data processing system of claim 32, wherein the lower level cache of the first processing unit empirically measuring success by computing an average amount of data requests of the first processing unit in the home LCO address region satisfied by cache-to-cache intervention.

36. The data processing system of claim 31, wherein:

the LCO command identifies the victim cache line to be castout from the lower level cache of the first processing unit and indicates a target lower level cache is an intended destination of the victim cache line; and

the lower level cache of the first processing unit, responsive to a coherence response to the LCO command indicating success of the LCO command, removes the victim cache line from the lower level cache of the first processing unit.

37. The data processing system of claim 31, wherein the lower level cache in each of the plurality of processing units is a victim cache.

38. A processing unit for a data processing system having a plurality of processing units and a system memory coupled by an interconnect fabric, wherein each of the plurality of processing units includes a processor core and associated upper and lower level caches, said processing unit comprising:

a processor core;

an upper level cache coupled to the processor core; and

a lower level cache coupled to the upper level cache;

wherein the lower level cache, responsive to a data request of the processor core, selects a victim cache line to be removed from the lower level cache and selects among a lateral castout (LCO) to another lower level cache and a castout (CO) to the system memory, wherein the lower level cache selects either the LCO or CO based upon empirical success of the upper level cache in obtaining requested data by intervention from cache memories of other of the plurality of processing units rather than the system memory; and

wherein the lower level cache, responsive to selecting an LCO, performs an LCO of the victim cache line to a lower level cache of one of the plurality of processing units by issuing a LCO command on the interconnect fabric and, responsive to selecting a CO, performs a CO of the victim cache line to the system memory.

39. The data processing system of claim 38, wherein:

the lower level cache preferentially selects LCOs for victim cache lines in a home LCO address region of the lower level cache, wherein the home LCO address region spans multiple congruence classes;

the lower level cache empirically measures success of the upper level cache in obtaining requested data within the home LCO address region by intervention from cache memories of other of the plurality of processing units rather than the system memory; and

the lower level cache disables LCOs for victim cache line outside the home LCO address region of the lower level cache based upon lack of success of the upper level cache in obtaining requested data within the home LCO address region by intervention from cache memories of other of the plurality of processing units rather than the system memory.

40. The data processing system of claim 39, wherein the lower level cache empirically measures success by comparing to at least one threshold a metric indicative of success of the upper level cache in obtaining requested data within the home LCO address region by intervention from cache memories of other of the plurality of processing units rather than the system memory.

41. The data processing system of claim 40, wherein said at least one threshold comprises a lower LCO threshold and an upper LCO threshold.

42. The data processing system of claim 39, wherein the lower level cache empirically measuring success by computing an average amount of data requests in the home LCO address region satisfied by cache-to-cache intervention.

43. The data processing system of claim 38, wherein:

the LCO command identifies the victim cache line to be castout from the lower level cache and indicates a target lower level cache is an intended destination of the victim cache line; and

the lower level cache, responsive to a coherence response to the LCO command indicating success of the LCO command, removes the victim cache line from the lower level cache.

44. The data processing system of claim 38, wherein the lower level cache in each of the plurality of processing units is a victim cache.