Method and apparatus for collapsing writebacks to a memory for resource efficiency

[0002] The present invention relates generally to a memory controller, and more particularly to a method and apparatus for improving the performance of a memory system.

[0003] Cache memories are typically used in computer systems to decrease the memory access time of processors thereof. A cache memory is a relatively small, high speed memory in which previously accessed information (program instructions and/or data) are stored within cache lines of the cache memory. A cache memory is typically faster than main memory by a factor of 5 to 10 and typically approaches the speed of its corresponding processor. By keeping the most frequently accessed data items in the high speed cache memories, the average memory access time of the processors will approach the access time of the cache memories.

[0004] In computer systems having multiple processors and cache memories, the gain in performance from improved memory access time is offset somewhat by the added complexity of maintaining cache coherency. Cache coherency is the method of ensuring that all of the processors in a computer system, and their associated cache memories, are using the latest data. This coherency problem specifically occurs when data stored in cache memory is modified. There are two approaches for providing processors of the computer system with modified data stored in the cache memory. The first approach utilizes a write-through cache system. In a write through cache system, modified data is written to and through a first cache memory to the main memory, and any corresponding copy of the modified data that may reside in other cache memories of the computer system is invalidated. Therefore, when processors subsequently attempt to read the modified data, the modified data is supplied from main memory for all processors whose associated cache memory contains no valid copy of the data.

[0005] The second approach utilizes a writeback cache system. In a writeback cache system, a processor and associated cache memory must first obtain ownership of a memory location before the processor may modify the memory location in its cache memory. In response to the processor and associated cache memory obtaining ownership of the memory location, the other cache memories invalidate any copy of the memory location which they may contain. After obtaining ownership of the memory location, the processor may write modified data to its associated cache memory without immediately writing the modified data to main memory. Therefore, data in a cache memory may be different than corresponding data in main memory. In order to maintain coherency, the modified data is later written back to the main memory in response to various events. For example, a writeback cache may write the data back to main memory when: a) a first processor requests the use of modified data stored in the associated cache memory of a second processor, b) a cache line having modified data needs to be replaced with a different line from main memory, or c) a periodic flush of cache memory is performed in order to prevent accidental data loss.

[0006] When multiple processors in a writeback computer system are performing operations that require frequent data modifications, the processors of the computer system may spend a large part of their processing time waiting for the completion of writebacks. An example of when frequent writebacks are likely to occur is when two processors are updating counters located in different memory locations of the same line of memory. In response to a first processor attempting to update a first counter of a memory line, a second processor may be forced to write the memory line back to the main memory, and in response to a second process attempting to update a second counter of the memory line, the first processor may be forced to write the memory line back to main memory. As a result, each successive update of a counter in the memory line may cause a cache memory to write the memory line back to main memory (i.e. to perform a writeback). These writebacks may possibly happen in an alternating fashion which would drastically decrease the performance of the system because a write to main memory takes longer than a write to cache memory. It would, therefore, be more efficient if the intermediate values of a memory location were not written back to main memory on every change. Instead, if a writeback to main memory is pending but not yet complete, successive writebacks could be collapsed, with the final value being the only value actually written back to main memory.

[0007] What is needed therefore is a method and apparatus for increasing the performance of a computer system by reducing the number of writebacks to a main memory.

[0008] In accordance with one embodiment of the present invention, there is provided a method of collapsing writebacks to a memory. For a memory having multiple memory lines and an associated memory controller, the method includes the steps of (a) storing a first address and a first modified copy of a first memory line in the memory controller; (b) issuing from a first device a read request that includes a second address; (c) storing the second address in the memory controller; and (d) transferring a second modified copy of a second memory line from a cache for a second device to the first device in response to the read request. The transferring step includes the step of replacing the first modified copy of the first memory line stored in the memory controller with the second modified copy of the second memory line if the first address and the second address both map to the same memory line in the memory.

[0009] Pursuant to another embodiment of the present invention, there is provided a computer system for implementing a writeback collapse. The computer system includes a first processor, a first writeback cache coupled to the first processor, a second processor, a memory controller, a memory coupled to the memory controller, and a first bus that couples the first writeback cache, the second processor, and the memory controller together. The memory includes several memory lines. The first writeback cache is configured to receive via the first bus a read request that was issued from the second processor. The read request includes a first address that maps the read request to a first memory line of the memory. The first writeback cache is also configured to (a) generate a response if the first writeback cache contains a first modified copy of the first memory line, and (b) transfer the first modified copy of the first memory line to the second processor if said response is generated. Furthermore, the memory controller includes a writeback storage for storing a second modified copy of a second memory line that is to be written back to the memory. The memory controller is configured to (a) receive the read request via the first bus, (b) generate a hit signal if (1) the writeback storage contains the second modified copy of the second memory line and (2) the first address and the second address map to the same memory line in the memory, and (c) replace the second modified copy of the second memory line with the first modified copy of the first memory line if the response and the hit signal are generated.

[0010] It is an object of the present invention to provide an improved method and apparatus for processing memory requests.

[0011] It is an object of the present invention to provide a new and useful method and apparatus for processing memory requests.

[0012] It is a further object of the present invention to provide a method and apparatus which reduces traffic across a memory bus.

[0013] It is yet a further object of the present invention to provide a method and apparatus which increases the performance of a computer system by reducing the number of writes to main memory.

[0014] It is yet a further object of the present invention to provide a method and apparatus which reduces the number of writes to main memory while maintaining coherency amongst multiple cache memories and main memory.

[0015] Yet another object of the present invention is to provide a method and apparatus which collapses multiple cache memory writebacks into a single write to main memory.

[0016] It is yet a further object of the present invention to provide a method and apparatus which prevents a deadlock of memory requests.

[0017] The above and other objects, features, and advantages of the present invention will become apparent from the following description and the attached drawings.

[0018] FIGS. 1A and 1B show a simplified block diagram of an exemplary computer system incorporating features of the present invention therein;

[0019] FIG. 2 shows a simplified block diagram of the memory controller of FIG. 1;

[0020] FIG. 3 shows a flowchart of writeback collapsing method which is utilized by the computer system of FIG. 1;

[0021] FIG. 4 shows a flowchart of a first series of exemplary memory requests that illustrates the writeback collapsing method of FIG. 3; and

[0022] FIG. 5 shows a flowchart of a second series of exemplary memory requests that illustrates how the writeback collapsing method of FIG. 3 may resolve a deadlock situation.

[0023] While the invention is susceptible to various modifications and alternative forms, a specific embodiment thereof has been shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.

[0024] A simplified block diagram of an exemplary computer system 6 which incorporates features of the present invention therein is shown in FIG. 1. The computer system 6 includes a first node 8a, a second node 8b, and an interconnection bus 9 that couples the first node 8ato the second node 8b. The first node 8aincludes a first group of caching agents 10a,a first memory controller 16a, a first memory 18a, a first memory line status table (MLST) 19a, a first processor bus 20a,and a first memory bus 22a. The first group of caching agents 10ais operatively coupled to the first memory controller 16aby the first processor bus 20a, and the first memory 18ais operatively coupled to the first memory controller 16aby the first memory bus 22a. Furthermore, the first memory controller 16ais operatively coupled to the second node 8bby the interconnection bus 9 and is further operatively coupled to the first MLST 19a.

[0025] The second node 8bincludes a second group of caching agents 10b, a second memory controller 16b, a first memory 18b, a second MLST 19b, a second processor bus 20b, and a second memory bus 22a. The second group of caching agents 10bis operatively coupled to the second memory controller 16bby the second processor bus 20b, and the second memory 18bis operatively coupled to the second memory controller 16bby the second memory bus 22b. Furthermore, the second memory controller 16bis operatively coupled to the first node 8aby the interconnection bus 9 and is further operatively coupled to the second MLST 19b.

[0026] For purposes of clarity, a component is local to another component if both components are in the first node 8aor if both components are in the second node 8b. On the other hand, a component is remote to another component if one component is in the first node 8aand the other component is in the second node 8b. In other words, components of the same node are local to one another and components of different nodes are remote to one another.

