Managing memory access requests with prefetch for streams

Patent metadata

Field	Value
Publication number	US-10013357-B2
Application number	US-201615269072-A
Country	US
Kind code	B2
Filing date	Sep 19, 2016
Priority date	May 9, 2016
Publication date	Jul 3, 2018
Grant date	Jul 3, 2018

Abstract

Managing memory access requests to a cache system including one or more cache levels that are configured to store cache lines that correspond to memory blocks in a main memory includes: storing stream information identifying recognized streams that were recognized based on previously received memory access requests, where one or more of the recognized streams comprise strided streams that each have an associated strided prefetch result corresponding to a stride that is larger than or equal to a size of a single cache line; and determining whether or not a next cache line prefetch request corresponding to a particular memory access request will be made based at least in part on whether or not the particular memory access request matches a strided prefetch result for at least one strided stream, and a history of past next cache line prefetch requests.

First claim

What is claimed is:

1. A method for managing memory access requests to a cache system including one or more cache levels that are configured to store cache lines that correspond to memory blocks in a main memory, the method comprising:
storing stream information identifying recognized streams that were recognized based on previously received memory access requests, where one or more of the recognized streams comprise strided streams that each have an associated strided prefetch result corresponding to a stride that is larger than or equal to a size of a single cache line; and
determining whether or not a next cache line prefetch request corresponding to a particular memory access request will be made based at least in part on whether or not the particular memory access request matches a strided prefetch result for at least one strided stream, and a history of past next cache line prefetch requests;
wherein, if the particular memory access request does not match any strided prefetch result, then a next cache line prefetch request corresponding to the particular memory access request is made; and if the particular memory access request does match a strided prefetch result for at least one strided stream, then a next cache line prefetch request corresponding to the particular memory access request is not made.

2. The method of claim 1 , wherein the strided streams comprise a plurality of strided streams, where a first strided stream has an associated first strided prefetch result corresponding to a first stride, and a second strided stream has an associated second strided prefetch result corresponding to a second stride that is larger than the first stride.

3. The method of claim 2 , wherein the first strided prefetch result and the second strided prefetch result have a plurality of highest order address bits that are identical to each other.

4. The method of claim 1 , wherein, for each of one or more strided streams included in the recognized streams, at least one next cache line prefetch request was made corresponding to at least one memory access request of a set of multiple memory access requests based on which that strided stream was recognized.

5. The method of claim 4 , wherein each of the memory access requests of the set of multiple memory access requests has a plurality of highest order address bits that are identical to each other.

6. The method of claim 1 , wherein the history of past next cache line prefetch requests comprises stored history information that depends on results of past next cache line prefetch requests corresponding to memory access requests made before the particular memory access request, and the stored history information is accessed based on a combination that includes: (1) bits from an address of the particular memory access request, and (2) bits from an address of at least one of the memory access requests made before the particular memory access request.

7. The method of claim 1 , wherein each stride is computed based on a difference between a first address of a first memory access request and a second address of a second memory access request, where the first and second addresses have a plurality of highest order bits that are identical to each other.

8. A method for managing memory access requests to a cache system including one or more cache levels that are configured to store cache lines that correspond to memory blocks in a main memory, the method comprising:
storing stream information identifying recognized streams that were recognized based on previously received memory access requests, where one or more of the recognized streams comprise strided streams that each have an associated strided prefetch result corresponding to a stride that is larger than or equal to a size of a single cache line; and
determining whether or not a next cache line prefetch request corresponding to a particular memory access request will be made based at least in part on whether or not the particular memory access request matches a strided prefetch result for at least one strided stream, and a history of past next cache line prefetch requests;
wherein, if the particular memory access request does not match any strided prefetch result, then whether or not a next cache line prefetch request corresponding to the particular memory access request is made is determined based at least in part on stored history information that depends on results of past next cache line prefetch requests corresponding to memory access requests made before the particular memory access request; and if the particular memory access request does match a strided prefetch result for at least one strided stream, then a next cache line prefetch request corresponding to the particular memory access request is not made.

9. The method of claim 8 , wherein the stored history information comprises a state of a counter that is accessed based on a combination that includes: (1) bits from an address of the particular memory access request, and (2) bits from an address of at least one of the memory access requests made before the particular memory access request.

10. The method of claim 9 , wherein the state of the counter is stored in a data structure that is indexed by a result of a function that preforms the combination.

11. The method of claim 8 , wherein the strided streams comprise a plurality of strided streams, where a first strided stream has an associated first strided prefetch result corresponding to a first stride, and a second strided stream has an associated second strided prefetch result corresponding to a second stride that is larger than the first stride.

12. The method of claim 11 , wherein the first strided prefetch result and the second strided prefetch result have a plurality of highest order address bits that are identical to each other.

13. The method of claim 8 , wherein, for each of one or more strided streams included in the recognized streams, at least one next cache line prefetch request was made corresponding to at least one memory access request of a set of multiple memory access requests based on which that strided stream was recognized.

14. The method of claim 13 , wherein each of the memory access requests of the set of multiple memory access requests has a plurality of highest order address bits that are identical to each other.

15. The method of claim 8 , wherein the history of past next cache line prefetch requests comprises stored history information that depends on results of past next cache line prefetch requests corresponding to memory access requests made before the particular memory access request, and the stored history information is accessed based on a combination that includes: (1) bits from an address of the particular memory access request, and (2) bits from an address of at least one of the memory access requests made before the particular memory access request.

16. The method of claim 8 , wherein each stride is computed based on a difference between a first address of a first memory access request and a second address of a second memory access request, where the first and second addresses have a plurality of highest order bits that are identical to each other.

17. A memory system comprising:
at least one memory controller for accessing a main memory;
a cache system including one or more cache levels that are configured to store cache lines that correspond to memory blocks in the main memory; and
a memory access request manager configured to manage memory access requests, the managing including:
storing stream information identifying recognized streams that were rec

Assignees

• Cavium Inc

Inventors

• Mukherjee Shubhendu Sekhar
• Carlson David Albert
• Manne Srilatha

Classifications

• G06F12/0897

  with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811) · CPC title

• G06F12/0862 Primary

  with prefetch · CPC title

• G06F2212/6024

  History based prefetching · CPC title

• G06F2212/6026

  Prefetching based on access pattern detection, e.g. stride based prefetch · CPC title

• G06F2212/1016

  Performance improvement · CPC title