Cache coherency mechanism using arbitration masks

• US 20020099833A1
• Filed: 01/24/2001
• Published: 07/25/2002
• Est. Priority Date: 01/24/2001
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Sharma, Madhumitra, Doren, Stephen Van, Steely, Simon C. Jr.
• Granted Patent: US 6,961,825 B2
• Time in Patent Office: Days
• US Class Current: 709/228
• CPC Class Codes: G06F 12/0824 Distributed directories, e.g. linked lists of caches
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers
• CPC Class Codes: H04L 67/561 Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A distributed processing system includes a cache coherency mechanism that essentially encodes network routing information into sectored presence bits. The mechanism organizes the sectored presence bits as one or more arbitration masks that system switches decode and use directly to route invalidate messages through one or more higher levels of the system. The lower level or levels of the system use local routing mechanisms, such as local directories, to direct the invalidate messages to the individual processors that are holding the data of interest.

Claims

1. A method of operating a cache coherency mechanism for a distributed computer system that includes multiple processors, the method including the steps of:

A. determining which processors have copies of data of interest;

B. determining paths through various system switching devices on routes from an associated home node to the processors that have copies of the data of interest;

C. encoding information that is indicative of the paths into one or more masks;

D. when the data of interest is the subject of an update operation, producing at the home node an invalidate message that includes the masks;

E. at the switching devices, decoding the applicable masks and routing the invalidate message over the paths indicated by the decoded information; and

F. at switching devices that connect to the processors, forwarding the invalidate message to the processors that have copies of the data of interest.

2. The method of claim 1, wherein the step of encoding includes setting bits in a given mask to indicate paths from a corresponding switching device to a next switching device on the routes to the processors.

3. The method of claim 2, wherein the step of encoding further includes setting the bits to correspond to a combination of the paths through a plurality of switching devices.

4. The method of claim 2, wherein the step of encoding further includes setting bits that correspond to ports of the respective switching devices.

5. The method of claim 1 further including in the step of encoding

a. separately encoding into a first mask information relating to paths through the switching device that is associated with the home node,

b. encoding into one or more second masks information relating to paths through the switching devices that connect to the switching device of step a,

c. encoding into one or more additional masks information relating to paths through the switching devices that connect to the switching devices of the previous step, and

d. repeating step c for paths through additional switching devices.

6. A method of operating a cache coherency mechanism for a distributed computer system that includes multiple processors which are interconnected by layers of switching devices, the method including the steps of:

A. determining which processors have copies of data of interest;

B. determining paths through various system switching devices on routes from a home node to the processors that have copies of the data of interest;

C. encoding information that is indicative of the paths through a highest layer of the system into a first mask;

D. encoding information that is indicative of the paths through a next highest layer of the system into a next mask;

E. repeating step D for the remaining layers of the system;

F. when the data of interest is the subject of an update operation, producing at the home node an invalidate message that includes the masks;

G. at the switching devices in the highest layer, decoding the first mask and routing the invalidate message over the indicated paths;

H. at the switching devices in the remaining layers, decoding the corresponding masks and routing the invalidate message over the indicated paths through the layers; and

I. at switching devices that connect to the processors of interest, forwarding the invalidate message to the processors.

7. The method of claim 6, wherein the steps of encoding include setting bits in a given mask to indicate one or more paths from a corresponding switching device to one or more switching devices in a next layer of the system.

8. The method of claim 6, wherein the steps of encoding further include setting the bits to correspond to a combination of the paths through a plurality of switching devices in a given layer of the system.

9. The method of claim 7, wherein the steps of encoding further include setting bits that correspond to ports of the switching devices.

10. The method of claim 6 wherein the highest layer includes one or more switching devices that receive messages from the home node.

11. A distributed computer system including:

A. a plurality of processors, with one or more processors designated as home nodes;

B. a plurality of switching devices that interconnect the processors;

C. one or more encoders for encoding into one or more masks information relating to paths through the switching devices from an associated home node to the processors that have data of interest;

D. a cache coherency directory with entries for data of interest, the directory including in a given entry

a. information that identifies the owner of the data, and

b. one or more associated masks; and

E. one or more decoders at the switching devices, the decoder in a given switching device decoding an associated mask to set paths through the switching device for messages directed from the home node to processors that have copies of the associated data of interest.

12. The distributed computer system of claim 11 wherein

i. the plurality of switching devices are organized into layers with one or more switching devices in a highest layer connected to transmit messages from the home node, one or more switching devices in a next highest layer connected to transmit messages from the one or more switching devices in the highest layer to the switching devices in a lower layer, one or more switching devices in lower layers connected to transmit messages from the switching devices in preceding levels to switching devices in subsequent layers, and one or more switching devices in a lowest level connected to transmit messages to the processors, and

ii. the masks relate, respectively, to paths through the switching devices in the associated layers.

13. The distributed computer system of claim 12 wherein one or more of the masks relate to combinations of the paths through the switching devices in the associated layers.

14. The distributed computer system of claim 11 wherein a given home node produces messages directed to processors that have copies of date of interest and includes in the messages the associated masks.

15. The distributed computer system of claim 12 wherein the switching devices are switches and the masks designate port of the associated switches.

16. The distributed computer system of claim 14 wherein the switches that connect to the processors use local routing information to provide the messages to the associated processors that have copies of the data of interest.

17. The distributed computer system of claim 14 wherein the switches that connect to the processors locally broadcast the messages to the associated processors.