Method and apparatus for primary cache tag error handling

A method and apparatus is disclosed for maintaining coherency between a primary cache and a secondary cache in a directory-based cache system. Upon identifying a parity error in the primary cache, a tag parity packet and a load instruction are sent from the primary cache to the secondary cache. In response to the tag parity packet, each tag entry in the secondary cache that is associated with the parity error is invalidated. Upon receiving an acknowledgment of receipt of the tag parity packet, the primary cache functions to invalidate each tag entry in the primary cache that is associated with the parity error. Then, the secondary cache communicates data requested in the load instruction to the primary cache.

BACKGROUND

It is common for a modern microprocessor chip (“chip”) to implement a cache system including a first cache level and a second cache level. The first cache level represents a small amount of very fast memory defined on the chip. The first cache level is used to provide a temporary holding place for data and instructions that have recently been transferred to or from a main memory that resides outside the chip. The second cache level is generally larger than the first cache level. The second cache level is defined between the first cache level and the main memory. Data access operations between the first cache level and the second cache level can be performed faster than between the first cache level and the main memory. Thus, the second cache level represents an intermediate memory that can quickly service requests from the first cache level.

In a multiprocessor chip, a single second cache level is often used to service multiple first cache levels corresponding to multiple processors. In general, the second cache level maintains a copy of the data in the first cache level of each processor. Thus, multiple first cache levels may store a common data item that is also stored in the second cache level. During operation of the cache system, it is important to maintain coherency between the first and second cache levels. This is particularly true when handling data errors identified within the first cache level. For example, if the first cache level modifies data stored therein due to identification of an error, the corresponding data in the second cache level needs to be modified in the same manner to remain consistent. Otherwise, a coherency problem may occur later.

Because the first cache level communicates directly with the processor, it is important to operate the first cache level in the most efficient manner possible. Therefore, a continuing need exists for advancements in cache system operation, particularly with respect to optimization of error handling in the first cache level while maintaining coherence with the second cache level.

SUMMARY

It should be appreciated that the present invention can be implemented in numerous ways, such as a process, an apparatus, a system, a device or a method. Several inventive embodiments of the present invention are described below.

In one embodiment, a multiprocessor chip is disclosed. The multiprocessor chip includes a primary cache having primary cache logic and a secondary cache having secondary cache logic. The primary cache is defined to include a tag structure. The secondary cache is defined to include a tag directory representing the tag structure of the primary cache. A first portion of the primary cache logic is defined to identify a parity error in the tag structure of the primary cache. In response to identifying the parity error, a second portion of the primary cache logic is defined to send a tag parity packet from the primary cache to the secondary cache. A first portion of secondary cache logic is defined to invalidate each entry in the tag directory of the secondary cache as identified by the tag parity packet. A second portion of secondary cache logic is defined to send an acknowledgment of receipt of the tag parity packet to the primary cache logic. In response to the acknowledgment, a third portion of primary cache logic is defined to invalidate each entry in the tag structure of the primary cache that is associated with the parity error.

In another embodiment, a method is disclosed for maintaining coherency between a primary cache and a secondary cache in a directory-based cache system. The method includes identifying a parity error in the primary cache. Upon identifying the parity error, a tag parity packet is sent from the primary cache to the secondary cache. Each tag entry in the secondary cache that is associated with the parity error is then invalidated. The method further includes receiving an acknowledgement at the primary cache to indicate receipt of the tag parity packet at the secondary cache. Then, in response to receiving the acknowledgment, each tag entry in the primary cache that is associated with the parity error is invalidated.

In another embodiment, an apparatus for maintaining coherency within a cache system is disclosed. The apparatus includes a primary cache having a tag structure. The apparatus also includes a secondary cache having a tag directory structure. The tag directory structure represents the tag structure of the primary cache. The apparatus further includes primary cache logic and secondary cache logic. The primary cache logic is defined to control the primary cache and communicate with the secondary cache. The secondary cache logic is defined to control the secondary cache and communicate with the primary cache. The primary cache logic is configured to identify a parity error in an entry of the tag structure of the primary cache, and send a tag parity packet to the secondary cache logic upon identifying the parity error. Upon receiving the tag parity packet, the secondary cache logic is configured to invalidate each entry in the tag directory structure that is associated with the parity error. The secondary cache logic is further configured to send an acknowledgement to the primary cache logic indicating receipt of the tag parity packet. Upon receiving the acknowledgment, the primary cache logic is configured to invalidate each entry in the tag structure that is associated with the parity error.

