Token mechanism for cache-line replacement within a cache memory having

Abstract

A mechanism for cache-line replacement within a cache memory having redundant cache lines is disclosed. In accordance with a preferred embodiment of the present invention, the mechanism comprises a token, a multiple of token registers, multiple allocation-indicating circuits, multiple bypass circuits, and a circuit for replacing a cache line within the cache memory in response to a location of the token. Incidentally, the token is utilized to indicate a candidate cache line for cache-line replacement. The token registers are connected in a ring configuration, and each of the token registers is associated with a cache line of the cache memory, including all redundant cache lines. Normally, one of these token registers contains the token. Each token register has an allocation-indicating circuit. An allocation-indicating circuit is utilized to indicate whether or not an allocation procedure is in progress at the cache line with which the allocation-indicating circuit is associated. Each token register also has a bypass circuit. A bypass circuit is utilized to transfer the token from one token register to an adjacent token circuit in response to an indication from the associated allocation-indicating circuit.