System and method for deleting read-only head entries in multi-processor computer systems supporting cache coherence with mixed protocols

This application is a continuation of U.S. patent application Ser. No. 09/235,588 filed on Jan. 22, 1999.

1. Field of the Invention

This invention relates generally to cache coherence in computer systems having multiple processors with caches, and more particularly to a system and method for deleting a read-only head entry in systems supporting mixed-coherence protocol options.

2. Description of the Prior Art

Multiple-processor computer systems involve various processors that may each work at the same time on a separate portion of a problem or work on a different problem. FIG. 1 shows a multi-processor system, including a plurality of central processing units (CPUs) or processors 102 A, 102 B, . . . 102 N, communicating with memory 104 via interconnect 106 , which could be, for example, a bus or a collection of point-to-point links. Processors 102 access data from memory 104 for a read or a write operation. In a read operation, processor 102 receives data from memory 104 without modifying the data, while in a write operation processor 102 modifies the data transmitted to memory 104 .

Each processor 102 generally has a respective cache unit 108 A, 108 B, . . . 108 N, which is a relatively small group of high-speed memory cells dedicated to that processor. A cache 108 is usually located on the processor chip itself or may be on separate chips, but is local to a processor 102 . Cache 108 is used to hold data for each processor 102 that was accessed recently by that processor. Since a processor 102 does not have to go through the interconnecting bus 106 and wait for the bus traffic, the processor 102 can generally access data in its cache 108 faster than it can access data in the main memory 104 . In a normal operation, a processor 102 N first reads data from memory 104 and, copies that data to its corresponding cache 108 N. During subsequent accesses for the same data, the processor 102 N fetches the data from its own cache 108 N. In effect, after the first read, data in cache 108 N is the same copy of data in memory 104 except that the data is now in a high-speed local storage. Typically, cache 108 N can be accessed in one or two cycles of CPU time while it takes a processor 102 15 to 50 cycles to access memory 104 . A typical processor 102 runs at about 333 Mhz or 3 ns (nanoseconds) per cycle, but it takes at least 60 ns or 20 cycles to access memory 104 .

A measure of data, typically 32, 64, 128, or 2 n bytes, brought from memory 104 to cache 108 is usually called a “cache line.” The data of which a copy was brought to cache 108 and which remains in memory 104 is called a “memory line.” The size of a cache line or a memory line is determined by a balance of the overhead per read/write operation versus the usual amount of data transferred from memory and cache. An efficient size for a cache line results in transfers spending about 25% of their time on overhead and 75% of their time on actual data transfer.

A particular problem with using caches is that data becomes “stale.” A first processor 102 A may access data in the main memory 104 and copy the data into its cache 108 A. If the first processor 102 A subsequently modifies the cache line of data in its cache 108 A, then at that instant the corresponding memory line becomes stale. If a second processor, 102 B for example, subsequently accesses the original data in the main memory 104 , the second processor 102 B will not find the most current version of the data because the most current version is in the cache 108 A. For each cache-line address, cache coherence guarantees that only one copy of data in cache 108 can be modified. Identical copies of a cache line may be present in multiple caches 108 , and thus be read by multiple processors 102 at the same time, but only one processor 102 is allowed to write, i.e., modify, the data. After a processor 102 writes to its cache 108 that processor 102 must “invalidate” any copies of that data in other caches to notify other processors 102 that their cache lines are no longer current.

FIG. 2A shows valid cache lines DO for caches 108 A to 108 N whereas FIG. 2B shows cache 108 B with an updated cache line D 1 and other caches 108 A, 108 C, and 108 N with invalidated cache lines DO. The processors 102 A, 102 C, and 102 N with invalidated cache data DO in their respective caches 108 must fetch the updated version of cache line D 1 if they want to access that data line again.

Normally and for illustrative purposes in the following discussion, cache coherence protocols are executed by processors 102 associated with their related caches. However, in other embodiments these protocols may be executed by one or more specialized and dedicated cache controllers.

There are different cache coherence management methods for permitting a processor 102 to modify its cache line in cache 108 and invalidate other cache lines. One method (related to the present invention) utilizes, for each cache line, a respective “shared list” representing cache-line correspondences by “double-links” where each cache has a forward pointer pointing to the next cache entry in the list and a backward pointer pointing to the previous cache entry in the list. Memory 104 has a pointer that always points to the head of the list.

