Caching method for selecting data blocks for removal from cache based on recall probability and size
US6742084B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | May 4, 2000 |
| Grant date | May 25, 2004 |
| Priority date | — |
| Expiry date | May 4, 2020 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/122
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A caching method for selecting variable size data blocks for replacement or removal from a cache includes determining the size and the unreferenced time interval of each block in the cache. The size of a block is the amount of cache space taken up by the block. The unreferenced time interval of a block is the time that has elapsed since the block was last accessed, and may be determined using a least recently used (LRU) algorithm. The recall probability of each block in the cache is then determined. The recall probability of a block is a function of its unreferenced time interval and possibly size and other auxiliary parameters. The caching method then determines a quality factor (q) for each block. The (q) of a block is a function of its recall probability and size. The caching method concludes with removing from the cache the block with the lowest (q). Various formulas or methods for determining the quality factor may be chosen so as to minimize the quantity of data that must be staged, minimize mean response time, or maximize the cache hit ratio.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.