Multi-Processor Cache Coherency Protocol Allowing Asynchronous Modification of Cache Data

1. Field of the Invention

The present invention relates to multi-processor systems, and, more particularly, to cache coherency in such multi-processor systems.

2. Background of the Invention

The disparity between the cycle time of a processor and memory access time forces processors to utilize a cache which contains a subset of the memory that can be accessed quickly. In a multi-processor system wherein each processor is attached to its own local cache, a coherency problem can develop unless some coordination between the contents of the local caches attached to different processors is exercised. Consider a cache which is updated whenever the attached processor performs a memory update (store) operation. Typically, such systems enforce cache coherency by requiring that when a processor wishes to modify the contents of its own cache, the memory system creates an exclusive copy of the cache line being modified in the cache of the modifying processor by invalidating all other copies of the cache line in the other caches. Such line invalidation is a time consuming operation and, if each memory update operation is synchronized to the completion of all invalidations, a substantial delay may ensue.

There is no inherent requirement that the memory system perform such steps. The essence of coherency in a multi-processor system is that all processors agree on the order in which the memory system is updated by the action of all the processors. The order for the update of memory system can be discerned by a program by examining two locations of memory. If the program inspects location A and finds that it has a new value and then examines location B and finds that it has an old value, then the program may infer that location A was updated before location B was updated. In a multi-processor system all processors must come to a common resolution of this question. This requirement has many subtle implications. For example, in a multi-processor system if a single processor issues two fetch requests (or inspection requests), these requests must be processed in sequence. If a processor issues two store requests (or update requests), these requests must be processed in sequence. If fetch requests are not processed in sequence, then there is no need to process store requests in sequence. Further within a uni-processor, a fetch request must see the last store issued by the processor that is conceptually earlier than the fetch. In a multi-processor, there is no requirement that any particular fetch request on one processor see the result of any particular store from another processor as long as there is no violation of the common inference about the order in which store operations occur within the memory subsystem. The rule which summarizes this requirement can be stated in the following manner.

There is no violation of observable order in a multi-processor system as long as there can be no occurrence of the following example.

Given a system that involves K processors P.sub.i where i=1, 2, . . . , K and two sets of K memory locations, X.sub.i and Y.sub.i where Y.sub.i is a permutation of X.sub.i. Each of the K processors, P.sub.i, inspects X.sub.i followed by Y.sub.i and sees a new value for X.sub.i and an old value for Y.sub.i. This example, called a precedence cycle, causes two or more processors to come to a contradictory inference on the order of store operations.

The object of the invention is to provide a cache coherency protocol which avoids the possibility of a precedence cycle occurring, yet does not require that only cache lines which are exclusively held by a processor may be subject to an update operation.

According to the present invention, a cache coherency protocol is set forth that allows a processor to modify data within its own cache while it still resides unmodified in another processor's cache. This is done in a manner that assures that multiple processors can not concurrently modify the same line and that the result of such modifications can not cause a forbidden precedence cycle from occurring. The rule for authorizing a processor to modify a given line is as follows:

1) the given line does not have modify status (i.e., no other processors have been granted authorization to modify the line); and

2) no other processors that share the given line (i.e., the given line is located within the cache associated with the processor) currently have been granted modify status with respect to any other line.

The principle advantage of this protocol is that the modification of an authorized line can occur without invalidating all other copies of the line in the multi-processor system, thus reducing the processing time associated with the update operation.

Other objects and advantages of the invention will become more fully understood upon consideration of the following detailed description presented in conjunction with the accompanying drawings.

FIG. 1 is a functional block diagram of a multi-processor system embodying the present invention;

FIG. 2 is a pictorial representation of the processor modifying register of the cache coherency mechanism of FIG. 1 according to the present invention; and

FIG. 3 is a pictorial representation of the line status register of the cache coherency mechanism of FIG. 1 according to the present invention.

FIG. 4 is a pictorial representation of cache line stored in the local caches of FIG. 1.

FIG. 5 illustrates the format of a request issued to the cache coherency mechanism of the present invention.

