Balanced P-LRU tree for a “multiple of 3” number of ways cache

Patent metadata

Field	Value
Publication number	US-9348766-B2
Application number	US-201113994690-A
Country	US
Kind code	B2
Filing date	Dec 21, 2011
Priority date	Dec 21, 2011
Publication date	May 24, 2016
Grant date	May 24, 2016

Abstract

In accordance with embodiments disclosed herein, there are provided methods, systems, mechanisms, techniques, and apparatuses for implementing a balanced P-LRU tree for a “multiple of 3” number of ways cache. For example, in one embodiment, such means may include an integrated circuit having a cache and a plurality of ways. In such an embodiment the plurality of ways include a quantity that is a multiple of three and not a power of two, and further in which the plurality of ways are organized into a plurality of pairs. In such an embodiment, means further include a single bit for each of the plurality of pairs, in which each single bit is to operate as an intermediate level decision node representing the associated pair of ways and a root level decision node having exactly two individual bits to point to one of the single bits to operate as the intermediate level decision nodes representing an associated pair of ways. In this exemplary embodiment, the total number of bits is N−1, wherein N is the total number of ways in the plurality of ways. Alternative structures are also presented for full LRU implementation, a “multiple of 5” number of cache ways, and variations of the “multiple of 3” number of cache ways.

First claim

The invention claimed is:

1. An integrated circuit comprising:
a plurality of ways of cache, wherein the plurality of ways comprises a quantity that is a multiple of three and not a power of two, and wherein the plurality of ways are organized into a plurality of pairs;
a single bit for each of the plurality of pairs, wherein each single bit is to operate as an intermediate level decision node representing the associated pair of ways;
a root level decision node comprised of exactly two individual bits to point to one of the single bits to operate as the intermediate level decision node representing an associated pair of ways; and
wherein a total number of bits of the decision nodes is N−1, wherein N is a total number of ways in the plurality of ways and the decision nodes to determine which of the plurality of ways of cache to use.

2. The integrated circuit of claim 1 , wherein each of the plurality of ways comprises a stored cache element within the cache.

3. The integrated circuit of claim 1 , wherein the plurality of ways are arranged into a tree structure which is symmetrically balanced.

4. The integrated circuit of claim 1 , wherein the root level decision node comprised of exactly two individual bits points to one of a leftmost, center, or rightmost single bit at the intermediate level, each of the leftmost, center, and rightmost single bits corresponding to one of the intermediate level decision nodes representing one of the plurality of pairs of ways.

5. The integrated circuit of claim 1 , wherein the root level decision node comprised of exactly two individual bits comprises an information capacity to store values of 00, 01, 10, and 11, and wherein each of three of the values uniquely identify one of three of the single bits to operate as the intermediate level decision nodes, and wherein a fourth of the values is not used.

6. The integrated circuit of claim 1 :
wherein the plurality of pairs are organized as at least:
a group A having a first pair of ways,
a group B having a second pair of ways, and
a group C having a third pair of ways;

wherein a first of the single bits to operate as the intermediate level decision nodes representing one of the plurality of pairs of ways comprises a leftmost single-bit decision node of a branch to represent group A having the first pair of ways;
wherein a second of the single bits to operate as the intermediate level decision nodes representing one of the plurality of pairs of ways comprises a middle single-bit decision node of the branch to represent group B having the second pair of ways;
wherein a third of the single bits to operate as the intermediate level decision nodes representing one of the plurality of pairs of ways comprises a rightmost single-bit decision node of the branch to represent group C having the first pair of ways;
wherein the root level decision node comprised of exactly two individual bits comprises legal values of 00, 01, and 10, and an illegal value of 11;
wherein 00 maps to the leftmost single-bit decision node of the branch representing group A;
wherein 01 maps to the middle single-bit decision node of the branch representing group B;
wherein 10 maps to the rightmost single-bit decision node of the branch representing group C; and
wherein cache update or hit operations and cache replace operations conform to the following rules:
a cache update or hit operation to group A writes a value of 00 into the two bits of the root level decision node;
a cache update or hit operation to group B writes a value of 01 into the two bits of the root level decision node;
a cache update or hit operation to group C writes a value of 10 into the two bits of the root level decision node;
a cache replace operation given a present value of 00 for the root level decision node replaces a way in group B;
a cache replace operation given a present value of 01 for the root level decision node replaces a way in group C; and
a cache replace operation given a present value of 00 for the root level decision node replaces a way in group A.

