Balanced P-LRU tree for a “multiple of 3” number of ways cache
US9348766B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 21, 2011 |
| Grant date | May 24, 2016 |
| Priority date | — |
| Expiry date | Aug 14, 2032 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/125
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 “multipl…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.