As shown in FIG. 1, a multi-processor system includes a plurality of processors (P.sub.1, P.sub.2, . . . P.sub.N) that access a shared memory 101. Each processor is associated with a corresponding local cache (C.sub.1, C.sub.2, . . . C.sub.N) that stores a subset of the shared memory 101 and arranged as a plurality of lines. Each line within a given local cache preferably has two bits associated with the line as shown in FIG. 4. The first bit 401, typically referred to as a valid bit, identifies if the line has valid status or invalid status. If the first bit 401 indicates the line has valid status, the second bit 403 indicates if the line has read-only status or modify status.

The references that a processor issues to its associated local cache may be organized into two classes:

1) class 1 reference--reference where the processor does not intend to modify the given line; and

2) class 2 reference--reference where the processor intends to modify the given line.

If the processor issues a class 1 reference and the referenced line is (a) in the local cache associated with the processor and (b) has valid status with either read-only status or modify status, then the class 1 reference may be honored by transferring the requested line from the local cache to the processor.

If a processor issues a class 1 reference and the referenced line is (a) not in the local cache associated with the processor or (b) in the local cache associated with the processor but has invalid status, a cache miss (CM) request is issued. The processing of a CM request will be discussed in detail below. When the processing of the CM request is complete, the referenced line is stored in the local cache associated with the processor with valid and read-only status. The class 1 reference can then be honored by transferring the requested information from the local cache to the processor.

If a processor issues a class 2 reference and the cache line is in the local cache associated with the processor with valid and modify status, the class 2 reference is honored by allowing the referenced line stored in the local cache to be updated by the processor.

If the processor issues a class 2 reference and the cache line is in the local cache associated with the processor with valid and read-only status, a cache miss with intent to modify line present (CMIMLP) request is issued. The processing of a CMIMLP request will be discussed in detail below. When the processing of the CMIMLP request is complete, the referenced line is stored in the local cache associated with the processor with valid and modify status. The class 2 reference can then be honored by allowing the referenced line stored in the local cache to be updated by the processor.

If the processor issues a class 2 reference and referenced line is (a) not in the local cache associated with the processor or (b) present in the local cache associated with the processor with invalid status, a cache miss with intent to modify line absent (CMIMLA) request is issued. The processing of a CMIMLA request will be discussed in detail below. When the processing of the CMIMLA request is complete, the referenced line is stored in the local cache associated with the processor with valid and modify status. The class 2 reference can then be honored by allowing the referenced line stored in the local cache to be updated by the processor.

FIG. 5 illustrates the format of the CM, CMIMLP, and CMIMLA requests. Each includes a request ID field 501, a processor ID field 503, and a line address field 505. The request ID field 501 identifies the request as either a CM request, CMIMLP request or CMIMLA request. The processor ID field 503 identifies the requesting processor. And the line address field identifies the cache line associated with the request.

After determining that the requesting processor be given authorization to modify a line, the processing of the CMIMLP and the CMIMLA requests are identical with the following exception: for the CMIMLA request, the line with modify status must be transferred from its current owner to the cache of the processor which initiates the request. Moreover, when the CMIMLP request is deferred, it may be necessary to change the CMIMLP request to a CMIMLA request. Thus, for the sake of simplifying the description, the common processing of the CMIMLP request and the CMIMLA request will be referred to below the processing of a CMIM request. However, when there are differences in the processing of the CMIMLP request and the CMIMLA request, the specific differences will be detailed.

According to the present invention, a cache coherency mechanism 103 is provided that receives the CMIM request issued by a processor/cache pair and determines if the copy of the line in the cache may be granted modify status. The cache coherency mechanism of the present invention grants such modify status based upon (a) information about the line maintained by the cache coherency mechanism, and (b) information that identifies which processors have been granted modify status with respect to other lines for which modify status was requested at a point in time where the other lines may have been shared and present in the local caches associated with other processors. If the copy of the line is not granted modify status by the cache coherency mechanism, then the processing of the CMIM request is deferred until the next cache coherency reset (CCR).

