Re-reference interval prediction (RRIP) with pseudo-LRU supplemental age information
AssigneeAdvanced Micro Devices, Inc.
InventorPaul J. Moyer
Life of this patent
Estimating the term…
Abstract
Systems and methods for cache replacement are disclosed. Techniques are described that determine a re-reference interval prediction (RRIP) value of respective data blocks in a cache, where an RRIP value represents a likelihood that a respective data block will be re-used within a time interval. Upon an access, by a processor, to a data segment in a memory, if the data segment is not stored in the cache, a data block in the cache to be replaced by the data segment is selected, utilizing a binary tree that tracks recency of data blocks in the cache.
Claims22
A method for cache replacement, comprising:
- determining, by a cache controller, a re-reference interval prediction (RRIP) value associated with each data block in a cache;
- accessing, by a processor, a data segment in memory;
- and
- in response to the data segment not being stored in the cache, selecting a data block in the cache to be replaced by the data segment, wherein the selecting the data block comprises:
- searching for data blocks in the cache associated with values having a maximum RRIP value, and
- selecting one of at least two data blocks based on a binary tree, responsive to finding the at least two data blocks having the maximum RRIP value,
- wherein the selecting one of the at least two data blocks based on the binary tree includes selecting a different starting level in the binary tree responsive to a current state of the binary tree pointing to a data block other than the at least two data blocks.
A system, comprising:
- at least one processor;
- and
- memory storing instructions that, when executed by the at least one processor, cause the system to:
- determine, by a cache controller, an RRIP value associated with each data block in a cache,
- access, by the at least one processor, a data segment in a memory, and
- in response to the data segment not being stored in the cache, select a data block in the cache to be replaced by the data segment, wherein the data block is selected by a process that comprises:
- searching for data blocks in the cache associated with values having a maximum RRIP value, and
- selecting one of at least two data blocks based on a binary tree, responsive to finding the at least two data blocks having the maximum RRIP value,
- wherein the selecting one of the at least two data blocks based on the binary tree includes selecting a different starting level in the binary tree responsive to a current state of the binary tree pointing to a data block other than the at least two data blocks.
A non-transitory computer-readable medium comprising instructions executable by at least one processor to:
- determine, by a cache controller, an RRIP value associated with each data block in a cache, the RRIP value representing a likelihood that an associated data block will be re-used within a time interval, wherein a larger RRIP value corresponds to a time interval farther in the future;
- access, by the at least one processor, a data segment in memory;
- and
- in response to the data segment not being stored in the cache, select a data block in the cache to be replaced by the data segment, wherein the selecting a data block comprises:
- searching for data blocks in the cache associated with values having a maximum RRIP value, and
- selecting one of at least two data blocks based on a binary tree, responsive to finding the at least two data blocks having the maximum RRIP value,
- wherein the selecting one of the at least two data blocks based on the binary tree includes selecting a different starting level in the binary tree responsive to a current state of the binary tree pointing to a data block other than the at least two data blocks.
Dependencies are inferred from the claim text.