Method and apparatus for relaxing the FIFO ordering constraint for memory accesses in a multi-processor asynchronous cache system

[0002] 1. Field of the Invention

[0003] The present invention relates to memory models for microprocessor control. More particularly, the present invention relates to relaxing the first-in-first-out (FIFO) constraint on the processing of all snoop requests received from the system bus. Some concurrent processing of snoop requests is possible through the separation of locally generated requests from remotely generated requests, allowing selected requests to proceed without strict order constraints.

[0004] 2. The Prior Art

[0005] In computer systems, memory access times often limit the throughput of the system. Relative to current processor speeds, data access times for the main memory can be quite long. One scheme to minimize this data access time limitation is to store some of the more frequently-used data in a location that is more quickly accessible to the processor than is the main memory. For example, in systems with multiple processors, a cache memory associated with each of the processors is used to store copies of certain data so that the data can be accessed more quickly than from the main memory. Cache memory generally has faster access times than does the main memory.

[0006] Unfortunately, cache memory systems are not without their own problems. Because the use of cache memory involves creating a copy of some of the main memory data, multiple copies of the same data may exist in different locations within the multi-processor computer system. When one copy of the data is changed, multiple copies of the same data held in other locations must also be updated. Data errors will occur within the multi-processor system if different processors within the system are operating (performing reads and writes) on such inconsistent copies of data. This problem is known as a cache consistency or cache coherence problem. To avoid this problem, a common solution is to maintain a total order for all memory accesses with the help of cache consistency protocols and hardware.

[0007] Hardware-based solutions to the cache coherence problem generally follow either a centralized or distributed approach. In a centralized approach, directory protocols maintain information about where copies of information reside in a centralized directory. The directory contains information about the contents of local caches for the entire multi-processor system. A centralized controller keeps this information up to date and interacts with all of the local caches to ensure that data consistency is maintained.

[0008] In a distributed approach, “snoopy” protocols distribute the responsibility for maintaining cache coherence among all of the processors. The updates each processor makes to a shared memory block must be broadcast to all other processors. Each cache controller “snoops”, or reads, these broadcast messages and updates its own cache accordingly.

[0009] In the “snoopy” system, each individual processor and its cache is connected to a shared system bus that is connected to the shared main memory. As data operations are performed in each processor, the processor will broadcast these operations onto the shared system bus. For example, as a first processor performs read and write operations on shared data copies located in its cache, it broadcasts this information to the system bus to alert other processors to update the status of their data copies. By “snooping” the system bus, a second processor knows that it must invalidate its copy of a piece of data after it receives the broadcast that the first processor has operated on that same piece of data. Other examples of the messages broadcast by processors onto the shared system bus are well known to those of ordinary skill in the art.

[0010] In the asynchronous cache system 10 shown in FIG. 1, each processor 12-1 through 12-n has an associated cache 14-1 through 14-n and an associated first-in-first-out (FIFO) snoop buffer 16-1 through 16-n. Each snoop buffer 16-1 through 16-n is responsible for storing the snoop broadcasts received from the system bus 18 until they can be processed by each individual processor 12-1 through 12-n.

[0011] When a cache coherence transaction such as an invalidation is broadcast on the system bus 18, the invalidation request is buffered in each individual snoop buffer 16-1 through 16-n. The data selected for invalidation located in a cache 14 is not invalidated immediately. Instead, the broadcast messages are propagated separately following a FIFO order through each snoop buffer 16 to its associated cache 14. Accordingly, a copy of the data found in a cache 14 is invalidated independently or “asynchronously” of the invalidations occurring in other processor caches.

[0012] Total Store Ordering (TSO) and Sequential Consistency (SC) are two well-known techniques for specifying the order in which memory accesses are performed. SC and TSO do not allow any processors in the system to read two different write updates as having occurred in a different order. SC is a stronger model than TSO because SC also does not allow a processor to read and return the value of a write while the write is still pending in the buffer.

[0013] As an example of the type of errors TSO and SC prevent, suppose that the initial value of location X in the cache of a first processor is 0 and the initial value of location Y in the cache of a second processor is also 0. The first processor attempts to update location X to a value of 1 and the second processor attempts to update location Y to a value of 1. An illegal result occurs if a third processor reads X as 1 and Y as 0, while a fourth processor reads X as 0 and Y as 1. The third and fourth processors must read these two operations as having occurred in the same order.

