Patent ID: 6041390
Filing Date: 2000-03-21
Classification: G06F

Abstract:
A cache memory, comprising:a plurality of cache lines;a plurality of token registers connected in a loop configuration, wherein each of said plurality of token registers is associated with a respective one of said plurality of cache lines;a plurality of K-bit memory cells, wherein each of said plurality of K-bit memory cells is associated with a respective one of said plurality of cache lines;a plurality of V-bit memory cells, wherein each of said plurality of V-bit memory cells is associated with a respective one of said plurality of cache lines; anda token for indicating a candidate cache line for cache-line replacement, wherein said token resides within one of said plurality of token registers having its associated V-bit memory cell set to a first state, wherein said token moves to another one of said plurality of token registers when said associated V-bit memory cell changes to a second state, wherein said token skips a token register associated with a cache line when its associated K-bit memory cell is in a first state.