[0027] The first group of caching agents 10aincludes four processors 12a-12dthat are each coupled to a corresponding cache memory 14a-14d.Similarly the second group of caching agents includes two processors 12e-12fthat are each coupled to a corresponding cache memory 14e-14f. The processors 12a-12f, which are the computational and control components of the computer system 6, fetch, interpret, and execute instructions stored in the first memory 18aand the second memory 18b. The processors 12a-12falso send and receive information over the processor buses 20aand 20bto and from other devices within the computer system 6. In a preferred embodiment the processors 12a-12fare Pentium Pro™ processors which are commercially available form Intel Corporation of Santa Clara, Calif.

[0028] The cache memories 14a-14fare implemented with a small amount of very fast memory such as static random access memory (SRAM). The cache memories 14a-14finclude several cache lines 24 for storing frequently accessed information (i.e. instructions and/or data). Each cache line 24 includes several words 26 that may each store several bytes of information. For example, each cache line 24 in the preferred embodiment includes four words 26 of sixty-four bits or eight bytes each. Furthermore, the cache memories 14a-14fare implemented as writeback cache memories. In other words, information to be written to the first memory 18aor the second memory 18bis first stored in the cache memories 14a-14fand is later transferred in response to various conditions to the first memory controller 16aor the second memory controller 16bfor writing to first memory 18aand the second memory 18b. In a preferred embodiment, the cache memories 14a-14fhave a capacity to store one Megabyte of information and are implemented as the internal cache memory of the processors 12a-12f; however, it should be appreciated that the cache memories 14a-14fmay be implemented as (1) external cache memory, (2) internal cache memory, (3) internal and external cache memory, or (4) several levels of cache memory.

[0029] The first memory 18aand the second memory 18bstore information (data and instructions). The first memory 18aand the second memory 18bgenerally consists of several Megabytes of storage and are typically implemented with dynamic random access memory (DRAM). While DRAM is slower than SRAM, DRAM is also much cheaper. The first memory 18aand the second memory 18beach include several memory lines 28 which include several addressable storage locations or memory locations 30. In the preferred embodiment, each memory line 28 holds the same amount of information as each cache line 24 and transfers of information between the cache memories 14a-14fand the first memory 18aand the second memory 18btypically occur a memory line at a time.

[0030] Most computer systems are designed for byte addressability and the computer system 6 is no exception. In other words, each addressable memory location 30 holds one byte of information and the processors 12a-12fmay modify a single memory location 30 by modifying a single byte of a cache line 24. However, in order to simplify the description of the present invention and FIG. 1, each addressable memory location 30 is assumed to be the same size as the cache line words 26. In other words, each addressable memory location 30 in the following description may store eight bytes of information.

[0031] The advantage of a memory system which uses a hierarchy of faster cache memories 14a-14fwith slower first memory 18aand second memory 18bis that the memory system is both economical and efficient in processing memory requests. This advantage is a direct result of the spatial and temporal locality of reference principles. The spatial locality of reference principle contends that a small percentage of the first memory 18aand the second memory 18bis used a large percentage of the time. The temporal locality of reference principle contends that a memory location once referenced is likely to be referenced again within a short period of time. If these parts of the first memory 18aand the second memory 18b(or large part thereof) are stored in cache memories 14a-14f, a large percentage of memory operations such as reads and writes may be performed directly to and from these faster cache memories 14a-14d.

[0032] For example, when a processor 12a-12frequests information from a memory location 30 of the first memory 18aor the second memory 18b, the processor 12a-12fchecks to see if a valid copy of the memory location 30 is already in its corresponding cache memory 14a-14f. If a valid copy of the memory location 30 is already in its corresponding cache memory 14a-14f, the processor 12a-12fmay acquire the information from the corresponding cache memory 14a-14fat a rate that is many times faster than the same acquisition from either the first memory 18aor the second memory 18b.

[0033] Ideally, the speed of the cache memories 14a-14fis equal to the speed of the processors 12a-12fin order to minimize the amount of time the processors 12a-12fwait on memory operations. Hence, the cache memories 14a-14fmay effectively decrease the average latency of memory operations by speeding up a large percentage of memory operations. However, since both the cost of the memory system and the number of memory operations that may be performed directly to and from the cache memories 14a-14fincreases as the capacity of the cache memories 14a-14fincreases, the storage capacity of the cache memories 14a-14fis a compromise between performance of the memory system and cost of the memory system.

[0034] The interconnection bus 9 is a set of conductor lines that transmits information between the first memory controller 16aand the second memory controller 16b. Likewise, the first processor bus 20ais a set of conductor lines that transmits information between the first memory controller 16aand the first group of caching agents 10a, and the second processor bus 20bis a set of conductor lines that transmits information between the second memory controller 16band the second group of caching agents 10b. In the preferred embodiment, the interconnection bus 9, the first processor bus 20a, and the second processor bus 20bare each pipe-lined split transaction buses (e.g. a Pentium Pro™ processor bus) in which memory operations are split into several phases such as an arbitration phase, a request phase, a snoop phase, a response phase, and a data phase, and in which several memory operations at different phases may be concurrently taking place.

[0035] The interconnection bus 9, the first processor bus 20a, and the second processor bus 20bin the preferred embodiment perform similarly. Therefore, in order to simplify the following description of the various bus phases, only the operation of the first processor bus 20awill be described. One of the first bus phases of a typical memory operation is the arbitration phase. During the arbitration phase, the processors 12a-12dof the first group of caching agents 10aand the first memory controller 16aarbitrate for access to the first processor bus 20a. The winner of this arbitration phase is granted the right to issue a memory request during the following request phase.

[0036] After the arbitration phase comes the request phase. In the request phase, a processor 12a-12dof the first group of caching agents 10aor the first memory controller 16aissues on the first processor bus 20aa memory request (e.g. a read request, or a write request) that targets a memory location 30. Generally, the memory request includes an address and a request type. The address indicates which memory location 30 the memory request is targeting, and the request type indicates the type of memory request (e.g. read, read for ownership, or write).

[0037] The snoop phase follows the request phase. During the snoop phase, each processor 12a-12dof the first group of caching agents 10adetermines whether its corresponding cache memory 14a-14dhas a valid copy of the targeted memory location 30 and whether the processor 12a-12dmust take some action in response to the memory request (e.g. invalidate cache lines 24, and/or transfer information stored in cache lines 24). The processors 12a-12dof the first group of caching agents 10amake this determination by comparing the address issued during the request phase to addresses of the memory line copies stored in their corresponding cache memories 14a-14d.

[0038] The response phase follows the snoop phase. During the response phase, a response to the memory request is issued from either the first memory controller 16aor one of the processors 12a-12dof the first group of caching agents 10a. The response indicates how the memory request will be handled. For example, the first memory controller 16amay indicate that the memory request is to be deferred, retried, stalled, or satisfied. If the memory request is to be deferred, the requested information will be supplied at some future time, thus freeing the first processor bus 20afor other memory requests. If the memory request is to be retried, the requesting processor 12a-12dis forced to re-issue the memory request. If the memory request is to be stalled, the memory request is temporarily stopped thereby delaying the data phase until the memory request can be satisfied. If the memory request is to be satisfied, the memory request continues to the data phase where information will be transferred in response to the memory request.

[0039] The data phase follows the response phase. During the data phase, information is transferred across the first processor bus 20ato fulfill the memory request. Depending upon the type of request and the contents of the cache memories 14a-14dof the first group of caching agents 10a, this transfer of information may be somewhat complicated due to the requirement that the cache memories 14a-14dremain coherent with the first memory 18a, the second memory 18b, and the cache memories 14e-14fof the second group of caching agents 10b.

[0040] Coherency methods or cache coherency methods refer to the methods that the computer system 6 utilizes to ensure that when a processor 12a-12frequests information from a memory location 30, the requesting processor 12a-12freceives a valid copy of the information (the latest, most up-to-date copy of the information). Since each of the cache memories 14a-14fstores copies of memory lines 28, the computer system 6 must implement coherency methods to make sure that whenever a processor 12a-12frequests information from the first memory 18aor the second memory 18b, the requesting processor 12a-12freceives a valid copy of the requested information no matter where that valid copy resides (i.e. the cache memories 14a-14f, the first memory controller 16a, the second memory controller 16b, the first memory 18a, or the second memory 18b).

