Cache coherency protocol for multi processor computer system

In a computer system including a plurality of nodes and at least one memory device, each at least one memory device storing one or more data blocks, at most one of the plurality of nodes having, at any one time, write access to any one of the one or more data blocks, each of the at least one memory device comprising:

• a) a storage space for one or more data blocks;
• b) a memory directory for maintaining information associated with the one or more data blocks, the memory directory including, for each data block stored in the storage space,
• i) a respective data block identification field for identifying the data block, and
• ii) a respective memory state field, wherein the memory state field maintains one of a plurality of states including a SHARED-UNMODIFIED state, an EXCLUSIVE-MODIFIED state, and a FORWARD-EXCLUSIVE state;
• c) the memory device operating to determine, for each of the one or more data blocks,
• i) whether any one of the plurality of nodes has write access to a respective one of the one or more data blocks, and
• ii) whether any one of the plurality of nodes has requested non-exclusive read access to the respective one of the one or more data blocks by issuing a Read Shared command to the memory device for the respective one of the one or more data blocks;
• d) the memory device operating to set the memory state field for each of the one or more data blocks:
• i) to the SHARED-UNMODIFIED state in response to the memory device determining that none of the plurality of nodes has write access to a copy of a respective one of the one or more data blocks;
• ii) to the EXCLUSIVE-MODIFIED state in response to the memory device determining that one and only one of the plurality of nodes has write access to the respective one of the one or more data blocks;
• iii) to the FORWARD-EXCLUSIVE state in response to the memory device determining that the memory state field for the respective one of the one or more data blocks is in the EXCLUSIVE-MODIFIED state and the memory device further determining that there is an outstanding Read Shared command from one of the plurality of nodes;
• and
• g) the memory device further operating to not process any additional read commands for any one of the one or more data blocks determined to be in the FORWARD-SHARED state until processing of said Read Shared command is complete.

In a computer system including a plurality of nodes and at least one memory device, each at least one memory device storing one or more data blocks, at most one of the plurality of nodes having, at any one time, write access to any one of the one or more data blocks, each of the at least one memory device comprising:

• a) a storage space for one or more data blocks
• b) a memory directory for maintaining information associated with one or more data blocks, the memory directory including, for each data block to be stored,
• i) a respective data block identification field for identifying the data block,
• ii) a respective memory state field, wherein the memory state field maintains a plurality of states including a SHARED-UNMODIFIED, and EXCLUSIVE-MODIFIED state,
• iii) a block owner identification field, wherein said block owner identification field maintains unique address information for a one and only node having write access to the data block;
• c) the memory device operating to determine, for each of the one or more data blocks,
• i) whether any one of the plurality of nodes has write access to a respective one of the one or more data blocks, and
• ii) whether any one of the plurality of nodes has requested exclusive read access to the respective one of the one or more data blocks by issuing a Read Exclusive command to the memory device for the respective one of the one or more data blocks;
• d) said memory device operating to set the memory state field for each one of the one or more data blocks;
• i) to the SHARED-UNMODIFIED state in response to the memory device determining that none of the plurality of nodes has write access to a copy of the one of the one or more data blocks;
• ii) to the EXCLUSIVE-MODIFIED state in response to the memory device determining that one and only one of the plurality of nodes has write access to the one of the one or more data blocks;
• and
• e) the memory device setting the memory state field associated with the one of the one or more data blocks to an EXCLUSIVE-MODIFIED state and storing in the block owner identification field associated with the one of the one or more data blocks the unique address information for the one and only one node having write access to the one of the one or more data blocks to indicate ownership of each one of the one or more data blocks.

A multi-node computer system, comprising:

• (a) a memory device including a memory control mechanism and a plurality of data blocks in either modified or unmodified form;
• (b) a plurality of nodes, each of which includes a write-back cache for temporary storage of copies of one or more of the plurality of data blocks, the copies of one or more of the plurality of data blocks being in either modified or unmodified form, at most one of the plurality of nodes having, at any one time, write access to any one of the plurality of data blocks;
• (c) a memory/node coupling mechanism connected to each of the nodes and to the memory device;
• (d) the memory control mechanism including a memory state identifier for each one of the plurality of data blocks;
• e) the memory control mechanism operating to determine, for each of the plurality of data blocks,
• i) whether any one of the plurality of nodes has write access to a respective one of the plurality of data blocks, and
• ii) whether any one of the plurality of nodes has requested exclusive read access to the respective one of the plurality of data blocks by issuing a Read Exclusive command to the memory device for the respective one of the plurality of data blocks;
• (f) each one of the memory state identifiers being selectively set by the memory control mechanism to indicate the identification of the respective one of the plurality of data blocks and to indicate one of a plurality of states including a SHARED-UNMODIFIED, EXCLUSIVE-MODIFIED, FORWARD-EXCLUSIVE, and FORWARD-SHARED state for the one of the plurality of data blocks;
• (g) each one of the nodes operating independently to selectively issue one or more of the following:
• (i) a Read Shared command requesting the memory device to send to the node a read-only copy of a preselected one of the plurality of data blocks;
• (ii) the Read Exclusive command requesting the memory device to send to the node a writable copy of a preselected one of the plurality of data blocks;
• (h) the memory device operating to set the SHARED-UNMODIFIED state for the respective one of the plurality of data blocks in response to the memory device determining that none of the plurality of nodes has write access to a copy of the respective one of the plurality of data blocks;
• (i) the memory device operating to set the EXCLUSIVE-MODIFIED state for the respective one of the plurality of data blocks in response to the memory device determining that one and only one of the plurality of nodes has write access to the respective one of the plurality of data blocks;
• (j) the memory device operating to set the FORWARD-EXCLUSIVE state for the respective one of the plurality of data blocks in response to the memory device determining that the respective one of the plurality of data blocks is in the EXCLUSIVE-MODIFIED state and further determining that there is an outstanding Read Exclusive command from one of the plurality of nodes, the memory device further operating to delay processing any additional read commands to the respective one of the plurality of data blocks until processing of the outstanding Read Exclusive command is complete;
• and
• (k) the memory device operating to set the FORWARD-SHARED state for the respective one of the plurality of data blocks in response to the memory device determining that the respective one of the plurality of data blocks is in the EXCLUSIVE-MODIFIED state and further determining that there is an outstanding Read Shared command, the memory device further operating to delay processing any additional read commands to the respective one of the plurality of data blocks until processing of the outstanding Read Shared command is complete.

A multi-node computer system, which comprises:

• (a) a memory device including a memory control mechanism and a plurality of data blocks in either modified or unmodified form;
• (b) a plurality of nodes, each of which includes a write-back cache for temporary storage of copies of one or more of the plurality of data blocks, the copies of one or more of the plurality of data blocks being in either modified or unmodified form, at most one of the plurality of nodes having, at any one time, write access to any one of the plurality of data blocks;
• (c) a memory/node coupling mechanism connected to each of said nodes and to said memory device;
• (d) said memory control mechanism including a memory state identifier for each one of the plurality of data blocks;
• e) the memory device operating to determine, for each of the one or more data blocks,
• i) which, if any, one of the plurality of nodes has write access to a respective one of the plurality of data blocks, and
• ii) which, if any, one of the plurality of nodes has requested exclusive read access to the respective one of the plurality of data blocks by issuing a Read Exclusive command to the memory device for the respective one of the plurality of data blocks;
• (f) each one of the memory state identifiers being selectively set by said memory control mechanism to indicate the identification of the respective one of the plurality of data blocks and to indicate one of a plurality of states including a SHARED-UNMODIFIED, EXCLUSIVE-MODIFIED, and UNOWNED state for said one of the plurality of data blocks;
• (i) the memory device operating to set the SHARED-UNMODIFIED state for the respective one of the plurality of data blocks in response to the memory device determining that none of the plurality of nodes has write access to a copy of the respective one of the plurality of data blocks,
• (ii) the memory device operating to set the EXCLUSIVE-MODIFIED state for the respective one of the plurality of data blocks in response to the memory device determining that one and only one of the plurality of nodes has write access to the respective one of the plurality of data blocks,
• (iii) the UNOWNED state in response to the memory device determining that none of the plurality of nodes has a copy of the respective one of the plurality of data blocks;
• (g) each one of said nodes operating independently to selectively issue one or more of the following:
• (i) a Read Shared command requesting of the memory device to send to the node a read-only copy of a preselected one of the plurality of data blocks;
• (ii) a Read Exclusive command requesting of the memory device to send to the node a writable copy of a preselected one of the plurality of data blocks;
• (iii) a Write Unowned command for storing in the memory device a preselected one of the copies of one or more of the plurality of data blocks from the node;
• (iv) a Write Shared command for storing in the memory device a preselected one of the copies of one or more of the plurality of data blocks from the node subsequent to a Read Shared command issued by another node;
• (v) a Read Data Response command for sending a preselected one of the copies of one or more of the plurality of data blocks to another node subsequent to a Read Exclusive or Read Shared command issued by said another node;
• and
• (vi) a Forward Acknowledge command to notify said memory device that a Read Exclusive command has been processed;
• (h) said memory device operating to selectively issue one or more of the following:
• (i) a Read Data Response command for sending a preselected one of the plurality of data blocks to one of the plurality of nodes in response to either a Read Shared or Read Exclusive command from the one of the plurality of nodes in response to the memory state identifier associated with the preselected one of the plurality of data blocks indicating said preselected one of the plurality of data blocks is in either the SHARED-UNMODIFIED or UNOWNED state;
• (ii) a Forward Read Shared command to one of the plurality of nodes, for sending a preselected one of the copies of one or more of the plurality of data blocks from said one of the plurality of nodes to the memory device and to another one of the plurality of nodes, the memory device issuing the Forward Read Shared command to said one of the plurality of nodes in response to
• 1) the memory device receiving a Read Shared command from said another one of the plurality of nodes,
• 2) the memory state identifier associated with the preselected one of the plurality of data blocks indicating said preselected one of the plurality of data blocks is in the EXCLUSIVE-MODIFIED state, and
• 3) the one of the plurality of nodes being determined by the memory device to have write access to the preselected one of the plurality of data blocks;
• (iii) a Forward Read Exclusive command to one of the plurality of nodes, for sending a preselected one of the copies of one or more of the plurality of data blocks from said one of the plurality of nodes to another of the plurality of nodes and for returning a Forward Acknowledge command to the memory device from said one of the plurality of nodes, the memory device issuing the Forward Read Exclusive command to said one of the plurality of nodes in response to
• 1) the memory device receiving a Read Exclusive command from said another of the plurality of nodes,
• 2) the memory state identifier associated with the preselected one of the plurality of data blocks indicating said predetermined one of the plurality of data blocks is in the EXCLUSIVE-MODIFIED state, and
• 3) the one of the plurality of nodes being determined by the memory device to have write access to the preselected one of the plurality of data blocks;
• and
• (iv) an Invalidate command issued to each of the plurality of nodes to request an identified preselected one of the copies of one or more of the plurality of data blocks be marked invalid.

In a memory device for connection to a computer system having a multiplicity of nodes, at least two of the nodes having a write-back cache, said caches and memory device adapted to store one or more data blocks, at most one of the at least two of the nodes having, at any one time, read-AND-write access to any one of the one or more data blocks stored in the memory device, each data block having associated therewith a coherency state, a computer implemented method of maintaining data block coherency among the memory device and said multiplicity of nodes, the method comprising the steps of:

• reserving memory space in the memory device for storing the coherency state of each data block;
• determining, for each data block, whether any one of the at least two nodes has read-AND-write access to said each data block, and further determining whether any one of the at least two nodes has requested read-AND-write access to said each data block;
• storing in the space reserved for the coherency state of each data block;
• the coherency state of SHARED-UNMODIFIED in response to none of the plurality of nodes having read-AND-write access to the data block;
• the coherency state of EXCLUSIVE-MODIFIED in response to one and only one node having read-AND-write access to the data block;
• the coherency state of FORWARD-EXCLUSIVE in response to the coherency state of the data block being EXCLUSIVE-MODIFIED and an other than the one and only one node requesting read-AND-write access to the data block;
• inhibiting all requests for read-AND-write or read-only access to a preselected data block in response to the coherency state of the preselected data block being FORWARD-EXCLUSIVE.

In a memory device for connection to a computer system having a multiplicity of nodes, at least two of the nodes having a write-back cache, said caches and memory device storing one or more data blocks, at most one of the at least two of the nodes having, at any one time, write access to any one of the one or more data blocks stored in the memory device, each data block having associated therewith a coherency state, a computer implemented method of maintaining data block coherency among the memory device and said multiplicity of nodes, the method comprising the steps of:

• reserving memory space in the memory device for storing the coherency state of each data block;
• determining, for each data block, whether any one of the at least two nodes has read-AND-write access to said each data block, and further determining whether any one of the at least two nodes has requested read-AND-write access to said each data block;
• storing in the space reserved for the coherency state of each data block;
• the coherency state of SHARED-UNMODIFIED in response to none of the plurality of nodes having read-AND-write access to the data block;
• the coherency state of EXCLUSIVE-MODIFIED in response to one and only one node having read-AND-write access to the data block;
• the coherency state of FORWARD-SHARED in response to the coherency state of the data block being EXCLUSIVE-MODIFIED and an other than the one and only one of the plurality of nodes requesting read-only access to the data block;
• inhibiting all requests for read-AND-write or read-only access to a preselected data block in response to the coherency state of the preselected data block being FORWARD-SHARED.

In a memory device for connection to a multi-node computer system including a plurality of nodes, said memory device including storage space for one or more data blocks, at most one of the plurality of nodes having, at any one time, write access to any one of the one or more data blocks, a computer implemented method of maintaining information associated with one or more data blocks, said method comprising the steps of:

• reserving, for each data block to be stored, a data block identification field;
• reserving, for each data block to be stored, a block owner identification field;
• reserving, for each data block to be stored, a memory state field;
• determining whether any of the plurality of nodes has write access to the respective data block;
• storing, in the data block identification field for each data block to be stored, identification information for each data block;
• storing, in said memory state field for each data block to be stored, one of a plurality of states including
• a SHARED-UNMODIFIED state in response to none of the plurality of nodes being determined to have write access to a respective data block,
• and an EXCLUSIVE MODIFIED state in response to one and only one of the plurality of nodes being determined to have write access to the respective data block;
• indicating ownership of a certain data block to be stored by storing in a certain memory state field associated with the certain data block an EXCLUSIVE-MODIFIED state and by storing in the block owner identification field unique address information for a one and only one node determined to have write access to the certain data block;
• indicating that no node has write access to the certain data block by storing in the certain memory state field associated with the certain data block to be stored a SHARED-UNMODIFIED state.

In a computer system comprising a first and a second node and a separate memory device, each of the nodes having a write-back cache, wherein the memory device and the nodes include storage space for one or more data blocks, each data block having associated therewith a coherency state, a computer implemented method of maintaining data block coherency among the memory device and the nodes, said method comprising the steps of:

• reserving space in the memory device for storing the coherency state of one or more data blocks;
• reserving space in the memory device for storing ownership identification information of one or more data blocks;
• storing in the space reserved for the coherency state of a data block the coherency state of EXCLUSIVE-MODIFIED in response to said first node being determined to have read-AND-write access to the data block;
• storing in the space reserved for ownership identification information of the data block, the identification of said first node in response to said first node being determined to have read-AND-write access to the data block;
• sending from said second node to the memory device a command to provide to said second node the data block for the purpose of read-AND-write access;
• checking the space reserved for the coherency state of the data block to determine whether the data block is in the EXCLUSIVE-MODIFIED state;
• responding to the data block being in the EXCLUSIVE-MODIFIED state, checking the space reserved for the ownership identification of the data block to determine which node owns the data block;
• sending from the memory device to said first node a command to send the data block to said second node in response to the determination that the first node owns the data block;
• changing the stored coherency state of the data block from EXCLUSIVE-MODIFIED to FORWARD-EXCLUSIVE;
• responding to the command to said first node by sending to said second node the data block;
• sending to the memory device an acknowledgment signal that the command to said first node has been processed;
• changing the stored coherency state of the data block from FORWARD-EXCLUSIVE to EXCLUSIVE-MODIFIED;
• and
• changing the stored ownership identification information of the data block from the identification of the first node to the identification of the second node.

In a computer system comprising a first and a second node and a separate memory device, each of the nodes having a write-back cache, wherein the memory device and the nodes include storage space for one or more data blocks, each data block having associated therewith a coherency state, a computer implemented method of maintaining data block coherency among the memory device and the nodes, said method comprising the steps of:

• reserving space in the memory device for storing the coherency state of one or more data blocks;
• reserving space in the memory device for storing ownership identification information of one or more data blocks;
• storing in the space reserved for the coherency state of a given data block the coherency state of EXCLUSIVE-MODIFIED in response to said first node being determined to have read-AND-write access to the data block;
• storing in the space reserved for the ownership identification information of the data block, the identification of said first node in response to said first node being determined to have read-AND-write access to the data block;
• sending from said second node to the memory device a command to provide to said second node the data block for the purpose of read-only access;
• checking the space reserved for the coherency state of the data block to determine whether the data block is in the EXCLUSIVE-MODIFIED state;
• responding to the data block being in the EXCLUSIVE-MODIFIED state, checking the space reserved for the ownership identification of the data block to determine which node owns the data block;
• sending from the memory device to said first node a command to send the data block to said second node in response to the determination that the first node owns the data block;
• changing the stored coherency state of the data block from EXCLUSIVE-MODIFIED to FORWARD-SHARED;
• responding to the command to said first node by sending to said second node the data block;
• sending to the memory device an acknowledgment signal that the command to said first node has been processed;
• changing the stored coherency state of the data block from FORWARD-SHARED to SHARED-UNMODIFIED.

In a computer system including a plurality of nodes and at least one memory device, each at least one memory device storing one or more data blocks, at most one of the plurality of nodes having, at any one time, write access to any one of the one or more data blocks, each of the at least one memory device comprising:

• a) a storage space for one or more data blocks;
• b) a memory directory for maintaining information associated with the one or more data blocks, the memory directory including, for each data block stored in the storage space,
• i) a respective data block identification field for identifying the data block, and
• ii) a respective memory state field, wherein the memory state field maintains one of a plurality of state including a SHARED-UNMODIFIED state and an EXCLUSIVE-MODIFIED state,
• iii) a block owner identification field, wherein said block owner identification field maintains unique address information for a one and only node having write access to the data block,
• iv) a copy mask field containing a plurality of bits, each bit corresponding to one of the plurality of nodes, wherein setting one or more of the plurality of bits to a non-zero value indicates that a copy of the data block is present at the nodes corresponding to the bits;
• c) the memory device operating to set the memory state field and the block owner identification field in said memory directory to indicate data block ownership of each one of the one or more data blocks by setting in the memory state field associated with the one of the one or more data blocks an EXCLUSIVE-MODIFIED state and by storing, in the block owner identification field associated with the one of the one or more data blocks, the unique address information for the one and only one node having write access to the one of the one or more data blocks;
• d) said memory device responding to receiving a Read-Exclusive command for a particular one of the data blocks whose copy mask field has a non-zero value by transmitting an INVALIDATE command to each of the plurality of nodes indicated by the copy mask field.