Processor and method of prefetching data based upon a detected stride

• US 6,430,680 B1
• Filed: 03/31/1998
• Issued: 08/06/2002
• Est. Priority Date: 03/31/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Burky, William Elton, Tung, Shih-Hsiung Stephen, Vaden, Michael Thomas, Schroter, David Andrew
• Primary Examiner(s): Ellis, Richard L.
• Application Number:
  US09/052,567
• Time in Patent Office: 1,589 Days
• Field of Search: 712/225, 712/241, 711/137, 711/213
• US Class Current: 712/225
• CPC Class Codes: G06F 9/3455 using stride
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers

Abstract

A processor and method of fetching data within a data processing system are disclosed. According to the method, a first difference between a first load address and a second load address is calculated. In addition, a determination is made whether a second difference between a third load address and the second load address is equal to the first difference. In response to a determination that the first difference and the second difference are equal, a fourth load address, which is generated by adding the third address and the second difference, is transmitted to the memory as a memory fetch address. In an embodiment of the data processing system including a processor having an associated cache, the fourth load address is transmitted to the memory only if the fourth load address is not resident in the cache or the target of an outstanding memory fetch request.

Claims

1. A method within a data processing system including a processor and a memory for generating a load address, said method comprising:

storing at least a portion of a first instruction address of a first load instruction;

determining a first difference between a first load target address and a second load target address;

determining a second difference between said second load target address and a third load target address, said third load target address having a second instruction address associated therewith;

generating a fourth load target address in response to comparing said first and second differences; and

supplying said fourth load target address to the memory as a memory request address if a program loop is detected by comparison of said second instruction address and said at least said portion of said first instruction address, wherein said memory is an upper level memory and said data processing system further includes a lower level memory, said supplying step comprising transmitting said fourth load target address to said lower level memory only if data associated with said fourth load target address is neither resident in said upper level memory nor a target of an outstanding memory fetch request transmitted to said lower level memory.

2. The method of claim 1, wherein said first and second differences are equal and a third difference between said third load target address and said fourth load target address is equal to said first and second differences.

3. The method of claim 1, and further comprising:

executing one or more load instructions to compute said fist, second, and third load target addresses.

4. The method of claim 1, and further comprising storing at least said first and said second load target addresses in a load address queue.

5. The method of claim 1, wherein said supplying step comprises transmitting said fourth load target address from said processor to said memory as a memory request address.

6. The method of claim 1, wherein said supplying is performed only if a program loop is detected.

7. A data processing system, comprising:

an upper level memory and a lower level memory;

means for storing at least a portion of a first instruction address of a first load instruction;

means for determining a first difference between a first load target address and a second load target address;

means for determining a second difference between said second load target address and a third load target address, said third load target address having a second instruction address associated therewith;

means for generating a fourth load target address in response to comparing said first and second differences;

means for comparing said second instruction address and said at least said portion of said first instruction address to detect a program loop; and

means for supplying said fourth load target address to the upper level memory as a memory request address if a program loop is detected, said means for supplying comprising means for transmitting said fourth load target address to said lower level memory only if data associated with said fourth load target address is neither resident in said upper level memory nor a target of an outstanding memory fetch request transmitted to said lower level memory.

8. The data processing system of claim 7, wherein said first and second differences are equal, said means for generating a fourth load target address comprising means for generating a fourth load target address such that a third difference between said third load target address and said fourth load target address is equal to said first and second differences.

9. The data processing system of claim 7, and further comprising means for executing one or more load instructions to compute said first, second, and third load target addresses.

10. The data processing system of claim 7, and further comprising means for storing said at least said first and second load target addresses.

11. The data processing system of claim 7, wherein said means for supplying comprises means for transmitting said fourth load target address from a processor to said memory as a memory request address.

12. The data processing system of claim 7, wherein said means for supplying supplies said fourth load target address to the memory as a memory request address only if a program loop is detected.

13. A processor having an associated upper level memory and a lower level memory, said processor comprising:

a load-store unit that executes one or more load instructions to produce at least first, second, and third load target addresses, wherein said third load address has a second instruction address associated therewith;

an instruction address queue that stores at least a portion of a first instruction address of an executed first load instruction;

a difference circuitry that determines a first difference between said first load target address and said second load target address and determines a second difference between said third load target address and said second load target address;

address generation circuitry that generates a fourth load target address in response to a comparison of said first and said second differences; and

loop detection circuitry that compares said second instruction address and said at least said portion of said first instruction address to detect a program loop; and

logic circuitry that supplies said fourth load target address to a memory as a memory request address if a program loop is detected by said loop detection circuitry, wherein said logic circuitry supplies said fourth load target address to said lower level memory only if data associated with said fourth load target address is neither resident in said upper level memory nor a target of an outstanding memory fetch request transmitted to said lower level memory.

14. The processor of claim 13, and further comprising a load target address queue capable of storing at least said first and second load target addresses.

15. The processor of claim 13, wherein said address generation circuitry generates said fourth load target address in response to said comparison indicating that said first difference and said second difference are equal.

16. The processor of claim 13, wherein said logic circuitry supplies said fourth load target address to the memory as a memory request address only if a program loop is detected.