[0041] The computer system 6 maintains coherency via (a) coherency rules, (b) the first MLST 19a, (c) the second MLST 19b, (d) the various phases of the interconnection bus 9, the first processor bus 20a, the second processor bus 20b, and (e) memory intervention cycle (MIC) requests. MIC requests are essentially read or read invalidate requests that are issued by the first memory controller 16aand the second memory controller 16bin order to maintain coherency between the first node 8aand the second node 8b.

[0042] One coherency rule of the preferred embodiment is that each cache line 24 and corresponding memory line 28 stored therein is marked as being in one of four states: a “modified” state, an “exclusive” state, a “shared” state, or an “invalid” state. A cache line 24 is marked as being in the invalid state if the cache line 24 does not contain a valid copy of a memory line 28 or has been requested to invalidate its copy of a memory line 28. A cache line 24 is marked as being in the shared state if the cache line 24 of a cache memory 14a-14dhas a valid, unmodified copy of a memory line 28 and another cache line 24 of another cache memory 14a-14dmay also have a valid, unmodified copy of the same memory line 28. A cache line 24 is marked as being in the exclusive state if the cache line 24 has a valid, unmodified copy of a memory line 28 and no other cache line 24 may have a valid, unmodified copy of the same memory line 28. Finally, a cache line 24 is marked as being in the modified state if the cache line 24 has a modified copy of a memory line 28 that has not been written back to the main memory 18.

[0043] Another coherency rule of the preferred embodiment is that a processor 12a-12fmay only modify a memory line 28 stored in a cache line 24 if the cache line 24 was in a modified state or an exclusive state prior to the modification. In the preferred embodiment, a processor 12a-12fmay place a cache line 24 into the exclusive state by issuing a “read for ownership” request or a “read and invalidate” request upon its respective processor bus 20aor 20b. The “read for ownership” request causes a valid copy of the requested memory line 28 to be placed into a cache line 24 of the cache memory 14a-14fthat corresponds to the requesting processor 12a-12fand causes the cache memories 14a-14fthat do not correspond to the requesting processor 12a-12fto invalidate any copy of the requested memory line 28 that may reside in these non-corresponding cache memories 14a-14f.

[0044] Furthermore, another coherency rule of the preferred embodiment is that the processors 12a-12fand corresponding cache memories 14a-14fare forced to writeback any modified memory line 28 to the first memory 18aor the second memory 18bwhen the modified memory line 28 is replaced or invalidated in the cache memories 14a-14f. Yet another coherency rule of the preferred embodiment is that (a) MIC requests and (b) memory requests that generate writebacks from the cache memories 14a-14fto their respective local memory controller 16aor 16bmay not be deferred or retried, but may be stalled. The above combination of coherency rules ensures that a modified copy of a memory line 28 is easily tracked and that only one of the cache memories 14a-14fmay contain a modified copy of a memory line 28, thus simplifying the determination of where valid data exists in the computer system 6.

[0045] One consequence of the above coherency rules is that a memory line such as memory line 28′ that has been modified in a cache line such as cache line 24′ is written back to the first memory 18ain response to a read or read invalidate type of request that targets a first memory line 28′ if the memory request is issued from a non-corresponding processor such as processors 12b-12d. A writeback in response to a read or read invalidate type of request is referred to as an implicit writeback. An implicit writeback is different than a normal writeback in that activities other than corresponding processor activities cause the writeback. In a normal writeback, a processor 12a-12fmay force its corresponding cache memory 14a-14fto writeback a modified memory line. Typically a processor 12a-12fdoes a normal writeback in response to two situations: (a) a modified memory line 28 is replaced with another memory line 28; or (b) the cache memory 14a-14fhas reached some triggering condition such as a time interval has expired or a certain percentage of the cache memory 14a-14fcontains modified memory lines 28.

[0046] While the above coherency rules and the various bus phases of the first processor bus 20a, and the second processor bus 20bmaintain coherency within a single node 8aor 8b, the first MLST 19a, the second MLST 19b, and the MIC requests provide a mechanism for maintaining coherency across the first node 8aand the second node 8b. The first MLST 19aand the second MLST 19bare each implemented in SRAM in the preferred embodiment. The first MLST 19acontains status information about each cached memory line of the first memory 18a(i.e. each memory line 28 of the first memory 18athat is stored in the cache memories 14a-14f). Likewise, the second MLST 19bcontains status information about each cached memory line of the second memory 18b. The first memory controller 16autilizes the information stored in the first MLST 19ato determine whether a memory request on the first processor bus 20arequires a MIC request be issued to the second memory controller 16bvia the interconnection bus 9. Likewise, the second memory controller 16butilizes the information stored in the second MLST 19bto determine whether a memory request on the second processor bus 20brequires a MIC request be issued to the first memory controller 16avia the interconnection bus 9.

[0047] In the preferred embodiment, each cached memory line 28 is marked in either the first MLST 19aor the second MLST 19bas being in an “owned local” state, “owned remote” state, a “shared local” state, or a “shared both” state. In particular, a memory line 28 may be marked in the first MLST 19aas (a) “owned local” if a single cache memory 14a-14dof the first group of caching agents 10amay contain a copy of the memory line 28 in the modified state or the exclusive state, (b) “owned remote” if a single cache memory 14e-14fof the second group of caching agents 10bmay contain a copy of the memory line 28 in the modified state or the exclusive state, (c) “shared local” if one or more cache memories 14a-14dof the first group of caching agents 10amay contain a copy of the memory line 28 in the shared state or the invalid state, or (d) “shared both” if cache memories 14a-14fof both the first group of caching agents 10aand the second group of caching agents 10bmay contain a copy of the memory line 28 in the shared state or the invalid state.

[0048] Likewise, a memory line 28 may be marked in the second MLST 19bas (a) “owned local” if a single cache memory 14e-14fof the second group of a caching agents 10bmay contain a copy of the memory line 28 in the modified state or the exclusive state, (b) “owned remote” if a single cache memory 14a-14dof the first group of caching agents 10amay contain a copy of the memory line 28 in the modified state or the exclusive state, (c) “shared local” if one or more cache memories 14e-14fof the second group of caching agents 10bmay contain a copy of the memory line 28 in the shared state or the invalid state, or (d) “shared both” if cache memories 14a-14fof both the first group of caching agents 10aand the second group of caching agents may contain a copy of the memory line 28 in the shared state or the invalid state.

[0049] In addition to the above states, the first memory controller 16aand the second memory controller 16bmark each memory line 28 that is targeted by a pending MIC request as being in a transient state. The transient state essentially means that a MIC request for the marked memory line 28 has been generated but has yet to complete. The first memory controller 16aand the second memory controller 16buse this transient state information to help simplify their respective coherency logic. In particular, the first memory controller 16aand the second memory controller 16b, if possible, retry any subsequent memory request that targets a memory line 28 that is marked in the transient state. By doing so, the first memory controller 16aand the second memory controller 16bensure that any subsequent memory request to the marked memory line 28 will complete after the pending MIC request to the marked memory line 28, thus maintaining coherency. However, it should be appreciated from the above coherency rules, that the first memory controller 16aand the second memory controller 16bmay not retry or defer (a) MIC requests, or (b) memory requests that generate writebacks. As a result, the first memory controller 16aand the second memory controller 16binclude additional coherency logic to deal with these requests. In particular the first memory controller 16aand the second memory controller 16binclude writeback collapsing circuitry in order to process requests that may not be deferred or retried but target memory lines marked in the transient state.

[0050] The first memory controller 16areceives and processes memory requests from the first processor bus 20aand the interconnection bus 9 and generally ensures that the memory request obtains the latest copy of the targeted memory line 28. To ensure that the memory request s obtain the latest copy of the targeted memory line 28, the first memory controller 16amay need to (a) obtain a copy of the targeted memory line 28 from the first memory 18a, (b) obtain a copy of the targeted memory line 28 from its writeback collapsing circuitry, (c) allow a processor 12a-12dof the first group of caching agents 10ato deliver a copy of the targeted memory line from its corresponding cache memory 14a-14d, and/or (d) issue a MIC request to the second memory controller 16bvia the interconnection bus 9 in order to (i) obtain a copy of the targeted memory line 28 from a cache memory 14e-14fof the second group of caching agents 10b, (ii) invalidate copies of the targeted memory line 28 stored in cache memories 14e-14fof the second group of caching agents 10b, (iii) update the second MLST 19b, and/or (iv) obtain the targeted memory line 28 from the second memory 18b.

