Smart-prefetch

• US 6,981,099 B2
• Filed: 12/16/2002
• Issued: 12/27/2005
• Est. Priority Date: 12/16/2002
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Paulraj, Dominic A., Goil, Sanjay
• Primary Examiner(s): Bataille, Pierre-Michel
• Assistant Examiner(s): TSAI, SHENG JEN
• Application Number:
  US10/320,284
• Publication Number:
  US 20040117557A1
• Time in Patent Office: 1,107 Days
• Field of Search: 711/137, 711/113, 711/123, 711/125, 711/126
• US Class Current: 711/137
• CPC Class Codes: G06F 9/345 of multiple operands or results addressing multiple banks G06F12/06
• CPC Class Codes: G06F 9/3455 using stride
• CPC Class Codes: G06F 9/3555 using scaling, e.g. multiplication of index
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862

Abstract

A method and system for the smart prefetching of instructions is disclosed. The method includes computing an effective memory latency of a request for data and using the effective memory latency to compute an effective address from which to prefetch data.

Claims

1. A method comprising:

computing an effective memory latency of a system;

using said effective memory latency to compute an effective address from which to prefetch data; and

,

performing a “

work in the loop”

(WL) computation to generate a smart prefetch request.

2. The method of claim 1, wherein said computing said effective memory latency is done during the execution of a computer program on said system.

3. The method of claim 2, further comprising:

notifying a processor of a load stream in memory, wherein said load stream defines data which is prefetchable; and

providing said processor with an address of said load stream.

4. The method of claim 3 further comprising:

generating a smart-prefetch instruction for said load stream, wherein said notifying and said providing are accomplished with said smart-prefetch instruction.

5. The method of claim 4, further comprising:

identifying said load stream in a computer program, the data of said load stream is accessed by a sequence of memory reads at dynamically determined intervals.

6. The method of claim 5, wherein said generating said smart-prefetch instruction comprises:

generating a load instruction for data in said load stream; and

including an identifier in said load instruction to notify said processor that said data is prefetchable.

7. The method of claim 4 further comprising:

during the execution of said computer program, generating the smart-prefetch request from said smart-prefetch instruction; and

updating said smart prefetch request with said effective memory latency.

11. The method of claim 3, further comprising:

computing the distance between address of consecutive requests for data within said load stream to define a memory stride.

12. The method of claim 11, further comprising:

if the memory stride is greater than a cache line size, issuing a prefetch during every iteration of a loop to access data in said load stream.

13. The method of claim 11, further comprising:

if the memory stride is less than a cache line size, preventing the issuance of multiple prefetches for the same cache line.

14. The method of claim 1, further comprising:

prefetching data from said effective address into a buffer; and

satisfying cache misses using data from said buffer.

8. A method comprising:

computing an effective memory latency of a system, said computing said effective memory latency is done during the execution of a computer program on said system;

using said effective memory latency to compute an effective address from which to prefetch data;

notifying a processor of a load stream in memory, wherein said load stream defines data which is prefetchable;

providing said processor with an address of said load stream;

generating a smart-prefetch instruction for said load stream, wherein said notifying and

said providing are accomplished with said smart-prefetch instruction;

during the execution of said computer program, generating a smart-prefetch request from said smart-prefetch instruction; and

updating said smart prefetch request with said effective memory latency;

computing a time between consecutive requests of data in said load stream to define a “

work in the loop”

(WL); and

updating said smart prefetch request with said WL.

9. The method of claim 8, further comprising:

computing an ahead distance by dividing said effective memory latency by said WL; and

computing said effective address by adding a current effective address with the product of said ahead distance and a cache line size.

10. The method of claim 9, further comprising:

updating a load miss buffer with said effective address.

15. A system, comprising:

a memory;

a processor coupled to said memory, said processor comprising a smart-prefetch unit configured to use a run-time memory latency to compute an effective address from which to prefetch data, said smart-prefetch unit comprising a “

work in the loop”

(WL) computation module.

16. The system of claim 15, wherein said smart-prefetch unit comprises:

an effective memory latency computation module configured to compute a time interval between a memory request for data and an arrival of said data by said processor.

17. The system of claim 15, wherein said smart-prefetch unit further comprises:

an ahead distance computation module.

18. The system of claim 17, wherein said smart-prefetch unit further comprises:

an ahead distance computation module.

19. The system of claim 18, wherein:

said effective memory address computation module is configured to compute a time interval between a memory request for data and an arrival of said data by said processor;

said WL computation module is configured to compute a time between two consecutive prefetches executed for a smart-prefetch request issued by said processor;

said ahead distance computation module is configured to compute a ratio of said time interval computed by said effective memory address computation module to said time between two consecutive smart-prefetches computed by said work in the loop computation module; and

said effective address computation module is configured to sum a current effective address with the product of said ratio and a cache line size.

20. The system of claim 16, said smart-prefetch unit further comprising:

a process module, said process module configured to generate a smart-prefetch request from a smart-prefetch instruction.

21. The system of claim 20, said smart-prefetch unit further comprising:

a prefetch computation module, said prefetch computation module configured to compute said effective address.

22. The system of claim 21, further comprising:

a buffer configured to store a plurality of smart-prefetch requests.

23. A system, comprising:

a memory;

a processor coupled to said memory, said processor comprising a smart-prefetch unit configured to use a run-time memory latency to compute an effective address from which to prefetch data, the smart-prefetch unit including a work in the loop computation module;

means for computing a time interval between a memory request for data and an arrival of said data by said processor;

means for computing a time between two consecutive prefetches executed for a smart-prefetch request issued by said processor;

means for computing a ratio of said time interval computed by said effective memory latency computation module to said time between two consecutive smart-prefetches computed by said work in the loop computation module; and

means for adding a current effective address with the product of said ratio and a cache line size to define an effective address from which to prefetch data.

24. A computer program product encoded in computer readable media, said computer program product comprising:

a first set of instructions, executable on a computer system, configured to generate a smart-prefetch instruction for a load stream of data defined in a computer program, and

a second set of instructions, executable on said computer system, configured to perform a “

work in the loop”

(WL) computation.

25. The computer program product of claim 24, further comprising:

a third set of instructions, executable on said computer system, configured to identify said load stream in said computer program, the data of said load stream is accessed by a sequence of memory reads at dynamically determined intervals.

26. The computer program product of claim 24, further comprising:

a fourth set of instructions, executable on said computer system, configured to generate a load instruction for data in said load stream; and

a fifth set of instructions, executable on said computer system, configured to include an identifier in said load instruction to notify said processor that said data is prefetchable.