DETAILED DESCRIPTION

It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, or a method. Several exemplary embodiments of the invention will now be described in detail with reference to the accompanying drawings.

FIG. 1is an illustration showing a multiprocessor chip100, in accordance with one embodiment of the present invention. In the embodiment ofFIG. 1, the multiprocessor chip100is shown to include eight processor cores, identified as Core0(101a) through Core7(101h). It should be appreciated, however, that in other embodiments the multiprocessor chip100can have less than or more than eight processor cores. Each of the processor cores101a-101hare connected to a bus109of the multiprocessor chip100, as indicated by connections107a-107h. In one embodiment, the bus109is implemented as a crossbar bus. Additionally, each of the processor cores101a-101his defined to include a primary cache (L1) that includes an instruction cache (103a-103h) and a data cache (105a-105h). With respect toFIG. 1, each instruction cache (103a-103h) of each processor core (101a-101h) is labeled as “L1 I$.” Similarly, each data cache (105a-105h) of each processor core (101a-101h) is labeled as “L1 D$.” It should be appreciated that the primary cache of each processor core is a separate and independent instantiation of primary cache. In other words, even though the structure of the primary cache in each processor core is identical, each processor core maintains independent control over its own primary cache.

The multiprocessor chip100further includes a secondary cache (L2). In the embodiment ofFIG. 1, the secondary cache (L2) is shown to be implemented in four banks identified as L2 Bank0(111a), L2 Bank1(111b), L2 Bank2(111c), and L2 Bank3(111d). Each bank of the secondary cache (L2) is connected to the bus109, as indicated by connections113a-113d. Thus, each processor core101a-101h, including its respective primary cache (L1), is capable of communicating with any bank of the secondary cache (L2) via the connections107a-107h, the bus109, and the connections113a-113d. It should be understood that communication between the processor cores101a-101h(including the primary caches) and the secondary cache111a-111dcan be performed in a bi-directional manner.

It is useful to now describe the structure of the primary cache (L1) as instantiated in each of the processor cores101a-101h. For ease of discussion, the primary cache (L1) structure will be described with respect to processor core101a, i.e., Core0. It should be understood, however, that the description provided for the primary cache of processor core101ais equally applicable to the primary cache in each of processor cores101b-101h, i.e., Core1through Core7.

Each of the instruction cache (L1 I$)103aand the data cache (L1 D$)105ais defined two structures, namely a tag structure and a data structure. It should be noted that the data cache (L1 D$)105ais not to be confused with the data structure. The data structure represents one of two parts of the data cache (L1 D$)105a, as well as one of two parts of the instruction cache (L1 I$)103a. Thus, the instruction cache (L1 I$)103ais defined to have an instruction cache tag structure and an instruction cache data structure. Also, the data cache (L1 D$)105ais defined to have a data cache tag structure and a data cache data structure.

Each entry in the instruction cache tag structure has a corresponding entry in the instruction cache data structure. Also, each entry in the data cache tag structure has a corresponding entry in the data cache data structure. A given entry in the instruction cache tag structure is defined to store a memory address (“address” hereafter) for data stored in the corresponding entry in the instruction cache data structure. Also, a given entry in the data cache tag structure is defined to store an address for data stored in the corresponding entry in the data cache data structure. Thus, the instruction cache tag structure and the instruction cache data structure are equivalent in terms of the number and arrangement of entries. Similarly, the data cache tag structure and the data cache data structure are equivalent in terms of the number and arrangement of entries.