[0051] The second memory controller 16breceives and processes memory requests from the second processor bus 20band the interconnection bus 9 and generally ensures that the memory requests obtain the latest copy of the targeted memory line 28. To ensure that the memory request obtains the latest copy of the targeted memory line 28, the second memory controller 16bmay need to (a) obtain a copy of the targeted memory line 28 from the second memory 18b, (b) obtain a copy of the targeted memory line 28 from its writeback collapsing circuitry, (c) allow a processor 12e-12fof the second group of caching agents 10bto deliver a copy of the targeted memory line from its corresponding cache memory 14e-14f, and/or (d) issue a MIC request to the first memory controller 16avia the interconnection bus 9 in order to (i) obtain a copy of the targeted memory line 28 from a cache memory 14a-14dof the first group of caching agents 10a, (ii) invalidate copies of the targeted memory line 28 stored in cache memories 14a-14dof the first group of caching agents 10a, (iii) update the first MLST 19a, and/or (iv) obtain the targeted memory line 28 from the first memory 18a.

[0052] Upon deciding to process a memory request, the first memory controller 16achecks and updates the information stored in the first MLST 19ain order to determine whether a MIC request is required for the selected request. Likewise, upon deciding to process a memory request, the second memory controller 16bchecks and updates the information stored in the second MLST 19bin order to determine whether a MIC request is required for the selected request. For example, if the second memory controller 16breceives a read for ownership request for the memory line 28′ from processor 14eof the second group of caching agents 10band the second MLST 19bindicates that the memory line 28′ is “owned remote,” then the second memory controller 16bmust issue a MIC request upon the interconnection bus 9 in order to obtain the latest copy of the memory line 28′ and to invalidate any copy of the memory line 28′ that is stored in cache memories 14a-14dof the first group of caching agents 10a.

[0053] Furthermore, the first memory controller 16aincludes writeback collapsing circuitry which reduces the number of transfers across the interconnection bus 9 by collapsing multiple writes from the first caching agents 10ato the second memory 18binto a single write. Likewise, the second memory controller 16bincludes writeback circuitry which reduces the number of transfers across the interconnection bus 9 by collapsing multiple writes from the second caching agents 10bto the first memory 18ainto a single write. Since the writeback circuitry of the first memory controller 16aand the second memory controller 16bfunction similarly in the preferred embodiment, only the writeback circuitry of the first memory controller 16awill be described in detail. As shown in FIG. 2, the writeback collapsing circuitry 50 of the first memory controller 16aincludes a collapsing controller 51, a writeback storage 58, a write status monitor 64, and an output latch 66.

[0054] The collapsing controller 51 is coupled to the first processor bus 20aand to the writeback storage 58. The write status monitor 64 is coupled to the writeback storage 58 and is further coupled to the output latch 66 which is in turn coupled to the first memory bus 22a. The collapsing controller 51 controls the collapsing of writebacks on the first processor bus 20a. The collapsing controller 51 includes an address latch 52, a comparator 56, a storage full monitor 60, and a bus stall controller 62.

[0055] The address latch 52 is configured to latch the address of a memory request on the first processor bus 20aduring the request phase of the memory request. The purpose of the address latch 52 is to latch the address of a writeback, to hold the address while the comparator 56 compares the latched address to addresses in the writeback storage 58, and, when appropriate, to pass the writeback address on to the writeback storage 58. Since in the preferred embodiment the first processor bus 20ais a pipe-lined bus, multiple memory requests may be pending on the first processor bus 20aat any given time. As a result, the address latch 52 in the preferred embodiment contains several storage locations for storing addresses of multiple pending memory requests.

[0056] The comparator 56, when an address is latched by the address latch 52, compares the latched address to the addresses stored in the writeback storage 58. The purpose of the comparator 56 is to generate a hit signal when the latched address corresponds to, maps to, or targets a memory line 28 that is already targeted by a pending writeback in the writeback storage 58. If the hit signal is generated and the present memory request generates a writeback, the generated writeback can be collapsed with a pending writeback stored in the writeback storage 58.

[0057] The writeback storage 58 includes an address store 68 and a data store 70. Both the address store 68 and the data store 70 in combination form several storage elements 74 for storing writebacks or writeback requests. In other words, each storage element 74 includes an address portion and a data portion. The writeback storage 58 further has an output whereby the contents of the writeback storage 58 can be transmitted to the output latch 66 via the write status monitor 64. The writeback storage 58 in the preferred embodiment has eight storage elements 74; however, it should be appreciated that certain advantages of the present invention may be obtained from a writeback storage 58 that contains a different number of storage elements 74. Furthermore, the writeback storage 58 in the preferred embodiment has a buffer structure wherein writebacks are buffered and can be serviced in any order.

[0058] The storage full monitor 60 generates a full signal when the writeback storage 58 is full (i.e. has no storage elements 74 that are empty or available). A storage element 74 is considered available when it no longer stores a pending writeback. The bus stall controller 62 stalls the first processor bus 20ato ensure that a writeback is not lost due to lack of storage in the first memory controller 16a. In one embodiment of the present invention, the bus stall controller 62 stalls the first processor bus 20awhen the storage full monitor 60 generates the full signal and the comparator 56 does not generate the hit signal.

[0059] The write status monitor 64 monitors pending MIC requests and prevents data stored in the writeback storage 58 from being transferred to the second memory controller 16bif the writeback data targets a memory line 28 that is targeted by a pending MIC request. Once the first memory controller 16aresolves the data phase of the pending MIC request, the write status monitor 64 allows data stored in the writeback storage 58 to be transferred to the second memory controller 16bin order to fulfill the MIC request and to update the second memory 18b. This prevention of data transfer until the MIC request is resolved, ensures that the latest copy of the targeted memory line 28 is written back to the second memory 18b. Once the data phase of the MIC request resolves, the write status monitor 64 may latch the address and data of a pending writeback for the memory request into the output latch 66. The output latch 66, then, holds the address and data being written to the second memory 18buntil the transfer across the interconnection bus 9 to the second memory controller 16bis completed.

[0060] Referring now to FIG. 3, there is shown a writeback collapsing method 300. In order to simplify the description, the writeback collapsing method 300 will be described as applied to only the first processor bus 20a. The writeback collapsing method 300 begins in step 302 with a processor 12a-12dof the first group of caching agents 10aissuing a memory request that targets a memory line 28. In particular, a processor 12a-12dof the first group of caching agents 10aduring the request phase of the first processor bus 20aplaces a first address upon the first processor bus 20awhich maps to one of the memory lines 28. Also, during the request phase, the processor 12a-12dplaces a request type on the first processor bus 20athat indicates the type of memory request that the processor 12a-12ddesires to perform. In response to the processor 12a-12dissuing the request upon the first processor bus 20a, the address latch 52 of the first memory controller 16alatches the first address of the request (step 304).

[0061] During the snoop phase of step 306, the non-requesting processors 12a-12dof the first group of caching agents each determine from the address of the request and information stored in its corresponding cache memory 14a-14dwhether the non-requesting processor 12a-12dmust take some action in response to the memory request (e.g. invalidate a cache line 24 or supply a modified memory line 28). Furthermore, each non-requesting processor 12a-12dgenerates a separate snoop result upon the first processor bus 20athat is indicative of the status of the targeted memory line 28 in its corresponding cache memory 14a-14d.

[0062] In step 308, the first memory controller 16adetermines from the snoop results generated during the snoop phase and the request type of the present request whether the present request will generate a writeback. If the memory controller 16 determines that no writeback will be generated, then computer system 6 ends its attempt of collapsing a writeback of the present memory request with another writeback. However, if the first memory controller 16adetermines that a writeback will be generated, then the computer system 6 continues to step 310.

