Online heuristic sequentiality detection over input/output streams for cache systems in large address spaces
A method and system for assessing sequentiality of a data stream is disclosed. Specifically, the method and system disclosed herein may entail receiving an incoming request to access a page in a cache memory, wherein the page is identified by a page address of an address space in a main memory; identifying, in a memory, a bin corresponding to an address range including the page address of the page of the incoming request, wherein the bin includes k address ranges of the address space of the main memory; determining whether to update an occupation count of the bin in the memory; locating the bin in a heuristics table to obtain an estimated total number of expected proximal accesses based on an updated occupation count of the bin; and determining, based on the estimated total number of expected proximal accesses, sequentiality of the data stream to device in order to generate a policy for the cache memory.
1. A method of assessing sequentiality of a data stream, the method comprising:
receiving an incoming request to access a page in a cache memory, wherein the page is identified by a page address of an address space in a main memory;
identifying, in a memory, a bin corresponding to an address range including the page address of the page of the incoming request, wherein the bin includes k address ranges of the address space of the main memory;
determining whether to update an occupation count of the bin in the memory;
locating the bin in a heuristics table to obtain an estimated total number of expected proximal accesses based on an updated occupation count of the bin; and
determining, based on the estimated total number of expected proximal accesses, sequentiality of the data stream to device in order to generate a policy for the cache memory.
2. The method of claim 1 , wherein determining whether to update the occupation count of the bin comprises:
determining whether the page preexists in the cache memory;
in response to determining the page does not preexist in the cache memory, determining whether the incoming request causes one or more prefetched pages in the cache memory;
in response to determining the incoming request does not cause prefetched pages in the cache memory, determining whether one or more evicted pages are associated with the incoming request; and
in response to determining one or more evicted pages are associated with the incoming request, decrementing the occupation count of the bin and occupation counts corresponding to each of a remaining evicted pages of the evicted pages.
3. The method of claim 1 , wherein determining whether to update the occupation count of the bin further comprising:
determining whether the page preexists in the cache memory;
in response to determining the page preexists in the cache memory, avoiding incrementing the occupation count of the bin; and
in response to determining the page does not preexist in the cache memory, incrementing the occupation count of the bin.
4. The method of claim 1 , wherein determining whether to update the occupation count of the bin further comprising:
determining whether the page preexists in the cache memory;
in response to determining the page does not preexist in the cache memory, determining whether the incoming request causes one or more prefetched pages in the cache memory;
in response to determining the incoming request causes the prefetched pages in the cache memory, avoiding incrementing the occupation count of the bin and occupation counts corresponding to each of a remaining prefetched pages of the prefetched pages associated with the page of the incoming request; and
in response to determining the incoming request does not cause the prefetched pages in the cache memory, incrementing the occupation count of the bin.
5. The method of claim 1 , wherein determining whether to update the occupation count of the bin further comprising:
determining whether the page preexists in the cache memory;
in response to determining the page does not preexist in the cache memory, determining whether the incoming request causes one or more prefetched pages in the cache memory;
in response to determining the incoming request does not cause prefetched pages in the cache memory, determining whether one or more evicted pages are associated with the incoming request;
in response to determining the evicted pages are associated with the incoming request, avoiding decrementing the occupation count of the bin and occupation counts corresponding to each of a remaining evicted pages of the evicted pages; and
in response to determining no evicted pages are associated with the incoming request, avoiding decrementing the occupation count of the bin.
6. The method of claim 1 , wherein the memory with the bin resides in the cache memory.
7. The method of claim 1 , wherein the memory with the bin resides externally to the cache memory.
8. The method of claim 1 , further comprising:
generating the heuristics table prior to receiving the incoming request.
9. The method of claim 1 , wherein the policy is a cache management policy or a cache optimization policy.
10. The method of claim 9 , wherein the policy is a prefetch policy or a promotion policy.
11. A device, comprising:
a processor; and
memory comprising instructions which, when executed by the processor, perform assessing sequentiality of a data stream, the method comprising:
receiving an incoming request to access a page in a cache memory, wherein the page is identified by a page address of an address space in a main memory;
identifying, in a memory, a bin corresponding to an address range including the page address of the page of the incoming request, wherein the bin includes k address ranges of the address space of the main memory;
determining whether to update an occupation count of the bin in the memory;
locating the bin in a heuristics table to obtain an estimated total number of expected proximal accesses based on an updated occupation count of the bin; and
determining, based on the estimated total number of expected proximal accesses, sequentiality of the data stream to device in order to generate a policy for the cache memory.
12. The device of claim 11 , wherein determining whether to update the occupation count of the bin comprises:
determining whether the page preexists in the cache memory;
in response to determining the page does not preexist in the cache memory, determining whether the incoming request causes one or more prefetched pages in the cache memory;
in response to determining the incoming request does not cause prefetched pages in the cache memory, determining whether one or more evicted pages are associated with the incoming request; and
in response to determining one or more evicted pages are associated with the incoming request, decrementing the occupation count of the bin and occupation counts corresponding to each of a remaining evicted pages of the evicted pages.
13. The device of claim 11 , wherein determining whether to update the occupation count of the bin further comprising:
determining whether the page preexists in the cache memory;
in response to determining the page preexists in the cache memory, avoiding incrementing the occupation count of the bin; and
in response to determining the page does not preexist in the cache memory, incrementing the occupation count of the bin.
14. The device of claim 11 , wherein determining whether to update the occupation count of the bin further comprising:
determining whether the page preexists in the cache memory;
in response to determining the page does not preexist in the cache memory, determining whether the incoming request causes one or more prefetched pages in the cache memory;
in response to determining the incoming request causes the prefetched pages in the cache memory, avoiding incrementing the occupation count of the bin and occupation counts corresponding to each of a remaining prefetched pages of the prefetched pages associated with the page of the incoming request; and
in response to determining the incoming request does not cause the prefetched pages in the cache memory, incrementing the occupation count of the bin.
15. The device of claim 11 , wherein determining whether to update the occupation count of the bin further comprising:
determining whether the page preexists in the cache memory;
in response to determining the page does not preexist in the cache memory, determining whether the incoming request causes one or more prefetched pages in the cache memory;
in response to determining the incoming request does not cause prefetched pages in the cache memory, determining whether one or more evicted pages are associated with the incoming request;
in response to determining the evicted pages are associated with the incoming request, avoiding decrementing the occupation count of the bin and occupation counts corresponding to each of a remaining evicted pages of the evicted pages; and
in response to determining no evicted pages are associated with the incoming request, avoiding decrementing the occupation count of the bin.
16. The device of claim 11 , wherein the memory with the bin resides in the cache memory.
17. The device of claim 11 , wherein the memory with the bin resides externally to the cache memory.
18. The device of claim 11 , further comprising:
generating the heuristics table prior to receiving the incoming request.
19. The device of claim 11 , wherein the policy is a cache management policy or a cache optimization policy.
20. A non-transitory computer readable medium comprising computer readable program code, which when executed by a computer processor enables the computer processor to perform a method for assessing sequentiality of a data stream, the method comprising:
receiving an incoming request to access a page in a cache memory, wherein the page is identified by a page address of an address space in a main memory;
identifying, in a memory, a bin corresponding to an address range including the page address of the page of the incoming request, wherein the bin includes k address ranges of the address space of the main memory;
determining whether to update an occupation count of the bin in the memory;
locating the bin in a heuristics table to obtain an estimated total number of expected proximal accesses based on an updated occupation count of the bin; and
determining, based on the estimated total number of expected proximal accesses, sequentiality of the data stream to device in order to generate a policy for the cache memory.