Method and apparatus for miss sequence cache block replacement utilizing a most recently used state
First Claim
1. A cache block replacement method used with a cache including a plurality of cache blocks in a computer system responsive to a cache miss comprising the steps of:
- checking for an invalid block;
responsive to identifying an invalid cache block, selecting said identified invalid block for replacement;
checking for a first priority cache block and not equal to most recently used (MRU) state;
responsive to identifying a first priority cache block and not equal to most recently used (MRU) state, selecting said identified first priority cache block not equal to most recently used (MRU) state for replacement;
checking for a next priority cache block and not equal to most recently used (MRU) state;
responsive to identifying a next priority cache block and not equal to most recently used (MRU) state, selecting said identified next priority cache block not equal to most recently used (MRU) state for replacement; and
in the absence of identifying an invalid cache block, a first priority cache block and not equal to most recently used (MRU) state, or a next priority cache block and not equal to most recently used (MRU) state, randomly selecting one of the plurality of cache blocks for replacement.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus are provided for miss sequence cache block replacement in a cache including a plurality of cache blocks in a computer system. First checking for an invalid block is performed. Responsive to identifying an invalid cache block, the identified invalid block is selected for replacement. If an invalid cache block is not found, then checking for a first priority cache block and not equal to most recently used (MRU) state is performed. Responsive to identifying a first priority cache block and not equal to most recently used (MRU) state, the identified first priority cache block is selected for replacement. If a first priority cache block and not equal to most recently used (MRU) state is not found, then checking for a next priority cache block and not equal to most recently used (MRU) state is performed. Responsive to identifying a next priority cache block and not equal to most recently used (MRU) state, the identified next priority cache block is selected for replacement. In the absence of identifying an invalid cache block, a first priority cache block and not equal to most recently used (MRU) state, or a next priority cache block and not equal to most recently used (MRU) state, one of the plurality of cache blocks is randomly selected for replacement. A tag field stores the most recently used (MRU) state information which is used to determine where not to replace a cache block in the cache.
-
Citations
20 Claims
-
1. A cache block replacement method used with a cache including a plurality of cache blocks in a computer system responsive to a cache miss comprising the steps of:
-
checking for an invalid block; responsive to identifying an invalid cache block, selecting said identified invalid block for replacement; checking for a first priority cache block and not equal to most recently used (MRU) state; responsive to identifying a first priority cache block and not equal to most recently used (MRU) state, selecting said identified first priority cache block not equal to most recently used (MRU) state for replacement; checking for a next priority cache block and not equal to most recently used (MRU) state; responsive to identifying a next priority cache block and not equal to most recently used (MRU) state, selecting said identified next priority cache block not equal to most recently used (MRU) state for replacement; and in the absence of identifying an invalid cache block, a first priority cache block and not equal to most recently used (MRU) state, or a next priority cache block and not equal to most recently used (MRU) state, randomly selecting one of the plurality of cache blocks for replacement. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. Apparatus for cache block replacement responsive to a cache miss in a cache including a plurality of cache blocks in a computer system comprising:
-
a cache directory for storing cache block address tags and a most recently used (MRU) state field, each of said cache block address tags including a cache block state field, means for checking said cache directory for an invalid block; means responsive to identifying an invalid cache block, for selecting said identified invalid block for replacement; means for checking said cache directory for a first priority cache block and not equal to most recently used (MRU) state; means responsive to identifying a first priority cache block and not equal to most recently used (MRU) state, for selecting said identified first priority cache block not equal to most recently used (MRU) state for replacement; means for checking said cache directory for a next priority cache block and not equal to most recently used (MRU) state; means responsive to identifying a next priority cache block and not equal to most recently used (MRU) state, for selecting said identified next priority cache block not equal to most recently used (MRU) state for replacement; and means responsive to the absence of identifying an invalid cache block, a first priority cache block and not equal to most recently used (MRU) state, or a next priority cache block and not equal to most recently used (MRU) state, for randomly selecting one of the plurality of cache blocks for replacement. - View Dependent Claims (11, 12, 13, 14)
-
-
15. A computer system comprising:
-
a processor; a cache coupled to said processor, said cache including a plurality of cache blocks; a plurality of input/output devices; a bus connecting said processor and said plurality of input/output devices; a cache directory for storing cache block address tags and a most recently used (MRU) state field, said cache block address tags including a cache block state field, means, responsive to a cache miss, for checking said cache directory for an invalid block; means responsive to identifying an invalid cache block, for selecting said identified invalid block for replacement; means for checking said cache directory for a first priority cache block and not equal to most recently used (MRU) state; means responsive to identifying a first priority cache block and not equal to most recently used (MRU) state, for selecting said identified first priority cache block not equal to most recently used (MRU) state for replacement; means for checking said cache directory for a next priority cache block and not equal to most recently used (MRU) state; means responsive to identifying a next priority cache block and not equal to most recently used (MRU) state, for selecting said identified next priority cache block not equal to most recently used (MRU) state for replacement; and means responsive to the absence of identifying an invalid cache block, a first priority cache block and not equal to most recently used (MRU) state, or a next priority cache block and not equal to most recently used (MRU) state, for randomly selecting one of the plurality of cache blocks for replacement. - View Dependent Claims (16, 17, 18)
-
-
19. Apparatus for cache block replacement in a computer system comprising:
-
a cache including a plurality of cache blocks; a cache controller for implementing a cache block replacement method responsive to a cache miss;
said cache controller including;a cache directory storing cache block address tags and a most recently used (MRU) state field, each of said cache block address tags including a cache block state field, each said cache block state field storing one cache block state, one of five states being stored in said cache block state field for each cache block, said five states including invalid, shared-modified, shared, exclusive and modified said cache controller utilizing said most recently used (MRU) state field and said stored cache block state for selecting a cache block for replacement; and wherein priorities are assigned to said five states for selecting a cache block for replacement and wherein an invalid state is assigned a highest priority. - View Dependent Claims (20)
-
Specification