7. The integrated circuit of claim 1 , wherein the integrated circuit comprises a central processing unit for one of a tablet computing device or a smartphone.

8. An integrated circuit comprising:
a plurality of ways of cache, wherein the plurality of ways comprises a quantity that is a multiple of three and not a power of two, and wherein the plurality of ways are organized into a subgroups of three ways each;
an intermediate level decision node representing each of the subgroups of three ways, wherein each intermediate level decision node comprises exactly two individual bits to point to one of the three ways in the subgroup associated with the intermediate level decision node;
a root level decision node having exactly one single bit to point to one of two subordinate decision nodes; and
wherein a total number of bits of the decision nodes is N−1, wherein N is a total number of ways in the plurality of ways and the decision nodes to determine which of the plurality of ways of cache to use.

9. The integrated circuit of claim 8 , wherein each of the plurality of ways comprises a stored cache element within the cache.

10. The integrated circuit of claim 8 , wherein the plurality of ways are arranged into a tree structure which is symmetrically balanced.

11. The integrated circuit of claim 8 , wherein the root level decision node having exactly one single bit to point to one of two subordinate decision nodes comprises one of:
pointers to the two subordinate decision nodes, wherein each of the subordinate decision nodes comprise exactly one single bit each to point to additional subordinate nodes at a tree structure level superior to the intermediate level occupied by the intermediate level decision nodes representing each of the subgroups of three ways; or
pointers to the two subordinate decision nodes, wherein each of the subordinate decision nodes point directly to one of the intermediate level decision nodes representing each of the subgroups of three ways.

12. The integrated circuit of claim 8 , wherein each intermediate level decision node representing an associated one of the subgroups of three ways and having the exactly two individual bits to point to one of the three ways in the associated subgroup comprises an information capacity of four unique values via the exactly two individual bits.

13. The integrated circuit of claim 12 , wherein the four unique values of the intermediate level decision node are 00, 01, 10, and 11, and wherein:
unique value 00 maps to a leftmost way of the three ways in the subgroup associated with the intermediate level decision node;
unique value 01 maps to a middle way of the three ways in the subgroup associated with the intermediate level decision node;
unique value 10 maps to a rightmost way of the three ways in the subgroup associated with the intermediate level decision node; and
unique value 11 is an unused value.

14. The integrated circuit of claim 12 , wherein a cache hit or cache update associated with one of the intermediate level decision nodes causes the intermediate level decision node to point to a next way among the three associated ways to the right of the way subject to the cache hit or cache update.

15. The integrated circuit of claim 12 , wherein the integrated circuit implements a cache memory circuit for one of a tablet computing device or a smartphone.

16. An integrated circuit comprising:
a plurality of ways of cache, wherein the plurality of ways comprises a quantity that is a multiple of three and not a power of two, and whe

Assignees

• Basel Adi
• Hildesheim Gur
• Raikin Shlomo
• Chappell Robert
• Kim Ho-Seop
• Bhatia Rohit
• Intel Corp

Inventors

• Basel Adi
• Hildesheim Gur
• Raikin Shlomo
• Chappell Robert
• Kim Ho-Seop
• Bhatia Rohit

Classifications

• G06F12/124 Primary

  being minimized, e.g. non MRU · CPC title

• G06F12/125

  being generated by decoding an array or storage · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F12/0864

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

• G06F12/00

  Accessing, addressing or allocating within memory systems or architectures (digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06) · CPC title