Microprocessor circuits, systems, and methods implementing a load target buffer with entries relating to prefetch desirability

• US 6,216,219 B1
• Filed: 12/30/1997
• Issued: 04/10/2001
• Est. Priority Date: 12/31/1996
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Cai, George Z. N., Shiell, Jonathan H.
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US09/000,937
• Time in Patent Office: 1,197 Days
• Field of Search: 712/207, 712/237
• US Class Current: 712/207
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 9/3455 using stride
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers

Abstract

A microprocessor (12) comprising a memory system (20) for outputting data in response to an address, wherein the memory system is further operable to receive a prefetch request having a predicted target data address. The microprocessor further includes a load target circuit (56 or 112), which comprises a first plurality of entries (116) of a first length and a second plurality of entries (114) of a second length. Each of the first plurality of entries comprises a value (ADDRESS TAG) for corresponding the entry to a corresponding first plurality of data fetching instructions. Further, each of the first plurality of entries further comprises a value (POINTER A) for indicating a corresponding predicted target data address. Each of the second plurality of entries also comprises a value (ADDRESS TAG) for corresponding each of the second plurality of entries to a corresponding second plurality of data fetching instructions. However, each of the second plurality of data fetching instructions is of a type for which it is undesirable to issue a prefetch request.

Claims

1. A microprocessor, comprising:

a memory system for outputting data in response to an address, wherein the memory system is further operable to receive a prefetch request having a predicted target data address; and

a load target circuit connected to said memory system for generating said predicted target data address, comprising;

a first plurality of entries of a first length, wherein each of the first plurality of entries comprises;

a first address tag for indicating a memory address of a corresponding one of a first plurality of data fetching instructions; and

first prediction information for indicating a corresponding predicted target data address;

a second plurality of entries of a second length different than the first length, wherein each of the second plurality of entries comprises a second address tag for indicating a memory address of a corresponding one of a second plurality of data fetching instructions;

said load target circuit operative to compare a corresponding memory address of a decoded data fetching instruction with each first address tag and with each second address tag;

said load target circuit operative to issue a prefetch request to said memory system for data at a corresponding predicted target data address upon a match of said memory address of a decoded data fetching instruction and one of said first address tags; and

said load target circuit operative to inhibit issue of a prefetch request to said memory system upon a match of said memory address of a decoded data fetching instruction and one of said second address tags.

2. The microprocessor of claim 1:

wherein the first prediction information enables prediction of target data addresses for each of the first plurality of data fetching instructions according to a first data pattern;

and further comprising a third plurality of entries;

wherein each of the third plurality of entries comprises a third address tag for indicating a corresponding one of a third plurality of data fetching instructions and second prediction information;

wherein the second prediction information enables prediction of target data addresses for each of the third plurality of data fetching instructions according to a second data pattern.

3. The load target circuit of claim 2:

wherein each of the first plurality of data fetching instructions is predicted to have a looping pattern such that, for each of the first plurality of data fetching instructions, the corresponding target data address advances from a first target data address through at least one intermediate address to a last target data address and back to the first target data address

wherein each of the third plurality of data fetching instructions is predicted to have a striding pattern followed by a looping pattern;

wherein the striding pattern is such that, for each of the third plurality of data fetching instructions, the corresponding target data address advances from a first target data address through a plurality of additional target data addresses, wherein the data target address of each of the plurality of additional target data addresses has a stride length as the difference between itself and a data target address of an immediately preceding target data address; and

wherein the looping pattern following the striding pattern is such that, for each of the third plurality of data fetching instructions, the corresponding target data address advances from a first target data address through at least one intermediate address to a last target data address and back to the first target data address.

4. The microprocessor of claim 3:

wherein the second plurality of entries greater are greater in number than the first plurality of entries; and

wherein the first plurality of entries greater are greater in number than the third plurality of entries.

5. The microprocessor of claim 2:

wherein the second plurality of entries are greater in number than the first plurality of entries; and

wherein the second plurality of entries are greater in number than the third plurality of entries.