[0063] In step 310, the comparator 56 of the first memory controller 16acompares the latched address with addresses of other writebacks which are stored in the writeback storage 58. If the address maps to the same memory line 28 as another address of the writeback storage 58, then the comparator 56 generates a hit signal. Furthermore, in step 310, if the writeback storage 58 is full, the storage full monitor 60 generates a full signal.

[0064] In step 312, the bus stall controller 62 determines whether the full signal and the hit signal were generated in step 310. If in step 310 the full signal was not generated or the hit signal was generated, the computer system 6 proceeds to step 314. However, if in step 310 the full signal was generated and the hit signal was not generated, then the bus stall controller 62 stalls the first processor bus 20aand the computer system 6 returns to step 310. In essence, if in step 310 the full signal was generated and the hit signal was not generated, the bus stall controller 62 stalls the first processor bus 20auntil a storage element 74 of the writeback storage 58 becomes available. However, if in step 310 the full signal was not generated or the hit signal was generated, then the bus stall controller 62 need not stall the first processor bus 20abecause the first memory controller 16ahas sufficient storage space to process a writeback regardless of whether the writeback may be collapsed with another writeback.

[0065] In step 314, the first memory controller 16adetermines whether the hit signal was generated in step 310. If the hit signal was generated in step 310, then the computer system 6 proceeds to step 316 where the writeback storage 58 is configured to collapse a writeback with another writeback. However, if the hit signal was not generated in step 310, the computer system 6 proceeds to step 318 where the writeback storage 58 is configured to store a writeback in an empty storage element 74 of the writeback storage 58.

[0066] For step 316, the latched address is written over another address in the address store 68 that corresponds to another writeback stored in the writeback storage 58. Furthermore, the corresponding location in the data store 70 is configured to store the modified memory line 28 during the data phase of the request issued in step 302. For step 318, the latched address is stored in an available location in the address store 68 of the writeback storage 58. Furthermore, the corresponding location in the data store 70 is configured to store the modified memory line 28 during the data phase of the request issued in step 302.

[0067] After the writeback storage 58 is properly configured, the non-requesting processor 12a-12dof the first group of caching agents 10awhich contains the modified copy of the memory line 28 transfers, during the data phase of step 320, the modified memory line 28 from a cache line 24 of its cache memory 14a14dto a cache line 24 of the cache memory 14a-14dof the requesting processor 12a-12d. The transfer of the modified memory line 28 during the data phase of the first processor bus 20aalso causes the modified memory line 28 to be stored in the data portion of one of the storage elements 74 since the data store 70 was configured in step 316 or step 318 to receive the modified memory line 28. After step 320, the requesting processor 12a-12dof the first group of caching agents 10aand the writeback storage 58 have valid copies of the requested memory line 28.

[0068] In order to illustrate the writeback collapsing method 300 in greater detail, a flowchart is shown in FIG. 4 of an exemplary series of memory requests 400 that utilize the writeback collapsing method 300. The following description of the exemplary series of memory requests 400 assumes that first data is stored in a first memory location 30′ of the second memory 18band that no writebacks are stored in the writeback storage 58 of the first memory controller 16a.

[0069] In step 402, a first processor 12aof the first group of caching agents 10aissues upon the first processor bus 20aa first read for ownership request that targets the first memory location 30′. Assuming that the second memory 18bcontains the only valid copy of the first memory location 30′, the information stored in a first memory line 28′ which includes the first data stored in the first memory location 30′ is transferred from the second memory 18bto a first cache line 24′ of a first cache memory 14a. The first word 26′ of the first cache line 24′ now contains a valid copy of the first data stored in the first memory location 30′. Furthermore, the first cache line 24′ is marked as being in the exclusive state since the first processor 12aissued a read for ownership request in step 402.

[0070] The first processor 12athen in step 404 generates second data for the first memory location 30′ by modifying the copy of the first memory location 30′ in its corresponding first cache memory 14a(i.e. by writing the second data over the first data stored in first word 26′ of first cache line 24′). As a direct result of modifying the copy of the first memory location 30′, the copy of the first memory line 28′ which is stored in the first cache line 24′ is also modified. Therefore, the first cache line 24′ is marked as being in the modified state.

[0071] In step 406, a second processor 12bof the first group of caching agents 10adesires to modify a second memory location 30″ which is also a part of the first memory line 28′. However, due to the coherency rules of the preferred embodiment, the second processor 12bmay only modify those memory lines 28 which are stored in its corresponding second cache memory 14bin an exclusive state or a modified state. Therefore, in order to obtain an exclusive state copy of the second memory location 30″, the second processor 12bissues upon the first processor bus 20aa second read for ownership request that targets the second memory location 30″. In particular, the second processor 12bduring the request phase of the first processor bus 20aplaces a first address upon the first processor bus 20awhich maps to the second memory location 30″ and therefore also maps to the first memory line 28′. Also, during the request phase, the second processor 12bplaces a request type on the first processor bus 20athat indicates that the second processor 12bdesires to perform a read for ownership request. In response to the second processor 12bissuing the second memory request upon the first processor bus 20a, the address latch 52 of the first memory controller 16alatches the first address of the second memory request (step 408).

[0072] During the snoop phase of step 410, each non-requesting processor 12a, 12c, and 12dof the first group of caching agents 10adetermines from the first address of the second memory request and information stored in its corresponding cache memory 14a, 14c, or 14dwhether it must take some action in response to the second memory request (e.g. invalidate a cache line 24 or supply a modified copy of the first memory line 28′). Furthermore, each non-requesting processor 12a, 12c, and 12dgenerates a separate snoop result upon the first processor bus 20athat is indicative of the status of the first memory line 28′ in its corresponding cache memory 12a, 12c, or 12d.

[0073] In step 412, since the first cache memory 14acontains a first modified copy of the first memory line 28′, the combination of the request type and the generated snoop results informs the first memory controller 16athat the second memory request will generate a writeback. Therefore, the computer system 6 proceeds to step 414.

[0074] In step 414, the comparator 56 of the first memory controller 16agenerates a hit signal if the first address indicates that the memory request maps to the same memory line of the second memory 18bas a writeback stored in the writeback storage 58. Furthermore, in step 414, the storage full monitor 60 generates a full signal if the writeback storage is full. Since the present example assumes that no pending writebacks were stored in the writeback storage 58 prior to the first memory request of step 402, the comparator 56 does not generate the hit signal and the storage full monitor 60 does not generate the full signal.

[0075] In step 416, the bus stall controller 62 determines that the full signal was not generated in step 414. As a result, the bus stall controller 62 does not stall the first processor bus 20aand the computer system 6 proceeds to step 418. In other words, the first memory controller 16ahas sufficient storage space to process a writeback regardless of whether the writeback may be collapsed with another writeback and the bus stall controller 62 has no need to stall the first processor bus 20a.

[0076] In step 418, the first memory controller 16adetermines that the hit signal was not generated in step 414. As a result, the computer system 6 proceeds to step 422 where the writeback storage 58 is configured to store a writeback in an empty storage element 74′ of the writeback storage 58.

[0077] The latched first address in step 422 is stored in an empty location in the address store 68 of the writeback storage 58. Furthermore, the corresponding location in the data store 70 is configured to store the first modified copy of the first memory line 28′ during the data phase of the second memory request. In particular, the first address is stored in the address portion of a first storage element 74′ and the corresponding data portion of the first storage element 74′ is configured to store the first modified copy of the memory line 28′, during the data phase of the second memory request.

[0078] After the writeback storage 58 is properly configured, the first processor 12aduring the data phase of step 424 transfers the first modified copy of the first memory line 28′ from the first cache line 24′ to a second cache line 24″ of the second cache memory 14b. The transfer of the first modified copy of the first memory line 28′ during the data phase of the first processor bus 20aalso causes the first modified copy of the first memory line 28′ to be stored in the data portion of the first storage element 74′ since the data store 70 was configured in step 422 to receive the first modified copy of the first memory line 28′.

