Cache Coherency Method and Apparatus for a Multiple Path Interconnection Network

The present invention relates to electronic data processing (EDP) systems, and more particularly to EDP systems which have multiple processors, each processor having its own cache memory, interconnected by multiple interconnections, e.g. buses.

Cache memories were originally added to uniprocessor systems in order to increase memory access speed. Without cache memories, every memory access, either READ or WRITE, involved main memory. Typically main memory was distantly located, and also was relatively slow in operation. This meant that a number of processor cycles were required in order to access data stored at a main memory address. It was found that the number of processor cycles required for an access could be reduced by transferring the data of some main memory addresses to a cache memory that is closer to the uniprocessor and faster at READING and WRITING the data than main memory. When a transaction involving encached data is completed, the resulting data is typically stored in the cache memory again and also is eventually copied back to the corresponding address locations in main memory. For proper system operation some type of record is kept to indicate at the end of an operation whether the location for the resulting data corresponding to an address is in cache memory or in main memory.

A multiple processor system that has a cache memory associated with each of its processors has an even more complex data problem. In multiple processor systems, each cache may contain data associated with a main memory address, and each processor may process the data for that address and store the results in its respective cache. Thus, unless something in the EDP system prevents it, it is possible that many different data values will exist among the multiple caches for a single address. This possible inconsistency among corresponding address locations is referred to in the art as the cache coherency problem.

One solution to the cache coherency problem requires the main memory to record the location of each encached copy of data associated with a main memory address. When any encached copy is modified, the results are stored in the cache of the processor performing the processing, copied through to the corresponding address in main memory, and then copied to each additional cache that also has data associated with the main memory address. It is up to the EDP system to provide a cache data protocol for the processing of the data associated with each address so that each of the processors always processes current, coherent data. The copy back process works quite well for two processor systems; however, as the number of processors increases, the interconnect sub-system tends to become overloaded by the frequent copying back of information to main memory and the frequent updating of all of the encached copies of the information. In such a system, the gains in processing power provided by multiple processors may be negated by the overloading of the system interconnect by update messages to the processor caches.

One approach to preventing the cache messages from overloading and bogging down the common system interconnect is to provide a separate cache management subsystem, including a separate cache interconnect. Such a separate cache interconnect connecting to each cache memory, however, is the equivalent of a second system interconnect in speed and data requirements. So this approach adds a non-standard cache interconnect that is roughly equivalent to common system interconnect. Such a cache interconnect would require considerable software and hardware investments to upgrade existing platforms or to manufacture a completely new software and hardware platform.

A second approach to preventing the cache messages from overloading the common interconnect is to provide multiple system interconnects, e.g. multiple parallel buses to a common memory. By spreading the data traffic among multiple parallel buses, the traffic on each bus could be reduced such that the copying back, or similar operation, of resulting data would not cause an overload. However, such a system architecture may require as many parallel system buses as there are processors with caches. Since typical standard system bus architectures have one or two system buses, such architectures could not be readily extended to systems with five processors or more without incurring expensive custom hardware components and considerably more complex memory architectures.

Thus, there is an unfulfilled need for a method and apparatus for interconnecting a number of processors with a like number of caches which maintains data coherency and yet may be effectively used within existing system hardware and back plane designs.

It is an object of the present invention to provide a method and apparatus that ensures coherency of the data in each cache of a multiple bus interconnection system.

It is a further object of the present invention to provide an apparatus that ensures coherency of encached data which is extensible within existing system interconnect architectures.

According to one aspect of the invention, the foregoing objects are achieved by providing an apparatus for maintaining data coherency in a system having multiple independent paths interconnecting multiple processors, each of said processors having a respective cache memory associated with it. The apparatus includes a device for storing data from a main memory into a corresponding address of a first of the cache memories that is connected to one of the multiple independent paths and a device for storing cache tag information in each of a plurality of cache monitors associated with the first cache memory. Each of the cache monitors monitors a respective one of the multiple independent paths for any access to any of the cache memories which would render data stored in the first cache non-coherent. Each of the cache monitors has a device for transmitting a control signal to the system indicating that data stored in the first cache is non-coherent if any such access is detected on any of the multiple independent paths.

