Optimizing a cache eviction mechanism by selectively introducing different levels of randomness into a replacement algorithm
First Claim
1. A method of improving operation of a cache used by a processor of a computer system, comprising the steps of:
- providing a cache-replacement control unit to select a cache block for eviction from among a plurality of blocks in the cache;
selectively introducing a first level of randomness into a replacement algorithm used by the cache-replacement control unit;
evicting cache blocks according to the replacement algorithm using the first level of randomness;
selectively introducing a second level of randomness into the replacement algorithm; and
evicting cache blocks according to the replacement algorithm using the second level of randomness.
3 Assignments
0 Petitions
Accused Products
Abstract
A method of improving operation of a cache used by a processor of a computer system by introducing a level of randomness into a replacement algorithm used by the cache in order to lessen "strides" within the cache is disclosed. Different levels of randomness may be introduced into the replacement algorithm at different times to optimize the cache for different procedures running on the processor. The level of randomness can be selectively introduced by using a basic replacement algorithm to select a subset of a congruence class, and one or more random bits are then used to select a specific cache block within the subset for eviction. The basic replacement algorithm can be a least recently used algorithm. There may be three levels of randomness for a 4-way set associative cache, and there may be four levels of randomness for an 8-way set associative cache.
-
Citations
17 Claims
-
1. A method of improving operation of a cache used by a processor of a computer system, comprising the steps of:
-
providing a cache-replacement control unit to select a cache block for eviction from among a plurality of blocks in the cache; selectively introducing a first level of randomness into a replacement algorithm used by the cache-replacement control unit; evicting cache blocks according to the replacement algorithm using the first level of randomness; selectively introducing a second level of randomness into the replacement algorithm; and evicting cache blocks according to the replacement algorithm using the second level of randomness. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer system comprising:
-
a processor; a memory device; a cache connected to said processor and said memory device, having a plurality of cache blocks for storing memory blocks corresponding to addresses of said memory device; and a cache-replacement control unit having means for selecting a cache block for eviction from among a plurality of blocks in the cache, including means for selectively introducing at least two different levels of randomness into a replacement algorithm used by said cache-replacement control unit. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A computer system comprising:
-
a processor; a memory device; a cache connected to said processor and said memory device, having a plurality of cache blocks for storing memory blocks corresponding to addresses of said memory device; and a cache-replacement control unit having means for selecting a cache block for eviction from among a plurality of blocks in the cache, including means for selectively introducing a level of randomness into a replacement algorithm used by said cache-replacement control unit, wherein said level of randomness is selectively introduced by using a basic replacement algorithm to select a subset of a congruence class, and one or more random bits are used to select a specific cache block within the subset for eviction.
-
Specification