Cache remapping using synonym classes

What is claimed:

1. In a cache unit adapted for use with a memory used for storing a plurality of data values in a digital processor system, a method for storing said plurality or data values in said memory using said cache trait, said cache trait including:

a plurality of congruence classes each for storing a different one of said plurality of data values in said cache unit, and

a synonym class including ones of said plurality of congruence classes, each of said ones of said congruence classes addressed by a first address field which is identical in each of said ones of said congruence classes and a second address field which differs in each of said ones of said congruence classes,

wherein at least one of said plurality of congruence classes included in said synonym class is an inoperative congruence class, the method comprising the steps of:

(a) determining that one of said plurality of congruence classes is said inoperative congruence class;

(b) selecting a further one of said plurality of congruence classes included in said synonym class as an alternate congruence class to substitute for said inoperative congruence class;

(c) storing a synonym class data value in a location associated with said inoperative congruence class to identify said inoperative congruence class as being inoperative;

(d) storing a further data value in a further location associated with said inoperative congruence class to identify said alternate congruence class as a substitute for said inoperative congruence class;

(e) storing a congruence class data value in a location associated with said alternate congruence class to identify said alternate congruence class as said alternate congruence class;

(f) initiating storage of one of said plurality of data values to a memory location in said memory;

(g) determining that said one of said plurality of data values is intended to be stored in a cache location in said cache unit corresponding to said memory location if, in step (f) a cache hit results, wherein said cache location is said inoperative congruence class;

(h) storing said one of said plurality of data values into said alternate congruence class by accessing said further data value in said further location associated with said inoperative congruence class;

(i) transferring said one of said plurality of data values from said alternate congruence class to said memory location which corresponds to said inoperative congruence class;

(j) determining that said one of said plurality of data values is not intended to be stored in said cache unit if in step (f) a cache miss occurs and then performing one of 1) storing said one of said plurality of data values in said memory without storing said one of said plurality of data values in said cache unit and 2) allocating said cache location in said cache unit to receive said one of said plurality of data values.

2. A method in accordance with claim 1, in which the cache unit has a cache directory with a plurality of entries, further comprising the step of setting an indicator within said cache directory in one of said entries which is associated with said alternate congruence class when said data are stored in said alternate congruence class.

3. A method in accordance with claim 1, further comprising the steps of:

(g) identifying a further request to retrieve said data from said inoperative congruence class; and

(h) retrieving said data from said alternate congruence class in response to said further request.

4. A method in accordance with claim 3 in which the system has a cache directory with a plurality of entries, each entry associated with a respective one of said plurality of congruence classes, in which step (h) comprises the steps of:

selecting one of said entries which is associated with said disabled congruence class;

retrieving from said selected entry a value which identifies a further entry that is associated with said alternate congruence class;

determining whether said further entry contains a value associated with said inoperative congruence class; and

fetching said data from said alternate congruence class only if said field contains said value associated with said disabled congruence class.

5. A method in accordance with claim 1 which includes the further steps of:

using a real address to determine, for which congruence class, storage is requested when transferring said data to said cache unit; and

using said real address to determine from which congruence class said data is subsequently retrieved.

6. A method in accordance with claim 1 which includes the further steps of:

using a virtual address to determine, for which congruence class, storage is requested when transferring said data to said cache unit; and

using said virtual address to determine from which congruence class said data are subsequently retrieved.

7. A cache unit for providing rapid access to a memory used for storing a plurality of data values, said cache unit comprising:

(a) congruence class means including a plurality of congruence classes,

(b) synonym class means including a synonym class, said synonym class including ones of said plurality of congruence classes, each of said ones of said congruence classes addressed by a first address field which is identical in each of said ones of said congruence classes and a second address field which differs in each of said ones of said congruence classes;

(c) identifying means for determining that one of said plurality of congruence classes is an inoperative congruence class;

(d) means for selecting a further one of said congruence classes included in said synonym class as an alternate congruence class to substitute for said inoperative congruence class;