[0014] It was normally believed that requests received from the system bus needed to be processed by the system processors in the order in which they were received according to the prior art constraints. If the processor has a hierarchical cache system with multiple levels of cache associated with each processor, a FIFO path from the system bus through each level of cache must be maintained. Thus, the system bus behaves as a reference point at which memory accesses are ordered. It provides the necessary information to guarantee that all processors will observe the same sequence of events, and it is impossible to observe two writes, for example, in different orders.

[0015] Maintaining this strict FIFO order does create a memory access time penalty. If a strict FIFO order is maintained on all coherence transactions, a pending request that may have a long memory access latency, for example a request to access the shared main memory which will take longer than a cache access, will penalize other transactions further down in the FIFO store path. The processor will pause and wait for the pending request to complete, wasting processor time that could be used to execute other requests if the FIFO restraint could be relaxed. Accordingly, a method for relaxing this FIFO constraint would be desirable. Such a method could reduce the amount of time an individual processor is idle while waiting for a request to complete, and thus reduce overall execution time for the multi-processor computer system.

[0016] The present invention is a method for relaxing the first-in-first-out (FIFO) constraint on the processing of snoop requests received by local processors from the system bus and also requests generated locally within the processor itself. These snoop requests contain coherence transaction information designed to maintain consistency between the multiple memory data copies which may exist in various processors' local caches. The relaxation of this FIFO constraint allows certain snoop requests to be processed out-of-order without compromising the data coherence of the multi-processor system. The relaxation of this constraint allows for a more efficient utilization of processor resources in order to decrease the overall multi-processor system execution time.

[0017] In a preferred embodiment of the present invention, each processor in a multi-processor system separates locally generated processor requests and remote processor requests into from the snoop queue into two categories. In the first category, are all coherence transactions, both read and write, generated by the local processor, as well as all coherence transactions generated by a remote processor which are write accesses. Each of the transactions in the first category maintain a strict FIFO structure wherein accesses to the cache are performed and retired. In the second category are all coherence transactions generated by a remote processor which are read accesses. In the second category of transactions, there are no order constraints between the transactions, with the exception that a transaction in the second category which references the same memory location as a transaction in the first category cannot be performed, if the transaction in the first category that was received before the transaction in the second category, and has not yet been completed. During this exception, the FIFO order must be maintained between the transaction in the first category and the transaction in the second category.

[0018] FIG. 1 is a block diagram of an asynchronous cache multi-processor system known in the art.

[0019] FIG. 2 is a block diagram of an inclusive asynchronous cache multi-processor system suitable for use according to the present invention.

[0020] FIG. 3 is a block diagram of a first embodiment of a non-inclusive asynchronous cache multi-processor system suitable for use according to the present invention.

[0021] FIG. 4 is a block diagram of a second embodiment of a non-inclusive asynchronous cache multi-processor system suitable for use according to the present invention.

[0022] FIG. 5 is a block diagram of an inclusive asynchronous cache multi-processor system with the FIFO snoop queue constraint relaxed according to the present invention.

[0023] FIG. 6 is a block diagram of a non-inclusive asynchronous cache multi-processor system with the FIFO snoop queue constraint relaxed according to the present invention.

[0024] FIG. 7 is a block diagram of a non-inclusive asynchronous cache multi-processor system with the FIFO snoop queue constraint relaxed using a single queue and a picker element according to the present invention.

[0025] Those of ordinary skill in the art will realize that the following description of the present invention is illustrative only and not in any way limiting. Other embodiments of the invention will readily suggest themselves to such skilled persons.

[0026] The present invention relates to a computer architecture for use in a multi-processor computer system. Each processor may have several caches associated with it, organized into a hierarchical structure. These caches can be located either on- or off-chip. On-chip caches tend to be smaller with faster access times, whereas off-chip caches tend to be larger with slower access times.