More specifically, the cache coherency mechanism of the present invention preferably includes a processor modifying register and a line status register. As shown in FIG. 2, the processor modifying register stores n bits each associated with one of the processors P.sub.1, P.sub.2, . . . P.sub.N of the system. Each bit indicates if the associated processor has been granted modify status for a line that was shared with other processors at the point where modify status was requested. The ordering of bits within the processor modifying register preferably represents a canonical ordering of the processors P.sub.1, P.sub.2 . . . P.sub.N of the system. Preferably, a bit of the processor modifying register having a binary value of `1` (or being set) indicates the associated processor has been granted modify status for a line that was shared with other processors at the point where modify status was requested, and a bit of the processor modifying register having a binary value of `0` (or being cleared) indicates the associated processor has not been granted modify status for a line that was shared with other processors at the point where modify status was requested.

As shown in FIG. 3, the line status register stores a plurality of entries 303 called line status vectors each of which is associated with a block of the shared memory 101. Preferably, the block of shared memory 101 associated with each entry is a cache line sized block, and each entry is addressed via the real memory address of cache line. Each line status vector has a length of n+1 bits. The first n bits B.sub.1, B.sub.2 . . . B.sub.N of the vector specify which processors P.sub.1, P.sub.2 . . . P.sub.N (preferably, using the same canonical ordering of the processors employed in the processor modify register) have or have had copies of the associated line in their cache C.sub.1, C.sub.2 . . . C.sub.N since the last occurrence of a CCR which affected the associated line. Preferably, if a bit B.sub.1, B.sub.2 . . . B.sub.N has a binary value of `1` (typically referred to as being set), the bit indicates the associated processor has or has had a copy of the associated line in its local cache since the last occurrence of a CCR which affected the associated line; and, if the bit has a binary value of `0` (typically referred to as being cleared), the bit indicates the associated processor does not have or has not had a copy of the associated line in its local cache since the last occurrence of a CCR which affected the associated line. The n+1 bit B.sub.N+1 of the vector specifies if any of the processors P.sub.1, P.sub.2 . . . P.sub.N have been granted modify status for the associated line. Lines that are modified (that is, have the n+1 bit B.sub.N+1 of the associated vector in the line status register set to indicate that they are subject to modification by a processor) can be of two types:

1) SINGLETON--at most one processor (therefore, the modifying processor) has a valid copy of the line in its cache; and

2) SHARED-MODIFY--multiple processors have copies of the line and one of these processors has the line with modify status in its cache.

A SINGLETON type line as described above may be identified as follows:

1) the n+1 bit B.sub.N+1 of the vector associated with a given line indicates the line is subject to modification by a processor; and

2) only one of the other n bits B.sub.1, B.sub.2 . . . B.sub.N of the vector associated with the given line are set, thereby indicating that only a single processor has a copy of the given line.

A SHARED-MODIFY line as described above may be identified as follows:

1) the n+1 bit B.sub.N+1 of the vector associated with a given line indicates the line is subject to modification by a processor; and

2) more than one of the other n bits B.sub.1, B.sub.2 . . . B.sub.N of the vector associated with the given line are set, thereby indicating that more than one processor has a copy of the given line.

The final component of the cache coherency mechanism of the present invention is a cache line invalidator, which functions to invalidate the copies of lines that have been granted modify status while they were shared. The entire set of such lines must be treated as a class and when all lines within this class have had their copies invalidated, then a CCR can be invoked. At the conclusion of a CCR, all the lines have their associated vector in the line status register set to SINGLETON status indicating that the line has been modified and exclusive within the cache of the processor that last modified the line. In addition, the processor modifying register is set to indicate that no processor currently has modify status. All memory requests that have been deferred because of the status of lines effected by such memory request or the status of processors that share such lines can now be processed.

