System for prefetching data into a cache
In one aspect, a delta prefetcher disclosed herein bases its predictions on both past memory accesses and predictively prefetched memory accesses. More specifically, the delta prefetcher disclosed herein bases its prediction on both the difference or “delta” between memory addresses of data previously fetched from memory and the difference or “delta” between addresses of data predictively fetched from memory. The delta prefetcher tracks the delta memory accesses by utilizing two distinctive tables. The fetch table tracks the memory deltas for each memory operation, such as a LOAD or STORE instruction, that the CPU has executed. The delta table predicts the next memory address to prefetch based on the last prefetched memory accesses.
1. A prefetch system for prefetching data into a cache, comprising:
a prefetch control circuit;
a fetch table;
a delta table; and
in response to a signal, the prefetch control circuit configured to:
select a first fetch entry in the fetch table, the first fetch entry comprising a first address for a first memory operation, a set of prefetched memory deltas, and a last prefetched address in the first fetch entry;
access a first delta entry in the delta table based on the first address for the first memory operation and the set of prefetched memory deltas, the first delta entry comprising a next memory delta;
determine a calculated address for prefetching by adding the next memory delta to the last prefetched address in the first fetch entry; and
fetch data based on the calculated address.
2. The prefetch system of claim 1 , wherein the prefetch control circuit is further configured to:
in response to receiving a second memory operation comprising a second address of the second memory operation and a second data memory address:
access a second fetch entry of a plurality of fetch entries in the fetch table based on the second address of the second memory operation;
access a second delta entry of a plurality of delta entries in the delta table based on the second address of the second memory operation and a set of fetched memory deltas in the second fetch entry;
determine whether a difference between the second data memory address and a last fetched address in the second fetch entry matches a next delta in the second delta entry; and
adjust a confidence value in the second delta entry.
3. The prefetch system of claim 2 , wherein the prefetch control circuit adjusts the confidence value by incrementing the confidence value of the second delta entry if the difference between the second data memory address and the last fetched address in the second fetch entry matches the next delta in the second delta entry and by decrementing the confidence value if the difference does not match the next delta in the second delta entry.
4. The prefetch system of claim 2 , wherein the second memory operation is a load-based operation.
5. The prefetch system of claim 2 , wherein the fetch table is an M-way set associative table and wherein the first fetch entry in the fetch table further includes a least recently used field for managing replacement among M-fetch entries in a row of the fetch table.
6. The prefetch system of claim 2 , wherein the delta table is an M-way set associative table and wherein the first delta entry in the delta table further includes a least recently used field for managing replacement among M-delta entries in a row of the delta table.
7. The prefetch system of claim 1 , wherein the signal is received every clock cycle.
8. The prefetch system of claim 2 , wherein the first address for the first memory operation, the last fetched address in the second fetch entry, and the last prefetched address in the first fetch entry are virtual addresses.
9. The prefetch system of claim 1 , further comprising a launch queue from which addresses are fetched from memory, wherein the prefetch control circuit is further configured to send the calculated address for prefetching to the launch queue.
10. The prefetch system of claim 2 , further comprising a training queue that sends the second address of the second memory operation and the second data memory address to the prefetch control circuit.
11. The prefetch system of claim 2 , wherein a size of the set of fetched memory deltas and the set of prefetched memory deltas is selected from a group consisting of 2, 3, and 4 memory deltas.
12. A method for prefetching data, comprising:
in response to a signal:
selecting a first fetch entry in a fetch table;
accessing a first delta entry in a delta table based on a first address for a first memory operation in the first fetch entry and a set of prefetched memory deltas in the first fetch entry; and
determining a prefetch address for prefetching by adding a next memory delta in the first delta entry to a last prefetched address in the first fetch entry.
13. The method of claim 12 , further comprising:
in response to receiving a second memory operation comprising a second address of the second memory operation and a second data memory address:
accessing a second fetch entry of a plurality of fetch entries in the fetch table based on the second address of the second memory operation;
accessing a second delta entry of a plurality of delta entries in the delta table based on the second address of the second memory operation and a set of fetched memory deltas in the second fetch entry;
determining whether a difference between the second data memory address and a last fetched address in the second fetch entry matches a next delta in the second delta entry; and
adjusting a confidence field in the second delta entry.
14. The method of claim 13 , wherein the adjusting the confidence field in the second delta entry further comprises:
incrementing the confidence field in the second delta entry if the difference between the second data memory address and the last fetched address in the second fetch entry matches the next delta in the second delta entry; and
decrementing the confidence field in the second delta entry if the difference does not match the next delta in the second delta entry.
15. The method of claim 14 , wherein the second memory operation is a load-based instruction.
16. The method of claim 13 , wherein the second address of the second memory operation, the first address of the first memory operation, the last fetched address in the second fetch entry, and the last prefetched address in the first fetch entry are virtual addresses.
17. A non-transitory computer-readable storage medium comprising instructions executable by a processor, which, when executed by the processor, cause the processor to prefetch data from external memory to cache memory, comprising:
in response to a signal:
selecting a first fetch entry in a fetch table;
accessing a first delta entry in a delta table based on a first address for a first memory operation in the first fetch entry and a set of prefetched memory deltas in the first fetch entry; and
determining a prefetch address for prefetching by adding a next memory delta in the first delta entry to a last prefetched address in the first fetch entry.
18. The non-transitory computer-readable storage medium of claim 17 , further comprising:
in response to receiving a second memory operation comprising a second address of the second memory operation and a second data memory address:
accessing a second fetch entry of a plurality of fetch entries in the fetch table based on the second address of the second memory operation;
accessing a second delta entry of a plurality of delta entries in the delta table based on the second address of the second memory operation and a set of fetched memory deltas in the second fetch entry;
determining whether a difference between the second data memory address and a last fetched address in the second fetch entry matches a next delta in the second delta entry; and
adjusting a confidence field in the second delta entry.
19. The non-transitory computer-readable storage medium of claim 18 , further including:
decrementing the confidence field in the second delta entry if the next memory delta in the first delta entry does not equal the difference between the second data memory address and the last fetched address in the first fetch entry.
20. The non-transitory computer-readable storage medium of claim 18 , wherein the second memory operation is a load-based instruction.