[0079] After step 424, the second cache line 24″ contains a valid copy of the first memory line 28′ and is marked as being in the exclusive state since the second processor 12bissued a read for ownership request in step 406. In particular, a second word 26″ of the second cache line 24″ contains a copy of the second data for the first memory location 30′ and a third word 26′″ contains a copy of whatever was stored in the second memory location 30″. The second processor 12bthen in step 426 generates third data for the second memory location 30″ by writing the third data to the third word 26′″ of the second cache line 24″. As a direct result of writing the third data to the third word 26′″, the copy of the first memory line 28′ stored in the second cache line 24″ is also modified. Therefore, the second cache line 24″ is marked as being in the modified state.

[0080] In step 428, a third processor 12cof the first group of caching agents 10adesires to obtain data stored in the second memory location 30″ which is a part of the first memory line 28′. Therefore, in order to obtain a copy of the first memory line 28′ and the second memory location 30″, the third processor 12cissues upon the first processor bus 20aa third read request that targets the memory location 30″. In particular, the third processor 12cduring the request phase of the first processor bus 20aplaces a second address upon the first processor bus 20awhich maps to the second memory location 30″ and therefore also maps to the first memory line 28′. Also, during the request phase, the third processor 12cplaces a request type on the first processor bus 20athat indicates that the third processor 12cdesires to perform a read request. In response to the third processor 12cissuing the third memory request upon the first processor bus 20a, the address latch 52 of the first memory controller 16alatches the second address of the third memory request (step 430).

[0081] During the snoop phase of step 432, each non-requesting processor 12a, 12b, and 12dof the first group of caching agents 10adetermines from the second address of the request and information stored in its corresponding cache memory 14a, 14b, or 14dwhether it must take some action in response to the memory request (e.g. invalidate a cache line 24 or supply a modified copy of the first memory line 28′). Furthermore, each non-requesting processor 12a, 12b, and 12dgenerates a separate snoop result upon the first processor bus 20athat is indicative of the status of the first memory line 28′ in its corresponding cache memory 12a, 12b, or 12d.

[0082] In step 434, since the second cache memory 14acontains a second modified copy of the first memory line 28′, the combination of the request type and the generated snoop results informs the first memory controller 16athat the third memory request will generate a writeback. Therefore, the computer system 6 proceeds to step 436.

[0083] In step 436, the comparator 56 of the first memory controller 16agenerates a hit signal if the second address indicates that the third memory request maps to the same memory line of the second memory 18bas a writeback stored in the writeback storage 58. Furthermore, in step 436, the storage full monitor 60 generates a full signal if the writeback storage is full. The present example assumes that the writeback that was generated in response to the second read for ownership request of step 406 has yet to be written back to the second memory 18band that no other pending writebacks are stored in the writeback storage 58. As a result, the comparator 56 generates the hit signal since the second address maps to the first memory line 28′ and the writeback stored in the first storage element 74′ maps to the first memory line 28′. Further, the storage full monitor 60 does not generate the full signal since the writeback storage 58 in the preferred embodiment contains eight storage elements 74 and only the first storage element 74′ is occupied.

[0084] In step 438, the bus stall controller 62 determines that the full signal was not generated in step 436. As a result, the bus stall controller 62 does not stall the first processor bus 20aand the computer system 6 proceeds to step 440. In other words, the first memory controller 16ahas sufficient storage space to process a writeback regardless of whether the writeback may be collapsed with another writeback and the bus stall controller 62 has no need to stall the first processor bus 20a.

[0085] In step 440, the first memory controller 16adetermines that the hit signal was generated in step 436. As a result, the computer system 6 proceeds to step 444 where the writeback storage 58 is configured to collapse the writeback generated in response to the third memory request with the writeback stored in the writeback storage 58.

[0086] The latched second address in step 444 is written over the address stored in the first storage element 74′. Furthermore, the data portion of the first storage element 74′ is configured to store the second modified copy of the first memory line 28′ during the data phase of the third memory request.

[0087] Then, the second processor 12btransfers, during the data phase of step 446, the second modified copy of the first memory line 28′ from the second cache line 24″ to a third cache line 24′″ of the third cache memory 14c. The transfer of the second modified copy of the first memory line 28′ during the data phase of the first processor bus 20aalso causes the second modified copy of the first memory line 28′ to overwrite the first modified copy of the first memory line 28′ in the writeback storage 58.

[0088] As a result of replacing the first modified copy of the first memory line 28′ with the second modified copy of the second memory line 28′, the first memory controller 16a, in order to maintain coherency, need only transfer the second modified copy of the first memory line 28′ back across the interconnection bus 9 to the second memory controller 16bfor writing to the second memory 18b. As should be appreciated, the overwriting or collapsing of writebacks in the first memory controller 16aand the second memory controller 16breduces the amount of data transfer traffic across first memory bus 22a, the second memory bus 22b, and the interconnection bus 9, thus increasing the efficiency of these shared resources.

[0089] Furthermore, it should be appreciated from the above description of the exemplary series of memory requests 400 that the writeback collapsing circuitry 50 is especially useful for collapsing writebacks to a memory 18aor 18bthat is remote from the memory controller 16aor 16bthat receives the writeback. This is especially true since the memory controller 16aor 16bthat receives the writeback needs to arbitrate for the interconnection bus 9 before propagating the writeback through to the remote memory controller 16aor 16b. A considerable amount of time may pass between receiving the writeback and gaining access to the interconnection bus 9. As a result, receiving memory controller 16aor 16bmay easily receive and collapse other writebacks to the same memory line prior to propagating the writeback through to the remote memory controller 16aor 16b.

[0090] While the writeback collapsing circuitry 50 is especially useful for collapsing writebacks to a remote memory 18aor 18b, the writeback collapsing circuitry 50 may also be useful for collapsing writebacks to a local memory 18aor 18b. Since the local memory controller 16aor 16bis the only device coupled to its respective local memory 18aor 18b, the local memory controller 16aor 16bneed not arbitrate for access to its local memory 18aor 18b. As a result, the latency between receiving a writeback and writing it to a local memory 18aor 18bshould not be nearly as long as propagating a writeback to the remote memory 18aor 18b. As a result, the writeback collapsing circuitry 50 will probably have less opportunities for receiving additional writebacks to collapse before writing data back to its local memory 18aor 18b. However, any collapsing of writebacks to the local memory 18aor 18bwill reduce data traffic across its respective local memory bus 22aor 22b, thus increasing the performance of the computer system 6.

[0091] Shown in FIG. 5 is a flowchart of an exemplary series of memory requests 500 that illustrates how the writeback collapsing method 300 resolves a memory request deadlock situation. The following description of the exemplary series of memory request 500 assumes that first data is stored in a first memory location 30′ of the second memory 18band that no writebacks are stored in the writeback storage 58 of the second memory controller 16b.

[0092] In step 502, a first processor 12aof the first caching agents 10aissues upon the first processor bus 20aa first read for ownership request that targets a first memory location 30′. Assuming that the second memory 18bcontains the only valid copy of the first memory location 30′, the information stored in a first memory line 28′ which includes the first data stored in the first memory location 30′ is transferred from the second memory 18bto a first cache line 24′ of a first cache memory 14a. The first word 26′ of the first cache line 24′ now contains a valid copy of the first data stored in the first memory location 30′. Furthermore, since the first processor 12aissued a read for ownership request in step 502, the first cache line 24′ is marked as being in the exclusive state, and the second MLST 19bis updated to indicate that the first memory line 28′ is owned remote.

[0093] The first processor 12athen in step 504 generates second data for the first memory location 30′ by modifying the copy of the first memory location 30′ in its corresponding first cache memory 14a(i.e. by writing the second data over the first data stored in first word 26′ of first cache line 24′). As a direct result of modifying the copy of the first memory location 30′, the copy of the first memory line 28′ which is stored in the first cache line 24′ is also modified. Therefore, the first cache line 24′ is marked in the first cache memory 14aas being in the modified state.