[0027] The cache with the fastest access time is referred to as the highest cache level, or the Level 1 cache. It is intended to hold the data that is most likely to be used frequently by the processor. The lower cache levels, Level 2 and/or Level 3, depending on the total number of caches each processor has, are generally slower than the Level 1 cache, but are able to hold more data. Thus a processor will first look for the data it needs in the Level 1 cache, then the Level 2 cache, and then the Level 3 cache. If the data is not found in any of the cache levels a cache miss will be broadcast to the system bus to locate the data either in another processor's cache or in the main memory.

[0028] The organization of the multiple caches can be either inclusive or non-inclusive. In an inclusive cache hierarchy, the lower level of the cache memory hierarchy is a superset of all of the upper levels. In a non-inclusive cache hierarchy, the lower level of the cache memory hierarchy does not necessarily contain the subsets of all upper levels of cache. Both inclusive and noninclusive cache hierarchies are contemplated by the present invention.

[0029] An inclusive asynchronous cache system 20 suitable for use according to the present invention is shown in FIG. 2. The inclusive asynchronous cache system 20 is well known to those of ordinary skill in the art. Accordingly, to avoid overcomplicating the present disclosure and thereby obscuring the present invention, the disclosure of inclusive asynchronous cache system 20 is limited to the details needed to understand the present invention. The inclusive asynchronous cache system 20 is arranged as a plurality of processor and cache units 22-1 through 22-n. Each processor and cache unit 22 is connected to the system bus 18. The snoop queue 24 receives the snoop broadcasts off of the system bus 18 and moves them through the processor according to a FIFO scheme. In this example, each processor and cache unit 22 has 3 levels of cache associated with each processor 26. The Level 3 cache 28 is located off-chip and all of the Level 3 cache tags 30 are maintained on-chip to speed up access times. The Level 3 cache tags 30 contain only information about the addresses of the data contained in the actual Level 3 cache 28, and are used to filter out snoop requests that are actually applicable to data in the Level 3 cache 28.

[0030] The embodiment of the asynchronous cache system 20 shown in FIG. 2 is inclusive, and thus the Level 1 cache 32 and Level 2 cache 34 are subsets of the Level 3 cache 28. The Level 3 cache tags 30 can be used to filter out all inapplicable snoop traffic for all three levels of cache. Applicable snoop requests are stored in FIFO queue 36 for processing in Level 1 cache 32 or Level 2 cache 34. These requests are moved through the processor 24 according to a FIFO scheme.

[0031] A non-inclusive asynchronous cache system 40 is shown in FIG. 3. The non-inclusive asynchronous cache system 40 is well known to those of ordinary skill in the art. Accordingly, to avoid overcomplicating the present disclosure and thereby obscuring the present invention, the disclosure of non-inclusive asynchronous cache system 40 is limited to the details needed to understand the present invention. The non-inclusive asynchronous cache system 40 is arranged as a plurality of processor and cache units 42-1 through 42-n. Each processor and cache unit 42 is connected to the 20 system bus 18. The snoop queue 44 receives the snoop broadcasts off of the system bus 18 and moves them through the processor 46 according to a FIFO scheme. In this example, each processor and cache unit 42 has 3 levels of cache associated with each processor 46. The Level 3 cache 48 is located off-chip and all of the Level 3 cache tags 50 are maintained on-chip to speed access times.

[0032] In the non-inclusive cache system 40, the Level 3 cache 48 is not a superset of the Level 1 cache 52 and the Level 2 cache 54. Thus snoop requests must be sent to the Level 3 cache tag 50 and to the Level 2 cache 54 to filter out the inapplicable snoop traffic, in the instance that the Level 2 cache 54 maintains inclusion of all Level 1 cache 50 data. As will be appreciated by those of ordinary skill in the art, if the Level 2 cache 48 does not maintain inclusion of all Level 1 cache 52 data, the snoop requests must also be sent to the Level 1 cache 52 because they would not be filtered out by the Level 2 cache 50. All snoop requests are moved through the processor 46 according to a FIFO scheme.

