US6041390A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Token mechanism for cache-line replacement within a cache memory having redundant cache lines
Assignee: International Business Machines Corp
•
Filing: 1996-12-23
•
Granted: 2000-03-21
•
Expires: 2016-12-23
Abstract
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.
Inventors
- 👤 Peichun Peter Liu
- 👤 Rajinder Paul Singh
- 👤 Shih-Hsiung Steve Tung
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 22:11
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/12; G06F12/121
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
175 words
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; and a 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.
Claim 2
Dependent Claim
175 words
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; and a 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.
Claim 3
Dependent Claim
20 words
The cache memory according to claim 1, wherein said first state for said V-bit memory cell is a logical "0."
Claim 4
Dependent Claim
20 words
The cache memory according to claim 1, wherein said first state for said K-bit memory cell is a logical "1."
Claim 5
Dependent Claim
45 words
The cache memory according to claim 1, wherein said cache memory further includes an allocation-indicating circuit for indicating a line allocation procedure is in progress in a cache line such that said token will not reside in a token ring associated with said cache line.
Claim 6
Dependent Claim
38 words
The cache memory according to claim 1, wherein said cache memory further includes a plurality of fuse decoders, wherein each of said plurality of fuse decoders is associated with a respective one of said plurality of cache lines.
Claim 7
Dependent Claim
32 words
The cache memory according to claim 5, wherein said token will not reside in a token register of a cache line when a fuse decoder associated with said cache line is set.
Claim 8
Dependent Claim
32 words
The cache memory according to claim 1, wherein said cache memory further includes a means for replacing a cache line within said cache memory in response to a location of said token.
Claim 9
Dependent Claim
183 words
A data-processing system, comprising: a cache memory, wherein said cache memory includes 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; and a 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.
Claim 10
Dependent Claim
183 words
A data-processing system, comprising: a cache memory, wherein said cache memory includes 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; and a 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.
Claim 11
Dependent Claim
20 words
The data-processing system according to claim 8, wherein said first state for said V-bit memory cell is a logical "0."
Claim 12
Dependent Claim
20 words
The data-processing system according to claim 8, wherein said first state for said K-bit memory cell is a logical "1."
Claim 13
Dependent Claim
45 words
The data-processing system according to claim 8, wherein said cache memory further includes an allocation-indicating circuit for indicating a line allocation procedure is in progress in a cache line such that said token will not reside in a token register associated with said cache line.
Claim 14
Dependent Claim
38 words
The data-processing system according to claim 8, wherein said cache memory further includes a plurality of fuse decoders, wherein each of said plurality of fuse decoders is associated with a respective one of said plurality of cache lines.
Claim 15
Dependent Claim
31 words
The data-processing system according to claim 8, wherein said token will not reside in token register of a cache line when a fuse decoder associated with said cache line is set.
Claim 16
Dependent Claim
32 words
The data-processing system according to claim 8, wherein said cache memory further includes a means for replacing a cache line within said cache memory in response to a location of said token.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-21 | 2003-09-20 | 2004-03-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-21 | 2007-09-20 | 2008-03-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-21 | 2011-09-20 | 2012-03-21 | $7700.00 | Window Closed / Lapsed |