(e) storage means including a location associated with said inoperative congruence class for receiving a synonym class data value which identifies said inoperative congruence class as being inoperative;

(f) further storage means, including a further location associated with said inoperative congruence class, for receiving a further data value which identifies said alternative congruence class as a substitute for said inoperative congruence class;

(g) means for storing a congruence class data value in a location associated with said alternate congruence class to identify said alternate congruence class as said alternate congruence class;

(h) means for initiating storage of one of said plurality of data values to a memory location in said memory;

(i) means for determining that said one of said plurality of data values is intended to be stored in a cache location in said cache unit corresponding to said memory location if a cache hit results, wherein said cache location is said inoperative congruence class;

(j) means, responsive to said cache hit, for storing one of said plurality of said data values into said alternate congruence class;

(k) means for transferring said one of said plurality of data values from said alternate congruence class to said memory location which corresponds to said inoperative congruence class; and

(l) means for determining that said one of said plurality of data values is not intended to be stored in said cache unit and for then performing one of 1) storing said one of said plurality of data values in said memory without storing said one of said plurality of data values in said cache unit if a cache miss occurs and 2) allocating said cache location in said cache unit to receive said one of said plurality of data values.

8. A system in accordance with claim 7, wherein said cache unit is a direct mapped cache.

9. A system in accordance with claim 7, wherein said cache unit is a set-associative cache.

10. A system for addressing data in a cache memory which has a plurality of synonym classes, each of said synonym classes having a plurality of congruence classes, following a failure which disables at least one of said congruence classes wherein said cache memory is used with a memory used for storing a plurality of data values, comprising:

identifying means for identifying said disabled congruence class;

means responsive to said identifying means for selecting an alternate congruence class from a subset of said plurality of congruence classes which are in the same synonym class as said disabled congruence class;

a cache directory which includes a plurality of entries, each respective entry associated with a respective congruence class which is used for storing a different one of said plurality of data values in said cache memory, each entry comprising:

(a) a first indicator which indicates whether said associated congruence class is disabled;

(b) a second indicator which indicates whether said associated congruence class contains data remapped from a further congruence class which is disabled;

(c) an address tag field which identifies a respective datum which is stored in said associated congruence class; and

(d) a further field which identifies an alternate congruence class in which said datum is stored as said alternate congruence class if said associated congruence class is disabled; and

means for setting said first and second indicator, said address tag field and said further field associated with said disabled congruence class so as to remap access to said respective datum into said alternate congruence class;

means for initiating storage of one of said plurality of data values to a memory location in said memory and for determining that said one of said plurality of data values is intended to be stored in a cache location in said cache unit corresponding to said memory location if a cache hit results, wherein said cache location is said disabled congruence class;

means for transferring said one of said plurality of data values from said alternate congruence class to said memory location which corresponds to said inoperative congruence class; and

means for determining that said one of said plurality of data values is not intended to be stored in said cache unit and for then performing one of 1) storing said one of said plurality of data values in said memory without storing said one of said plurality of data values in said cache unit if a cache miss occurs and 2) allocating said cache location in said cache unit to receive said one of said plurality of data values.

11. A system in accordance with claim 10, further comprising means for storing a line of data in said alternate congruence class in response to a request to store said line of data in said disabled congruence class if said first indicator is set in one of said entries which is associated with said disabled congruence class.

12. A system in accordance with claim 11, further comprising means for retrieving said line of data from said alternate congruence class if said first indicator is set in one of said entries which is associated with said disabled congruence class, and said second indicator is set in a further one of said entries which is associated with said alternate congruence class.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to cache memory systems, and in particular, to mechanisms for accommodating hardware failures which disable a subset of the cache storage elements.

2. Description of the Related Art

High performance processors have used cache memory systems as an integral component of overall system design for many years. A cache memory typically has a much faster access time than main storage. For example, cache may make use of a relatively small number (N) of high-speed data storage elements, located in close proximity to an associated processor, while main storage typically uses larger numbers of storage elements and is located at some distance from the processor. Cache memory systems have been designed to overcome the access speed limitation of main storage by providing rapid access to a relatively small set of data which is likely to be used during a relatively short time interval.

