Smart-prefetch

• US 20040117557A1
• Filed: 12/16/2002
• Published: 06/17/2004
• 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
• Granted Patent: US 6,981,099 B2
• Time in Patent Office: Days
• 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; and

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

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 a smart-prefetch request from said smart-prefetch instruction; and

updating said smart prefetch request with said effective memory latency.

8. The method of claim 7, further comprising:

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.

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.

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.

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:

a “

work in the loop”

(WL) 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 smart-prefetch unit further comprises:

an effective address computation module.

20. The system of claim 19, 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.

21. 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.

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

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

23. The system of claim 22, further comprising:

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

24. The system of claim 15, further comprising:

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 address 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.

25. 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.

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

a second 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.

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

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

a fourth 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.