Scheme for insuring data consistency between a plurality of cache memories and the main memory in a multi-processor system

• US 5,222,224 A
• Filed: 07/09/1991
• Issued: 06/22/1993
• Est. Priority Date: 02/03/1989
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Arnold, Scott, Webb, David J., DeLaHunt, Stephen J., Flynn, Michael E., Hetherington, Ricky C., Fossum, Tryggve
• Primary Examiner(s): Dixon, Joseph L.
• Assistant Examiner(s): RUDOLPH, REBECCA
• Application Number:
  US07/727,296
• Time in Patent Office: 714 Days
• Field of Search: 395/400, 395/425
• US Class Current: 711/144
• CPC Class Codes: G06F 12/0822 Copy directories local copy tags for implementing a bus snooping protocol G06F12/0831

Abstract

A method for insuring data consistency between a plurality of individual processor cache memories and the main memory in a multi-processor computer system is provided which is capable of (1) detecting when one of a set of predefined data inconsistency states occurs as a data transaction request is being processed, and (2) correcting the data inconsistency states so that the operation may be executed in a correct and consistent manner. In particular, the method is adapted to address two kinds of data inconsistency states: (1) A request for a operation from a system unit to main memory when the location to be written to is present in the cache of some processor unit-in such a case, data in the cache is "stale" and the data inconsistency is avoided by preventing the associated processor from using the "stale" data; and (2) when a read operation is requested of main memory by a system unit and the location to be read may be written or has already been written in the cache of some processor--in this case, the data in main memory is "stale" and the data inconsistency is avoided by insuring that the data returned to the requesting unit is the updated data in the cache. The presence of one of the above-described data inconsistency states is detected in a SCU-based multi-processing system by providing the SCU with means for maintaining a copy of the cache directories for each of the processor caches. The SCU continually compares address data accompanying memory access requests with what is stored in the SCU cache directories in order to determine the presence of predefined conditions indicative of data inconsistencies, and subsequently executes corresponding predefined fix-up sequences.

Claims

1. In a multi-processor system having a system memory and a plurality of central processor units (CPUs), and CPUs being connected to said system memory, and wherein each CPU includes a respective cache memory for storing data from predefined blocks of memory locations in said system memory, said respective cache memory including storage locations for blocks of data words and associated block addresses and associated block status information indicating whether each block of data words in said respective cache memory has an "invalid" status, a "read" status, a "written-partial" status, or a "written-full" status, and status information indicating whether each word in a "written-partial" block of data words is valid or not,

a method for controlling access to said respective cache memory in response to a memory access request from said each CPU, said memory access request specifying a block address of a specified block of data, said method comprising the steps of:

(a) searching said respective cache memory for an associated block address matching said specified block address, and when a matching associated block address is found in said respective cache memory, retrieving the associated block status information for the matching associated block address, and

(b1) when said memory access request is a request to read data and a matching associated block address is found in said respective cache memory and the associated status information for the matching associated block address does not indicate an "invalid" status, reading data from said respective cache memory,

(b2) when said memory access request is a request to read data and either a matching associated block address is not found in said respective cache memory or a matching associated block address is found in said respective cache memory but the associated block status information for the matching associated block address indicates an "invalid" status, fetching said specified data block from said system memory, writing said fetched data block into said respective cache memory, and setting in said respective cache memory the associated status information for the fetched data block to indicate a "read" status;

(b3) when said memory access request is a request to write specified data to less than a full portion of at least one of said words and a matching associated block address is not found in said respective cache memory or a matching associated block address is found in said respective cache memory but the associated block status information for the matching associated block address indicates an "invalid" status, fetching said specified data block from said system memory, and writing at least a portion of the fetched data block and said specified data into said respective cache memory, and setting in said respective cache memory the associated status information for the fetched data block to indicate a "written full" status;

(b4) when said memory access request is a request to write specified data to a full portion of at least a specified one of said words, and a matching associated block address is not found in said respective cache memory or a matching associated block address is found in said respective cache memory but the associated block status information for the matching associated block address indicates that the block is invalid, writing said specified data into said respective cache memory, setting in said respective cache memory the associated status information for each word in said specified block to indicate that said specified one of said words is valid, and setting in said respective cache memory the associated status information for said specified block to indicate a status of "written partial";

(b5) when said memory access request is a request to write specified data and a matching associated block address is found in said cache memory and the associated block status information for the matching associated block address indicates neither an "invalid" status nor a "written full" status, fetching said specified data block from said system memory, writing at least a portion of the fetched data block and said specified data into said respective cache memory, and setting in said respective cache memory the associated status information for the fetched data block to indicate a "written full" status; and

