Bypass predictor for an exclusive last-level cache

Patent metadata

Field	Value
Publication number	US-11113207-B2
Application number	US-201916289645-A
Country	US
Kind code	B2
Filing date	Feb 28, 2019
Priority date	Dec 26, 2018
Publication date	Sep 7, 2021
Grant date	Sep 7, 2021

Abstract

A system and a method to allocate data to a first cache increments a first counter if a reuse indicator for the data indicates that the data is likely to be reused and decremented the counter if the reuse indicator for the data indicates that the data is likely not to be reused. A second counter is incremented upon eviction of the data from the second cache, which is a higher level cache than the first cache. The data is allocated to the first cache if the value of the first counter is equal to or greater than the first predetermined threshold or the value of the second counter equals zero, and the data is bypassed from the first cache if the value of the first counter is less than the first predetermined threshold and the value of the second counter is not equal to zero.

First claim

What is claimed is:

1. A method to allocate data evicted from a first cache to a second cache, the method comprising:
determining upon eviction of a block of data from the first cache whether a reuse indicator for the block of data indicates that the block of data has been reused from the first cache or the second cache, the first cache being a higher level cache than the second cache;
incrementing a first counter based on the reuse indicator for the block of data indicating that the block of data has been reused;
decrementing the first counter based on the reuse indicator for the block of data indicating that the block of data has not been reused;
incrementing a second counter upon eviction of the block of data from the first cache;
comparing a value of the first counter to a first predetermined threshold;
determining whether a value of the second counter is equal to zero;
allocating the block of data to the second cache based on the value of the first counter being equal to or greater than the first predetermined threshold or the value of the second counter equaling zero; and
writing the block of data to a system memory while bypassing the second cache based on the value of the first counter being less than the first predetermined threshold and the value of the second counter being not equal to zero.

2. The method of claim 1 , further comprising:
receiving a request for the block of data in the first cache;
setting the reuse indicator to indicate that the block of data has been reused based on the request for the block of data being a hit in the second cache; and
setting the reuse indicator to indicate that the block of data has not been reused based on the request for the block of data being a miss in the second cache.

3. The method of claim 1 , further comprising:
receiving a request for the block of data in the first cache;
setting the reuse indicator to indicate that the block of data has been reused based on the request for the block of data being a hit in the first cache; and
setting the reuse indicator to indicate that the block of data has not been reused based on the request for the block of data being a miss in the first cache.

4. The method of claim 1 , wherein writing the block of data to the system memory while bypassing the second cache based on the value of the first counter being less than the first predetermined threshold and the value of the second counter being not equal to zero further comprises:
bypassing the block of data from the second cache based on the block of data being clean data; and
allocating the block of data to the second cache based on the block of data being dirty data.

5. The method of claim 1 , wherein writing the block of data to the system memory while bypassing the second cache based on the value of the first counter being less than the first predetermined threshold and the value of the second counter being not equal to zero further comprises:
dropping the block of data from the first cache based on the block of data being clean data; and
writing the block of data to the system memory based on the block of data being dirty data.

6. The method of claim 1 , wherein the second cache is a last-level cache.

7. A method to allocate data evicted from a first cache to a second cache, the method comprising:
determining upon eviction of a block of data from the first cache whether a reuse indicator for the block of data indicates that the block of data has been reused from the first cache or the second cache, the first cache being a higher level cache than the second cache;
incrementing a first counter based on the reuse indicator for the block of data indicating that the block of data has been reused;
decrementing the first counter based on the reuse indicator for the block of data indicating that the block of data has not been reused;
incrementing a second counter upon eviction of the block of data from the second cache;
determining whether a value of the first counter is less than a first predetermined threshold;
determining whether a value of the second counter is equal to zero;
allocating the block of data to a location in the second cache that is above a least recently used location in the second cache based on the value of the first counter being equal to or greater than the first predetermined threshold or the value of the second counter equaling zero; and
allocating the block of data in the least recently used location in the second cache based on the value of the first counter being less than the first predetermined threshold and the value of the second counter being not equal to zero.

8. The method of claim 7 , further comprising:
receiving a request for the block of data in the first cache;
setting the reuse indicator to indicate that the block of data has been reused based on the request for the block of data being a hit in the first cache; and
setting the reuse indicator to indicate that the block of data has not been reused based on the request for the block of data being a miss in the first cache.

9. The method of claim 7 , further comprising:
receiving a request for the block of data in the first cache;
setting the reuse indicator to indicate that the block of data has been reused based on the request for the block of data being hit in the first cache and the reuse indicator being configurable in response to a request for the block of data; and
setting the reuse indicator to indicate that the block of data has not been reused based on the request for the block of data being a miss in the first cache and the reuse indicator being configurable in response to a request for the block of data.

10. The method of claim 7 , wherein the second cache is a last-level cache.

11. A cache system, comprising:
a first cache comprising at least one block of data, each block of data comprising a tag, each tag comprising a plurality of bits, at least one bit of each tag providing a reuse indicator that a corresponding block of data has been reused;
a second cache that is a lower-level cache than the first cache; and
a cache controller coupled to the first cache and the second cache, the cache controller comprising a first counter and a second counter, the cache controller configured to increment the first counter based on the reuse indicator for a first block of data indicating that the first block of data has been reused from the first cache or the second cache upon eviction from the first cache and decrement the first counter based on the reuse indicator for the first block of data indicating that the first block of data has not been reused upon eviction from the first cache, the cache controller further configured to increment a second counter upon eviction of the first block of data from the first cache, provide an indication to allocate the first block of data to the second cache based on a value of the first counter being equal to or greater than a first predetermined threshold or a value of the second counter equaling zero, and provide an indication for the first block of data to bypass the second cache based on the value of the first counter being less than the first predetermined threshold and the value of the second counter being not equal to zero.

12. The cache system of claim 11 , wherein the cache controller is configured to set the reuse indicator for the first block of data to indicate that the first block of data has been reused based on a request for the first block of data in the first cache being a hit, and sets the reuse indicator for the first block of data to indicate that the first block of data has not been reused based on the request for the first block of data in the first cac

Assignees

• Samsung Electronics Co Ltd

Inventors

• Tian Yingying
• Nakra Tarun
• Sinha Vikas
• Le Hien

Classifications

• G06F12/123 Primary

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F12/0897

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

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F12/0888 Primary

  using selective caching, e.g. bypass · CPC title

• G06F2212/1016

  Performance improvement · CPC title