METHOD AND SYSTEM FOR INSERTING CACHE BLOCKS
First Claim
1. A method of inserting cache blocks into a cache queue, comprising:
- detecting, by a processor, a first cache miss for the cache queue;
identifying, by the processor, a storage block receiving an access in response to the cache miss;
calculating, by the processor, a first estimated cache miss cost for a first storage container comprising the storage block;
calculating, by the processor, an insertion probability for the first storage container based on a mathematical formula of the first estimated cache miss cost;
randomly selecting an insertion probability number from a uniform distribution, wherein the insertion probability exceeds the insertion probability number; and
inserting, in response to the insertion probability exceeding the insertion probability number, a new cache block corresponding to the storage block into the cache queue.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of inserting cache blocks into a cache queue includes detecting a first cache miss for the cache queue, identifying a storage block receiving an access in response to the cache miss, calculating a first estimated cache miss cost for a first storage container that includes the storage block, calculating an insertion probability for the first storage container based on a mathematical formula of the first estimated cache miss cost, randomly selecting an insertion probability number from a uniform distribution, and inserting, in response to the insertion probability exceeding the insertion probability number, a new cache block corresponding to the storage block into the cache queue.
56 Citations
20 Claims
-
1. A method of inserting cache blocks into a cache queue, comprising:
-
detecting, by a processor, a first cache miss for the cache queue; identifying, by the processor, a storage block receiving an access in response to the cache miss; calculating, by the processor, a first estimated cache miss cost for a first storage container comprising the storage block; calculating, by the processor, an insertion probability for the first storage container based on a mathematical formula of the first estimated cache miss cost; randomly selecting an insertion probability number from a uniform distribution, wherein the insertion probability exceeds the insertion probability number; and inserting, in response to the insertion probability exceeding the insertion probability number, a new cache block corresponding to the storage block into the cache queue. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method of inserting cache blocks into a cache queue, comprising:
-
calculating an estimated cache miss cost for a cache block within the cache queue; evicting the cache block from the cache queue; inserting an entry for a storage block corresponding to the cache block into a shadow list corresponding to the cache queue; detecting, by a processor, a cache miss for the cache queue referencing the storage block; accessing, in response to the cache miss, the entry within the shadow list; calculating, based on a mathematical formula of a plurality of estimated old cache miss costs for cache blocks evicted from the cache queue, an estimated cache miss cost threshold; and inserting, in response to the estimated cache miss cost exceeding the estimated cache miss cost threshold, a new cache block corresponding to the storage block into the cache queue. - View Dependent Claims (10, 11)
-
-
12. A computer readable storage medium storing a plurality of instructions for inserting cache blocks into a cache queue, the plurality of instructions comprising functionality to:
-
detect a cache miss for the cache queue; identify a storage block receiving an access in response to the cache miss; calculate a first estimated cache miss cost for a first storage container comprising the storage block; calculate, based on a mathematical formula of the first estimated cache miss cost, an insertion probability for the first storage container; randomly select an insertion probability number from a uniform distribution, wherein the insertion probability exceeds the insertion probability number; and insert, in response to the insertion probability exceeding the insertion probability number, a new cache block corresponding to the storage block into the cache queue. - View Dependent Claims (13, 14, 15, 16)
-
-
17. A system for inserting cache blocks, comprising:
-
a cache queue, comprising; a probationary segment at an end of the cache queue, and a protected segment adjacent to the probationary segment; and a cache manager executing on a processor and configured to; detect a cache miss for the cache queue; identify a storage block receiving an access in response to the cache miss; calculate an estimated cache miss cost for a storage container comprising the storage block; calculate, based on a mathematical formula of the estimated cache miss cost, an insertion probability for the storage container; randomly select a probability number from a uniform distribution, wherein the insertion probability exceeds the probability number; and insert, in response to the insertion probability exceeding the probability number, a new cache block corresponding to the storage block into the cache queue at a beginning of the probationary segment. - View Dependent Claims (18, 19, 20)
-
Specification