6. The microprocessor of claim 1 wherein the second plurality of entries are greater in number than the first plurality of entries.

7. The microprocessor of claim 1 further comprising:

a data fetching execution unit operative to compute a target data address and fetch data from said memory system at said target data address in response to a data fetching instruction;

wherein said load target circuit is operative to compare each target data address with a corresponding predicted target data address; and

wherein each of the first plurality of entries further comprises a past predicted address accuracy portion storing a value indicating a past predicted accuracy of the corresponding predicted target data address computed from a history of results of said comparisons of said predicted target data address and said corresponding target data address.

8. The microprocessor of claim 7:

wherein said past predicted address portion storing said value indicating a past predicted accuracy comprises a counter;

wherein the counter advances in a first direction in response to detection of a match upon comparing a target data address with the corresponding predicted target data address; and

wherein the counter advances in a second direction opposite the first direction in response to detection of a nonmatch upon comparing a target data address with the corresponding predicted target data address.

9. The microprocessor of claim 7:

wherein said past predicted address portion storing said value indicating a past predicted accuracy comprises a series of binary indicators; and

wherein each of the binary indicators in the series reflects detection of a match or a nonmatch upon comparing a target data address with the predicted target data address over a corresponding series of past incidents of the data fetching instruction corresponding to the entry.

10. The microprocessor of claim 1 wherein:

said memory system includes a bus interface unit to an external memory and a cache memory;

a data fetching execution unit operative to compute a target data address and fetch data from said memory system at said target data address in response to a data fetching instruction;

wherein said load target circuit is operative to detect whether each data fetching instruction generates a cache hit or a cache miss; and

wherein each of the first plurality of entries further comprises a past prefetch usefulness value for indicating whether at least one prior past incident of the data fetching instruction corresponding to the entry generated a cache hit or a cache miss.

11. The microprocessor of claim 10:

wherein the past prefetch usefulness value comprises a counter;

wherein the counter advances in a first direction in response to detecting that a prior past incident of the data fetching instruction generated a cache hit; and

wherein the counter advances in a second direction opposite the first direction in response to detecting that a prior past incident of the data fetching instruction generated a cache miss.

12. The microprocessor of claim 10:

wherein the past prefetch usefulness value comprises a series of binary indicators; and

wherein each of the binary indicators in the series reflects whether a prior past incident of the data fetching instruction generated a cache hit or a cache miss.

13. The microprocessor of claim 1 wherein the first length is greater than the second length.

14. The microprocessor of claim 1 wherein the data fetching instruction is a load instruction.

15. The microprocessor of claim 1 wherein the data fetching instruction is a store instruction.

16. A microprocessor, comprising:

a memory system for outputting data in response to an address, wherein the memory system is further operable to receive a prefetch request having a predicted target data address;

a data fetching execution unit operative to compute a target data address and fetch data from said memory system at said target data address in response to a data fetching instruction;

a load target circuit connected to said memory system for generating said predicted target data address, operative to compare each target data address with a corresponding predicted target data address, and comprising a plurality of entries, wherein each of the plurality of entries comprises;

an address tag indicating a memory address of a corresponding data fetching instruction;

a pointer indicating a corresponding predicted target data address; and

a past predicted address accuracy portion storing a value indicating a past predicted accuracy of the corresponding predicted target data address computed from a history of results of said comparisons of said predicted target data address and said corresponding target data address;

said load target circuit operative to compare a corresponding memory address of a decoded data fetching instruction with each address tag; and

said load target circuit operative to issue a prefetch request to said memory system for data at a corresponding predicted target data address upon a match of said memory address of a decoded data fetching instruction and said address tag of one of said entries.

17. The microprocessor of claim 16:

wherein said past predicted address portion storing said value indicating a past predicted accuracy comprises a counter;

wherein the counter advances in a first direction in response to detection of a match upon comparing a target data address with the corresponding predicted target data address; and