[0033] A presently preferred embodiment of a non-inclusive asynchronous cache system 60 suitable for use according to the present invention is illustrated in FIG. 4. To avoid overcomplicating the present disclosure and thereby obscuring the present invention, the disclosure of non-inclusive asynchronous cache system 60 is limited to the details needed to understand the present invention. A detailed disclosure of the asynchronous cache system 60 is made in co-pending application Ser. No. 08/940,217, now U.S. Pat. No. 6,073,212 filed Sep. 30, 1997, entitled “REDUCING BANDWIDTH AND AREAS NEEDED FOR NON-INCLUSIVE MEMORY HIERARCHY BY USING DUAL TAGS”, by inventors Norman Hayes, Rick Hetherington, Belliappa Kuttanna, Fong Pong, and Krishna Thatipelli, and assigned to the assignee of the present invention and specifically incorporated herein by reference. The non-inclusive asynchronous cache system 60 is arranged as a plurality of processor and cache units 62-1 through 62-n. The snoop queue 64 receives the snoop broadcasts off of the system bus 18 and moves them through the processor 66 according to a FIFO scheme. In this example, each processor and cache unit 62 has 3 levels of cache associated with each processor 66. The Level 3 cache 68 is located off-chip and a duplicate copy of all of the Level 3 cache tags 70 is maintained on-chip to speed access times.

[0034] The Level 2 cache 72 maintains inclusion of all of the Level 1 cache 74 data. A Level 2 cache tag directory 76 is maintained for use in filtering snoop traffic directed to the Level 1 cache 74 and the Level 2 cache 72. Applicable snoop requests are stored in queue 78 for processing in the Level 1 cache 74 or the Level 2 cache 72. These requests are moved through the processor according to a FIFO scheme.

[0035] The present invention can be used in any of the asynchronous cache systems 20, 40, or 60 shown in FIGS. 2, 3, and 4, as well as in various modifications as will be appreciated by those of ordinary skill in the art. All of these asynchronous cache systems 20, 40, and 60 use a FIFO constraint on the processing of snoop traffic to ensure cache coherence. If a strict FIFO constraint is used to process all snoop requests, later requests that could be quickly processed will be delayed by earlier requests that take more time to process.

[0036] As an example of this delay, a first processor in one of the asynchronous cache systems 20, 40 or 60 initially has the most recent copy of the data for location A in its Level 2 cache. In the normal course of operations this first processor attempts a write to location B and has a miss in its cache system. This miss causes a block to be fetched from the memory. Meanwhile, a second processor attempts a read to location A, and a miss occurs. This miss prompts a request to the first processor for the most recent data copy in location A. If an internal FIFO path is maintained within the first processor, the read miss to location A by the second processor will not be fulfilled until to the long memory access latency caused by the first processor's miss to location B is finished.

[0037] The present invention solves the problem demonstrated above by separating the snoop requests directed to the Level 2 cache into two separate categories. The processor can then receive certain requests out of the order in which they were received by the snoop queue. This FIFO constraint relaxation allows the processor in certain cases to continue receiving and processing snoop requests instead of waiting for a single request to be completed. Decreasing the amount of time each individual processor is idle waiting for a request can decrease the execution time for the overall multi-processor system.

[0038] According to the present invention, in order to relax the FIFO constraint, and thereby decrease the execution time for the overall multi-processor system, each processor in the multi-processor system will separate locally generated processor requests and remote processor requests received from the snoop queue into two categories.

[0039] In the first category, are all coherence transactions, both read and write, generated by the local processor, as well as all coherence transactions generated by a remote processor which are write accesses. Each of the transactions in the first category maintain a strict FIFO structure wherein accesses to the cache are performed and retired. In the second category are all coherence transactions generated by a remote processor which are read accesses.

[0040] In the second category of transactions, there are no order constraints between the transactions, with the exception that a transaction in the second category which references the same memory location as a transaction in the first category cannot be performed, if the transaction in the first category that was received before the transaction in the second category, and has not yet been completed. During this exception, the FIFO order must be maintained between the transaction in the first category and the transaction in the second category.

[0041] FIG. 5 shows the present invention implemented in an inclusive asynchronous cache system 80. The elements are similar to those described above in FIG. 2, except that the FIFO queue 36 of FIG. 2 has been replaced by a first category queue 96 and a second category queue 98

