Replacement data error detector

Details Replacement data error detector Replacement data error detector

2001-05-01

2003-05-27

Yoo, Do Hyun (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S134000, C711S159000, C714S006130, C714S048000, C714S049000, C714S052000

Reexamination Certificate

active

06571317

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to the field of caches and, more particularly, to error checking of replacement data used with caches.
2. Description of the Related Art
Memories may generally be subject to both hard errors and soft errors. Hard errors occur when a memory storage cell or cells has failed such that the cell or cells do not actually store values any longer. Thus, a value written to the memory cell or cells may not be read from the memory cell or cells regardless of the amount of time between the write and the read or the presence/absence of other activity in or near the memory between the write and the read. Soft errors occur if the memory cell or cells have not failed, but some external event (e.g. noise from surrounding circuitry) or some natural phenomena (such as charge leakage from dynamic random access memories, or DRAMs) has changed the value stored in the memory cell or cells between the write and the read. In either case, the value read from the memory may not be the value expected in view of the preceding write.
In order to account for the possibility of error and, in some cases, recovery therefrom, various error checking and/or correction schemes have been used in the past. For example, parity checking has been used. With parity, an additional bit is stored with a value in memory. The additional bit is the exclusive-OR (or exclusive-NOR) of the bits of the value. When the value is read, the parity bit is also read and exclusive-ORed (or exclusive-NORed) with the value to detect an error. If a single bit has changed since the value and the parity bit were stored in the memory, the exclusive-OR results in a binary one and an error is detected. However, if multiple bits have changed, the changes can offset each other in the exclusive-OR and no error is detected.
Other, more elaborate error checking/correction schemes have also been used in which various overlapping subsets of the bits of a value are exclusive-ORed to produce an error checking/correction (ECC) code. Depending upon the number of bits in the ECC code as compared to the number of bits in the underlying values and further depending upon the selected overlapping subsets, enhanced error detection may be possible. Particularly, with ECC codes it may be possible not only to detect certain errors, but also to correct the data read from the memory for some errors. For example, ECC codes that allow for single bit error correction and double bit error detection are popular. However, even the ECC codes may not detect some errors (e.g. double or triple bit errors for the example above).
Cache memories may be subject to the above-mentioned errors. Cache memories generally include storage for data as well as tags identifying the address in main memory at which the cached data is stored. Furthermore, cache memories may often store replacement data used to select a cache entry for replacement when an access to the cache misses. Any of the data, tags, or replacement data may experience the above-mentioned errors.
Errors in the replacement data may impact performance. If the replacement data is in error, it is possible that one or more cache entries will never be selected for replacement (or at least will temporarily not be selected, still impacting performance). Effectively, the non-selected entries may not be used by the cache, reducing the overall effectiveness of the cache if the data currently stored therein is not being used by the device or devices served by the cache. However, the error detection schemes described above generally are not capable of detecting all possible errors in the replacement data. Furthermore, since the replacement data may frequently include relatively few bits, storing parity or ECC bits corresponding to the replacement data alone may be inefficient. Frequently, other data (e.g. the tags) may be grouped with the replacement data and error detection data (e.g. ECC or parity) may be calculated for the group as a whole. For example, one or two parity bits might be used to cover the tags and the replacement data of a set in a set associative cache. Thus, detection of errors in the replacement data may be hampered by the occurrence of errors in the other data within the group.
SUMMARY OF THE INVENTION
A cache is described which includes an error circuit for detecting errors in the replacement data. If an error is detected, the cache may update the replacement data to eliminate the error. For example, a predetermined, fixed value may be used for the update of the replacement data. Each of the cache entries corresponding to the replacement data may be represented in the fixed value. By eliminating the error in the replacement data, the performance impacts of the error may be reduced.
In one embodiment, the error circuit may detect errors in the replacement data using only the replacement data (e.g. no parity or ECC information may be used). In this manner, errors may be detected even in the presence of multiple bit errors which may not be detectable using parity/ECC checking. Furthermore, inefficiency which may result if parity/ECC were used for the replacement data may be avoided, as may grouping the replacement data with other data for covering with parity/ECC data.
Broadly speaking, a cache is contemplated comprising a memory configured to store replacement data corresponding to a plurality of cache entries and a circuit coupled to receive the replacement data from the memory. The circuit is configured to determine whether or not at least one of the plurality of cache entries is not represented in the replacement data.
Additionally, a method is contemplated. Replacement data corresponding to a plurality of cache entries is received. Whether or not at least one of the plurality of cache entries is not represented in the replacement data is determined.
Furthermore, a cache is contemplated, comprising a memory configured to store replacement data corresponding to a plurality of cache entries and a circuit coupled to receive the replacement data from the memory. The replacement data indicates an order of the plurality of cache entries for replacement. The circuit is configured to detect an error in the order if a different one of the plurality of cache entries is not indicated at each position in the order.
Moreover, a cache is contemplated. The cache includes a memory configured to store replacement data corresponding to a plurality of cache entries and a circuit coupled to receive the replacement data from the memory. The circuit is configured to decode the replacement data to detect an error therein.
Still further, a cache including a memory configured to store replacement data corresponding to a plurality of cache entries and a circuit coupled to receive the replacement data from the memory is contemplated. The circuit is configured to detect an error in the replacement data using only the replacement data.


REFERENCES:
patent: 3958228 (1976-05-01), Coombes et al.
patent: 4967414 (1990-10-01), Lusch et al.
patent: 5283876 (1994-02-01), Tague
patent: 5588112 (1996-12-01), Dearth et al.
patent: 5829024 (1998-10-01), Sato
patent: 5978952 (1999-11-01), Hayek et al.
patent: 5987585 (1999-11-01), Motoyama et al.
patent: 6101614 (2000-08-01), Gonzales et al.
patent: 6108753 (2000-08-01), Bossen et al.
patent: 6145057 (2000-11-01), Arimilli et al.
AM2960 Family Handbook Advanced Micro Device, Inc p. 39.*
SiByte, “Target Applications,” http://sibyte.com/mercurian/applications.htm, Jan. 15, 2001, 2 pages.
SiByte, “SiByte Technology,” http://sibyte.com/mercurian/technology.htm, Jan. 15, 2001, 3 pages.
SiByte, “The Mercurian Processor,” http://sibyte.com/mercurian, Jan. 15, 2001, 2 pages.
SiByte, “Fact Sheet,” SB-1 CPU, Oct. 2000, rev. 0.1, 1 page.
SiByte, “Fact Sheet,” SB-1250, Oct. 2000, rev. 0.2, 10 pages.
Stepanian, SiByte, SiByte SB-1 MIPS64 CPU Core, Embedded Processor Forum 2000, Jun. 13, 2000, 15 pages.
Jim Keller, “The Mercurian Processor: A High Performance, Power-Efficient CMP for Networking,” Oct. 10, 2000, 22 pages.
Patterson and H

Affiliated with

Also associated with

Rating

Replacement data error detector does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Replacement data error detector, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Replacement data error detector will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3027738