US4967414A
Expired / Lapsed
US
⏱️ 0.0 years remaining
LRU error detection using the collection of read and written LRU bits
Assignee: International Business Machines Corp
•
Filing: 1989-01-06
•
Granted: 1990-10-30
•
Expires: 2009-01-06
Abstract
Abstract At least-recently used (LRU) storage means and its associated logic maintain usage history for associativity class entries of a cache directory. The storage means includes an independent storage array for each of the bit positions of an LRU binary code pattern. Parity bits are provided in the arrays for each LRU bit. Separate read/write controls simultaneously write updated LRU bits to some of the arrays and read out unchanged LRU bits from the remaining arrays during updating of a usage history entry when its associativity class is used. Pattern checking logic collects the update bits and the unchanged bits during the update cycle to determine whether or not the new entry is a valid LRU combination. A parity bit is written with each of the update LRU bits written into the arrays and parity bits are read out from the arrays with the unchanged LRU bits for parity checking of each unchanged LRU bit during updating of usage history entries.
Inventors
- 👤 Robert F. Lusch
- 👤 Jeffrey J. Dulzo
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 17:43
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/12; G06F12/121; G06F12/123; G06F12/125; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1008; G06F11/1064; G06F2212/00; G06F2212/10; G06F2212/1032
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
180 words
A system for producing and error checking a binary code pattern signifying the order of replacement of units in a plurality of units randomly used in sequence, comprising a plurality of storage elements, one for each logical bit in the pattern, for storing the pattern; means associated with each of the units for producing signals indicating the use of the associated unit; logic means, connected to the storage elements and to the signal producing means, for producing update bits for only certain of the pattern bits; separate read/write controls connected to the signal producing means, for each storage element, for writing the update bits into only certain of said storage elements in accordance with said use signals and for reading unchanged pattern bits from the storage elements other than said certain elements; means, connected to the logic means and to the storage elements, for collecting the updated pattern bits from the logic means and unchanged pattern bits from the storage elements; and pattern checking means connected to the collecting means for determining the validity or non-validity of the collected pattern.
Claim 2
Independent Claim
180 words
A system for producing and error checking a binary code pattern signifying the order of replacement of units in a plurality of units randomly used in sequence, comprising a plurality of storage elements, one for each logical bit in the pattern, for storing the pattern; means associated with each of the units for producing signals indicating the use of the associated unit; logic means, connected to the storage elements and to the signal producing means, for producing update bits for only certain of the pattern bits; separate read/write controls connected to the signal producing means, for each storage element, for writing the update bits into only certain of said storage elements in accordance with said use signals and for reading unchanged pattern bits from the storage elements other than said certain elements; means, connected to the logic means and to the storage elements, for collecting the updated pattern bits from the logic means and unchanged pattern bits from the storage elements; and pattern checking means connected to the collecting means for determining the validity or non-validity of the collected pattern.
Claim 3
Dependent Claim
17 words
The system of claim 1 wherein the reading and writing of the storage elements is performed concurrently.
Claim 4
Dependent Claim
163 words
In a system for producing a binary code signifying the order of use of units in a plurality of units randomly utilized in sequence including storage means for said binary code having separately selectable storage elements, one for each logical bit in the binary code, means associated with each of the units for producing signals indicating use of the associated unit, and logic means, connected to the storage elements and to the signal producing means, for updating only selected ones of the storage elements in accordance with said use signals, the combination therewith of apparatus for checking the validity of each updated binary code comprising means, connected to the storage elements and to the logic means, for collecting updated binary code bits from the logic means and unchanged binary code bits from the non-selected storage elements during updating of the storage elements; and pattern checking means connected to the collecting means for determining the validity of the collected bits as a binary code.
Claim 5
Dependent Claim
163 words
In a system for producing a binary code signifying the order of use of units in a plurality of units randomly utilized in sequence including storage means for said binary code having separately selectable storage elements, one for each logical bit in the binary code, means associated with each of the units for producing signals indicating use of the associated unit, and logic means, connected to the storage elements and to the signal producing means, for updating only selected ones of the storage elements in accordance with said use signals, the combination therewith of apparatus for checking the validity of each updated binary code comprising means, connected to the storage elements and to the logic means, for collecting updated binary code bits from the logic means and unchanged binary code bits from the non-selected storage elements during updating of the storage elements; and pattern checking means connected to the collecting means for determining the validity of the collected bits as a binary code.
Claim 6
Dependent Claim
62 words
The combination of claim 3 wherein the collecting means comprises a register for storing collected binary code bits, and multiplexor means responsive to the logic means for transferring to the register (1) logical bits from the logic means used to update said selected storage elements and (2) logical bits from non-selected storage elements, said pattern checking means being connected to the register.
Claim 7
Dependent Claim
65 words
The combination of claim 3 further comprising means, connected to the storage elements and to the logic means for producing and storing a parity bit for each updated binary code bit; and means, connected to the storage elements and to the logic means, for checking the parity of the parity and binary code bits of the unselected storage elements during updating of the storage elements.
Claim 8
Dependent Claim
240 words
In a system for producing and error checking a binary code pattern signifying the order of use of units in a plurality of units randomly utilized in sequence, including storage means for said binary code pattern having separately selectable storage elements, one for each logical bit in the binary code pattern, means associated with each of the units for producing signals indicating use of the associated unit, first logic means, connected to the storage elements and to the signal producing means, for creating updated binary code pattern bits for storage in only selected ones of the storage elements in accordance with said use signals, and second logic means, connected to the storage elements and to the signal producing means, for writing the updated binary code pattern bits into said selected storage elements, the combination therewith of apparatus for checking the validity of each updated binary code pattern during updating, comprising said second logic means including means for applying Write signals to the selected storage elements and Read signals to the non-selected storage elements during updating of the binary code pattern, means, connected to the storage elements and to the first and second logic means, for collecting updated binary code pattern bits from the first logic means and unchanged binary code pattern bits from the non-selected storage elements, and pattern checking means connected to the collecting means for determining whether or not the collected bits form a valid binary code pattern.
Claim 9
Dependent Claim
240 words
In a system for producing and error checking a binary code pattern signifying the order of use of units in a plurality of units randomly utilized in sequence, including storage means for said binary code pattern having separately selectable storage elements, one for each logical bit in the binary code pattern, means associated with each of the units for producing signals indicating use of the associated unit, first logic means, connected to the storage elements and to the signal producing means, for creating updated binary code pattern bits for storage in only selected ones of the storage elements in accordance with said use signals, and second logic means, connected to the storage elements and to the signal producing means, for writing the updated binary code pattern bits into said selected storage elements, the combination therewith of apparatus for checking the validity of each updated binary code pattern during updating, comprising said second logic means including means for applying Write signals to the selected storage elements and Read signals to the non-selected storage elements during updating of the binary code pattern, means, connected to the storage elements and to the first and second logic means, for collecting updated binary code pattern bits from the first logic means and unchanged binary code pattern bits from the non-selected storage elements, and pattern checking means connected to the collecting means for determining whether or not the collected bits form a valid binary code pattern.
Claim 10
Dependent Claim
75 words
The combination of claim 6 wherein the collecting means comprises a register for storing collected binary code pattern bits, and multiplexor means responsive to the Write and Read signals for transferring to the register (1) logical bits from the first logic means used to update said selected storage elements and (2) non-changed logical bits from non-selected storage elements to form a new, updated binary code pattern, said pattern checking means being connected to the register.
Claim 11
Dependent Claim
59 words
The combination of claim 7 further comprising means, connected to the first logic means and to the storage elements, for producing and storing parity bits in selected storage elements during updating; and means, connected to the second logic means and to the storage elements, for checking the parity of the bits read from the unselected storage elements during updating.
References Cited (Backward Citations)
US4323968A
Cited
US4298929A
Cited
US4490782A
Cited
US4483003A
Cited
US4807110A
Cited
US4835686A
Cited
US4831625A
Cited
US4833601A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-10-29 | 1994-04-30 | 1994-10-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-10-29 | 1998-04-30 | 1998-10-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-10-29 | 2002-04-30 | 2002-10-30 | $7700.00 | Window Closed / Lapsed |