System and method for limited fanout daisy chaining of cache invalidation requests in a shared-memory multiprocessor system

• US 7,389,389 B2
• Filed: 09/26/2003
• Issued: 06/17/2008
• Est. Priority Date: 06/10/2000
• Status: Expired due to Term

• Current Assignee: SK Hynix Inc.
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Ravishankar, Mosur K., Nowatzyk, Andreas, Barroso, Luiz A., Stets, Robert J. Jr., Gharachorloo, Kourosh
• Primary Examiner(s): Sough; Hyung
• Assistant Examiner(s): Chery; Mardochee
• Application Number:
  US10/672,960
• Publication Number:
  US 20040064653A1
• Time in Patent Office: 1,726 Days
• Field of Search: None
• US Class Current: 711/145
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device

Abstract

A protocol engine is for use in each node of a computer system having a plurality of nodes. Each node includes an interface to a local memory subsystem that stores memory lines of information, a directory, and a memory cache. The directory includes an entry associated with a memory line of information stored in the local memory subsystem. The directory entry includes an identification field for identifying sharer nodes that potentially cache the memory line of information. The identification field has a plurality of bits at associated positions within the identification field. Each respective bit of the identification field is associated with one or more nodes. The protocol engine furthermore sets each bit in the identification field for which the memory line is cached in at least one of the associated nodes. In response to a request for exclusive ownership of a memory line, the protocol engine sends an initial invalidation request to no more than a first predefined number of the nodes associated with set bits in the identification field of the directory entry associated with the memory line.

Claims

1. A multiprocessor computer system, comprising:

a plurality of nodes, each node including;

an interface to a local memory subsystem, the local memory subsystem storing a multiplicity of memory lines of information and a directory;

a memory cache for caching a multiplicity of memory lines of information, including memory lines of information stored in a remote memory subsystem that is local to another node;

the directory including an entry associated with a memory line of information stored in the local memory subsystem, the entry including an identification field for identifying a subset of nodes from the plurality of nodes caching the memory line of information;

the identification field configured to comprise a plurality of bits at associated positions within the identification field;

a protocol engine implementing a cache coherence protocol, said protocol engine configured to

associate with each respective bit of the identification field one or more nodes of the plurality of nodes, including a respective first mode, wherein the one or more nodes associated with each respective bit are determined by the reference to the position of the respective bit within the identification field;

set each bit in the identification field of the directory entry associated with the memory line for which the memory line is cached in at least one of the associated nodes;

send an initial invalidation request to no more than a first predefined number of the nodes associated with set bits in the identification field of the directory entry associated with the memory line, the first predefined number of nodes being greater than one, but less than the number of nodes associated with set bits in the identification field;

wherein the identification field is subdivided to form a number of groups of bits equal to the first predefined number and the protocol engine is configured to send at most one invalidation request for each group of bits, wherein the at most one invalidation request for each group of bits is sent to a first node, if any, associated with a set bit in the group of bits.

2. The system of claim 1, wherein the protocol engine is further configured to:

store in the identification field of the directory entry associated with the memory line one or more node identifiers that identify a subset of the plurality of nodes in which the memory line is cached, when the subset of nodes includes fewer than a second predefined number of nodes, wherein each node identifier stored in the identification field occupies a plurality of the bits of the identification field; and

send an initial invalidation request to no more than the first predefined number of the nodes whose node identifiers are stored in the identification field of the directory entry associated with the memory line.

3. The system of claim 2, wherein the protocol engine is configured to

respond to a request to share the memory line with an additional node such that the memory line will be cached in more than the second predefined number of nodes, by reconfiguring the identification field of the directory entry associated with the memory line by setting each bit in the identification field that is associated with any of the nodes in which the memory line is cached or will be cached upon servicing the request.

4. The system of claim 2, wherein

the directory entry further includes a state field, the state field indicating whether the identification field is configured to store the one or more node identifiers, the state field otherwise indicating that the identification field is configured to associate with each respective bit of the identification field one or more nodes of the plurality of nodes.

5. The system of claim 1, wherein