wherein the counter advances in a second direction opposite the first direction in response to detection of a nonmatch upon comparing a target data address with the corresponding predicted target data address.

18. The microprocessor of claim 16:

wherein said past predicted address portion storing said value indicating a past predicted accuracy comprises a series of binary indicators; and

wherein each of the binary indicators in the series reflects detection of a match or a nonmatch upon comparing a target data address with the predicted target data address over a corresponding series of past incidents of the data fetching instruction corresponding to the entry.

19. The microprocessor of claim 16 wherein:

said memory system includes a bus interface unit to an external memory and a cache memory;

wherein said load target circuit is operative to detect whether each data fetching instruction generates a cache hit or a cache miss; and

wherein each of the first plurality of entries further comprises a past prefetch usefulness value for indicating whether a prior past incident of the data fetching instruction corresponding to the entry generated a cache hit.

20. The microprocessor of claim 19:

wherein the past prefetch usefulness value comprises a counter;

wherein the counter advances in a first direction in response to detecting that a prior past incident of the data fetching instruction generated a cache hit; and

wherein the counter advances in a second direction opposite the first direction in response to detecting that a prior past incident of the data fetching instruction generated a cache miss.

21. The microprocessor of claim 19:

wherein the past prefetch usefulness value comprises a series of binary indicators; and

wherein each of the binary indicators in the series reflects whether a prior past incident of the data fetching instruction generated a cache hit or a cache miss.

22. A microprocessor, comprising:

a memory system for outputting data in response to an address, wherein the memory system is further operable to receive a prefetch request having a predicted target data address, said memory system including a bus interface unit connected to an external memory and a cache memory;

a data fetching execution unit operative to compute a target data address and to fetch data from said memory system at said target data address in response to a data fetching instruction;

a load target circuit operative to detect whether each data fetching instruction generates a cache hit or a cache miss, said load target buffer comprising a plurality of entries, wherein each of the plurality of entries comprises;

an address tag for indicating a memory address of a corresponding data fetching instruction;

a pointer for indicating a corresponding predicted target data address; and

a past prefetch usefulness value indicating whether at least one prior past incident of the data fetching instruction corresponding to the entry generated a cache hit or a cache miss;

said load target circuit operative to compare a corresponding memory address of a decoded data fetching instruction with each address tag; and

said load target circuit operative to issue a prefetch request to said memory system for data at a corresponding predicted target data address upon a match of said memory address of a decoded data fetching instruction and said address tag of one of said entries.

23. The microprocessor of claim 22:

wherein the past prefetch usefulness value comprises a counter;

wherein the counter advances in a first direction in response to detecting that a prior past incident of the data fetching instruction generated a cache hit; and

wherein the counter advances in a second direction opposite the first direction in response to detecting that a prior past incident of the data fetching instruction generated a cache miss.

24. The microprocessor of claim 22:

wherein the past prefetch usefulness value comprises a series of binary indicators; and

wherein each of the binary indicators in the series reflects whether a prior past incident of the data fetching instruction generated a cache hit or a cache miss.

25. A method of operating a microprocessor having an instruction pipeline and a load target buffer, comprising the steps of:

storing a plurality of entries in the load target buffer, each entry including an address tag, target data address prediction information and an indication of past prediction accuracy;

receiving a data fetching instruction in the instruction pipeline, wherein the data fetching instruction has a corresponding memory address;

upon a data fetching instruction reaching a predetermined stage in the instruction pipeline comparing a memory address of the data fetching instructions with an address tag of each entry in the load target buffer;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer;

generating a prefetch request to a memory system at an address calculated from the target address prediction information;

updating the indication of past prediction accuracy to indicate more accurate past prediction; and

if the memory address of a data fetching instruction does not match the address tags of any entry in the load target buffer;

identifying a group of entries in the load target buffer on the microprocessor, wherein the identified group is a group in which target data address prediction information corresponding to the received data fetching instruction may be stored based on the corresponding memory address;

identifying a least recently used entry from the identified group of entries;