FIG. 3 shows a linked list 300 of caches 108 A . . . 108 N with the associated memory 104 . Memory 104 has a pointer which always points to the head (cache 108 A) of the list while the forward pointers Af, Bf, and Cf of caches 108 A, 108 B, and 108 C respectively point forward to the succeeding caches 108 B, 108 C, and 108 D (not shown). Similarly, backward pointers Nb, Cb, and Bb of caches 108 N, 108 C, and 108 B respectively point backward to the preceding caches. Because each cache unit 108 is associated with a respective processor 102 , a linked list representation of cache 108 is also understood as a linked list representation of processors 102 .

There are typically two types of cache sharing lists. The first type list is the read-only (sometimes called “fresh”) list of caches for which none of the processors 102 has permission to modify the data. The second type list is a read-write (sometimes called “owned”) list of caches for which the head-of-list processor 102 may have permission to write to its cache 108 . A list is considered “stable” after an entry has been completely entered into or completely deleted from the list. Each of the stable list states is defined by the state of the memory and the states of the entries in the shared list. Relevant states of memory include HOME, FRESH, and STALE. HOME indicates no shared list exists, FRESH indicates a read-only shared list, and STALE indicates the shared list is a read-write list and data in the list can be modified. A processor 102 must get authorization to write to or read from memory. A list entry always enters the list as the list head, and the action of entering is referred to as “prepending” to the list. If a list is FRESH (the data is the same as in memory), the entry that becomes the newly created head receives data from memory; otherwise it receives data from the previous list head. In a read-write list, only the head is allowed to modify (or write to) its own cache line and, after the head has written the data, the head must invalidate the other stale copies of the shared list. In one embodiment, invalidation is done by purging the pending invalidated entries of the shared list.

FIGS. 4A-4F illustrate how the two types of lists are created and grown. Each of the figures includes a before and an after list with states of the list and memory 104 indicated. In FIG. 4A, initially memory 104 is in the HOME state, indicating there is no cache shared list. Processor 102 A requests permission to read a cache line. Since this is a read request, memory 104 changes from the HOME state to the FRESH state, and the resulting after list 402 AR is a read-only list with one entry 108 A. Cache 108 A receives data from memory 104 because cache 108 A accesses data that was previously uncached. This starts the read-only list 402 AR.

In FIG. 4B processor 102 B requests a read permission to enter the read-only list 402 B, which is the same list as 402 AR of FIG. 4 A. Cache 108 B then becomes the head of the list 402 BR receiving data line from head 108 A. The list 402 BR is still a read-only list since both entries of the list have asked for read-only permission, and therefore the memory state remains FRESH.

In FIG. 4C, memory 104 is initially in the HOME state and processor 102 A requests a read-write permission. Cache 108 A then becomes the head of the list 402 CR. Because a read-write permission was requested, list 402 CR is a read-write list. As soon as memory 104 grants a read-write permission, memory 104 changes from the HOME state to the STALE state.

In FIG. 4D processor 102 B requests a read permission to enter a read-write list 402 D. Cache 108 B becomes the head of the list 402 DR. Since memory 104 is initially in the STALE state, the resulting list 402 DR is a read-write list and memory 104 remains in the STALE state.

In FIG. 4E, the initial list 402 E is read-only with memory 104 in the FRESH state, and processor 102 B requests a write permission. Cache 108 B then becomes the head of the list 402 ER. Since processor 102 B asked for a write permission, memory 104 changes state from FRESH to STALE, and list 402 ER is a read-write list.

In FIG. 4F the list 402 F is a read-write list and processor 102 B requests a write permission. Since list 402 F is read-write, list 402 FR is also read-write, and memory 104 remains in the STALE state.

Cache list entries may be deleted. However, deleting a head-of-list presents a problem in mixed-coherence protocols, which exist where processor 102 associated with the head of the list supports a read-only option while processor 102 associated with the next-list entry supports only a read-write option. Currently most multi-processor systems support read-write lists and read-only lists are optional.

FIG. 5 illustrates how a cache head 108 D would be deleted if processor 102 C supports a read-only list. Initially, the list 502 A is read-only and memory 104 is FRESH. After cache 108 D has been deleted, cache 108 C becomes the head of the list 502 R, possessing all read-only characteristics of cache 108 D and memory 104 . List 502 R would be read-only with memory 104 in the FRESH state. However, if processor 102 C does not support a read-only list, cache 108 C cannot inherit the read-only property from memory 104 and cache 108 D, resulting in a conflicting situation.

