Scheme for insuring data consistency between a plurality of cache memories and the main memory in a multi-processor system
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
4 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. - View Dependent Claims (2)
-
-
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. - View Dependent Claims (4)
- 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;
Specification