Multiprocessor system and cache coherency control method

Details Multiprocessor system and cache coherency control method Multiprocessor system and cache coherency control method

1997-11-28

2001-10-02

Bragdon, Reginald G. (Department: 2185)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S145000

Reexamination Certificate

active

06298418

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a tightly coupled multiprocessor system in which a main storage is shared by a plurality of processors, and to techniques effective for the application to cache coherency control.
2. Description of the Related Art
It is common for a presently used processor module to have a high speed internal cache memory, which temporarily stores data transferred to and from an external main storage or the like, in order to speed up the operation. In a tightly coupled multiprocessor system having a main storage which is shared by a plurality of processors each having a cache memory, data in the main storage at the same address is dispersively present in cache memories of a plurality of processors. This dispersed data is updated independently at each processor if write-back caching is performed in which updated write data is also stored in the main storage via the cache memory. In this case, there is a possibility that the data in the cache memory at each processor is different (dirty) from the data in the main storage at the same address. Therefore, if any one of processors issues a read request to the main storage, it becomes essential to perform cache coherency control in order to ensure the correct operation of the system, i.e., to ensure time sequential integrity (coherency) of data in the cache memory of each processor and in the main storage, in other words, to ensure that read data is the newest data.
Typical techniques of a cache coherency control scheme for such a tightly coupled multiprocessor system are disclosed in various documents such as M. S. Papamacros and J. H. Paten, “A Low-overhead Coherence Solution for Multiprocessors with Private Cache Memories”, Proc. the 11th International Symposium on Computer Architecture, 1984. pp. 348-354.
This document defines the following cache states of a multiprocessor system having a plurality of processor modules sharing a main storage (memory module) via a bus. These cache states include: (a) Invalid (data is invalid); (b) Shared-Unmodified (data is also present in the cache memory of another processor and is the same as the data in the main storage); (c) Exclusive-Modified (data is present only in the cache memory in concern and not the same as the data in the main storage); and (d) Exclusive-Unmodified (data is present only in the cache memory in concern and is the same as the data in the main storage).
When any one of processor modules issues a read request and the data is not stored in the cache memory of this processor module (read miss), a Read Request Tx (Transaction) is broadcast via the bus to the memory module (MM) and processor modules (PMs). If any one of PM cache memories hits, the data is returned from this PM to the requesting PM and at the same time the data is written in MM. If any one of PM cache memories does not hit, data is returned from MM.
If a data line in the cache memory to be replaced (already stored data is driven out in order to form an empty area in the cache memory) is Exclusive-Modified, this is reflected upon MM by sending a Write Back Tx to the bus.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a multiprocessor system capable of realizing correct cache coherency control in both bus and switch coupled multiprocessor systems.
It is another object of the present invention to provide a multiprocessor system capable of realizing correct cache coherency control without lowering system performance.
It is a further object of the present invention to provide a multiprocessor system capable of realizing correct cache coherency control without unnecessarily complicating the structure of memory modules and the like.
It is a still further object of the present invention to provide cache coherency control techniques capable of acquiring correct results even in a switch coupled multiprocessor system even if the transaction orders become different according to monitor sites.
It is still another object of the present invention to provide cache coherency control techniques capable of acquiring correct results without lowering system performance and with a simple structure of memory modules, in a bus coupled multiprocessor system which permits the occurrence of transaction disorder in each module.
Cache coherency control means, for example, guarantee of coincidence between a main storage and a cache. Transaction means, for example, a memory read request from a processor, a memory write request from a processor, a check (called a cache coherency check) request to another processor for checking the presence/absence of contents at a memory address.
With the above-described conventional techniques, some problems of data coherency may occur, for example, when Write Back Tx for data reflection from a cache memory to MM and Read Request Tx from another PM for the same data line are issued at a short time interval. As illustratively shown in
FIG. 19
, the following problem may occur.
(1) When Write Back Tx from PM
0
and Read Request Tx from PM
1
are issued at a short time interval, the transactions appear on the bus in the order of Read Request Tx of PM
1
>Write Back Tx of PM
0
.
(2) Since PM
0
sends Write Back Tx to the bus, “Cache is invalid” is returned in response to Read Request Tx of PM
1
.
(3) MM reads the memory contents in response to the reception of Read Request Tx of PM
1
. Namely, MM returns to PM
1
the memory contents not reflecting the contents of Write Back Tx of PM
0
.
(4) Since PM
1
received the response that data in PM
0
is invalid, it uses invalid data returned from MM.
In the above case (1) to (4), cache coherency becomes contradictory. This problem result from transaction disorder of Write Back Tx of PM and Read Request Tx of another PM in PMs.
A first approach to solving the above problem is as follows. It is checked by all means before the issue of Write Back Tx as to whether Read Request Tx to the same address is not on the bus. If there is Read Request Tx, a process similar to an ordinary “Exclusive-Modified” hit is performed without issuing Write Back Tx. It is obvious to ensure that the transaction disorder can be prevented in the above manner.
As a second approach, an improved control scheme has been proposed as described, for example, in the publication of JP-A-7-281956. With this approach, the transaction order of Read Request Tx and Write Back Tx on the bus is stored. Specifically, PM and MM are each provided with a queue in which the order of transactions on the bus is stored. In accordance with this order, a transaction disorder is detected. In a memory controller in particular, the latest issued cache write and the latest issued coherent read are compared to check any possibility of conflict, and if necessary to rearrange the order of transactions and store coherent image of the memory.
The first approach is, however, associated with a technical issue that the system performance is lowered, as suggested in the publication of JP-A-7-281956. The second approach is also associated with a technical issue that the structure of each module, particularly a memory module, becomes complicated.
The first and second approaches cannot be used with a switch, such as crossbar switch, coupled system with a transaction order being different at each monitor site. For example, in a switch coupled system illustratively shown in
FIG. 11
, consider the case that a memory access by one PM is broadcast to other modules to allow them to monitor its access and ensure cache coherency. In this case, even if PM
1
issues Write Back Tx after confirming that Read Request Tx of PM
0
is not received, as with the first approach, Read Request Tx may reach thereafter in the transaction order of Write Back>Read. On the memory module side, there is a possibility of the transaction order of Read>Write Back. In this case, there is also a possibility that Write Back Tx of PM
1
may reach after the memory contents are returned to PM
0
. Therefore, cache coherency becomes contradictory. Obviously, the se

Affiliated with

Also associated with

Rating

Multiprocessor system and cache coherency control method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiprocessor system and cache coherency control method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiprocessor system and cache coherency control method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2562849