Hardware prefetcher for indirect access patterns
Two techniques address bottlenecking in processors. The first is indirect prefetching. The technique can be especially useful for graph analytics and sparse matrix applications. For graph analytics and sparse matrix applications, the addresses of most random memory accesses come from an index array B which is sequentially scanned by an application. The random accesses are actually indirect accesses in the form A[B[i]]. A hardware component is introduced to detect this pattern. The hardware can then read B a certain distance ahead, and prefetch the corresponding element in A. For example, if the “prefetch distance” is k, when B[i] is accessed, the hardware reads B[i+k], and then A[B[i+k]. For partial cacheline accessing, the indirect accesses are usually accessing random memory locations and only accessing a small portion of a cacheline. Instead of loading the whole cacheline into L1 cache, the second technique only loads a part of the cacheline.
1. A processor comprising:
a microcontroller to find a stream pattern;
indirect access detection logic to detect one or more indirect memory access patterns, the one or more indirect memory access patterns being based on a size of a data element and a base address, and when a candidate base address of a first index matches a candidate later base address, an indirect pattern exists; and
indirect prefetcher logic to read an array a prefetch distance ahead, and prefetch a corresponding element in a memory, wherein the prefetch distance varies based on a number of hits.
2. The processor of claim 1 , wherein the array is an index array.
3. The processor of claim 2 , wherein the indirect prefetcher logic reads B[i+k] when B[i] is accessed, where B is the index array and k is a prefetch distance.
4. The processor of claim 3 , wherein the indirect prefetcher logic further reads A[B[i+k]] to fetch an element from array A.
5. The processor of claim 3 , further comprising a stream pattern detector within the microcontroller that detects a stream accessing pattern to array B.
6. The processor of claim 2 , wherein the one or more indirect memory access patterns is equal to a size of a data element times a value from the index array plus a base address.
7. The processor of claim 2 , wherein at least two index accesses are tracked in conjunction with a number of cache misses.
8. The processor of claim 2 , further comprising memory that stores a size of a data element and a base address.
9. The processor of claim 1 , further comprising partial cacheline accessing logic to determine whether a whole cacheline or a part of the cacheline should be read into cache, and to read the determined cacheline or part of the cacheline into cache.
10. The processor of claim 9 , where a granularity detector determines a size of the part of the cacheline to read into cache.
11. A method comprising:
detecting one or more indirect memory access patterns, the one or more indirect memory access patterns being based on a size of a data element and a base address, and when a candidate base address of a first index matches a candidate later base address, an indirect pattern exists; and
reading an array a perfetch distance ahead, and prefetching a corresponding element in a memory, wherein the prefetch distance varies based on a number of hits.
12. The method of claim 11 , wherein the array is an index array.
13. The method of claim 12 , wherein the reading reads B[i+k] when B[i] is accessed, where B is the index array and k is a prefetch distance.
14. The method of claim 13 , wherein the reading further reads A[B[i+k]] to fetch an element from array A.
15. The method of claim 13 , further comprising detecting a stream accessing pattern to array B.
16. The method of claim 12 , wherein the one or more indirect memory access patterns is equal to a size of a data element times a value from the index array plus a base address.
17. The method of claim 12 , wherein at least two index accesses are tracked in conjunction with a number of cache misses.
18. The method of claim 12 , further comprising storing a size of a data element and a base address.
19. The method of claim 11 , further comprising determining whether a whole cacheline or a part of the cacheline should be read into cache, and reading the determined cacheline into cache.
20. The method of claim 19 , further comprising determining a size of the part of the cacheline to read into cache.