Prior art attempts to resolve this conflict are illustrated in the flowchart of FIG. 6 . In step 600 , the head of the list informs the next-list entry that the next-list entry is about to become a read-only-list head. In step 604 the next-list entry responds that it cannot become a read-only-list head because its system does not support the read-only-list option. In step 608 the head of the list then invalidates all copies in the list and in step 612 returns them to memory. However, this solution is inefficient because even processor 102 of the head list wants to withdraw its cache 108 from the list, but other processors may still want to access the same cache copies. In such a situation the other processors must re-start a new sharing cache list by getting the desired cache line from memory 104 .

The IEEE Standard of Scalable Coherent Interfaces, IEEE Std. 1596-1992, Institute of Electrical and Electronics Engineers , Aug. 2, 1993, defines a mechanism for deleting a read-only entry. This mechanism first detects a conflict, converts the list from the read-only to the read-write state, and then allows deletion of the head of the list. However, the deleting protocols rely on detection of conflicts and are complex because the conversion between read-only and read-write states is a special operation and, due to other conflicts, is not always successful.

The present invention provides a system and a method for deleting a head entry of a read-only list in a multi-processor computer system supporting mixed cache-coherence protocols involving both read-only and read-write processors. The head of the list supports a read-only protocol while the next-list entry supports only a read-write protocol. The head of the list first informs the next-list entry that the next-list entry is about to become the head of a read-only list. The next-list entry then responds with a status code indicating whether the next-list entry supports read-only. The system then performs operations for the next-list entry to become a new head entry, including updating the forward pointer of memory pointing to the next-list entry as a new head-of-list. If the next-list entry does not support the read-only protocol, the system changes the memory line status from fresh to stale, thereby indicating a new read-write list. However, if the next list entry does support the read-only protocol, the memory line remains fresh, thereby maintaining a read-only list. Finally, the previous head-of-list informs the next-list entry that the previous head-of-list has been completely deleted from the list. The invention also permits a simpler conversion from read-only to read-write only where data is being written.

FIG. 1 shows a multi-processor system with a cache memory for each processor;

FIG. 2A illustrates all processors' cache lines being valid;

FIG. 2B shows one cache line being valid while others are invalid;

FIG. 3 shows a cache-sharing double-linked list;

FIG. 4A illustrates a creation of a read-only shared list;

FIG. 4B illustrates a cache entry entering a read-only shared list;

FIG. 4C illustrates a creation of a read-write shared list;

FIG. 4D shows a read-permission entry entering a read-write list;

FIG. 4E shows a write-permission entry entering a read-only list;

FIG. 4F shows a write-permission entry entering a read-write list;

FIG. 5 shows a head entry being deleted in supporting systems;

FIG. 6 is a flowchart illustrating a prior art attempt to solve the problem of not supporting a read-only-list head;

FIG. 7A shows the steps of deleting a head entry in accordance with the present invention;

FIG. 7B shows the original list before and the two resulting lists after the head of the list has been deleted;

FIG. 8 shows a cache in accordance with the present invention;

FIGS. 9A-9C show details of a cache requester having performed a delete sequence;

FIG. 9D shows details of a cache responder going through a delete sequence;

FIG. 9E shows details of a cache responder when its processor does not support a read-only option; and

FIG. 9F shows a state table of a memory.

This invention provides a system and a method for deleting the head of a cache-sharing list in multiprocessor systems using mixed coherence-protocol options, which exist where one processor supports read-only and read-write lists while one or more other processors do not support read-only lists, but do support read-write lists.

The invention deletes a read-only head entry as shown in the flowchart of FIG. 7 A. In step 700 the head entry informs the next-list entry that the next-list entry is about to become the head of the list and the list should become read-only.

In step 704 the next-list entry returns a response status code which includes, for illustrative purposes, MORE for supporting and DONE for not supporting a read-only option.

In step 708 the system determines whether the return code from step 704 is DONE or MORE. If it is MORE, memory 104 in step 710 points to the next-list entry, allowing the next-list entry to become the new head of the list. If the return code is DONE, memory 104 in step 712 also points to the next-list entry but the system changes memory line from the FRESH state to the STALE state.

In step 716 the system informs the next-list entry, now the new head of the list, that deletion is complete.

