# US 6,732,238 B1 · Set-associative cache memory having variable time decay rewriting algorithm

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,732,238 B1
- Document ID: US6732238B1
- Status: Granted
- Kind: B1
- Application number: 10/167,133
- Filed: 2002-06-10
- Granted: 2004-05-04
- Earliest claimed: 2001-06-08
- Assignees: Tensilica, Inc.
- Inventors: Marc Alan Evans; Pavlos Konas
- Web page: https://patentgrep.com/patent/US6732238B1

## CPC

- G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
- G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing
- G06F 12/128: adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
- G06F 12/1027: using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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

### Claim 5 (depends on 1)

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

### Claim 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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 6)

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

### Claim 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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 10)

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

### Claim 14 (depends on 10)

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.

### Claim 15 (depends on 10)

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.

### Claim 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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 16)

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

### Claim 20 (depends on 16)

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.

### Claim 21 (depends on 16)

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.

### Claim 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.

### Claim 23 (depends on 22)

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

### Claim 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.