In a specific embodiment the aforementioned objects are achieved by providing, an electronic data processing apparatus which includes a plurality of processors; a plurality of caches, each of which is respectively connected to and associated with one of the plurality of processors; an interconnect network having a plurality of independent paths with the plurality of processors distributed substantially equally among the independent paths with each processor and its respective cache connecting to one of the plurality of independent paths; a main memory which is connected to each of the plurality of independent paths; and a plurality of activity monitors with each of the activity monitors uniquely connecting one of the plurality of caches to one of the plurality of independent paths. These elements operate together such that if any of the processors accesses data from its respective cache, the access signal will also be transmitted on its independent path, and the activity monitors that are connected to this independent path will each compare the address of the accessed data with addresses of information stored in each monitor's cache and each monitor will inform its respective cache if the access affects the coherency of data stored therein.

While the specification concludes with the appended claims particularly pointing out and distinctly claiming the subject matter which is regarded as the invention, it is believed that the invention will be better understood from the following detailed description of the illustrative embodiment taken in conjunction with the accompanying drawings in which:

FIG. 1 is a block diagram of a typical cache system having four processors, each having a respective cache, and the processors are interconnected via a generalized interconnect system between their cache outputs and memory.

FIGS. 2A and 2B together form a block diagram of a cache coherent system according to the invention with a multiple interconnect system of multiple parallel buses interconnects multiple processors and their respective caches.

FIG. 3 is a block diagram of a monitor that is shown in FIG. 2.

FIGS. 4, 4A, 4B, and 4C when joined together form a block diagram of a cache coherent system according to the invention with a multiple interconnect system having two parallel buses interconnecting 2N multiple processors and their 2N respective caches.

FIG. 1 is a generalized block diagram of a multiple processor system 10 which includes a generalized interconnect 12 for information and control data bits. Each of the processors P1-P4 is connected to the interconnect 12 via a respective processor bus PB1-PB4. Each processor P1-P4 is also connected via its respective processor bus PB1-PB4 to a respective cache memory C1-C4 which is associated therewith. The cache memories C1-C4 reduce the access time to addresses that are frequently used by their respective processors P1-P4 because an access to a cache is faster than a similar access from main memory segments 20.

If the interconnect 12 consists of a single path between the processors P1-P4 and memory segments 20, then the caches C1-C4 are connected via the processor buses PB1-PB4 and the interconnect 12. Connected in this manner, the caches C1-C4 can monitor all of the memory accesses directly. This assumes a typical cache operation where a processor P1-P4 initiates an access by transmitting a READ or WRITE command onto its processor bus PB1-PB4 which then propagates to the memory segments 20 and the cache memories C1-C4 other than the cache associated with the accessing processor, where the associated cache will essentially interrupt the READ or WRITE from the memory segments 20 and process the READ or WRITE itself whenever the associated cache has data corresponding to the accessed address encached therein.

A problem arises, however, if the interconnect 12 consists of multiple independent paths with some of the processors P1-P4 and their respective caches being connected to one of the paths by their processor buses PB1-PB4, and the remainder of the processors P1-P4 and their caches are connected to the remaining paths. In such an arrangement, an access to the segmented memory 20 as it propagated along its path could not be directly monitored by all of the processors and their respective caches as in the single path case. Thus, in the arrangement shown in FIG. 1 if the interconnect 12 has multiple independent paths, one processor may access and change data via its path, but a cache which is connected to a different one of the multiple paths may not be able to monitor the access, even though the access renders its encached data non-coherent.

Referring now to FIGS. 2A and 2B, one embodiment of a multiple processor system 30 which prevents such data coherency problems is shown. The multiple processor system 30 includes multiple parallel buses Bus.sub.-- 1 through Bus.sub.-- K as its interconnect network. The multiple parallel buses Bus.sub.-- 1-Bus.sub.-- K provide K independent paths that connect multiple processors P11-PNP to memory segments Mem.sub.-- 1-Mem.sub.-- J. The multiple processors P11-PNP are arranged on N boards Boards.sub.-- 1-Boards.sub.-- N with P processors to a board for a total of N.times.P processors. Each of the multiple processors P11-PNP is connected via a respective processor bus PB11-PBNP, one per processor, to one of the multiple independent buses Bus.sub.-- 1-Bus.sub.-- K. To the extent possible, the N.times.P processors and their respective N.times.P processor buses are connected in an equally distributed fashion to the K independent paths Bus.sub.-- 1-Bus.sub.-- K in order to evenly distribute the data processing operations.