If a datum with a given address can be stored in any location within the cache (a fully associative cache) access time is relatively slow, because of the large number of address comparisons required to find the datum. To provide rapid access to data in the cache, most caches limit the number of locations within the cache into which a datum with a given virtual address may be stored. The set-associativity of the cache determines the number of locations in the cache into which a datum with a given address (in main memory) can be placed. The set-associativity of the cache is an important design parameter, influencing the access speed and the cache hit ratio.

Set associative caches are commonly used. In a set associative cache, a datum with a given address may be stored in one of a limited group of locations in the cache, known as a congruence class. The directory for such a cache will include a row of addresses for each congruence class. To access data in the cache, the addresses in the row are compared to the desired address in parallel, to determine whether the desired datum is stored in the cache in any of the locations within the congruence class. Logic is required to determine which, if any, of the addresses match the desired address. Because a given datum can be stored in more than one location, a replacement strategy may be implemented to retain data in the cache which is likely to be accessed, improving the cache hit ratio.

When the set associativity is 1, the cache is said to be direct mapped. FIG. 1 shows a conventional direct mapped cache. That is, the congruence class only includes one location for a datum with a given address. FIG. 1 also shows a conventional apparatus for addressing data in a direct mapped cache unit 100. Cache unit 100 includes a cache directory 110 and a cache memory 112. The cache memory includes a plurality of rows, 108a-n, each row including a line of data. Each row 108a-n forms a congruence class with a single set or location within the row into which a given datum may be stored. The cache directory includes entries 180a-n which are associated with respective rows 108a-n. Entries 180a-n include address tags 105a-n which store the high order bits of the respective addresses (in main memory) of the requested data stored in respective rows 108a-n. Valid bits 103a-n indicate whether the data in the associated cache memory storage elements 108a-n are valid. There is also a one-for-one correspondence between the low order bits 116 of the requested address and the entries 180a-n in directory 110, so that it is unnecessary to store the low order bits of the address in entries 180a-n.

Because cache 100 is direct mapped, identification of a row in cache memory 108a-n is sufficient to determine where a given datum is stored. Because cache 100 uses real placement, the translated ADHIGH bits 114 of the translatable portion of the address are stored in the address tag 105a-n.

When a datum 120 is requested by the processor 140, the low order bits of the address in ADLOW 116 are used to select a row in directory 110 to check. The directory entry 180a-n contains an address tag which comprises the high order bits of the address in main memory in which the data in the associated cache memory line 105a-n are stored. The address tag 180a-n is compared to ADHIGH 114 at the same time that valid bit 103a-n is checked. If the addresses match and the data is valid, then there is a cache hit and the associated cache memory entry 108a-n is provided to the processor 140.

The direct mapped structure has a very fast access latency, because for any desired datum, only one address in the cache directory must be compared to the desired address to determine whether the datum is in the cache. The direct mapped cache may also be less expensive, because the logic used in a set-associative cache to perform multiple compares within each congruence class is not needed. For some applications, the faster cache access speed of a direct mapped cache outweighs the slightly higher (relative to set-associative mapping) cache miss rate.

Nonetheless, direct mapped caches have not been used as widely as set-associative caches. One reason is the inability of a direct mapped cache to accommodate hardware failures. If a location in the cache is subject to a hard failure (a failure of a storage element, the electrical path connecting the element, or the logic that is used to access the element), then data which map to the failed location in the cache cannot be stored in the cache at all. Any reference to data which map to the failed location results in a cache miss; the data must be fetched from main memory, which has a much longer access time than cache.

While set-associative caches are more reliable, they are not immune to failure. The loss of a single storage element in a set associative cache only disables one set of the congruence class. But a failure in one of the lines used to access the congruence class may result in the loss of an entire congruence class, even in a set associative cache.

