Create page locality in cache controller cache allocation

Patent metadata

Field	Value
Publication number	US-9846648-B2
Application number	US-201514709323-A
Country	US
Kind code	B2
Filing date	May 11, 2015
Priority date	May 11, 2015
Publication date	Dec 19, 2017
Grant date	Dec 19, 2017

Abstract

Integrated circuits are provided which create page locality in cache controllers that allocate entries to set-associative cache, which includes data storage for a plurality of Sets of Ways. A plurality of cache controllers may be interleaved with a processor and device(s), and allocate to any pages in the cache. A cache controller may select a Way from a Set to which to allocate new entries in the set-associative cache and bias selection of the Way according to a plurality of upper address bits (or other function). These bits may be identical at the cache controller during sequential memory transactions. A processor may determine the bias centrally, and inform the cache controllers of the selected Set and Way. Other functions, algorithms or approaches may be chosen to influence bias of Way selection, such as based on analysis of metadata belonging to cache controllers used for making Way allocation selections.

First claim

What is claimed is:

1. An integrated circuit comprising:
a cache controller to allocate memory within set-associative cache comprising a plurality of Sets of Ways, wherein the cache controller comprises a plurality of interleaved cache controllers and is to:
select a Way, from a series of Sets within the plurality of Sets of Ways, to which to allocate new entries in the set-associative cache; and
bias selection of the Way according to a plurality of upper address bits of memory transactions that are identical at the cache controller during sequential memory transactions.

2. The integrated circuit of claim 1 , wherein same-numbered Ways of a series of Sets belong to a page within the set-associative cache.

3. The integrated circuit of claim 1 , wherein the cache controller comprises a first cache controller and a second cache controller ordered sequentially after the first cache controller, the first cache controller to identify the Way for the second cache controller.

4. The integrated circuit of claim 3 , wherein the first cache controller is a lowest-numbered cache controller and the second cache controller is a next-higher-numbered.

5. A system comprising:
set-associative cache including a data storage in which to store: data in a plurality of Sets of Ways and metadata related to the data in respective Ways of the plurality of Sets of Ways, the metadata comprising a tag, valid bits, and dirty bits; and
a cache controller coupled to the data storage, wherein the cache controller comprises a plurality of interleaved cache controllers and is to:
select a Way, from a series of Sets within the plurality of Sets of Ways, to which to allocate new entries based on analysis of the metadata; and
allocate the new entries to the Way that was selected.

6. The system of claim 5 , further comprising a processor to analyze the metadata, wherein the cache controller is integrated as a part of the processor, and wherein the metadata belongs to the cache controller when making a Way selection.

7. The system of claim 6 , wherein the processor is further to communicate an identity of the Way to the plurality of interleaved cache controllers such that the plurality of interleaved cache controllers allocate sequential entries of a memory transaction to the Way of the series of Sets.

8. The system of claim 5 , wherein, to select the Way, the cache controller is further to:
identify an available number of Ways in the series of Sets;
determine a preferred Way that is available in response to execution of a function;
determine whether the preferred Way is among the Ways available within the series of Sets; and
select the Way for allocation of new entries as the preferred Way when the preferred Way is among the Ways available within the series of Sets.

9. The system of claim 8 , wherein the cache controller further to identify the available number of Ways in the series of Sets based on a number of least recently used clean entries and a number of least recently used dirty entries in the series of Sets.

10. A system on a chip (SoC) comprising:
interleaved first and second cache controllers to allocate memory entries to a plurality of Sets of Ways within set-associative cache, the second cache controller being sequentially-numbered after the first cache controller;
the first cache controller further to:
select a Way within a Set of the plurality of Sets of Ways to which to allocate an entry for a memory transaction; and
transmit to the second cache controller an identity of the Way that was selected for the Set; and

the second cache controller further to also select the Way for cache entry allocation, when available, in response to receipt of the identity of the Way from the first cache controller.

11. The SoC of claim 10 , wherein the first cache controller is a lowest-numbered cache controller and the second cache controller is a next-higher-numbered cache controller.

12. The SoC of claim 10 , wherein the first cache controller and the second cache controller comprise a plurality of cache controllers, and wherein each of the plurality of the cache controllers to transmit the identity of the Way to a sequentially next-higher-numbered cache controller during memory allocation for sequential memory transactions.

13. The SoC of claim 12 , wherein each sequentially next-higher-numbered cache controller further to prefer to allocate to the Way in response to receipt of the identity of the Way selected for memory allocation from a lower-numbered cache controller.

14. The SoC of claim 12 , wherein each sequentially next-higher-numbered cache controller further to:
determine whether it is a highest-numbered cache controller;
transmit the identity of the Way to a lowest-numbered cache controller in response to a determination that it is the highest-numbered cache; and
cease to transmit the identity of the Way to the next-higher-numbered cache controller upon receipt of a request that does not, in Way data storage, have locality with the Way of the Set selected by a previous cache controller.

15. The SoC of claim 14 , wherein the Set comprises a first Set, and wherein the lowest-numbered cache controller further to transmit the identity of the Way to the next-higher-numbered cache controller in response to the determination that a request for a new entry is to a second Set having page locality with the first Set.

16. A system comprising:
set-associative cache including a data storage in which to store data in a plurality of Sets of Ways; and
a cache controller, of a plurality of interleaved cache controllers coupled to the data storage, to:
identify an available number of Ways in a Set of the set-associative cache, the Set being one of an identically-numbered series of Sets;
determine a preferred Way within the plurality of Sets of Ways in response to execution of a function related to one or more requests received by the cache controller;
determine whether the preferred Way is among the Ways available within the Set; and
select the preferred Way as the Way to which to allocate new entries when the preferred Way is among the Ways available within the Set.

17. The system of claim 16 , wherein the function is based on system address bits that do not contribute to selection of the cache controller among the interleaved cache controllers.

18. The system of claim 16 , further comprising a processor to execute the function, wherein the cache controller is integrated as a part of the processor.

19. The system of claim 16 , wherein the cache controller further to select the Way for new entries based on a least recently used (LRU) algorithm when the preferred Way is not among the ways available within the set.

20. The system of claim 16 , wherein the cache controller further to identify the available number of Ways in the Set based on a number of least recently used clean entries and a number of least recently used dirty entries in the set.

21. The system of claim 16 , wherein the function is based on system address bits related to the one or more requests for which memory allocation is requested.

22. The system of claim 16 , wherein the function is based on system address bits that do not contribute to selection of the preferred Way.

Assignees

• Intel Corp

Inventors

• Greenspan Daniel
• Nori Anant V
• Majumder Supratik
• Lossin Yoav
• Rubinstein Asaf

Classifications

• G06F12/128

  adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel · CPC title

• G06F2212/1024

  Latency reduction · CPC title

• G06F2212/6032

  Way prediction in set-associative cache · CPC title

• G06F12/0851

  Cache with interleaved addressing · CPC title

• G06F12/0864 Primary

  using pseudo-associative means, e.g. set-associative or hashing · CPC title