ADAPTIVE DATA PREFETCHING

• US 20150143057A1
• Filed: 01/03/2013
• Published: 05/21/2015
• Est. Priority Date: 01/03/2013
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Pavlou, Demos, Lopez, Pedro, Hyuseinova, Mirem, Latorre, Fernando, Kosinski, Steffen, Goettsche, Ralf, Mohandru, Varun K.
• Granted Patent: US 9,280,474 B2
• Time in Patent Office: Days
• US Class Current: 711/137
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• 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 9/06 using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
• CPC Class Codes: G06F 9/30 Arrangements for executing machine instructions, e.g. instruction decode for executing microinstructions G06F9/22
• CPC Class Codes: G06F 9/3455 using stride
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862

Abstract

A system and method for adaptive data prefetching in a processor enables adaptive modification of parameters associated with a prefetch operation. A stride pattern in successive addresses of a memory operation may be detected, including determining a stride length (L). Prefetching of memory operations may be based on a prefetch address determined from a base memory address, the stride length L, and a prefetch distance (D). A number of prefetch misses may be counted at a miss prefetch count (C). Based on the value of the miss prefetch count C, the prefetch distance D may be modified. As a result of adaptive modification of the prefetch distance D, an improved rate of cache hits may be realized.

Claims

1. A method, comprising:

determining a value for a stride length (L) in response to detecting a stride pattern in memory operations;

prefetching data for expected memory operations based on a prefetch address determined based on a base memory address, the stride length L, and a prefetch distance (D), wherein the prefetch address is given by a sum of the base memory address and a product (L×

D);

maintaining a miss prefetch count (C) indicative of a number of prefetch misses; and

based on the value of the miss prefetch count C, modifying the prefetch distance D.

2. The method of claim 1, wherein the modifying the prefetch distance D includes incrementing the prefetch distance D.

3. The method of claim 2, wherein the prefetch distance D is not incremented when a maximum prefetch distance extending to a size of a memory page is attained and further comprising:

comparing the prefetch address determined to a maximum threshold and, when the prefetch addressed determined exceeds the maximum threshold, using the maximum threshold.

4. The method of claim 1, further comprising:

resetting the miss prefetch count C to zero and the prefetch distance D to one when the stride pattern is no longer detected.

5. The method of claim 1, wherein the modifying the prefetch distance D occurs when the miss prefetch count C reaches a count threshold (T).

6. The method of claim 1, wherein the counting of the miss prefetch count C comprises:

maintaining an instruction pointer prefetch array including an instance of a miss prefetch count C for each prefetch address value in the prefetch array.

7. The method of claim 1, wherein the stride pattern is indicative of a fixed memory address offset between successive memory operations.

8. The method of claim 7, wherein the fixed memory address offset is used for the stride length L.

9. The method of claim 1, wherein the base memory address is indicated by an instruction referenced by an instruction pointer.

10. A processor, comprising:

a data prefetch unit to;

determine a stride length (L) in response to detecting a stride pattern in memory operations;

prefetch for expected memory operations based on a prefetch address determined based on a base memory address, the stride length L, and a prefetch distance (D), wherein the prefetch address is given by a sum of the base memory address and a product (L×

D);

maintain a miss prefetch count (C) indicative of a number of prefetch misses; and

when the miss prefetch count C equals a count threshold (T), modify the prefetch distance D.

11. The processor of claim 10, wherein the data prefetch unit when modifying the prefetch distance D, the data prefetch unit is operable to increment the prefetch distance D.

12. The processor of claim 10, wherein the data prefetch unit is operable to:

when the stride pattern is no longer detected;

reset the miss prefetch count C to zero and the prefetch distance D to one.

13. The processor of claim 10, wherein the data prefetch unit is operable to initialize a value for the count threshold T.

14. The processor of claim 10, wherein, when the data prefetch unit counts the miss prefetch count C, the data prefetch unit is operable to:

maintain an instruction pointer prefetch array with an instance of the miss prefetch count C for each prefetch address value.

15. The processor of claim 10, wherein the stride pattern is indicative of a fixed memory address offset between successive memory operations.

16. The processor of claim 15, wherein the fixed memory address offset is used for the stride length L.

17. The processor of claim 10, wherein the base memory address is indicated by an instruction referenced by an instruction pointer.

18. A system comprising:

a processor;

a memory accessible to the processor;

a touchscreen controller; and

wherein the processor includes an adaptive data prefetch unit to;

determine a value for a stride length (L) responsive to detecting a stride pattern in memory operations;

prefetch for expected memory operations based on a prefetch address determined based on a base memory address, using the stride length L, and a prefetch distance (D), wherein the prefetch address is given by a sum of the base memory address and a product (L×

D);

count a number of prefetch misses as a miss prefetch count (C); and

when the miss prefetch count C equals a count threshold (T), modify the prefetch distance D.

19. The system of claim 18, wherein when modifying the prefetch distance D, the adaptive prefetch unit is operable to increment the prefetch distance D.

20. The system of claim 18, wherein the adaptive prefetch unit is operable to:

when the stride pattern is no longer detected;

reset the miss prefetch count C to zero and the prefetch distance D to one.

21. The system of claim 18, wherein the adaptive prefetch unit is operable to initialize a value for the count threshold T.

22. The system of claim 18, wherein, when the processor counts the miss prefetch count C, the processor is operable to:

maintain an instruction pointer prefetch array with an instance of the miss prefetch count C for each prefetch address value.

23. The system of claim 18, wherein the stride pattern is indicative of a fixed memory address offset between successive memory operations.

24. The system of claim 23, wherein the fixed memory address offset is used for the stride length L.

25. The system of claim 18, wherein the base memory address is indicated by an instruction referenced by an instruction pointer.