(b6) when said memory access request is a request to write specified data, a matching associated block address is found in said respective cache memory and the associated block status information for the matching associated block address indicates a "written full" status, writing said specified data into said cache memory.

2. The method as claimed in claim 1, further including the step of maintaining in a central directory copies of said cache status information indicating whether the blocks of data words in said cache memories each have a status of "invalid", "read", "written-partial", or "written-full", and when performing said fetching from said system memory during said steps (b3) and (b5) for a write access, accessing said central directory to determine whether another one of said cache memories other than said respective cache memory has a status of "written full" associated with said specified block address, and when said another one of said cache memories has a status of "written full" associated with said specified block address, writing the specified data block in said another cache memory back to said system memory and setting said associated status information in said another cache memory for said specified block address to a status of "invalid".

3. A multi-processor system comprising a system memory connected to a plurality of central processor units (CPUs), wherein each CPU includes a respective execution unit and a respective cache memory including means for storing data from predefined blocks of memory locations in said system memory;

said respective cache memory including storage locations for blocks of data words and associated block addresses and associated block status information indicating whether each block of data words in said respective cache memory has an "invalid" status, a "read" status, a "written-partial" status, or a "written-full" status, and status information indicating whether each word in a "written-partial" block of data words is valid or not;

said respective cache memory further including means for retrieving a specified data block and status information associated with an associated block address matching a specified block address specified by a memory access request by said respective execution unit of said each CPU;

said each CPU further including control means coupled to said respective execution unit, said respective cache memory and said system memory for controlling access to said respective cache memory, wherein said control means includes;

(a) means, responsive to said memory access request when said memory access request is a request to read data and a matching associated block address is found in said respective cache memory and the associated status information for the matching associated block address does not indicate an "invalid" status, for reading data from said respective cache memory,

(b) means, responsive to said memory access request when said memory access request is a request to read data and either a matching associated block address is not found in said respective cache memory or a matching associated block address is found in said respective cache memory but the associated block status information for the matching associated block address indicates an "invalid" status, for fetching said specified data block from said system memory, writing said fetched data block into said respective cache memory, and setting in said respective cache memory the associated status information for the fetched data block to indicate a "read" status;

(c) means, responsive to said memory access request when said memory access request is a request to write specified data to less than a full portion of at least one of said words and a matching associated block address is not found in said respective cache memory or a matching associated block address is found in said respective cache memory but the associated block status information for the matching associated block address indicates an "invalid" status, for fetching said specified data block from said system memory, and writing at least a portion of the fetched data bock and said specified data into said respective cache memory, and setting in said respective cache memory the associated status information for the fetched data block to indicate a "written full" status;

(d) means, responsive to said memory access request when said memory access request is a request to write specified data to a full portion of at least one of said words and a matching associated block address is not found in said respective cache memory or a matching associated block address is found in said respective cache memory but the associated block status information for the matching associated block address indicates that the block is invalid, for writing said specified data into said respective cache memory, setting in said respective cache memory the associated status information for each word in said specified block to indicate that said specified one of said words is valid, and setting in said respective cache memory the associated status information for said specified block to indicate a status of "written partial";

(e) means, responsive to said memory access request when said memory access request is a request to write specified data and a matching associated block address is found in said cache memory and the associated block status information for the matching associated block address indicates neither an "invalid" status nor a "written full" status, for fetching said specified data block from said system memory, writing at least a portion of the fetched data block and said specified data into said respective cache memory, and setting in said respective cache memory the associated status information for the fetched data block to indicate a "written full" status; and

(f) means, responsive to said memory access request when said memory access request is a request to write specified data and a matching associated block address is found in said respective cache memory and the associated block status information for the matching associated block address indicates a "written full" status, for writing said specified data into said cache memory.

4. The multi-processor system as claimed in claim 3, further including a system control unit coupled between said system memory and said CPUs, said system control unit including a central directory for storing copies of said cache status information indicating whether the blocks of data words in said cache memories each have a status of "invalid", "read", "written-partial", or "written-full", and control means responsive to said fetching from said system memory by said means (c) and said means (e) responsive to a write access request by said each CPU for accessing said central directory to determine whether another one of said cache memories other than said respective cache memory has a status of "written full" associated with said specified block address, and when said another one of said cache memories has a status of "written full" associated with said specified block address, transmitting a command to said another one of aid cache memories for writing the specified data block in said another one of said cache memories back to said system memory and setting said associated status information in said another one of said cache memories for said specified data block address to indicate a status of "invalid".