Stride prefetching across memory pages

• US 10,671,535 B2
• Filed: 07/17/2013
• Issued: 06/02/2020
• Est. Priority Date: 07/17/2013
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Kalamatianos, John, Keltcher, Paul, Evers, Marius, Narasimhaiah, Chitresh
• Primary Examiner(s): Bragdon, Reginald G
• Assistant Examiner(s): Thomas, James J.
• Application Number:
  US13/944,148
• Publication Number:
  US 20150026414A1
• Time in Patent Office: 2,512 Days
• Field of Search: None
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 2212/655 Same page detection

Abstract

A prefetcher maintains the state of stored prefetch information, such as a prefetch confidence level, when a prefetch would cross a memory page boundary. The maintained prefetch information can be used both to identify whether the stride pattern for a particular sequence of demand requests persists after the memory page boundary has been crossed, and to continue to issue prefetch requests according to the identified pattern. The prefetcher therefore does not have re-identify a stride pattern each time a page boundary is crossed by a sequence of demand requests, thereby improving the efficiency and accuracy of the prefetcher.

Claims

1. A method comprising:

identifying, at a processor, a first stride value based on a first memory access request to a first memory page;

in response to a sum of the first stride value and a physical memory address of the first memory access exceeding a page boundary of the first memory page, maintaining a first prefetch confidence associated with the first memory access; and

in response to a second memory access to a second memory page subsequent to the first memory access;

identifying an offset portion of the physical memory address of the first memory access;

identifying a sum value equal to a sum of the offset portion of the physical memory address of the first memory access and the first stride value;

in response to the sum value matching an offset portion of a second physical memory address of the second memory access, matching a second stride value for the second memory access to the first stride value; and

prefetching data from a memory based on the maintained first prefetch confidence in response to the second stride value matching the first stride value.

2. The method of claim 1, wherein the second memory page is not contiguous to the first memory page in a physical address space of the processor.

3. The method of claim 1, further comprising increasing the first prefetch confidence in response to the second stride value matching a third stride value associated with a third memory access request.

4. The method of claim 1, further comprising:

suppressing a prefetch in response to the sum of the first stride value and the physical memory address of the first memory access exceeding the page boundary of the first memory page.

5. The method of claim 1, wherein prefetching data in response to the second memory access further comprises:

increasing the first prefetch confidence to generate a second prefetch confidence in response to the second stride value matching the first stride value; and

prefetching the data in response to the second prefetch confidence exceeding a threshold.

6. The method of claim 1, wherein prefetching data in response to the second memory access comprises:

identifying a first page number for the first memory page and a second page number for the second memory page; and

prefetching the data in response to;

the first page number matching the second page number.

7. The method of claim 1, further comprising:

storing prefetch information in response to the first memory access, the prefetch information identifying the first prefetch confidence; and

maintaining a least-recently-used status of the stored prefetch information in response to the sum of the first stride value and the physical memory address of the first memory access exceeding the page boundary of the first memory page.

8. A method, comprising:

in response to a first memory access to a first memory page;

identifying a first stride for a first prefetch stream associated with the first memory access;

in response to a sum of the stride and a first physical memory address for the first memory access exceeding a page boundary of the first memory page, maintaining a stored prefetch confidence for the first prefetch stream, the stored prefetch confidence indicative of a threshold to identify whether data is to be prefetched from a memory; and

in response to a second memory access to a second memory page;

identifying an offset portion of the first physical memory address of the first memory access;

identifying a sum value equal to a sum of the offset portion of the first physical memory address of the first memory access and the first stride;

in response to the sum value matching an offset portion of a second physical memory address of the second memory access, matching a second stride for the second memory access to the first stride; and

prefetching data from a memory based on the maintained first prefetch confidence in response to the second stride matching the first stride.

9. The method of claim 8, wherein identifying the first prefetch stream comprises identifying the first prefetch stream based on an instruction pointer for the first memory access.

10. The method of claim 8, further comprising:

identifying the first prefetch stream based on a first page number identifier for the first memory page.

11. The method of claim 10, further comprising:

matching the second memory access to the first prefetch stream in response to the second memory page matching the first memory page.

12. The method of claim 10, further comprising:

in response to the second memory access to the second memory page;

identifying a first sum value based on a sum of the first stride and an offset portion of the first physical memory address;

identifying a second sum value based on a sum of the second stride and an offset portion of a third physical memory address associated with a second prefetch stream;

matching the second memory access to the first prefetch stream in response to the second memory page being different from the first memory page and the first sum value matching an offset portion of a second physical memory address for the second memory access;

matching the second memory access to the second prefetch stream in response to the second memory page not matching the first memory page and the second sum value matching an offset portion of the second physical memory address;

in response to matching the second memory access to the first prefetch stream and to the second prefetch stream selecting one of the first prefetch stream and the second prefetch stream based on which of the first prefetch stream and the second prefetch stream is associated with a more recent memory access; and

prefetching data from a memory based on a prefetch confidence for the selected prefetch stream.

13. A device, comprising:

a processor core to generate a plurality of memory access requests comprising a first memory access request and a second memory access request subsequent to the first memory access request;

a prefetch table to store prefetch state information for the plurality of memory access requests including a first prefetch confidence; and

a prefetcher to;

identify a first stride value based on the first memory access request accessing a first memory page;

in response to a sum of the first stride value and a physical memory address of the first memory access exceeding a page boundary of the first memory page, maintaining the first prefetch confidence at the prefetch table; and

in response to the second memory access request accessing a second memory page;

identify an offset portion of the physical memory address of the first memory access;

identify a sum value equal to a sum of the offset portion of the physical memory address of the first memory access and the first stride value;

in response to the sum value matching an offset portion of a second physical memory address of the second memory access, match a second stride value for the second memory access to the first stride value; and

prefetch data from a memory based on the maintained first prefetch confidence in response to the second stride value matching the first stride value.

14. The device of claim 13, wherein the second memory page is non-sequential to the first memory page in a memory page order organized by an operating system executing at the processor core.

15. The device of claim 13, wherein the prefetcher is to:

increase the first prefetch confidence in response to the second stride value matching a third stride value associated with a third memory access request.

16. The device of claim 13, wherein the prefetcher is to:

suppress a prefetch in response to the sum of the first stride value and the physical memory address of the first memory access exceeding the page boundary of the first memory page.

17. The device of claim 13, wherein the prefetcher is to prefetch data in response to the second memory access by:

increasing the first prefetch confidence in response to a second stride value associated with the second memory access matching the first stride value to identify a second prefetch confidence; and

prefetching the data in response to the second prefetch confidence exceeding a threshold.