Prefetching data

• US 10,810,125 B2
• Filed: 02/22/2016
• Issued: 10/20/2020
• Est. Priority Date: 12/15/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: El-Mahdy, Ahmed H., ElShishiny, Hisham Emadeldin
• Primary Examiner(s): MacKall, Larry T
• Application Number:
  US15/049,830
• Publication Number:
  US 20160246725A1
• Time in Patent Office: 1,702 Days
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 2212/6028 Prefetching based on hints or prefetch instructions

Abstract

A prefetch controller is configured to communicate with a prefetch cache in order to increase system performance. The prefetch controller includes an instruction lookup table (ILT) configured to receive a first tuple including a first instruction ID and a first missed data address. The prefetch controller further includes a tuple history queue (THQ) configured to receive an instruction/stride tuple, the instruction/stride tuple generated by subtracting a last data access address from the first missed data address. The prefetch controller further includes a sequence prediction table (SPT) in communication with the tuple history queue (THQ) and the instruction lookup table. The prefetch controller includes an adder in communication with the instruction lookup table (ILT) and the sequence prediction table (SPT) configured to generate a predicted prefetch address and to provide the predicted prefetch address to a prefetch cache.

Claims

1. A computer hardware system, comprising:

a data cache;

a prefetch controller configured to

receive an initial tuple including an initial instruction ID and an initial missed data address,

retrieve a last data access address,

subtract the last data access address from the initial missed data address to generate an instruction/stride tuple,

generate a predicted prefetch address using the instruction/stride tuple; and

a prefetch cache configured to

receive, from the prefetch controller, the predicted prefetch address, and

provide, to the data cache, the predicted prefetch address.

2. The system of claim 1, wherein

the prefetch controller includes a tuple history queue (THQ) configured to receive and store the instruction/stride tuple.

3. The system of claim 2, wherein

the prefetch controller includes a sequence prediction table (SPT) configured to receive at least one of a current tuple and current sequence from the tuple history queue (THQ).

4. The system of claim 3, wherein

the prefetch controller includes an instruction lookup table (ILT) in communication with the sequence prediction table (SPT) and configured to store a last data address accessed for each tuple.

5. The system of claim 3, wherein

the sequence prediction table (SPT) is configured to search for a match for the current sequence.

6. The system of claim 5, wherein

the sequence prediction table (SPT) is configured to increment a next tuple count if the match for the current sequence is located.

7. The system of claim 4, wherein

the predicted prefetch address is generated by adding a predicted tuple having a stride data address from the sequence prediction table (SPT) with a last data address obtained from the instruction lookup table (ILT).

8. A computer-implemented method, comprising:

receiving, by a prefetch controller, an initial tuple including an initial instruction ID and an initial missed data address;

retrieving, by the prefetch controller, a last data access address;

subtracting, by the prefetch controller, the last data access address from the initial missed data address to generate an instruction/stride tuple;

generating, by the prefetch controller, a predicted prefetch address using the instruction/stride tuple;

receiving, by a prefetch cache and from the prefetch controller, the predicted prefetch address, and

providing, to the data cache and by the prefect cache, the predicted prefetch address.

9. The method of claim 8, wherein

the prefetch controller includes a tuple history queue (THQ) configured to receive and store the instruction/stride tuple.

10. The method of claim 9, wherein

the prefetch controller includes a sequence prediction table (SPT) configured to receive at least one of a current tuple and current sequence from the tuple history queue (THQ).

11. The method of claim 10, wherein

the prefetch controller includes an instruction lookup table (ILT) in communication with the sequence prediction table (SPT) and configured to store a last data address accessed for each tuple.

12. The method of claim 10, wherein

the sequence prediction table (SPT) is configured to search for a match for the current sequence.

13. The method of claim 12, wherein

the sequence prediction table (SPT) is configured to increment a next tuple count if the match for the current sequence is located.

14. The method of claim 11, wherein

the predicted prefetch address is generated by adding a predicted tuple having a stride data address from the sequence prediction table (SPT) with a last data address obtained from the instruction lookup table (ILT).

15. A prefetch controller within a computer hardware system including a data cache and a prefetch cache, comprising:

an instruction lookup table (ILT) configured to receive an initial tuple including an initial instruction ID and an initial missed data address;

a tuple history queue (THQ) configured to receive an instruction/stride tuple generated by subtracting a last data access address from the initial missed data address;

a sequence prediction table (SPT) in communication with the instruction lookup table (ILT) and the tuple history queue (THQ);

an adder in communication with the instruction lookup table (ILT) and sequence prediction table (SPT) and configured to

generate a predicted prefetch address using the instruction/stride tuple, and

provide, to the prefetch cache, the predicted prefetch address, wherein

the prefetch cache is configured to provide, to the data cache, the predicted prefetch address.

16. The prefetch controller of claim 15, wherein

the tuple history queue (THQ) is configured to store the instruction/stride tuple and provide access for the sequence prediction table (SPT).

17. The prefetch controller of claim 16, wherein

the sequence prediction table (SPT) configured to receive at least one of a current tuple and current sequence from the tuple history queue (THQ).

18. The prefetch controller of claim 17, wherein

the instruction lookup table (ILT) is configured to store a last data address accessed for each tuple.

19. The prefetch controller of claim 17, wherein

the sequence prediction table (SPT) is configured to search for a match for the current sequence.

20. The prefetch controller of claim 19, wherein

the sequence prediction table (SPT) is configured to increment a next tuple count if the match for the current sequence is located.