the plurality of nodes is a first number of nodes;

the plurality of bits in the identification field is a second number of bits;

the first number is greater than the second number; and

the protocol engine is configured to associate both the first respective node and a respective second node with a particular one of the bits of the identification field, to generate a first node identifier corresponding to the first respective node in accordance with the position of the particular bit within the identification field, and to generate a second node identifier corresponding to the second respective node in accordance with the position of the particular bit within the identification field and the second number of bit in the identification field.

6. The system of claim 1, wherein

the protocol engine is configured to send the initial invalidation request to the first node associated with a particular set bit in the identification field.

7. The system of claim 1, wherein

the protocol engine is configured to include in the initial invalidation request a pattern of bits based on at least a subset of the plurality of bits in the identification field, such that a recipient node of the initial invalidation request can derive from the pattern of bits a next recipient node, if any, to which to send a second invalidation request corresponding to the initial invalidation request.

8. The system of claim 1, wherein

the identification field is subdivided to form a number of groups of bits;

and

the protocol engine is configured to send, for each respective group of bits, the initial invalidation request to a first node, if any, associated with a set bit in the respective group of bits, and to include in the invalidation request a pattern of bits based on the respective group of bits in the identification field.

9. The system of claim 8, wherein

the protocol engine is configured to send the initial invalidation request to a second node associated with a set bit in the respective group of bits when the first node is a node requesting exclusive ownership of the memory line of information.

10. The system of claim 8, wherein

the protocol engine is configured to send the initial invalidation request to a second node associated with a set bit in the respective group of bits when the first node is a home node of the memory line of information.

11. The system of claim 1, wherein

the protocol engine is further configured to forward an invalidation request received by the protocol engine to a next node identified in the invalidation request.

12. The system of claim 1, wherein

the protocol engine is further configured to associate with a respective subset of bits of the identification field one node of the subset of nodes when the subset of nodes includes fewer than a second predefined number of nodes.

13. The system of claim 12, wherein

the directory entry further includes a state field, the state field indicating whether the protocol engine is associating with a respective subset of bits of the identification field one node of the plurality of nodes or associating with each respective bit of the identification field one or more nodes of the plurality of nodes.

14. The system if claim 13, wherein

the protocol engine associates with a respective subset of bits of the identification field one node of the subset of nodes when the subset of nodes includes fewer than a second predefined number of nodes.

15. A protocol engine implementing a cache coherence protocol, for use in a multiprocessor computer system, the protocol engine located at a particular node of a plurality of nodes in the multiprocessor computer system, the protocol engine comprising:

input logic for receiving a first invalidation request, the invalidation request identifying a memory line of information and including a pattern of bits for identifying a subset of the plurality of nodes that are indicated to store cached copies of the identified memory line; and

processing circuitry, responsive to receipt of the first invalidation, for sending a second invalidation request corresponding to the first invalidation request to a next node if the plurality of bits in fact identify the next node;

sending an invalidation acknowledgement to a requesting node identified in the first invalidation message if the plurality of bits fail to identity a next node; and

invalidating a cached copy of the identified memory line, if any, in the particular node of the plurality of nodes in the multiprocessor computer system.

16. A protocol engine implementing a cache coherence protocol, for use in a multiprocessor computer system, the protocol engine located at a particular node of a plurality of nodes in the multiprocessor computer system, the protocol engine comprising:

input logic for receiving a first invalidation request, the invalidation request identifying a memory line of information and including a pattern of bits for identifying a subset of the plurality of nodes that are indicated to store cached copies of the identified memory line; and

processing circuitry, responsive to receipt of the first invalidation request, for determining a next node identified by the pattern of bits in the invalidation request and for sending to the next node, if any, a second invalidation request corresponding to the first invalidation request, and for invalidating a cached copy of the identified memory line, if any, in the particular node of the multiprocessor computer system.

17. The protocol engine of claim 16, wherein the processing circuitry is configured to determine when the particular node is a last node identified by the pattern of bits in the invalidation request, and when said determination is made, to send an invalidation acknowledgment message to a requesting node identified in the first invalidation message.