CMIMLP requests which are deferred because the line already had modify status are converted to CMIMLA requests because the cache line invalidator will have invalidated the copy of the line within the cache of the processor which issued the CMIMLP request. However, CMIMLP requests which are deferred because the line was shared with a processor which already had modify status can be processed as CMIMLP request as no invalidation of the copies of the line will occur as part of the action of the cache line invalidator. It is possible that a line is invalidated due to the action of an IO event. If such an invalidation occurs then deferred CMIMLP requests for the line must be converted to CMIMLA requests.

The operation of all elements of the cache coherency mechanism of the present invention is illustrated by following the actions that ensue at the point of a cache miss (CM) or a cache miss with intent to modify (CMIM). The result of such misses will either be a successful completion of the processor request or a deferral until a cache coherency reset (CCR). Preferably, the cache coherency mechanism of the present invention serializes the requests generated by all processors so that only a single CM or CMIM request is issued on any cycle.

Action on CM Request

For example, consider the scenario where a reference by processor P.sub..alpha. to local cache C.sub..alpha. of the multi-processor system results in issuance of a CM request. In this case, the cache coherency mechanism extracts from the line status register the line status vector associated with the line and examines the vector as follows:

If the n+1 bit B.sub.N+1 of the line status vector indicates that the line is not subject to modification by a processor, then a copy of the line is delivered to the local cache C.sub..alpha. with valid and read-only status and the bit B.sub..alpha. of the line status vector corresponding to the processor P.sub..alpha. is set to `1` to indicate that processor P.sub..alpha. has a copy of the line thereby completing the processing of the CM request.

If the n+1 bit B.sub.N+1 of the line status vector indicates that the line is subject to modification by a processor but the line is a SINGLETON with respect to a processor P.sub..beta., then the proper action will depend on whether the line is still valid within the cache C.sub..beta. associated with processor P.sub..beta.. If the line is valid within the cache C.sub..beta., then a copy of the line is sent from the cache C.sub..beta. to the shared memory 101 and to the cache C.sub..alpha., and line status bits associated with the line in the caches C.sub..alpha. and C.sub..beta. are set to valid and read-only. In addition, the line status vector is updated by setting B.sub.N+1 to `0` to reflect that the line is not subject to modification and by setting both B.sub..alpha. and B.sub..beta. to `1` to indicate that the line is shared by both processors P.sub..alpha. and P.sub..beta.. If the line is no longer valid within the cache C.sub..beta., then it can be inferred that when the modified line was invalidated a copy of the modified line was sent to the shared memory 101 of the system. In this case, a copy of the line is sent from the shared memory 101 and to the cache C.sub..alpha., and line status bits associated with the line in the cache C.sub..alpha. are set to valid and read-only. In addition, the line status vector is updated by setting B.sub.N+1 to `0` to reflect that the line is not subject to modification, by setting B.sub..alpha. to `1` to indicate that the line is held by processor P.sub..alpha., and by setting B.sub..beta. to `0` to indicate that the line is not held by processor P.sub..beta.. This completes the processing of the CM request.

If the n+1 bit B.sub.N+1 of the line status vector indicates that the line is subject to modification by a processor but the line is SHARED-MODIFY, then the processing of the CM request is deferred until a CCR occurs. The CCR resets the vector of such lines to SINGLETON status.

Action on CMIM Request

In another example, consider the scenario where a reference by processor P.sub..alpha. to local cache C.sub..alpha. of the multi-processor system results in issuance of a CMIM request. In this case, the cache coherency mechanism extracts from the line status register the vector associated with the line and examines the vector as follows:

If the following two conditions occur:

1) the n+1 bit B.sub.n+1 of the line status vector indicates the line is not subject to modification by a processor, and

2) either the first n bits of the line status vector are cleared thereby indicating that no processor has a copy of the line, or only the bit (of the first n bits of the vector) associated with the processor P.sub..alpha. is set thereby indicating that only processor P.sub..alpha. has or has had a copy of the line,