Another aspect of cache memory design is the determination of the number of congruence classes. The simplest method to increase the size of a cache memory is to increase the number of congruence classes without changing set associativity. So long as the number of bits required to uniquely identify the congruence class does not exceed the number of non-translatable bits in the virtual address, the non-translated (virtual) address may be used to request data from the cache. This is faster than using the real (translated) address to access the cache, because there is a delay associated with address translation.

When the number of congruence classes grows so large that the number of bits in the non-translated portions of the address is insufficient to uniquely identify the congruence class, then the requesting address expands into the translated field. This results in formation of cache synonym classes. A synonym class includes a plurality of congruence classes whose addresses have the same non-translatable address field but different low order bits within the translatable address field. If the virtual address is used to search for a datum in the cache, it is possible that the wrong congruence class within the synonym class is checked. The system responds as if there is a cache miss, even though the desired datum is actually present in the cache in another congruence class different from the class addressed by the request.

The existence of cache synonym classes has generally been regarded as a problem in cache design, and a number of systems have been disclosed to detect the existence of synonym classes, so that virtual addresses may be used for retrieving data from the cache. Such systems are discussed in U.S. Pat. Nos. 4,332,010 to Messina and 4,400,770 to Chan et al.

SUMMARY OF THE INVENTION

The present invention is embodied in a method for addressing data in a cache memory unit following a failure which disables one of the congruence classes in the cache. The cache memory unit is adapted for use in a digital processor system. The cache memory unit has a plurality of congruence classes.

A plurality of synonym classes are established. A respective subset of the congruence classes is assigned to each of the synonym classes. The congruence class which has been disabled by the failure is identified. The synonym classs to which this congruence class is assigned is identified. A further congruence class assigned to the identified synonym class is selected as an alternate congruence class.

A request to store a line of data into the disabled congruence class is identified. The line of data is stored into the alternate congruence class in response to the request.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 show a prior art cache unit.

FIG. 2 shows an exemplary embodiment of the invention.

FIG. 3 is a flow diagram of a process for storing data in accordance with the invention.

FIG. 4 is a flow diagram of a process for retrieving data in accordance with the invention.

FIG. 5 shows a further exemplary embodiment of the invention.

DESCRIPTION OF THE EXEMPLARY EMBODIMENTS

OVERVIEW

The present invention is embodied in a cache system in which a hardware failure that disables a congruence class is accommodated by remapping data to an alternate congruence class within the group of congruence classes assigned to the same synonym class as the affected congruence class.

FIG. 2 shows a cache unit 200 suitable for use in an exemplary cache memory in accordance with the present invention. The cache unit 200 includes a cache directory 210 with addressing information 204a-n and 206a-n and a cache memory 212, in which lines of data are retained. The embodiment of the invention shown in FIG. 2 is adapted for use in a system with a direct mapped cache memory. In a direct mapped cache, a word (datum or instruction, referred to as a datum) with a given virtual address in main memory has a single congruence class in the cache memory into which the datum is stored.

The cache directory includes, for each congruence class, an entry 280a-n with an AHIGH field 204a-n for the high order bits 222 of the address 220. Cache memory 212 includes respective lines 208a-n for storing data from the locations in main memory (not shown) associated with the respective congruence classes. The low order bits 226 of the address 220 of the datum are implicit in the location of the congruence class in directory 210 and cache memory 212. Valid bits 203a-n identify whether the data in the associated lines 208a-n of cache memory 212 is valid. AHIGH fields 204a-n, data lines 208a-n and valid bits 203a-n are similar to respective fields 180a-n, lines 108a-n and valid bits 103a-n in the conventional cache shown in FIG. 1. Mapping into this single congruence class, defined solely by the address used to store the data in main memory, is referred to as "canonical mapping."