The system 30 has a cache memory architecture according to one embodiment of the invention. Each processor P11-PNP of the system 30 has a respective cache memory C11-CNP associated therewith which is connected to its respective processor bus PB11-PBNP. Each of the cache memories C11-CNP in the system 30 provides high speed local storage for a limited amount of frequently used control and data information. This local storage is used in addition to the lower speed, higher capacity main segmented memory Mem.sub.-- 1-Mem.sub.-- J. The segmented memory Mem.sub.-- 1-Mem.sub.-- J is organized in J blocks Mem.sub.-- 1-Mem.sub.-- J. Each of the blocks Mem.sub.-- 1-Mem.sub.-- J is divided into segment A and segment B. Those skilled in the art will recognize that with a minor modification each block Mem.sub.-- 1-Mem.sub.-- J may be divided into more or fewer segments, and such modifications are deemed to be within the scope of the present invention. Segment A and segment B of each block are connected through respective K-way arbitrators to the independent paths Bus.sub.-- 1-Bus.sub.-- K. With the arrangement shown in FIGS. 2A and 2B, any of the processors P11-PNP may access any address of main memory Mem.sub.-- 1-Mem.sub.-- J, and the segmentation permits concurrent accesses to addresses in different segments in order to speed up the memory system. The main memory Mem.sub. -- 1-Mem.sub.-- J is a global memory and could be used as a commonly accessible location for cache tag information of the individual caches in order to provide cache coherency, but as mentioned previously, such an approach requires a more complex main memory structure and tends to overload the paths Bus.sub.-- 1-Bus.sub.-- J with cache coherency data transfers, thereby preventing the multiple processors from being used to their greatest efficiency.

In order to provide coherency among the cache memories C11-CNP for the multiple independent path system 30 without the addition of a complex main memory sub-system or an expensive, non-standard cache bus sub-system, each of the caches C11-CNP is provided with a plurality of monitors M111-MNPK. Cache C11 is associated with a set of K monitors M111-M11K, cache C12 is associated with another set of K monitors M121-M12K, and so forth for the remaining caches and monitors. Each monitor within its set of K monitors is connected to and associated with a respective path of the K independent paths Bus.sub.-- 1-Bus.sub.-- K. These connections are actually made to the independent paths Bus.sub.-- 1-Bus.sub.-- K via the processor buses PB11-PBNP as shown in FIGS. 2A and 2B. Further, each monitor of a set is connected to the processor bus of the cache it is associated with in order to receive information about data stored therein as explained below.

Connected in this manner, each cache C11-CNP may monitor the memory accesses made on all of the independent paths Bus.sub.-- 1-Bus.sub.-- K of the multiple processor system 30. For example, processor P11 is connected via its processor bus PB11 to independent path Bus.sub.-- 1 and also to its cache C11. The cache C11 has a set of monitors M111-M11K that it is associated with. Each of the set of monitors M111-M11K is connected at one port thereof to the cache C11 via the processor bus PB11. Each of the set of monitors M111-M11K is connected at a second port thereof to one of the processor buses PB11-PB1P on Board.sub.-- 1 respectively. By the connections to PB11-PB1P, the second ports of monitors M111-M11K are also connected to Bus.sub.-- 1-Bus.sub.-- K respectively. By their first ports, the monitors M111-M11K may receive information regarding the current contents stored in its associated cache C11, e.g. cache tag information. By their second ports, the monitors M111-M11K may monitor the accesses made by all of the processors P11-PNP over the paths Bus.sub.-- 1-Bus.sub.-- K to memory Mem.sub.-- 1-Mem.sub.-- J. Thus, the monitors M111-M11K may each compare the accesses made on their respective paths Bus.sub.-- 1-Bus.sub.-- K to the addresses of information stored in their cache C11 and if any processor other than P11 is accessing and updating a corresponding address in another cache C12-CNP or in main memory Mem.sub.-- 1-Mem.sub.-- J, then C11 is informed by the monitor connected to the accessing processor's bus that its encached data is now non-coherent with the current version located in another cache or in main memory. C11, upon being informed of the non-coherency of some of its data takes appropriate action, e.g. marking the data invalid, or a flushing of the noncoherent addresses followed by a copying in of coherent data for the addresses.

