CORRELATED ADDRESSES AND PREFETCHING

• US 20200133863A1
• Filed: 10/31/2018
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Arm Limited (SoftBank Group Corp.)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: PUSDESRIS, Joseph Michael, DOOLEY, Miles Robert, FILIPPO, Michael
• Granted Patent: US 11,263,138 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/602 Details relating to cache prefetching
• CPC Class Codes: G06F 2212/6024 History based prefetching

Abstract

An apparatus is provided that includes cache circuitry that comprises a plurality of cache lines. The cache circuitry treats one or more of the cache lines as trace lines each having correlated addresses and each being tagged by a trigger address. Prefetch circuitry causes data at the correlated addresses stored in the trace lines to be prefetched.

Claims

1. An apparatus comprising:

cache circuitry comprising a plurality of cache lines, wherein the cache circuitry is adapted to treat one or more of the cache lines as trace lines each comprising correlated addresses and each being tagged by a trigger address; and

prefetch circuitry to cause data at the correlated addresses stored in the trace lines to be prefetched.

2. An apparatus according to claim 1, wherein

the prefetch circuitry is adapted to cause the data at the correlated addresses to be prefetched in response to the trigger address being accessed.

3. An apparatus according to claim 1, comprising:

obtaining circuitry to obtain the correlated addresses, wherein the correlated addresses relate to data where a miss has occurred.

4. An apparatus according to claim 1, wherein

the correlated addresses relate to data that has been explicitly fetched.

5. An apparatus according to claim 1, wherein

the correlated addresses relate to data that has been fetched as part of a load operation.

6. An apparatus according to claim 1, wherein

the correlated addresses contain at least one storage location where another of the correlated addresses is stored.

7. An apparatus according to claim 1, wherein

the trigger address and the correlated addresses form a linked list.

8. An apparatus according to claim 1, wherein

each line in the plurality of cache lines include a c flag and a d flag to indicate whether that line is one of the trace lines;

the c flag and the d flag are mutually-exclusive.

9. An apparatus according to claim 1, wherein

the correlated addresses in each of the trace lines are compressed.

10. An apparatus according to claim 9, wherein

the correlated addresses in a given trace line are compressed by storing a base address and, for each individual address in the correlated addresses of the given trace line, a delta between the base address and the individual address.

11. An apparatus according to claim 10, wherein

the base address comprises common bits between the plurality of correlated addresses in the given trace line;

and

the delta comprises remaining bits from the individual address when the common bits are removed.

12. An apparatus according to claim 8, comprising:

eviction circuitry to evict the plurality of cache lines from the cache circuitry in dependence on one or more standard eviction conditions, wherein

the eviction circuitry is inhibited from evicting the trace lines in dependence on one or more correlated-address eviction conditions.

13. An apparatus according to claim 12, wherein

the one or more correlated-address eviction conditions includes a fill condition;

the plurality of cache lines are grouped into a plurality of sets;

each set in the plurality of sets has a set counter, which is incremented in response to a fill being made to that set; and

the fill condition causes a given trace line in the set to be made evictable based on the set counter associated with the given trace line.

14. An apparatus according to claim 13, wherein

the given trace line in the set is associated with a line counter;

the line counter is incremented each time the set counter of the given line reaches a predetermined value; and

the fill condition causes the given line to be made evictable when the line counter reaches a further predetermined value.

15. An apparatus according to claim 12, comprising:

trigger queue circuitry to store a plurality of triggering addresses, wherein

in response to the trigger address of the given line missing when the trigger queue circuitry is at its maximum capacity, the line counter associated with the given line is incremented.

16. An apparatus according to claim 12, wherein

the one or more correlated-address eviction conditions includes a double-hit condition;

the double-hit condition causes a given trace line to be made evictable in response to the cache circuitry hitting, in response to a request, on both the given cache line and a further cache line that is other than one of the trace lines; and

the given cache line and the further cache line have a same tag.

17. An apparatus according to claim 16, wherein

in response to adding a new trace line when the cache contains the further cache line that is other than one of the trace lines, the further cache line is marked as being evictable.

18. An apparatus according to claim 1, wherein

the cache circuitry is adapted to limit a number of the trace lines to a predetermined level.

19. A method comprising:

storing a plurality of cache lines including one or more trace lines each comprising correlated addresses and each being tagged by a trigger address; and

causing data at the correlated addresses stored in the trace lines to be prefetched.

20. An apparatus comprising:

means for storing a plurality of cache lines including one or more trace lines each comprising correlated addresses and each being tagged by a trigger address; and

means for causing data at the correlated addresses stored in the trace lines to be prefetched.