then the operation depends upon whether the request is a CMIMLA request or a CMIMLP request. If the request is a CMIMLA request, the line is delivered from the shared memory 101 to the local cache C.sub..alpha. associated with the processor P.sub..alpha. with a valid modify status. If the request is a CMIMLP request, the line status bits of the line within the cache C.sub..alpha. i set to valid modify status. In either case, the line status vector associated with the line in the line status register is updated to represent that the line is a SINGLETON. This preferably is accomplished by setting only one bit (of the first n bits of the vector) associated with the processor P.sub..alpha. and setting the n+1 bit of the vector to indicate the line is subject to modification by a processor. The CMIM is completed.

If the following two conditions occur:

1) the n+1 bit B.sub.N+1 of the line status vector indicates the line is not subject to modification by a processor, and

2) the first n bits of the line status vector indicate at least one processor other than the processor P.sub..alpha. has a copy of the line,

then the first n bits of the line status vector associated with each of the processors are compared to the corresponding bits of the processor modifying register. If any corresponding bit pairs of the vector and processor modifying register, other than the bit pair associated with the processor P.sub..alpha., are set, then the processing of the CMIM request is deferred until the CCR occurs. The CCR clears the processor modifying register. If there are no corresponding bit pairs other than the bit pair associated with the processor P.sub..alpha., then the following actions are taken:

If the request is a CMIMLA request, then the line is delivered to the local cache C.sub..alpha. associated with the processor P.sub..alpha.. If the request is a CMIMLP request, no line movement is required.

The line is assigned modify status in the cache C.sub..alpha..

the n+1 bit B.sub.N+1 of the line status vector associated with the line is set to indicate the line is subject to modification by a processor;

the bit of the first n bits of the line status vector associated with the processor P.sub..alpha. is set to thereby indicate that the processor P.sub..alpha. has a copy of the line.

information concerning invalidation of sharers of this line is provided to the cache line invalidator (a more detailed description of the information is set forth below); and

the bit of the processor modifying register corresponding to the processor P.sub..alpha. is set (thereby indicating the processor P.sub..alpha. is now one of the processors that must be checked on all future requests to grant modify status to the shared line, and the processing of the CMIM request is completed.

If the line is SHARED-MODIFY, then the processing of the CMIM request is deferred until the CCR occurs. The CCR converts the line to a SINGLETON.

If the line is a SINGLETON with respect to a processor P.sub..beta., then the following actions are taken:

the line status vector is updated to represent the line is a SINGLETON with respect to processor P.sub..alpha.. This preferably is accomplished by setting only one bit (of the first n bits of the vector) associated with the processor P.sub..alpha. and retaining the n+1 bit B.sub.N+1 of the vector to indicate the line continues to be subject to modification by a processor;

the line is delivered from the local cache associated with the processor P.sub..beta. to the local cache associated with the processor P.sub..alpha. ;

the line is marked invalid in the local cache associated with the processor P.sub..beta. and marked valid with modify status in the local cache associated with the processor P.sub..alpha., and the processing of the CMIM request is completed.

The cache line invalidator invalidates the cache entries for all sharing users of a given line utilizing the line address, its associated line status vector which is stored in the line storage register, and the identity of the processor P.sub..gamma. that has been granted the valid-modify within its cache directory and therefore is the sole processor with the ability to modify the given line. A list of such requests are maintained by the cache line invalidator. When all sharing users have been invalidated, the cache line invalidator declares a cache coherency reset (CCR).

In order to process the CCR, the cache line invalidator updates the line status vector of the line status register associated with each pending line to identify the line as a SINGLETON, thereby representing that the line has been modified and exclusive within the cache of the processor that last modified the line. In addition, the processor modifying register is set to indicate that no processor currently has modify status.

In summary, the cache coherency protocol of the present invention decouples the invalidation of shared copies of a line that a single processor wished to modify from the granting of modify status. Thus, invalidations can occur asynchronously within the system while the processors continue to access and modify their individual caches. This eliminates the delay that may arise when utilizing conventional cache coherency protocols that require invalidation prior to line modification.

Other embodiments of the invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and examples be considered as examples only, with the true scope of the invention being indicated by the claims.