Referring now to FIG. 3, the monitors M111-MNPK will be described in detail. Each of the monitors M111-MNPK has a dual port RAM 40. The dual port RAM 40 has two input/output ports PORT1, PORT2. PORT1 of each RAM 40 is connected to the processor bus PB11-PBNP of its respective cache C11-CNP and processor P11-PNP (shown in FIGS. 2A and 2B). For example, the set of monitors M111-M11K would all have PORT1 of their RAMs 40 connected to processor bus PB11 of processor P11 and cache C11. Each PORT2 of each RAM 40 of a set of monitors is connected uniquely (within its set) to one of the K independent paths Bus.sub.-- 1-Bus.sub.-- K (shown in FIGS. 2A and 2B) via one of the processor buses on its board Board.sub.-- 1-Board.sub.-- N. Thus, the set of K monitors M111-M11K would have the PORT2s of their RAMs 40 respectively connected to PB11-PB1K as their unique processor bus connections. The other sets of monitors M121-MNPK are analogously connected for their processors P12-PNP and caches C12-CNP.

The monitors M111-MNPK each have a comparator 44 connected at one input thereof to a data output portion of the PORT2 of RAM 40. A second input of each comparator 44 is connected to a group of tag bits from the most significant bits from the processor bus PB11-PBNP that the PORT2 is connected to.

In operation, dual port RAM 40 and comparator 44 are operated as a cache-tag circuit. For monitor M111, for example, when its processor P11 does a READ or a WRITE access with its cache C11 or main memory Mem.sub.-- 1-Mem.sub.-- J, the processor P11 will also sends control signals to cache C11 to indicate the cache state of the current address, e.g. valid, invalid, shared, dirty, etc. depending on the protocol of the multiple processor system. The monitor M111 will be updated at the same access from P11 and it will use the same control signals to mark the cache tags stored therein so that the monitor M111 indicates the same cache state for the cache tags of cache C11 as the encached data stored in cache C11 has. If another processor P21-PN1 connected to path Bus.sub.-- 1 does an access, monitor M111 receives the address information on PORT2 of its RAM 40 which accesses the stored cache tag information of its cache C11. The address on PORT2 will retrieve a group of tag bits from the RAM 40 and these tag bits will be compared to the tag portion of the address on PORT2. If the comparator indicates a MATCH, this means that the access of another processor on Bus.sub.-- 1 has affected the coherency of part of the data encached in C11. The MATCH signal is used as a control signal to initiate action to prevent use of this non-coherent data, i.e. mark it as invalid and/or initiate a copy from a memory having a coherent copy of the data. Those skilled in the art will understand such cache operations.

In addition to the cache coherency enforcement described above, monitors M112-M11K are connected to processor P11 and cache C11 at the PORT1s of their RAMs 40, just as M111 is. Further, monitors M112-M11K are updated by processor P11 as to the addresses and state of the data encached in cache C11, just as monitor M111 is updated. But, instead of monitoring the same path Bus.sub.-- 1 for accesses affecting the state of the data encached in C11, M112-M11K monitor paths Bus.sub.-- 2-Bus.sub.-- K respectively. Thus, if a processor connected to paths Bus.sub.-- 2-Bus.sub.-- K accesses an address that corresponds to an address of data encached in C11, and that access affects the coherency of the data in cache C11 for that address, then the monitor, from the set of monitors M111-M11K, that is uniquely attached to the path over which the access is made will receive the address on PORT2 of its RAM 40. This access address on its PORT2 will retrieve a group of index bits from the RAM 40 and these index bits will be compared to the index portion of the address on PORT2. If the comparator indicates a MATCH, this means that the access of another processor on another path Bus.sub.-- 2-Bus.sub.-- K has affected the coherency of part of the data encached in C11. This MATCH signal is then used to initiate action to prevent use of this non-coherent data, i.e. mark it as invalid and/or initiate a copy from a memory having a coherent copy of the data, in a similar manner to a MATCH generated by an access on path Bus.sub.-- 1 described previously.

FIGS. 4A, 4B, and 4C together shows a specific embodiment of the invention described above in connection with FIGS. 2A and 2B in which K is two. This embodiment of the invention is of particular interest because systems with two parallel buses have been built, and standard hardware, i.e. the back plane and board cabinet, are readily available. For a two parallel bus system, such as the system 50 shown in FIGS. 4A, 4B, and 4C, cache monitors and their interconnections could be added at the board level, and standard back plane and cabinet level hardware of a two parallel bus system, such as a Future Bus system, could be used.

Thus, it will now be understood that there has been disclosed a cache coherency method and apparatus for a multiple path interconnection system which provides cache coherency for all caches without the addition of a cache-to-cache bus subsystem. While the invention has been particularly illustrated and described with reference to a preferred embodiment thereof, it will be understood by those skilled in the art that various changes in form, details, and applications may be made therein. It is accordingly intended that the appended claims shall cover all such changes in form, details and applications which do not depart from the true spirit and scope of the invention.