in response to the value for indicating a past predicted accuracy falling below a predetermined threshold, overwriting the identified entry with target data address prediction information corresponding to the received data fetching instruction;

updating the indication of past prediction accuracy to indicate less accurate past prediction; and

upon a data fetching instruction reaching a second predetermined state in the instruction pipeline computing a target data address; and

fetching data from said memory system at said target data address in response to a data fetching instruction.

26. A method of operating a microprocessor having, a cache memory, an instruction pipeline and a load target buffer, comprising the steps of:

storing a plurality of entries in the load target buffer, each entry including an address tag, target data address prediction information and an indication of past prediction usefulness;

receiving a data fetching instruction in the instruction pipeline, wherein the data fetching instruction has a corresponding memory address;

upon a data fetching instruction reaching a first predetermined stage in the instruction pipeline comparing a memory address of the data fetching instructions with an address tag of each entry in the load target buffer;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer;

generating a prefetch request to a memory system at an address calculated from the target address prediction information; and

if the memory address of a data fetching instruction does not match the address tag of any entry in the load target buffer;

identifying a group of entries in the load target buffer on the microprocessor, wherein the identified group is a group in which target data address prediction information corresponding to the received data fetching instruction may be stored based on the corresponding memory address;

identifying a least recently used entry from the identified group of entries;

in response to the indication of past prefetch usefulness falling below a predetermined threshold, overwriting the identified entry with target data address prediction information corresponding to the received data fetching instruction; and

upon a data fetching instruction reaching a second predetermined state in the instruction pipeline;

computing a target data address;

fetching data from said memory system at said target data address in response to a data fetching instruction;

detecting whether each data fetching instruction generates a cache hit or a cache miss; and

updating the indication of past prefetch usefulness to indicate more usefulness upon a cache hit and to indicate less usefulness upon a cache miss.

27. A method of operating a microprocessor having, a cache memory, an instruction pipeline and a load target buffer, comprising the steps of:

storing a plurality of entries in the load target buffer, each entry including an address tag, target data address prediction information, an indication of past prediction accuracy and an indication of past prediction usefulness;

receiving a data fetching instruction in the instruction pipeline, wherein the data fetching instruction has a corresponding memory address;

upon a data fetching instruction reaching a first predetermined stage in the instruction pipeline comparing a memory address of the data fetching instructions with an address tag of each entry in the load target buffer;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer;

generating a prefetch request to a memory system at an address calculated from the target address prediction information;

updating the indication of past prediction accuracy to indicate more accurate past prediction; and

if the memory address of a data fetching instruction does not match the address tags of any entry in the load target buffer;

identifying a group of entries in the load target buffer on the microprocessor, wherein the identified group is a group in which target data address prediction information corresponding to the received data fetching instruction may be stored based on the corresponding memory address;

identifying a least recently used entry from the identified group of entries;

updating the indication of past prediction accuracy to indicate less accurate past prediction;

in response to a combination of the value for indicating a past predicted accuracy combined with the past prefetch usefulness value falling below a predetermined threshold, overwriting the identified entry with target data address prediction information corresponding to the received data fetching instruction; and

upon a data fetching instruction reaching a second predetermined state in the instruction pipeline;

computing a target data address;

fetching data from said memory system at said target data address in response to a data fetching instruction;

detecting whether each data fetching instruction generates a cache hit or a cache miss; and

updating the indication of past prefetch usefulness to indicate more usefulness upon a cache hit and to indicate less usefulness upon a cache miss.

28. A method of operating a microprocessor having an instruction pipeline and a load target buffer, comprising the steps of:

storing a plurality of entries in the load target buffer, each entry including an address tag, target data address prediction information and an indication of past prediction accuracy;

receiving a data fetching instruction in the instruction pipeline, wherein the data fetching instruction has a corresponding memory address;

upon a data fetching instruction reaching a first predetermined stage in the instruction pipeline comparing a memory address of the data fetching instructions with an address tag of each entry in the load target buffer;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer;

generating a prefetch request to a memory system at an address calculated from the target address prediction information;