FIG. 7B shows the original list 702 B and two resulting lists 702 BR 1 and 702 BR 2 after cache 108 D, the head of the list, has been deleted in accordance with the invention. List 702 B is read-only and memory 104 is in the FRESH state. Processor 102 D supports a read-only list and processor 102 C may support both a read-only and a read-write list. If processor 102 C supports a read-write list, cache 108 C, upon deletion of the head-of-list 108 D, becomes the head of the list 702 BR 1 and the list becomes read-write. Memory 104 changes from the FRESH state to the STALE state. If processor 102 C supports read-only lists, memory 104 remains in the FRESH state and cache 108 C becomes the head of a read-only list 702 BR 2 .

FIG. 8 shows, in relevant parts, a cache 108 in accordance with the invention that includes a requester 802 and a responder 804 . Requester 802 , via a Request on line 8003 , initiates an action desired by the processor 102 to another processor 102 or to memory 104 , and receives a Response on line 8005 . Responder 804 receives either from a processor 102 or memory 104 a Request on line 8007 , and, via a Response on line 8009 , responds to the action requested by a requester 802 . In the preferred embodiment memory 104 includes a responder 804 , but does not include a requester 802 .

FIGS. 9A and 9B show the applicable portion of the state transition table of cache requester 802 D having performed a delete sequence as illustrated in FIG. 7 B. Row 2 specifies actions when in a state generated by a response to row 1 , and row 3 specifies actions when in a state generated by a response to row 2 .

In row 1 of FIG. 9A, because the list 702 B was read-only with memory in the state “FRESH,” the old state of cache 108 D is “HEADf,” that is, cache 108 D is the head (“HEAD”) of a read-only or fresh (“f”) list. Cache 108 D then sends a request “cMarkNextFresh” to cache 108 C. “c” indicates a communication to a cache (cache 108 C, rather than memory 104 ). “Mark” indicates no data is transferred, but a state update is requested. “Next” indicates cache 108 C is the next entry after cache 108 D, and “Fresh” indicates that the list should be read-only. Cache 108 D then receives a response, either a “MORE” or a “DONE,” from cache 108 C. If a “MORE” is received (as in row 1 ) cache 108 D's next state is “HEADf_PUSH,” that is, cache 108 D remains a read-only (“f”) head (“HEAD”), but will be deleted by pushing (“PUSH”) the data to the new entry in the list.

In row 2 , cache 108 D is in a state “HEADf_PUSH” and generates a request “mMarkForwardFresh” to memory (“m”) 104 . “Mark” indicates no data is transferred, “Forward” indicates a request to move the memory pointer forward (to cache 108 C), and “FRESH” indicates a read-only list. After receiving the response “DONE” from memory 104 cache 108 D changes to a new state “HEAD_POKE.” Cache 108 D will then inform cache 108 C that cache 108 C has become the new head of the list.

In row 3 , cache 108 D, having an old state “HEAD_POKE,” generates a request “cMarkHeadPoke,” which informs cache 108 C that cache 108 C is about to become a head, and cache 108 D will go to the next stable state (“Poke”). After receiving the response “DONE” from cache 108 C, cache 108 D changes to a new state “INVALID.” Cache 108 D thus has been invalidated or deleted from the list.

In FIG. 9B, processor 102 C does not support a read-only list. In row 1 , cache 108 D, after generating a request “cMarkNextFresh” to cache 108 C, receives a response “DONE” and changes to a new state “HEADd_PUSH.” Cache 108 D will be deleted (“PUSH”) so that cache 108 C becomes the head (“HEAD”) of a read-write (“d”) list.

In row 2 cache 108 D has an old state “HEADd_PUSH” and generates a request “mMarkFowardOwned.” Cache 108 D instructs memory (“m”) 104 that memory 104 is about to point to the next entry in the list (“Forward” to cache 108 C) and memory state should change to read-write (“Owned”). Cache 108 D then receives a response “DONE” from memory 104 and has a new state “HEAD_POKE.”

In row 3 , because cache 108 D has an old state “HEAD_POKE” like that of row 3 in FIG. 9A, all row 3 explanation is the same as that of FIG. 9A row 3 .