Cache directory 210 includes three additional fields in the respective entries 280a-n for each congruence class, which are not present in the cache unit shown in FIG. 1. The first added field is the synonym class (SC) field 202a-n. The SC field 202a-n indicates whether there is a hardware failure which has disabled the congruence class associated with each entry 280a-n. The second added field is the Remapped Data (RM) field 201a-n. The RM field 201a-n stores an indicator which indicates whether the congruence class is an "alternate congruence class" which contains data that have been remapped from a disabled congruence class. The third added field is the AMID field 206a-n. AMID 206a-n includes additional bits from the address 220 which are used to locate data in the cache. If references to a given disabled congruence class are remapped to an alternate congruence class within the same synonym class, the AMID field 206a-n identifies that alternate congruence class. Replacing a portion 224 of the address 220 of the datum requested by the processor with the value stored in AMID 206a-n for the associated cache entry 280a-n causes the directory to point to the alternate congruence class.

FIG. 3 is a flow diagram showing an exemplary method in accordance with the present invention. In the exemplary embodiment of FIG. 2, each synonym class includes four congruence classes. That is, there may be four locations in the cache memory for any given ALOW field 226 value. Consequently, the AMID field 206a-n includes two of the higher order bits from the address.

At step 500, during the power-on sequenced the cache memory 212 is checked for hardware failures. The processor determines whether there is a hardware failure in the storage element 208a-n associated with any congruence class. If there is a failure, at step 502, recovery software in the processor selects an alternate congruence class within the same synonym class as the congruence class disabled by the hardware failure. At step 504, the SC field 202a-n for the disabled congruence class is set to a value to indicate that a failure has been detected. The AMID field 206a-n for the disabled congruence class is set to a value associated with the alternate congruence class. Data from the address in main memory that normally would be mapped to the disabled congruence class (by canonical mapping) may now be stored in cache memory 212 in the alternate congruence class.

At step 506, the processor issues a request for a datum. At step 508, the datum is fetched from the main memory (not shown) in response to a processor request. The datum is a candidate for storage in the cache 200. At step 510, the low order bits 226 of address 220 are examined. The low order bits 226 identify the congruence class in which the datum may be stored. At step 512, if there is no hardware failure in that congruence class, than at step 514, the datum is stored in the congruence class defined by canonical mapping.

If, however, at step 512, a hardware failure has disabled the storage element 208a-n associated with this congruence class, then at step 516, the AMID field 206a-n identifies the alternate congruence class to which this congruence class is remapped. At step 518, the value in AMID 206a-n is substituted for the middle bits 224 of the address 220. At step 520, the datum is stored in cache memory 212 in the alternate congruence class defined by the low order bits 226 and the substituted middle bits 224. The RM field 201a-n is set in the alternate congruence class to indicate that the data stored in this line of the cache was stored by remapping, and not by canonical mapping.

FIG. 4 is a flow chart of a method for retrieving data from cache memory 212 following remapping. At step 400, the cache 200 receives a processor request for data from address 220 (as shown in FIG. 2. At step 402, the congruence class is determined from the low order bits 226 of the address 220. At step 404, the SC field is checked to determine whether this congruence class has a hardware failure. At step 406, if no failure is indicated (no remapping has occurred), then the requested data may be in the cache in the canonical congruence class; at step 408, an address compare for the high order address bits 222 is performed similar to the method used for a conventional cache. At step 409, the RM field 201a-n is checked. At step 409, if RM 201a-n is not set, an address tag comparison is performed at step 411. If the addresses match at step 411, there is a cache hit. If the RM field 201a-n is set at step 409, then the data in the line of the cache is not from the desired line, but has been remapped from another congruence class, so a miss is detected. In other words, this congruence class is the alternate congruence class for a disabled congruence class within the same synonym class.

If a hardware failure is detected at step 406 (remapping has occurred), then at step 410, the AMID field 206a-n is read from the directory 210 and substituted for the middle bits 224 of the requested virtual address. At step 412, the value of AMID 206a-n is used to identify the alternate congruence class in which the requested data may be stored. The processor will wait for another cache cycle, while the directory 210 entry 280a-n associated with the alternate congruence class is checked. At step 416, the RM field 201a-n of the alternate congruence class is checked. If the address tag (which includes the AHIGH field 204a-n) of the entry 280a-n matches desired value 222 and RM 201a-n is set then there is a cache hit in the alternate congruence class. If RM 201a-n is not set, then the data stored in the alternate congruence class are not