Set-associative cache memory having variable time decay rewriting algorithm

• US 6,732,238 B1
• Filed: 06/10/2002
• Issued: 05/04/2004
• Est. Priority Date: 06/08/2001
• Status: Expired due to Fees

• Current Assignee: Tensilica Incorporated
• Original Assignee: Tensilica Incorporated
• Inventors: Konas, Pavlos, Evans, Marc Alan
• Primary Examiner(s): Moazzami, Nasser
• Application Number:
  US10/167,133
• Time in Patent Office: 694 Days
• Field of Search: 711/122-136, 711/154, 711/159-160, 711/205-207, 365/49
• US Class Current: 711/128
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel

Abstract

A set-associative structure replacement algorithm is particularly beneficial for irregular set-associative structures which may be affected by different access patterns, and different associativities available to be replaced on any given access. According to certain aspects, methods and apparatuses implement a novel decay replacement algorithm that is particularly beneficial for irregular set-associative structures. An embodiment apparatus includes set-associative structures having decay information stored therein, as well as update/replacement logic to implement replacement algorithms for translation lookup buffers (TLBS) and caches that vary in the number of associativities; have unbalanced associativity sizes, e.g., associativities can have different numbers of indices; and can have varying replacement criteria. The implementation apparatuses and methods provide good performance, on the level of LRU, random and clock algorithms; and is efficient and scalable.

Claims

1. A method of updating replacement information in a cache memory having a plurality of entries, the entries arranged in a plurality of ways, the method comprising:

determining whether a variable time decay (VTD) field of each of the plurality of entries, including an entry corresponding to a way just accessed, have all fully decayed;

if all VTD fields have fully decayed, setting the VTD fields of all entries except the entry of the way just accessed to an undecayed state; and

if all VTD fields are not fully decayed, decaying the VTD field of the entry of the way just accessed;

wherein, at least two of the ways have a different number of entries.

2. A method according to claim 1, wherein the cache memory implements a TLB, and wherein the entries for at least two of the ways translate different size pages.

3. A method according to claim 1, wherein the number of ways is not a factor of 2.

4. A method according to claim 1, wherein the number of entries in the at least two ways are powers of 2.

5. A method according to claim 1, wherein the cache memory is set-associative.

6. A method of replacing data in a cache memory upon a cache miss, the method comprising:

determining if a way within the cache can be considered for replacement;

if the way can be considered for replacement, determining whether the way has already been accessed and therefore should be replaced; and

indicating, in order of preference, that a particular way should be replaced, that a particular way can be replaced, and that the replacement failed;

wherein, the cache memory comprises a plurality of entries arranged in a plurality of the ways, and wherein at least two of the ways have a different number of entries.

7. A method according to claim 6, wherein the cache memory implements a TLB, and wherein the entries for at least two of the ways translate different size pages.

8. A method according to claim 7, wherein the step of determining if a way can be considered for replacement includes determining a page size for which the way is configured to translate.

9. A method according to claim 6, wherein the cache memory is set-associative.

10. A method of maintaining a cache memory, the cache memory comprising a plurality of entries arranged in a plurality of ways, the method comprising:

providing a decay field in each of the entries;

updating the decay fields after each access to the cache memory in accordance with a decay replacement algorithm; and

replacing data in the cache corresponding to certain of the entries upon a cache miss based on the updated decay fields;

wherein, at least two of the ways have a different number of entries.

11. A method according to claim 10, wherein the cache memory implements a TLB, and wherein the entries for at least two of the ways translate different size pages.

12. A method according to claim 11, wherein the step of replacing data in the cache includes determining a page size for which the ways are configured to translate.

13. A method according to claim 10, wherein the cache memory is set-associative.

14. A method according to claim 10, wherein the step of updating the decay fields includes:

determining whether the decay fields of each of the plurality of entries, including an entry corresponding to a way just accessed, have all fully decayed;

if all decay fields have fully decayed, setting the decay fields of all entries except the entry of the way just accessed to an undecayed state;

if all decay fields are not fully decayed, decaying the decay field of the entry of the way just accessed.

15. A method according to claim 10, wherein the step of replacing data in the cache includes:

determining if a way within the cache can be considered for replacement;

if the way can be considered for replacement, determining whether the way has already been accessed and therefore should be replaced; and

indicating, in order of preference, that a particular way should be replaced, that a particular way can be replaced, and that the replacement failed.

16. A cache memory comprising:

a plurality of entries arranged in a plurality of ways;

a decay field in each of the entries;

means for updating the decay fields after each access to the cache memory in accordance with a decay replacement algorithm; and

means for replacing data in the cache corresponding to certain of the entries upon a cache miss based on the updated decay fields;

wherein, at least two of the ways have a different number of entries.

17. A cache memory according to claim 16, wherein the cache memory implements a TLB, and wherein the entries for at least two of the ways translate different size pages.

18. A cache memory according to claim 17, means for replacing data in the cache includes means for determining a page size for which the ways are configured to translate.

19. A cache memory according to claim 16, wherein the cache memory is set-associative.

20. A cache memory according to claim 16, wherein means for updating the decay fields includes:

means for determining whether the decay fields of each of the plurality of entries, including an entry corresponding to a way just accessed, have all fully decayed;

means for, if all decay fields have fully decayed, setting the decay fields of all entries except the entry of the way just accessed to an undecayed state;

means for, if all decay fields are not fully decayed, decaying the decay field of the entry of the way just accessed.

21. A cache memory according to claim 16, wherein the means for replacing data in the cache includes:

means for determining if a way within the cache can be considered for replacement;

means for, if the way can be considered for replacement, determining whether the way has already been accessed and therefore should be replaced; and

means for indicating, in order of preference, that a particular way should be replaced, that a particular way can be replaced, and that the replacement failed.

22. A cache memory comprising:

a plurality of entries arranged in a plurality of ways;

a decay field in each of the entries;

a plurality of inverters that invert a hit vector that indicates which one of the ways was just accessed;

a plurality of AND gates that combine the decay fields read from each of the entries and the inverted hit vector; and

a plurality of multiplexers that provide updated decay fields for each of the entries in accordance with the operation of the inverters and AND gate;

wherein, at least two of the ways have a different number of entries.

23. A cache memory according to claim 22, wherein the cache memory is set-associative.

24. A cache memory comprising:

a plurality of entries arranged in a plurality of ways;

a decay field in each of the entries;

a first input for receiving a replace vector indicating whether each of the ways can be replaced;

a second input for receiving a read vector structure comprising information from the decay fields;

a first logic stage that selects a first way that can be replaced based on a logical combination of bits in the replace vector;

a second logic stage that selects a second way that should be replaced based on a logical combination of bits in the read vector and the replace vector; and

a multiplexer that chooses between the first and second ways in accordance with a predetermined preference;

wherein, at least two of the ways have a different number of entries, and wherein the cache memory is set-associative.