[0094] In step 506, a fifth processor 12eof the second group of caching agents 10bdesires to modify a second memory location 30″ which is also a part of the first memory line 28′. However, due to the coherency rules of the preferred embodiment, the fifth processor 12emay only modify those memory lines 28 which are stored in its corresponding fifth cache memory 14ein an exclusive state or a modified state. Therefore, in order to obtain an exclusive state copy of the second memory location 30″, the fifth processor 12eissues upon the second processor bus 20ba second read for ownership request that targets the second memory location 30″. In particular, the fifth processor 12eduring the request phase of the second processor bus 20bplaces a first address upon the second processor bus 20bwhich maps to the second memory location 30″ and therefore also maps to the first memory line 28′. Also, during the request phase, the fifth processor 12eplaces a request type on the second processor bus 20bthat indicates that the fifth processor 12edesires to perform a read for ownership request.

[0095] In response to the fifth processor 12eissuing the second memory request upon the second processor bus 20b, the second memory controller 16breceives in step 508 the first address and the request type for the second memory request. Once the second memory controller 16bdecides to process the second memory request, the second memory controller 16bchecks the second MLST 19band updates the second MLST 19bto indicate that the first memory line 28′ is owned local. By checking the second MLST 19b, the second memory controller 16bdetermines that the first memory line 28′ was owned remote. As a result of the first memory line 28′ being owned remote, the second memory controller 16bissues in step 509 a first MIC request (i.e. a coherency request) upon the interconnection bus 9 in order to retrieve the latest copy of the first memory line 28′ and to invalidate any copy of the first memory line 28′ contained in the cache memories 14a-14dof the first group of caching agents 10a. It should be appreciated from the above that the first MIC request is essentially a read and invalidate request that includes the first address of the second memory request.

[0096] Furthermore, since the first memory line 28′ is owned remote, no caching agent of the second group of caching agents 10bwill generate a writeback in response to the second read for ownership request, and the second memory controller 16bis free to defer the data phase of the second memory request until a later time. Therefore, the second memory controller 16bissues a response during the response phase that indicates that the data phase will be deferred until a later time. Furthermore, the second memory controller 16bwill retry all subsequent memory requests to the first memory line 28′ if the subsequent memory requests may be retried and the first MIC request is still pending. It should be appreciate that, from the above mentioned coherency rules, the second memory controller 16bmay not retry MIC request or a memory request that generates a local writeback. As a result, the first memory controller 16awill be forced to process subsequent MIC requests or local writeback generating memory requests to the first memory line 28′ even though the first memory controller 16awould be more simple to implement if all subsequent memory requests to the first memory line 28′ could be retried until the first MIC request completed. However, since the first memory line 28′ was owned remote prior to the first MIC request, no caching agent of the second group of caching agents 10bcould generate a writeback to the first memory line 28′ prior to the completion of the first MIC request without violating the coherency rules of the computer system 6.

[0097] In response to the second memory controller 16bissuing the first MIC request upon the interconnection bus 9, the first memory controller 16areceives in step 510 the first MIC request which includes the first address of the second memory request and a request type indicating that the request is a MIC request. Once the first memory controller 16areceives the first MIC request, the first memory controller 16amarks in the first memory controller 16athe first memory line 28′ targeted by the first MIC request as being in the transient state. Furthermore, upon receiving the first memory request, the first memory controller retries all subsequent memory requests to the first memory line 28′ if the subsequent memory request may be retried and the first MIC request is still pending. It should be appreciated that, from the above mentioned coherency rules, the first memory controller 16amay not retry a MIC request or a memory request that generates a local writeback. As a result, the first memory controller 16awill be forced to process subsequent local writeback generating requests to the first memory line 28′ even though the first memory controller 16awould be more simple to implement if all subsequent memory request to the first memory line 28′ could be retried until-the first MIC request completed.

[0098] Once the first memory controller 16adecides to process the first MIC request, the first memory controller 16adetermines from the first address of the first MIC request that the first MIC request targets a memory line 28 that is remote from the first memory controller 16b. As a result, the first memory controller 16awill need to propagate the first MIC request through to the first processor bus 20ain order to obtain and invalidate any copy of the first memory line 28′ that may be stored in the cache memories 12a-12dof the first group of caching agents 10a. In order to propagate the first MIC request through to the first processor bus 20a, the first memory controller 16amust first arbitrate for and be granted access to the first processor bus 20a.

[0099] However, before the first memory controller 16ais granted access to the first processor bus 20ain order to propagate the first MIC request, the second processor 12bof the first group of caching agents is granted the first processor bus 20ain step 511. Upon being granted access to the first processor bus 20a, the second processor 12bissues a third read for ownership request for the first memory location 30′ which is a part of the first memory line 28′ (step 512). In response to the second processor 12bissuing the third read memory request, the first memory controller 16areceives (a) a request type indicating that the third memory request is a read for ownership request and (b) a second address that maps to the first memory location 30′ and therefore the first memory line 28′.

[0100] In step 514, the first memory controller 16aselects the third read for ownership memory request for processing. Once the first memory controller 16adecides to process the third memory request, the first memory controller 16adetermines from the second address that the third memory request targets a memory line 28 that is (a) remote from the first memory controller 16band (b) marked as being in the transient state due to the first MIC request having yet to complete. As a result, the first memory controller 16awill in order to avoid a deadlock situation either (a) defer or retry the third memory request if the third memory request does not generate a local writeback, or (b) utilize the writeback collapsing method 300 of FIG. 3 if the third memory request does generate a local writeback. In either case, the first memory controller 16awill not propagate the third memory request through to the interconnection bus 9 until the first MIC request completes and the first memory line 28′ is no longer marked as being in the transient state. Also in response to selecting the third memory request, the first address latch 52 of the first memory controller 16alatches the second address of the third read for ownership request in case the third memory request does generate a local writeback (step 516).

[0101] During the snoop phase of the third memory request, each non-requesting processor 12a, 12c, and 12dof the first group of caching agents 10ain step 518 determines from the second address of the third memory request and information stored in its corresponding cache memory 14a, 14c, or 14dwhether it must take some action in response to the third memory request (e.g. invalidate a cache line 24 or supply a modified copy of the first memory line 28′). Furthermore, each non-requesting processor 12a, 12c, and 12dgenerates a separate snoop result upon the first processor bus 20athat is indicative of the status of the first memory line 28′ in its corresponding cache memory 12a, 12c, or 12d.

[0102] In step 520, since the first cache memory 14acontains a first modified copy of the first memory line 28′, the combination of the request type and the generated snoop results informs the first memory controller 16athat the third memory request will generate a local writeback to the first memory line 28′. Therefore, the first memory controller 16awill not be able to retry or defer the third read for ownership request. The computer system 6 then proceeds to step 522.

[0103] As a result of the above memory requests, a deadlock situation would occur if the writeback collapsing method 300 were not employed. Since the third memory request precedes the first MIC request on the first processor bus 20a, the third memory request must resolve on the first processor bus 20abefore the first MIC request can resolve on the first processor bus 20a. However, without the writeback collapsing method 300 and the writeback collapsing circuitry 50, the third memory request would have to be propagated through the first memory controller 16ato the interconnection bus 9 in order for the third memory request to resolve. Since the first MIC request would precede the third memory request on the interconnection bus 9, the first MIC request would have to resolve prior to the third memory request being resolved. Therefore, the third memory request would block the first MIC request from completing on the first processor bus 20aand the first MIC request would block the third memory request from completing on the interconnection bus 9. In other words, a circular dependency has occurred which the first memory controller 16amust resolve by breaking one of the dependencies. The writeback collapsing circuitry 50 allows the first memory controller 16ato break one of these dependencies while still retaining coherency.

[0104] In step 522, the comparator 56 of the first memory controller 16agenerates a hit signal if the first address indicates that the memory request maps to the same memory line of second memory 18bas a writeback stored in the writeback storage 58. Furthermore, in step 522, the storage full monitor 60 generates a full signal if the writeback storage is full. Since the present example assumes that no pending writebacks were stored in the writeback storage 58 prior to the third memory request of step 512, the comparator 56 does not generate the hit signal and the storage full monitor 60 does not generate the full signal.

[0105] In step 524, the bus stall controller 62 determines that the full signal was not generated in step 522. As a result, the bus stall controller 62 does not stall the first processor bus 20aand the computer system 6 proceeds to step 526. In other words, the first memory controller 16ahas sufficient storage space to process a writeback regardless of whether the writeback may be collapsed with another writeback and the bus stall controller 62 has no need to stall the first processor bus 20a.