FIG. 2is an illustration showing an tag structure corresponding to each of the instruction cache103atag structure and the data cache105atag structure, in accordance with an exemplary embodiment of the present invention. The tag structure is defined as a two-dimensional structure having a number of rows identified as “indices” and a number of columns identified as “ways.” In the exemplary embodiment ofFIG. 2, the tag structure includes 128 indices and 4 ways. It should be appreciated, however, that other embodiments of the present invention can utilize a different number of indices and a different number of ways to define the tag structure. Each entry in the tag structure corresponds to a particular index (i) and a particular way (w). Each entry in the tag structure specifies an address, a validity status, and an expected parity result. The address is defined within a tag portion of the entry. In one embodiment, the index corresponding to the entry is embedded within the tag portion of the entry. The validity status is defined as a single validity bit. A state, i.e., high or low, of the validity bit identifies whether the tag portion of the entry is valid or not valid. In one embodiment, a high state of the validity bit can be used to indicate a valid tag portion. In another embodiment, a low state of the validity bit can be used to indicate a valid tag portion. For ease of discussion, the remainder of this disclosure is based on using a low state of the validity bit to indicate a valid tag portion. The state of the validity bit is set based on a parity check of the tag portion of the entry.

The expected parity result is defined as a single parity bit. A state, i.e., high or low, of the single parity bit represents a result that is expected from performing a parity check of the tag portion of the entry. In one embodiment, the parity check is performed by evaluating an exclusive-or (XOR) combination of the tag portion of the entry. More specifically, a first bit of the tag portion of the entry is XOR'd with a second bit of the tag portion of the entry to generate an intermediate XOR combination. The intermediate XOR combination is then XOR'd with a third bit of the tag portion of the entry to generate an updated intermediate XOR combination. The updated intermediate XOR combination is XOR'd with the next bit of the tag portion of the entry and so on until the last bit of the tag portion of the entry has been XOR'd. The final result of XOR'ing all the bits of the tag portion of the entry represents a parity check signal. For example, if the tag portion was represented as “1011”, the parity check signal would be “1.” If the parity check signal matches the state of the parity check bit, the parity of the tag portion of the entry is good and the validity bit remains low. If the parity check signal does not match the state of the parity check bit, the parity of the tag portion of the entry is bad and the validity bit is reset to high to invalidate the entry. It should be appreciated that other parity check methods, e.g., even parity, can be used to check the validity of the tag portion. Furthermore, alternative embodiments can use error detection schemes other than parity check methods to check the validity of the tag portion and set the validity bit accordingly.

FIG. 3is an illustration showing a data structure corresponding to each of the instruction cache103adata structure and the data cache105adata structure, in accordance with the exemplary embodiment ofFIG. 2. As previously discussed, each entry in the tag structure ofFIG. 2has a corresponding entry in the data structure ofFIG. 3. Thus, the data structure ofFIG. 3is identical to the two-dimensional tag structure ofFIG. 2. Therefore, if an address is located in the tag structure ofFIG. 2, the index and way values corresponding to the address can be used to retrieve the appropriate data entry from the data structure ofFIG. 3.

Referring back toFIG. 1, the secondary cache (L2) is defined to include a primary cache tag directory. More specifically, each bank of the secondary cache111a-111dis defined to include a portion of the complete primary cache tag directory. The primary cache tag directory is a representation of the tag structure of the primary cache of each processor core101a-101h. The L2 Bank0(111a) includes an L1 instruction cache (I$) tag directory115aand an L1 data cache (D$) tag directory117a. The L2 Bank1(111b) includes an L1 instruction cache (I$) tag directory115band an L1 data cache (D$) tag directory117b. The L2 Bank2(111c) includes an L1 instruction cache (I$) tag directory115cand an L1 data cache (D$) tag directory117c. The L2 Bank3(111d) includes an L1 instruction cache (1$) tag directory115dand an L1 data cache (D$) tag directory117d.

Each of the L1 instruction cache (I$) tag directories115a-115drepresents a portion of the primary instruction cache (L1 I$) tag structure of each processor core101a-101h. Similarly, each of the L1 data cache (D$) tag directories117a-117drepresents a portion of the primary data cache (L1 D$) tag structure of each processor core101a-101h. In one embodiment, the L1 I$ and L1 D$ tag directories,115aand117arespectively, of the L2 Bank0(111a) are defined to represent index lines0through31of the tag structures of the primary instruction cache (L1 I$) and primary data cache (L1 D$), respectively, of each processor core101a-101h.