updating the indication of past prediction accuracy to indicate more accurate past prediction; and

if the memory address of a data fetching instruction does not match the address tags of any entry in the load target buffer;

identifying a group of entries in the load target buffer on the microprocessor, wherein the identified group is a group in which target data address prediction information corresponding to the received data fetching instruction may be stored based on the corresponding memory address;

identifying a particular entry from the identified group of entries;

in response to the value for indicating a past predicted accuracy falling below a predetermined threshold, overwriting the identified entry with target data address prediction information corresponding to the received data fetching instruction;

updating the indication of past prediction accuracy to indicate less accurate past prediction;

upon a data fetching instruction reaching a second predetermined state in the instruction pipeline;

computing a target data address; and

fetching data from said memory system at said target data address in response to a data fetching instruction.

29. A method of operating a microprocessor having, a cache memory, a n instruction pipeline and a load target buffer, comprising the steps of:

storing a plurality of entries in the load target buffer, each entry including an address tag, target data address prediction information and an indication of past prediction usefulness;

receiving a data fetching instruction in the instruction pipeline, wherein the data fetching instruction has a corresponding memory address;

upon a data fetching instruction reaching a first predetermined stage in the instruction pipeline comparing a memory address of the data fetching instructions with an address tag of each entry in the load target buffer;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer;

generating a prefetch request to a memory system at an address calculated from the target address prediction information and

if the memory address of a data fetching instruction does not match the address tag of any entry in the load target buffer;

identifying a group of entries in the load target buffer on the microprocessor, wherein the identified group is a group in which target data address prediction information corresponding to the received data fetching instruction may be stored based on the corresponding memory address;

identifying a least recently used entry from the identified group of entries;

in response to the indication of past prefetch usefulness falling below a predetermined threshold, overwriting the identified entry with target data address prediction information corresponding to the received data fetching instruction; and

upon a data fetching instruction reaching a second predetermined state in the instruction pipeline;

computing a target data address;

fetching data from said memory system at said target data address in response to a data fetching instruction;

detecting whether each data fetching instruction generates a cache hit or a cache miss; and

updating the indication of past prefetch usefulness to indicate more usefulness upon a cache hit and to indicate less usefulness upon a cache miss.

30. A method of operating a microprocessor having, a cache memory, an instruction pipeline and a load target buffer, comprising the steps of:

storing a plurality of entries in the load target buffer, each entry including an address tag, target data address prediction information, an indication of past prediction accuracy and an indication of past prediction usefulness;

receiving a data fetching instruction in the instruction pipeline, wherein the data fetching instruction has a corresponding memory address;

upon a data fetching instruction reaching a first predetermined stage in the instruction pipeline comparing a memory address of the data fetching instructions with an address tag of each entry in the load target buffer;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer;

generating a prefetch request to a memory system at an address calculated from the target address prediction information;

updating the indication of past prediction accuracy to indicate more accurate past prediction; and

if the memory address of a data fetching instruction does not match the address tags of any entry in the load target buffer;

identifying a group of entries in the load target buffer on the microprocessor, wherein the identified group is a group in which target data address prediction information corresponding to the received data fetching instruction may be stored based on the corresponding memory address;

identifying a particular entry from the identified group of entries;

updating the indication of past prediction accuracy to indicate less accurate past prediction;

in response to a combination of the value for indicating a past predicted accuracy combined with the past prefetch usefulness value falling below a predetermined threshold, overwriting the identified entry with target data address prediction information corresponding to the received data fetching instruction; and

upon a data fetching instruction reaching a second predetermined state in the instruction pipeline;

computing a target data address;

fetching data from said memory system at said target data address in response to a data fetching instruction;

detecting whether each data fetching instruction generates a cache hit or a cache miss; and

updating the indication of past prefetch usefulness to indicate more usefulness upon a cache hit and to indicate less usefulness upon a cache miss.

31. A method of operating a microprocessor having an instruction pipeline and a load target buffer, comprising the steps of:

