System and method for cooperative prefetching
View Patent ↗A first prefetch engine from a first plurality of prefetch engines is allocated to a first load instruction in response to a buffer miss of an iteration of the first load instruction in a program stream. The first plurality of prefetch engines include prefetch engines for prefetching data from memory to a buffer based on a predicted stride. A second prefetch engine from a second plurality of prefetch engines is allocated to the first load instruction in response to the buffer miss. The second plurality of prefetch engines include prefetch engines for prefetching data from memory to the buffer based on an instruction loop representative of a sequence of instructions that affect an address value associated with an allocated load instruction. One of the first or second prefetch engines is deallocated if the other prefetch engine achieves a prefetch performance greater than a first threshold value.
1. A method comprising:
identifying a first load instruction of a program stream executed by a processing unit as delinquent based on a buffer miss during an iteration of the first load instruction;
performing a first prefetching process at a first prefetch unit for one or more iterations of the first load instruction for prefetching data from memory into a buffer, the first prefetching process based on an expected stride pattern of the one or more iterations of the first load instruction;
performing a second prefetching process at a second prefetch unit for one or more iterations of the first load instruction for prefetching data from memory into the buffer, the second prefetching process based on an instruction loop that represents a subset of a sequence of instructions between iterations of the first load instruction that affect an address value associated with the first load instruction;
determining a first confidence value for the first prefetching process based on a prefetch performance of the first prefetching process;
determining a second confidence value for the second prefetching process based on a prefetch performance of the second prefetching process; and
terminating execution of one of the first prefetching process or the second prefetching process based on a comparison of the first confidence value and the second confidence value.
2. The method of claim 1 , wherein:
the first prefetching process is terminated if the first confidence value is less than the second confidence value; and
the second prefetching process is terminated if the second confidence value is less than or equal to the first confidence value.
3. The method of claim 1 , wherein:
determining the first confidence value comprises:
incrementing the first confidence value if a buffer hit occurs in the data prefetched by the first prefetching process during an iteration of the first load instruction; and
decrementing the first confidence value if a buffer miss occurs during an iteration of the first load instruction; and
determining the second confidence value comprises:
incrementing the second confidence value if a buffer hit occurs in the data prefetched by the second prefetching process during an iteration of the first load instruction; and
decrementing the second confidence value if a buffer miss occurs during an iteration of the first load instruction.
4. The method of claim 1 , wherein the first prefetching process is performed by a first prefetch unit and the second prefetching process is performed by a second prefetch unit different than the first prefetching unit.
5. The method of claim 4 , wherein the first and second prefetching processes are performed substantially in parallel.
6. The method of claim 1 , wherein performing the second prefetching process comprises:
generating a first prefetching graph based on a sequence of instructions of the program stream that are committed to an execution pipeline of the processing unit between a first iteration and a second iteration of a first load instruction;
generating a second prefetching graph from the first prefetching graph based on a first subset of the sequence of instructions that affect an address value associated with the first load instruction; and
generating the instruction loop based on the second prefetching graph.
7. The method of claim 6 , wherein generating the first prefetching graph includes filtering out an instruction from the sequence of instructions based on a comparison of an instruction type of the instruction with an identified set of one or more instruction types.
8. The method of claim 6 , wherein generating the first prefetching graph further includes filtering out a second load instruction from the sequence of instructions based on a comparison of an address value of the first load instruction with an address value of the second load instruction.
9. The method of claim 6 , wherein generating the second prefetching graph comprises:
filtering out an identified instruction of the sequence of instructions that uses an operand value that is not affected by another instruction of the sequence of instructions that is prior to the identified instruction.
10. A method comprising:
allocating a first prefetch engine from a first plurality of prefetch engines to a first load instruction in response to a buffer miss of an iteration of the first load instruction in a program stream, the first plurality of prefetch engines comprising prefetch engines for prefetching data from memory to a buffer based on a predicted stride;
allocating a second prefetch engine from a second plurality of prefetch engines to the first load instruction in response to the buffer miss of the iteration of the first load instruction, the second plurality of prefetch engines comprising prefetch engines for prefetching data from memory to the buffer based on an instruction loop representative of a sequence of instructions that affect an address value associated with an allocated load instruction; and
deallocating one of the first or second prefetch engines if the other of the first or second prefetch engines achieves a prefetch performance greater than a first threshold value.
11. The method of claim 10 , further comprising:
allocating a third prefetch engine from one of the first or second pluralities of prefetch engines if the prefetch performance of the other of the first or second prefetch engines achieves a prefetch performance less than a second threshold.
12. The method of claim 10 , further comprising:
identifying a first available prefetch engine of the first plurality of prefetch engines, wherein the first prefetch engine comprises the first available prefetch engine; and
identifying a second available prefetch engine of the second plurality of prefetch engines, wherein the second prefetch engine comprises the second available prefetch engine.
13. The method of claim 12 , wherein a prefetch engine is characterized as being available either if it is not allocated or if it is allocated and a prefetch performance associated with the prefetch engine is less than a second threshold value.
14. The method of claim 10 , further comprising:
deallocating both of the first and second prefetch engines if neither of the first or second prefetch engines achieves a prefetch performance greater than the first threshold value.
15. The method of claim 10 , wherein the program stream further comprises multiple iterations of a second load instruction and wherein the method further comprises:
allocating a third prefetch engine from the first plurality of prefetch engines to the second load instruction in response to a buffer miss of an iteration of the second load instruction in the program stream;
allocating a fourth prefetch engine from the second plurality of prefetch engines to the second load instruction in response to the buffer miss of the iteration of the second load instruction; and
deallocating one of the third or fourth prefetch engines if the other of the third or fourth prefetch engines achieves a prefetch performance greater than the first threshold value.
16. A system comprising:
a processing unit to execute a program stream comprising multiple iterations of a first load instruction;
a first plurality of prefetch engines, wherein each prefetch engine of the first plurality of prefetch engines is for prefetching data from memory to a buffer based on a predicted stride of a load instruction allocated to the prefetch engine;
a second plurality of prefetch engines, wherein each prefetch engine of the second plurality of prefetch engines is for prefetching data from memory to a buffer based on based on an instruction loop representative of a sequence of instructions that affect an address value associated with a load instruction allocated the prefetch engine; and
wherein a first prefetch engine from the first plurality of prefetch engines is allocated to the first load instruction in response to a buffer miss of an iteration of the first load instruction in the program stream;
wherein a second prefetch engine from the second plurality of prefetch engines is allocated to the first load instruction in response to the buffer miss of the iteration of the first load instruction; and
wherein one of the first or second prefetch engines is deallocated if the other of the first or second prefetch engines achieves a prefetch performance greater than a first threshold value.
17. The system of claim 16 , wherein a third prefetch engine from one of the first or second pluralities of prefetch engines is allocated if the prefetch performance of the other of the first or second prefetch engines achieves a prefetch performance less than a second threshold value.
18. The system of claim 16 , wherein both of the first and second prefetch engines are deallocated if neither of the first or second prefetch engines achieves a prefetch performance greater than the first threshold value.
19. The system of claim 16 , wherein the program stream further comprises multiple iterations of a second load instruction and wherein:
a third prefetch engine from the first plurality of prefetch engines is allocated to the second load instruction in response to a buffer miss of an iteration of the second load instruction in the program stream;
a fourth prefetch engine from the second plurality of prefetch engines is allocated to the second load instruction in response to the buffer miss of the iteration of the second load instruction; and
one of the third or fourth prefetch engines is deallocated if the other of the third or fourth prefetch engines achieves a prefetch performance greater than the first threshold value.
20. The system of claim 16 , wherein the buffer comprises a level 1 cache.