FIG. 4Ais an illustration showing an exemplary layout of the L1 I$ tag directory115aand the L1 D$ tag directory117aof L2 Bank0(111a). In the present embodiment, the L1 I$ and L1 D$ tag directories,115band117brespectively, of the L2 Bank1(111b) are defined to represent index lines32through63of the tag structures of the primary instruction cache (L1 I$) and primary data cache (L1 D$), respectively, of each processor core101a-101h.FIG. 4Bis an illustration showing an exemplary layout of the L1 I$ tag directory115band the L1 D$ tag directory117bof L2 Bank1(111b). In the present embodiment, the L1 I$ and L1 D$ tag directories,115cand117crespectively, of the L2 Bank2(111c) are defined to represent index lines64through95of the tag structures of the primary instruction cache (L1 I$) and primary data cache (L1 D$), respectively, of each processor core101a-101h.FIG. 4Cis an illustration showing an exemplary layout of the L1 I$ tag directory115cand the L1 D$ tag directory117cof L2 Bank2(111c). In the present embodiment, the L1 I$ and L1 D$ tag directories,115dand117drespectively, of the L2 Bank3(111d) are defined to represent index lines96through127of the tag structures of the primary instruction cache (L1 I$) and primary data cache (L1 D$), respectively, of each processor core101a-101h.FIG. 4Dis an illustration showing an exemplary layout of the L1 I$ tag directory115dand the L1 D$ tag directory117dof L2 Bank3(111d).

The tag directories (115a-115dand117a-117d) in the secondary cache (L2), as previously described, are reverse-mapped tag directories intended to represent a current copy of the tag structures of the primary cache (103a-103hand105a-105h) of each processor core101a-101h. Therefore, the tag directories (115a-115dand117a-117d) in the secondary cache (L2) can be used to maintain coherency in the cache system of the multiprocessor chip100. When using the reverse-mapped tag directories (115a-115dand117a-117d) to maintain coherency in the cache system, it is important to keep the reverse-mapped tag directories (115a-115dand117a-117d) consistent with the tag structures of the primary cache (103a-103hand105a-105h). Otherwise, a situation may occur in which a single address becomes associated with an incorrect data entry or multiple data entries.

To describe the secondary cache's responsibility with respect to maintaining coherency in the cache system, consider a situation in which a thread operating in a first processor core needs to modify data corresponding to a particular address. Further consider that the particular address is stored in the primary data cache (L1 D$) tag structure of both the first processor core and a second processor core. The secondary cache is responsible for maintaining coherency between the L1 D$ tag structure in each of the first and second processor cores. The secondary cache is also responsible for enabling the primary cache in the first processor to be modified to satisfy the request of the thread operating in the first processor.

In addition to maintaining coherency in the event of data modification as described above, the cache system also needs to maintain coherency in the presence of corrupted data. Consider a situation in which a thread executing on a given processor core issues a request that data be accessed at a target address. The target address includes an identification of a target index, i.e., line, within the tag structure of the primary cache at which the target address resides. However, the target address does not indicate the particular tag entry of the target index corresponding to the target address. Thus, each of the four tag entries of the target index is compared on a bit-wise basis to the target address. If the target address matches a particular entry at the target index, the target index value, i.e., line number, and the “way” value, i.e., column number, corresponding to the matching tag entry are used to retrieve the appropriate data entry from the corresponding data structure of the primary cache. If the target address does not match either entry at the target index, the data request is passed down to the secondary cache for processing.

In addition to performing the bit-wise comparison of the target address to each tag entry of the target index, the validity of each tag entry is also verified. As previously discussed, a parity check can be used to verify the validity of each tag entry. For a given tag entry, the parity check evaluates the XOR combination of the tag portion of the tag entry and compares the result of the XOR combination to the state of the parity bit associated with the tag entry. If the XOR combination result does not match the parity bit, a parity error exists. The parity error can cause a false mismatch or a false hit when comparing the target address to the tag portion of each tag entry. Both the false mismatch and the false match conditions can either corrupt or kill an executing thread associated with the parity error. Therefore, the cache system should be capable of identifying and handling parity errors within the primary cache while maintaining coherency within the cache system.

In the present invention, whenever a parity error is detected by the primary cache, the primary cache relies on the secondary cache to service the parity error condition. Upon encountering the parity error in the primary cache (either instruction cache or data cache) of a given processor core, a load-store unit (or fetch unit) of the primary cache issues a tag parity packet to the secondary cache. The target address at which the parity error occurred is included in the tag parity packet. The tag parity packet communicates to the secondary cache the parity error condition, the processor core whose primary cache contains the parity error, and the particular index of the primary cache tag structure at which the parity error exists. Following issuance of the tag parity packet, the primary cache further issues to the secondary cache a load (or ifetch) request for the data corresponding to the target address that was being processed when the parity error was encountered.