[0042] The inclusive asynchronous cache system 80 is arranged as a plurality of processor and cache units 82-1 through 82-n. Each processor and cache unit 82 is connected to the system bus 18. The snoop queue 84 receives the snoop broadcasts off of the system bus 18. In this example, each processor and cache unit 32 has 3 levels of cache associated with each processor 86. The Level 3 cache 88 is located off-chip and all of the Level 3 cache tags 90 are maintained on-chip to speed up access times. The Level 3 cache tags 90 contain only information about the addresses of the data contained in the actual Level 3 cache 88, and are used to filter out which snoop requests are actually applicable to data in the Level 3 cache 88.

[0043] The Level 1 cache 92 and Level 2 cache 94 are subsets of the Level 3 cache 88, and thus the Level 3 cache tags 90 can be used to filter out all inapplicable snoop traffic for all three levels of cache. First and second category queues 96 and 98, respectively, store the applicable snoop requests until they are processed in the Level 1 cache 92 and the Level 2 cache 94.

[0044] First category queue 96 receives all data coherence transactions generated by the local processor, as well as all coherence transactions generated by a remote processor which are write accesses. First category queue 96 maintains a strict FIFO order. Second category queue 98 receives all data coherence transactions generated by a remote processor which are read accesses. Second category queue 98 does not have any order constraints, and transactions in Second category queue 98 can normally be performed in any order. However, the exception for two transactions referencing the same address as described above applies. A transaction in second category queue 98 cannot be performed if there exists a transaction in first category queue 96 such that the transaction in first category queue 96 is received before the transaction in second category queue 96, and the transaction in first category queue 96 has not been retired. In this instance, the FIFO order must be maintained between the transaction in first category queue 96, and the transaction in second category queue 98.

[0045] FIG. 6 shows a preferred embodiment of the present invention implemented in a non-inclusive asynchronous cache system 100. The elements are similar to those described above in FIG. 4, except that the FIFO queue 78 of FIG. 4 has been replaced by first category queue 118 and second category queue 120.

[0046] The non-inclusive asynchronous cache system 100 is arranged as a plurality of processor and cache units 102-1 through 102-n. Each processor and cache unit 102 is connected to the system bus 18. The snoop queue 104 receives the snoop broadcasts off of the system bus 18. In this example, each processor and cache unit 102 has 3 levels of cache associated with each processor 106. The Level 3 cache 108 is located off-chip and a duplicate copy of all of the Level 3 cache tags 110 is maintained on-chip to speed access times.

[0047] The Level 2 cache 112 maintains inclusion of all of the Level 1 cache 114 data. A duplicate of all of the Level 2 cache tags 116 is maintained for use in filtering snoop traffic. Applicable snoop requests are stored in first and second category queues 118 and 120, respectively for processing in the Level 1 cache 114 or the Level 2 cache 112.

[0048] First category queue 118 receives all data coherence transactions generated by the local processor, as well as all coherence transactions generated by a remote processor which are write accesses. First category queue 118 maintains a strict FIFO order. Second category queue 120 receives all data coherence transactions generated by a remote processor which are read accesses, which can be processed in any order, subject to the exception for two transactions referencing the same address described above.

[0049] It should be appreciated that the relaxation of the strict FIFO constraint for those transactions in the second category may be implemented in several ways. An alternative embodiment for relaxing the FIFO constraint is illustrated in FIG. 7.

[0050] In the alternative embodiment illustrated in FIG. 7, the elements of the non-inclusive asynchronous cache system 130 and plurality of processor and cache units 132-1 through 132-n are the same as those shown in FIG. 4. However, also included is a picker 134. Unlike the embodiment illustrated in FIG. 6, wherein the queue 78 from FIG. 4 is broken into first and second category queues 118 and 120, in FIG. 7, a single queue 136 is employed to hold all of the data coherence transactions pending for the Level 1 cache 138 and the Level 2 cache 140. Transactions in queue 136 corresponding to the first category are processed in a FIFO order. The picker 134 is employed to select transactions for processing off of the queue 136 in the second category described above and which do not have to be processed in FIFO order, according to the rules discussed above. Any of several implementations of picker 134 according to the present invention is well within the abilities of those of ordinary skill in the art.

[0051] While illustrative embodiments and applications of this invention have been shown and described, it would be apparent to those skilled in the art that many more modifications than mentioned above are possible without departing from the inventive concepts herein. The invention, therefore, is not to be restricted except in the spirit of the appended claims.