Data reorganization in non-uniform cache access caches

• US 8,140,758 B2
• Filed: 04/24/2009
• Issued: 03/20/2012
• Est. Priority Date: 04/24/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Balakrishnan, Ganesh, Bell, Gordon B., Krishna, Anil, Ramani, Srinivasan
• Primary Examiner(s): DINH, SON T
• Application Number:
  US12/429,754
• Publication Number:
  US 20100274973A1
• Time in Patent Office: 1,061 Days
• Field of Search: 711/119, 711/3, 711/129, 711/157, 711/118
• US Class Current: 711/119
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0846 Cache with multiple tag or data arrays being simultaneously accessible

Abstract

Embodiments that dynamically reorganize data of cache lines in non-uniform cache access (NUCA) caches are contemplated. Various embodiments comprise a computing device, having one or more processors coupled with one or more NUCA cache elements. The NUCA cache elements may comprise one or more banks of cache memory, wherein ways of the cache are horizontally distributed across multiple banks. To improve access latency of the data by the processors, the computing devices may dynamically propagate cache lines into banks closer to the processors using the cache lines. To accomplish such dynamic reorganization, embodiments may maintain “direction” bits for cache lines. The direction bits may indicate to which processor the data should be moved. Further, embodiments may use the direction bits to make cache line movement decisions.

Claims

1. A method, comprising:

setting a first plurality of direction bits for a first cache line of a first way, wherein data of the first cache line is located in a first bank of a plurality of banks of a non-uniform cache access (NUCA) cache, wherein further sets of the NUCA cache are horizontally distributed across the plurality of banks;

setting a second plurality of direction bits for a second cache line of a second way, wherein data of the second cache line is located in a second bank; and

moving data of the first cache line to the second bank and data of the second cache line to the first bank to reduce access latency between at least one of the first and second cache lines to at least one processor, wherein the moving is based upon a calculation which uses the first and second plurality of direction bits.

2. The method of claim 1, further comprising:

setting bits of a partial tag array for the first and second cache lines.

3. The method of claim 2, wherein the partial tag array comprises a distributed array.

4. The method of claim 1, wherein the setting of the first plurality of direction bits comprises storing an identification number of a first processor.

5. The method of claim 4, wherein the setting of the second plurality of direction bits comprises storing a second identification number of a second processor.

6. The method of claim 5, further comprising:

performing additional calculations to determine access latencies between a plurality of processors and banks of the plurality of banks before selecting the first and second cache lines for the moving.

7. The method of claim 6, further comprising:

determining temporal-based accesses of cache lines of the plurality of banks to enable the performing of the additional calculations.

8. The method of claim 1, wherein the moving data of the first cache line to the second bank and data of the second cache line to the first bank comprises swapping data of non-adjacent banks.

9. An apparatus, comprising:

a latency module to determine access latencies between a plurality of processors and a plurality of banks of a non-uniform cache access (NUCA) cache, wherein ways are horizontally distributed across banks of the NUCA cache, wherein the latency module is configured to determine the access latencies via direction bits for cache lines of the ways; and

a data movement module to move data of a first cache line from a first bank of the plurality of banks to a second bank of the plurality of banks and move data of a second cache line from the second bank to the first bank, wherein the data movement module is configured to move the first and second cache lines based upon the determined access latencies of the latency module.

10. The apparatus of claim 9, further comprising a delay module to enable intervals of time to elapse between determinations of access latencies by the latency module.

11. The apparatus of claim 9, further comprising a partial tag array management module to maintain bits of a centralized partial tag array.

12. The apparatus of claim 11, wherein the NUCA cache comprises an L3 cache module and the latency module comprises a state machine.

13. The apparatus of claim 9, wherein the direction bits for the first cache line indicate a horizontal direction that the first cache line should be moved in order to reduce access latency between the first cache line and a processor which requested the cache line.

14. The apparatus of claim 13, wherein magnitude bits for the first cache line indicate a magnitude for the direction that the first cache line should be moved in order to reduce the access latency.

15. The apparatus of claim 9, wherein the direction bits for the first cache line indicate an identification number of a processor which requested the first cache line.

16. The apparatus of claim 15, wherein the latency module determines the access latencies for the first cache line based upon an inference related to distance between the processor and the first cache line.

17. The apparatus of claim 9, wherein the latency module is arranged to successively determine the improvements of access latencies for pairs of cache lines, wherein further determining an improvement for a pair comprising the first and second cache lines comprises:

calculating a first sum of current distances between ways of the first and second cache lines and processors that last requested the first and second cache lines, calculating a second sum of relocated distances of the first and second cache lines and processors that last requested the first and second cache lines, and subtracting the second sum from the first sum.

18. A system comprising:

a plurality of processors;

a plurality of banks of a non-uniform cache access (NUCA) cache, wherein the plurality of processors are coupled to the NUCA cache and arranged to search ways of the NUCA cache, wherein further the ways are horizontally distributed across multiple banks of the NUCA cache; and

a cache controller to evaluate access latencies between the plurality of processors and banks storing cache lines requested by the plurality of processors, wherein the cache controller is configured to swap data of the cache lines between pairs of banks only when at least one of the pairs of cache lines has been consecutively accessed by a processor, and evaluation of the access latencies comprises calculating access latencies for pairs of cache lines stored in pairs of banks to determine whether swapping the cache lines between the pairs of banks reduces access latency between at least one cache line of the pair and a processor that last requested the at least one cache line.

19. The system of claim 18, wherein the cache controller is configured to iteratively calculate access latencies for all cache lines of a set before selecting a single pair of cache lines to swap, wherein further the cache controller is configured to perform the swap, the swap comprising relocating data of the pairs of cache lines between the pairs of banks.