storing a plurality of entries in the load target buffer, each entry including an address tag, a plurality of address pointers each storing a corresponding target data address and an indication of a next address pointer;

receiving a data fetching instruction in the instruction pipeline, wherein the data fetching instruction has a corresponding memory address;

upon a data fetching instruction reaching a first predetermined stage in the instruction pipeline comparing a memory address of the data fetching instructions with an address tag of each entry in the load target buffer;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer;

generating a prefetch request to a memory system at an address corresponding to the target data address stored in the address pointer indicated by the indication of a next address pointer; and

updating the indication of a next address pointer to indicate a next address pointer in a circular sequence of the plurality of address pointers;

upon a data fetching instruction reaching a second predetermined state in the instruction pipeline;

computing a target data address; and

fetching data from said memory system at said target data address.

32. A method of operating a microprocessor having an instruction pipeline and a load target buffer, comprising the steps of:

storing a plurality of entries in the load target buffer, each entry including an address tag, a plurality of address pointers each storing a corresponding target data address, an indication of a next address pointer, a mode indicator indicating a looping mode or a striding/looping mode, a stride length, a stride threshold and a stride counter;

receiving a data fetching instruction in the instruction pipeline, wherein the data fetching instruction has a corresponding memory address;

upon a data fetching instruction reaching a first predetermined stage in the instruction pipeline comparing a memory address of the data fetching instructions with an address tag of each entry in the load target buffer;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer and the mode indicator indicates a looping mode;

generating a prefetch request to a memory system at an address corresponding to the target data address stored in the address pointer indicated by the indication of a next address pointer; and

updating the indication of a next address pointer to indicate a next address pointer in a circular sequence of the plurality of address pointers;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer and the mode indicator indicates a striding/looping mode and the stride counter is zero;

initializing the stride counter with the stride threshold;

generating a prefetch request to the memory system at an address corresponding to the target data address stored in the address pointer indicated by the indication of a next address pointer;

adding the stride length to the address pointer indicated by the indication of a next address pointer;

decrementing the stride counter; and

if the stride counter has decremented to zero restoring the address pointer to an initial value and updating the indication of a next address pointer to indicate a next address pointer in a circular sequence of the plurality of address pointers;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer and the mode indicator indicates a striding/looping mode and the stride counter is not zero;

generating a prefetch request to the memory system at an address corresponding to the target data address stored in the address pointer indicated by the indication of a next address pointer;

adding the stride length to the address pointer indicated by the indication of a next address pointer;

decrementing the stride counter; and

if the stride counter has decremented to zero restoring the address pointer to an initial value and updating the indication of a next address pointer to indicate a next address pointer in a circular sequence of the plurality of address pointers;

upon a data fetching instruction reaching a second predetermined state in the instruction pipeline;

computing a target data address; and

fetching data from said memory system at said target data address.

33. A method of operating a microprocessor having an instruction pipeline, a cache memory and a load target buffer, comprising the steps of:

storing a plurality of entries in the load target buffer, each entry including an address tag and target data address prediction information;

receiving a data fetching instruction in the instruction pipeline, wherein the data fetching instruction has a corresponding memory address;

upon a data fetching instruction reaching a first predetermined stage in the instruction pipeline comparing a memory address of the data fetching instructions with an address tag of each entry in the load target buffer;

if the memory address of a data fetching instruction matches the address tag of an entry in the load target buffer

generating a prefetch request to the cache memory at an address corresponding to the target data address stored in the address pointer indicated by the indication of a next address pointer;

determining if data at the target data address is stored in the cache memory; and

if the data at the target data address is not stored in the cache memory initiating a cache line fill operation from a higher level memory;

upon a data fetching instruction reaching a second predetermined state in the instruction pipeline;

computing a target data address; and

fetching data from said memory system at said target data address.

34. The method of claim 33, further comprising the steps of:

inhibiting generation of a data prefetch if a predicted target data address occupies the same cache line as the predicted target data address of prior prefetch request.