[0106] In step 526, the first memory controller 16 determines that the hit signal was not generated in step 522. As a result, the computer system 6 proceeds to step 530 where the writeback storage 58 is configured to store a writeback in an empty storage element 74 of the writeback storage 58.

[0107] The latched second address in step 530 is stored in an empty location in the address store 68 of the writeback storage 58. Furthermore, the corresponding location in the data store 70 is configured to store the first modified copy of the first memory line 28′ during the data phase of the third memory request. In particular, the first address is stored in the address portion of a first storage element 74′ and the corresponding data portion of the first storage element 74′ is configured to store the first modified copy of the memory line 28′, during the data phase of the third memory request.

[0108] After the writeback storage 58 is properly configured, the first processor 12aduring the data phase of step 532 transfers the first modified copy of the first memory line 28′ from the first cache line 24′ to a second cache line 24″ of the second cache memory 14b. The transfer of the first modified copy of the first memory line 28′ during the data phase of the first processor bus 20aalso causes the first modified copy of the first memory line 28′ to be stored in the data portion of the first storage element 74′ since the data store 70 was configured in step 530 to receive the first modified copy of the first memory line 28′.

[0109] After step 532, the second cache line 24″ contains a valid copy of the first memory line 28′ and is marked as being in the exclusive state since the second processor 12bissued a read for ownership request in step 512. In particular, a second word 26″ of the second cache line 24″ contains a copy of the second data for the first memory location 30′ and a third word 26′″ contains a copy of whatever was stored in the second memory location 30″. The second processor 12bthen in step 534 generates third data for the first memory location 30″ by writing the third data to the second word 26″ of the second cache line 24″. As a direct result of writing the third data to the second word 26″, the copy of the first memory line 28′ stored in the second cache line 24″ is also modified. Therefore, the second cache line 24″ is marked as being in the modified state.

[0110] In step 536, the first memory controller 16aobtains access to the first processor bus 20aand propagates the first MIC request upon the first processor bus 20a. Furthermore, in response to propagating the first MIC request, the address latch 52 latches the first address of the first MIC request (step 538).

[0111] During the snoop phase of step 540, each non-requesting processor 12a, 12b, 12c, and 12dof the first group of caching agents 10adetermines from the first address of the first MIC request and information stored in its corresponding cache memory 14a, 14b, 14c, or 14dwhether it must take some action in response to the first MIC request (e.g. invalidate a cache line 24 or supply a modified copy of the first memory line 28′). Furthermore, each non-requesting processor 12a, 12b, 12c, and 12dof the first group of caching agents 10agenerates a separate snoop result upon the first processor bus 20athat is indicative of the status of the first memory line 28′ in its corresponding cache memory 12a, 12b, 12c, or 12d.

[0112] In step 542, since the second cache memory 14acontains a second modified copy of the first memory line 28′, the combination of the request type of the first MIC request and the generated snoop results informs the first memory controller 16athat the present request will generate a writeback. Therefore, the computer system 6 proceeds to step 544.

[0113] In step 544, the comparator 56 of the first memory controller 16agenerates a hit signal if the first address indicates that the first MIC request maps to the same memory line of the second memory 18bas a writeback stored in the writeback storage 58. Furthermore, in step 544, the storage full monitor 60 generates a full signal if the writeback storage 58 is full. Since the write status monitor 64 of the first memory controller 16aprevents writebacks that target memory lines 28 that are also targeted by pending MIC requests from being transferred to the second memory controller 16b, the writeback that was generated in response to the third memory request has yet to be written back to the second memory 18b. As a result, the comparator 56 generates the hit signal since the first address maps to the first memory line 28′ and the writeback stored in first storage element 74′ maps to the first memory line 28′. Furthermore, the storage full monitor 60 does not generate the full signal since the writeback storage 58 in the preferred embodiment contains eight storage elements 74 and only the first storage element 74′ is occupied.

[0114] In step 546, the bus stall controller 62 determines that the full signal was not generated in step 544. As a result, the bus stall controller 62 does not stall the first processor bus 20aand the computer system 6 proceeds to step 548. In other words, the first memory controller 16ahas sufficient storage space to process a writeback regardless of whether the writeback may be collapsed with another writeback and the bus stall controller 62 has no need to stall the first processor bus 20a.

[0115] In step 548, the first memory controller 16adetermines that the hit signal was generated in step 544. As a result, the computer system 6 proceeds to step 552 where the writeback storage 58 is configured to collapse the writeback generated in response to the first MIC request with the writeback stored in the first storage element 74′.

[0116] The latched second address in step 552 is written over the address stored in the first storage element 74′. Furthermore, the data portion of the first storage element 74′ is configured to store the second modified copy of the first memory line 28′ during the data phase of the first MIC request.

[0117] Then, the second processor 12btransfers, during the data phase of step 554, the second modified copy of the first memory line 28′ from the second cache line 24″ to the first memory controller 16a. The transfer of the second modified copy of the first memory line 28′ during the data phase of the first processor bus 20aalso causes the second modified copy of the first memory line 28′ to overwrite the first modified copy of the memory line 28′ in the writeback storage 58.

[0118] Then, in step 556, the write status monitor 64 allows the first memory controller 16ato transfer the second modified copy of the first memory line 28′ from the writeback storage 58 to the second memory controller 16bin order to complete the first MIC request. Upon completing the first MIC request, the first memory controller 16aand the second memory controller 16bmark the first memory line 28′ as no longer being in the transient state. The second memory controller 16bthen transfers the second modified copy of the first memory line 28′ to a fourth cache line 24″″ of the fifth cache memory 14ein order to compete the second memory request. After step 556, (1) the fifth processor 12eand corresponding fifth cache memory 14ehave the latest copy of the first memory line 28′ in the exclusive state, (2) the first group of caching agents 10ado not contain a valid copy of the first memory line 28′, (3) the second MLST 19bproperly indicates that the first memory line 28′ is owned local, and (4) the second memory controller 16bhas the latest copy of the first memory line 28′ scheduled for writing back to the second memory 18b. In other words, the computer system 6 has maintained coherency in processing the exemplary memory requests 500.

[0119] It should be appreciated that since the interconnection bus 9, the first processor bus 20a, and the second processor bus 20bare preferably pipe-lined memory buses, several memory requests may be pending upon the buses at any give time. While the above exemplary series of memory requests 400 and 500 were essentially described in a sequential manner where a second memory request was initiated by the memory controllers 16aand 16bafter a first memory request completed, this sequential description was used to merely simplify the description. In other words, the three memory requests of exemplary series 400 may have all been in progress on the first processor bus 20asimultaneously, but in different phases. Likewise, the memory requests and the MIC request of exemplary series 500 may have all been in progress simultaneously, but in different phases.

[0120] Furthermore, since writebacks in the preferred embodiment may not be deferred or retried, the stalling of the first processor bus 20aensures that the first memory controller 16ahas available storage capacity for storing a normal writeback or an implicit writeback until the information is actually written back to the first memory 18a. In other words, the stalling of the processor buses 20aand 20bensures that no writebacks are lost due to lack of storage in the memory controllers 16aand 16b. It should be appreciated that the above writeback collapsing method 300 may be modified to stall the processor buses 20aand 20bafter different phases of the processor buses 20aand 20bor when different conditions occur. Furthermore, it should be appreciated that modifications to the writeback collapsing circuitry 50 may require that the processor buses 20aand 20bbe stalled after different phases or different conditions. The above method 300 basically stalls the processor buses 20aand 20bafter the snoop phase of a memory request; however, the writeback collapsing circuitry 50 could stall prior to the resolution of the snoop phase by stalling the processor buses 20aand 20bas soon as the writeback storage 58 for the local memory controller 16aor 16bis full. Furthermore, the writeback collapsing circuitry 50 could be configured to stall the processor buses 20aand 20bin response to the address store 68 or the data store 70 or the local memory controller 16aor 16bbeing full.

[0121] While the invention has been illustrated and described in detail in the drawings and foregoing description, such illustration and description is to be considered as exemplary and not restrictive in character, it being understood that only the preferred embodiment has been shown and described and that all changes and modifications that come within the spirit of the invention are desired to be protected.