Non-speculative distributed conflict resolution for a cache coherency protocol

• US 20050237941A1
• Filed: 06/24/2005
• Published: 10/27/2005
• Est. Priority Date: 12/19/2002
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Beers, Robert H., Goodman, James R., Hum, Herbert H.J.
• Granted Patent: US 7,434,006 B2
• Time in Patent Office: Days
• US Class Current: 370/236
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means

Abstract

A conflict resolution technique provides consistency such that all conflicts can be detected by at least one of the conflicting requestors if each node monitors all requests after that node has made its own request. If a line is in the Exclusive, Modified or Forward state, conflicts are resolved at the node holding the unique copy. The winner of the conflict resolution, and possibly the losers, report the conflict to the home node, which pairs conflict reports and issues forwarding instructions to assure that all requesting nodes eventually receive the requested data. If a requested cache line is either uncached or present only in the Shared state, the home node provides a copy of the cache node and resolves conflicts. In one embodiment, a blackout period after all responses until an acknowledgement message has been received allows all conflicting nodes to be aware of conflicts in which they are involved.

Claims

1. A method comprising:

resolving conflicting requests from multiple peer nodes for a block of data by a peer node having a valid copy of requested data that is requested by the conflicting messages; and

resolving conflicting requests for the block of data by a home node corresponding to the requested data if no unique, cached copy is stored by one of the peer nodes.

2. The method of claim 1 wherein resolving conflicting requests by a peer node comprises:

receiving, from a peer node not having a valid copy of the requested data, a list of peer nodes that have transmitted conflicting requests for the requested data; and

transmitting a copy of the requested data to a target peer node from the list.

3. The method of claim 2 wherein transmitting a copy of the requested data to the target peer node further comprises transmitting the list, less the transmitting peer node, to the target peer node.

4. The method of claim 2 further comprising receiving an acknowledgement message from a home node corresponding to the requested data.

5. The method of claim 2 further comprising changing a state associated with a copy of the requested data stored by the peer node transmitting the requested to the target node.

6. The method of claim 1 wherein resolving conflicting requests by the home node comprises:

receiving, from a peer node, a list of peer nodes that have transmitted conflicting requests for the requested data; and

transmitting a copy of the requested data from the home node to a target node from the list.

7. The method of claim 6 wherein transmitting a copy of the requested data to the target node further comprises transmitting the list, less the transmitting node, to the target node.

8. The method of claim 1 wherein the block of data comprises a cache line.

9. A system comprising:

a plurality of peer nodes having cache memories to generate requests for data, the peer node having a valid, cached copy of the requested data to resolve the conflicting requests and to provide a copy of the requested data to one of the multiple requesting peer nodes; and

a home node corresponding to the requested data coupled with the peer nodes, the home node to resolve the conflicting requests if no peer node stores a valid, cached copy of the requested data.

10. The system of claim 9 wherein the requested data comprises a cache line.

11. The system of claim 9 wherein one or more of the requesting peer nodes transmits a list of peer nodes that generated a conflicting request to the peer node to resolve the conflict.

12. The system of claim 11 wherein the peer node to resolve the conflicting requests transmits a copy of the requested data to a target node from the list.

13. The system of claim 12 wherein the peer node to resolve the conflicting requests further to transmit a copy of the list, less the transmitting node, to the target node.

14. The system of claim 9 wherein one or more of the requesting peer nodes transmits a list of peer nodes that generated a conflicting request to the home node.

15. The system of claim 14 wherein the home node transmits a copy of the requested data to a target node from the list.

16. The system of claim 15 wherein the peer node to resolve the conflicting requests further to transmit a copy of the list, less the transmitting and target nodes, to the target node.

17. The system of claim 9 wherein a peer node comprises:

a processor;

a cache memory coupled with the processor; and

an external memory coupled with the processor.

18. The system of claim 9 further comprising an agent to represent multiple nodes coupled with the peer nodes and the home node.

19. An apparatus comprising:

means for resolving conflicting requests from multiple peer nodes for a block of data by a peer node having a valid copy of requested data that is requested by the conflicting messages; and

means for resolving conflicting requests for the block of data by a home node corresponding to the requested data if no unique, cached copy is stored by one of the peer nodes.

20. The apparatus of claim 19 wherein the means for resolving conflicting requests by a peer node comprises:

means for receiving, from a peer node not having a valid copy of the requested data, a list of peer nodes that have transmitted conflicting requests for the requested data; and

means for transmitting a copy of the requested data to a target peer node from the list.

21. The apparatus of claim 19 wherein the means for resolving conflicting requests by the home node comprises:

means for receiving, from a peer node, a list of peer nodes that have transmitted conflicting requests for the requested data; and

means for transmitting a copy of the requested data from the home node to a target node from the list.

22. The apparatus of claim 19 wherein the block of data comprises

a cache line.

23-36. -36. (canceled)