Upon receiving the tag parity packet from the primary cache, the secondary cache invalidates all tag entries in the reverse-mapped tag directory corresponding to the index value of the target address. Then, the secondary cache sends an acknowledgment communication to the primary cache of the processor core from which the tag parity packet was received. Receipt of the acknowledgment enables the primary cache to invalidate all tag entries in the tag structure corresponding to the index value of the target address. Upon receiving the load request, the secondary cache responds with the requested data corresponding to the target address and updates the reverse-mapped tag directory to reflect storage of the requested data in the primary cache of the processor core from which the load request was received. It should be understood that operations performed by each of the primary cache and the secondary cache are controlled by primary cache logic and secondary cache logic, respectively. It should be further understood that each of the primary cache logic and the secondary cache logic can be defined by multiple hardware portions that are each configured to perform specific tasks.

FIG. 5is an illustration showing a flowchart of a method for maintaining coherency between a primary cache and a secondary cache in a directory-based cache system, in accordance with one embodiment of the present invention. The method includes an operation501for checking a parity of each tag entry in a primary cache that is associated with a particular index of the primary cache. In one embodiment, the particular index is represented within a target address associated with a data request generated by an executing application or thread. Additionally, in one embodiment, checking the parity of each tag entry can include evaluating an exclusive-or combination of each bit of a particular tag entry to generate a parity check signal, and comparing the parity check signal to a state of a parity bit associated with the particular tag entry.

The method further includes an operation503for identifying a parity error in the primary cache. With respect to the previous embodiment, a mismatch between the parity check signal and the state of the parity bit indicates a parity error. In an operation505, a tag parity packet is sent from the primary cache to the secondary cache in response to identifying the parity error in the operation503. In response to the tag parity packet, the method provides an operation507for invalidating each entry, associated with the parity error, that resides in a primary cache tag directory that is stored in the secondary cache. In an operation509, the secondary cache sends an acknowledgment communication to the primary cache to indicate receipt of the tag parity packet. In response to receiving the acknowledgment at the primary cache, the method includes an operation511for invalidating each tag directory entry in the primary cache associated with the parity error. In one embodiment, each tag directory entry in the primary cache and secondary cache associated with the parity error can be invalidated by resetting a validity bit associated with each tag directory entry.

The method further includes an operation513for sending a load instruction from the primary cache to the secondary cache. The load instruction directs the secondary cache to obtain the data corresponding to the target address. In one embodiment, sending the load instruction in the operation513is performed immediately after sending the tag parity packet in the operation505. In an operation515, the secondary cache is updated to include data requested in the load instruction sent in operation513. It should be appreciated that operation515is performed following operation507, such that the secondary cache is updated following invalidation of each entry, associated with the parity error, that resides in the primary cache tag directory that is stored in the secondary cache. Additionally, the data requested in the load instruction of operation513is sent from the secondary cache to the primary cache in an operation517. It should be appreciated that operation517is performed following operation511, such that the requested data is stored in the primary cache following invalidation of each tag directory entry in the primary cache associated with the parity error. In one embodiment, the requested data is sent to the requesting application or thread in conjunction with performing operation517.

The method of the present invention, as described with respect toFIG. 5, enables coherency to be maintained in the cache system when parity errors are encountered and resolved. It should be appreciated that in the present invention the primary cache is required to send two communications to the secondary cache upon encountering a parity error, wherein the first communication is a tag parity packet and the second communication is a load instruction. Flushing of the tag entries associated with the parity error ensures that coherency is maintained between the primary and secondary caches.

Embodiments of the present invention can be processed on a single computer, or using multiple computers or computer components which are interconnected. A computer, as used herein, shall include a standalone computer system having its own processor, its own memory, and its own storage, or a distributed computing system, which provides computer resources to a networked terminal. In some distributed computing systems, users of a computer system may actually be accessing component parts that are shared among a number of users. The users can therefore access a virtual computer over a network, which will appear to the user as a single computer customized and dedicated for a single user.