FIG. 9C shows the applicable portion of the state transition table of cache requester 802 D having performed a delete sequence if list 702 B (FIG. 7B) were a read-write list. In row 1 , cache 802 D has an old state “HEADd” because cache 802 D is the head (“HEAD”) of a read-write (“d”) list. Cache 108 D then sends a request “cMarkNextOwned” to cache 108 C, indicating a communication to a cache (“c”); no data is transferred (“Mark”); and the list should be read-write (“Owned”). Cache 108 D then receives a response “DONE” from cache 108 C, and changes state to “HEADd_PUSH,” that is, cache 108 D will be deleted (“PUSH”) from the list so that cache 108 C becomes the head (“HEAD”) of a read-write (“d”) list. Because FIG. 9C row 2 and row 3 include the same data as that of FIG. 9B row 2 and row 3 , FIG. 9C row 2 and row 3 explanation is the same as that of FIG. 9B row 2 and row 3 .

FIG. 9D shows details of cache responder 804 C of cache 108 C in FIG. 7 B. In row 1 , cache 108 C was initially a middle entry and its old state was “COREd.” “CORE” is for a non-head entry. Cache 108 C then receives a request “cMarkNextFresh” from cache 108 D, and cache 108 C is about to become the head of a read-only list. Because processor 102 C supports a read-only list, cache 108 C then changes to the new state “HEADf_WAIT,” i.e., cache 108 C is waiting (“WAIT”) to become a list head (“HEAD”) of a read-only (“f”) list. Cache 108 C then returns a response “MORE” to cache 108 D, which indicates additional interactions between cache 108 C, cache 108 D, and memory 104 will occur before cache 108 C becomes the head of the list.

In row 2 , cache 108 C, having an old state “HEADf_WAIT,” receives a request “cMarkHeadPoke” from cache 108 D. “Poke” indicates that cache 108 D will go into a stable state. Cache 108 C then becomes the head of a fresh list (“HEADf”), and thus returns a response “DONE” to cache 108 D.

In row 3 cache 108 D informs cache 108 C that cache 108 C is about to become the head of a read-write list (“cMarkNextOwned”). Therefore, cache 108 C changes to a new state “HEADd_WAIT,” waiting (“WAIT”) to become the head (“HEAD”) of a read-write (“d”) list. Cache 108 C then returns a response “DONE” to cache 108 D.

In row 4 cache 108 C has an old state “HEADd_WAIT,” receives a request “cMarkHeadPoke” from cache 108 D, and then becomes the head (“HEAD”) of a read-write list (“d”). Finally, cache 108 C returns a response “DONE” to cache 108 D.

FIG. 9E shows details of cache responder 804 C of cache 108 C when processor 102 C does not support read-only option. In row 1 , cache 108 C receives a request from cache 108 D that cache 108 C is about to become the head of a read-only list (“cMarkNextFresh”). Because processor 102 C does not support read-only option, cache 108 C will become the head of a read-write list (read-write option is presumably supported). Cache 102 C then changes to a new state “HEADd_WAIT,” and returns a response “DONE” to cache 108 D.

In row 2 , cache 108 C receives a request “cMarkNextOwned” from cache 108 D that requests cache 108 C to become the head of a read-write list. Because read-write option is presumably supported, cache 108 C waits to become the head of a read-write list (“HEADd_WAIT”), and then returns a response “DONE” to cache 108 D.

In row 3 , cache 108 C is waiting to become the head of a read-write list (“HEADd_WAIT”) and then receives a request “cMarkHeadPoke” from cache 108 D. Cache 108 C then becomes the head of a read-write list (“HEADd”), and returns a response “DONE” to cache 108 D.

FIG. 9F shows the state table of memory 104 . In both rows 1 and 2 , the list was read-only (having an old state “FRESH”), and memory 104 was pointing to cache entry 108 D (old Id) as being the head of the list. After the transaction is completed (“DONE”), memory 104 points to cache 108 C (new Id). However, in row 1 , memory 104 receives a request “mMarkForwardFresh,” i.e., to change the pointer from the old head to the new head of the list ( 108 D to 108 C), and remains read only (“Fresh”). In contrast, memory 104 in row 2 receives a request “mMarkForwardOwned.” Memory 104 then points forward to cache 108 C so that cache 108 C becomes the head of a read-write (“Owned”) list. Memory 104 therefore changes to the new state “STALE.”

The invention has been explained with reference to a preferred embodiment. Other embodiments will be apparent to those skilled in the art after reading this disclosure. For example, the present invention may be implemented in either software or hardware and any implementation of lists can utilize the invention. Additionally, the present invention may effectively be used in combination with multi-processor systems other than that described in accordance with the preferred embodiment. Therefore, these and other variations upon the preferred embodiment are intended to be covered by the following claims.