System and method for generating cache coherence directory entries and error correction codes in a multiprocessor system

• US 6,725,343 B2
• Filed: 10/05/2001
• Issued: 04/20/2004
• Est. Priority Date: 10/05/2000
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Nowatzyk, Andreas, Gharachorloo, Kourosh, Barroso, Luiz A.
• Primary Examiner(s): Ellis, Kevin L.
• Application Number:
  US09/972,477
• Publication Number:
  US 20020124143A1
• Time in Patent Office: 928 Days
• Field of Search: 711/118, 711/119, 711/141, 711/144, 711/148, 711/145
• US Class Current: 711/145
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories
• CPC Class Codes: G06F 11/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 2212/2542 Non-uniform memory access [NUMA] architecture

Abstract

Each node of a multiprocessor computer system includes a main memory, a cache memory system and logic. The main memory stores memory lines of data. A directory entry for each memory line indicates whether a copy of the corresponding memory line is stored in the cache memory system in another node. The cache memory system stores copies of memory lines and cache state information indicating whether the cached copy of each memory line is an exclusive copy. The logic of each respective node is configured to respond to a transaction request for a particular memory line and its corresponding directory entry, where the respective node is the home node of the particular memory. When the cache memory system of the home node stores an exclusive copy of the particular memory line, the logic responds to the request by sending the copy of the particular memory line retrieved from the cache memory system and a predefined null directory entry value, and thus does not retrieve the memory line and its directory entry from the main memory of the home node.

Claims

1. A multiprocessor computer system comprising a plurality of nodes, each respective node including:

a main memory storing data in a plurality of memory lines with a directory entry for each memory line;

wherein each memory line stored in the main memory of the respective node has a home node comprising the respective node;

a cache memory system storing copies of memory lines from the main memories in the plurality of nodes; and

logic;

wherein each directory entry in the main memory of each respective node indicates whether a copy of the corresponding memory line is stored in the cache memory system in another node;

wherein the cache memory system of each respective node includes, for each copy of each memory line stored in the cache memory system of the respective node, cache state information indicating whether the copy is an exclusive copy of the memory line; and

wherein the logic of each respective node is configured to respond to a transaction request for a particular memory line and its corresponding directory entry, when the cache memory system of the respective node stores a copy of the particular memory line and the cache state information indicates that the copy of the particular memory line is an exclusive copy, by retrieving the copy of the particular memory line from the cache memory system of the respective node and sending the retrieved copy and a predefined null directory entry value.

2. The system of claim 1, wherein the logic is further configured to respond to the transaction request, when the cache memory system of the respective node does not store an exclusive copy of the particular memory line, by retrieving the particular memory line and the corresponding directory entry from the main memory of the respective node and sending the retrieved particular memory line and corresponding directory entry.

3. The system of claim 1, wherein the logic is further configured to respond to a transaction request from the home node for a particular memory line and its corresponding directory entry, when the transaction request requires an exclusive copy of the particular memory line to be stored in the cache memory system of the home node, by completing the transaction request without changing the corresponding directory entry.

4. The system of claim 1, wherein the logic is further configured to respond to a read request from the home node for a particular memory line and its corresponding directory entry, when the cache memory system of the home node stores a copy of the particular memory line, by sending the copy of the particular memory line retrieved from the cache memory system and completing the read request without changing the corresponding directory entry.

5. The system of claim 1, wherein the logic is further configured to mark the cache state information to indicate that a copy of a respective memory line stored in the cache memory system of the home node of the respective memory line is an exclusive copy when the cache memory system issues a read request for the respective memory line and the corresponding directory entry for the respective memory line indicates that no cache memory system other than the cache memory system has a copy of the respective memory line, and when the cache memory system issues a write request for the respective memory line.

6. A multiprocessor computer system comprising a plurality of nodes, each respective node including:

a main memory storing data in a plurality of memory lines, each memory line having a corresponding directory entry and a combined error correction code, the combined error correction code for detecting and correcting errors in both the memory line and the directory entry for the memory line; and

a cache memory system for storing copies of memory lines from the main memories in the plurality of nodes;

wherein each directory entry in the main memory of each node indicates whether a copy of the corresponding memory line is stored in the cache memory system in another node.

7. The system of claim 6, wherein

N is an integer greater than 1;

each memory line is stored in the main memory in N sub-blocks, each memory line sub-block including a portion of the memory line data and a portion of the directory entry corresponding to the memory line; and

the combined error correction code for each memory line comprises N sub-block combined error correction codes, each sub-block combined error correction code for detecting and correcting errors in both the memory line portion and directory entry portion in a corresponding memory line sub-block.

8. The system of claim 7, wherein:

each memory line stored in the main memory of the respective node has a home node comprising the respective node;

the cache memory system of each respective node includes, for each copy of each memory line stored in the cache memory system of the respective node, cache state information indicating whether the copy is an exclusive copy of the memory line; and

each respective node further includes logic configured to respond to a transaction request for a particular memory line and its corresponding directory entry, when the cache memory system of the respective node stores a copy of the particular memory line and the cache state information indicates that the copy of the particular memory line is an exclusive copy, by retrieving the copy of the particular memory line from the cache memory system of the respective node and sending the retrieved copy and a predefined null directory entry value.

9. The system of claim 8, wherein the logic is further configured to respond to the transaction request, when the cache memory system of the respective node does not store an exclusive copy of the particular memory line, by retrieving the particular memory line and the corresponding directory entry from the main memory of the respective node and sending the retrieved particular memory line and corresponding directory entry.

10. The system of claim 8, wherein the logic is further configured to respond to a transaction request from the home node for a particular memory line and its corresponding directory entry, when the transaction request requires an exclusive copy of the particular memory line to be stored in the cache memory system of the respective node, by completing the transaction request without changing the corresponding directory entry.

11. The system of claim 8, wherein the logic is further configured to respond to a read request from the home node for a particular memory line and its corresponding directory entry, when the cache memory system of the home node stores a copy of the particular memory line, by sending the copy of the particular memory line retrieved from the cache memory system and a predefined null directory entry value and completing the read request without changing the corresponding directory entry.

12. The system of claim 8, wherein the logic is further configured to mark the cache state information to indicate that a copy of a respective memory line stored in the cache memory system of the home node is an exclusive copy when the cache memory system issues a read request for the respective memory line and the corresponding directory entry for the respective memory line indicates that no cache memory system other than the cache memory system has a copy of the respective memory line, and when the cache memory system issues a write request for the respective memory line.

13. The system of claim 7, wherein each node further includes:

read logic configured to respond to a transaction request for a specified memory line and its corresponding directory entry, the read logic including

error correction code circuitry for generating a partial error correction code for the specified memory line, based on data in the specified memory line alone without the corresponding directory entry; and

a buffer for storing the partial error correction code in the buffer; and

update logic configured to respond to a transaction completion request for the specified memory line, specifying a new directory entry for the specified memory line, the update logic configuring the error correction code circuitry to generate a new combined error correction code for the specified memory line based on the partial error correction code stored in the buffer and the new directory entry.

14. The system of claim 13, further including write circuitry for writing the new directory entry and the new combined error correction code to main memory without overwriting the specified memory line.

15. The system of claim 14, wherein the transaction completion request is a request from a remote node for a memory line for which current, non-stale, data is stored in the main memory of the respective node.

16. The system of claim 14, wherein:

each memory line stored in the main memory of the respective node has a home node comprising the respective node;

the cache memory system of each respective node includes, for each copy of each memory line stored in the cache memory system of the respective node, cache state information indicating whether the copy is an exclusive copy of the memory line; and

the read logic is further configured to respond to a transaction request for a particular memory line and its corresponding directory entry, when the cache memory system of the respective node stores a copy of the particular memory line and the cache state information indicates that the copy of the particular memory line is an exclusive copy, by retrieving the copy of the particular memory line from the cache memory system of the respective node and sending the retrieved copy and a predefined null directory entry value.

17. The system of claim 16, wherein the read logic is further configured to respond to the transaction request, when the cache memory system of the respective node does not store a copy of the particular memory line, by retrieving the particular memory line and the corresponding directory entry from the main memory of the respective node and sending the retrieved particular memory line and corresponding directory entry.

18. The system of claim 16, wherein the logic is further configured to respond to a transaction request from the home node for a particular memory line and its corresponding directory entry, when the transaction request requires an exclusive copy of the particular memory line to be stored in the cache memory system of the respective node, by completing the transaction request without changing the corresponding directory entry.

19. The system of claim 16, wherein the logic is further configured to respond to a read request from the home node for a particular memory line and its corresponding directory entry, when the cache memory system of the home node stores a copy of the particular memory line, by sending the copy of the particular memory line retrieved from the cache memory system and a predefined null directory entry value and completing the read request without changing the corresponding directory entry.

20. The system of claim 16, wherein the logic is further configured to mark the cache state information to indicate that a copy of a respective memory line stored in the cache memory system of the home node is an exclusive copy when the cache memory system issues a read request for the respective memory line and the corresponding directory entry for the respective memory line indicates that no cache memory system other than the cache memory system has a copy of the respective memory line, and when the cache memory system issues a write request for the respective memory line.

21. The system of claim 7, wherein each node further includes update logic configured to respond to a transaction completion request for a specified memory line, the transaction completion request specifying a new directory entry for the specified memory line, the update logic configuring error correction code circuitry to generate a new combined error correction code for the specified memory line based on predefined dummy data and the new directory entry when predefined stale memory criteria are satisfied.

22. The system of claim 7, wherein each node further includes:

logic for responding to a transaction request specifying a memory line;

error correction code circuitry for generating the combined error correction code for the memory line specified by the transaction request; and

update logic configured to respond to a transaction completion request for the specified memory line, specifying a new directory entry for the specified memory line, the update logic configuring the error correction code circuitry to generate a new combined error correction code for the specified memory line based on the new directory entry for the specified memory line and predefined dummy data when the transaction request renders data stored in the specified memory line stale.

23. The system of claim 22, wherein the update logic includes logic for writing the new directory entry and the new combined error correction code to the main memory.

24. The system of claim 22, wherein:

each memory line stored in the main memory of the respective node has a home node comprising the respective node;

the cache memory system of each respective node includes, for each copy of each memory line stored in the cache memory system of the respective node, cache state information indicating whether the copy is an exclusive copy of the memory line; and

each respective node further includes read logic configured to respond to a transaction request for a particular memory line and its corresponding directory entry, when the cache memory system of the respective node stores a copy of the particular memory line and the cache state information indicates that the copy of the particular memory line is an exclusive copy, by retrieving the copy of the particular memory line from the cache memory system of the respective node and sending the retrieved copy and a predefined null directory entry value.

25. The system of claim 24, wherein the read logic is further configured to respond to the transaction request, when the cache memory system of the respective node does not store a copy of the particular memory line, by retrieving the particular memory line and the corresponding directory entry from the main memory of the respective node and sending the retrieved particular memory line and corresponding directory entry.

26. The system of claim 24, wherein the logic is further configured to respond to a transaction request from the home node for a particular memory line and its corresponding directory entry, when the transaction request requires an exclusive copy of the particular memory line to be stored in the cache memory system of the respective node, by completing the transaction request without changing the corresponding directory entry.

27. The system of claim 24, wherein the logic is further configured to respond to a read request from the home node for a particular memory line and its corresponding directory entry, when the cache memory system of the home node stores a copy of the particular memory line, by sending the copy of the particular memory line retrieved from the cache memory system and a predefined null directory entry value and completing the read request without changing the corresponding directory entry.

28. The system of claim 24, wherein the logic is further configured to mark the cache state information to indicate that a copy of a respective memory line stored in the cache memory system of the home node is an exclusive copy when the cache memory system issues a read request for the respective memory line and the corresponding directory entry for the respective memory line indicates that no cache memory system other than the cache memory system has a copy of the respective memory line, and when the cache memory system issues a write request for the respective memory line.

29. The system of claim 7, wherein each node further includes:

read logic configured to respond to a transaction request for a specified memory line and its corresponding directory entry, the read logic including

error correction code circuitry for generating a partial error correction code for the specified memory line, based on data in the specified memory line alone without the corresponding directory entry; and

a buffer for storing the partial error correction code in the buffer; and

update logic configured to respond to a transaction completion request for the specified memory line, the transaction completion request specifying a new directory entry for the specified memory line;

wherein

the update logic configures the error correction code circuitry to generate a new combined error correction code for the specified memory line based on the partial error correction code stored in the buffer and the new directory entry when a first set of predefined criteria are satisfied; and

the update logic configures the error correction code circuitry to generate a new combined error correction code for the specified memory line based on the predefined dummy data and the new directory entry when a second set of predefined criteria are satisfied.

30. The system of claim 29, further including write back circuitry for writing the new directory entry and the new combined error correction code to main memory without overwriting the specified memory line when first set of predefined criteria are satisfied and when the second set of predefined criteria are satisfied.

31. The system of claim 29, wherein:

each memory line stored in the main memory of the respective node has a home node comprising the respective node;

the cache memory system of each respective node includes, for each copy of each memory line stored in the cache memory system of the respective node, cache state information indicating whether the copy is an exclusive copy of the memory line; and

the read logic is further configured to respond to a transaction request for a particular memory line and its corresponding directory entry, when the cache memory system of the respective node stores a copy of the particular memory line and the cache state information indicates that the copy of the particular memory line is an exclusive copy, by retrieving the copy of the particular memory line from the cache memory system of the respective node and sending the retrieved copy and a predefined null directory entry value.

32. The system of claim 31, wherein the read logic is further configured to respond to the transaction request, when the cache memory system of the respective node does not store a copy of the particular memory line, by retrieving the particular memory line and the corresponding directory entry from the main memory of the respective node and sending the retrieved particular memory line and corresponding directory entry.

33. The system of claim 31, wherein the logic is further configured to respond to a transaction request from the home node for a particular memory line and its corresponding directory entry, when the transaction request requires an exclusive copy of the particular memory line to be stored in the cache memory system of the home node, by completing the transaction request without changing the corresponding directory entry.

34. The system of claim 31, wherein the logic is further configured to respond to a read request from the home node for a particular memory line and its corresponding directory entry, when the cache memory system of the home node stores a copy of the particular memory line, by sending the copy of the particular memory line retrieved from the cache memory system and a predefined null directory entry value and completing the read request without changing the corresponding directory entry.

35. The system of claim 31, wherein the logic is further configured to mark the cache state information to indicate that a copy of a respective memory line stored in the cache memory system of the home node is an exclusive copy when the cache memory system issues a read request for the respective memory line and the corresponding directory entry for the respective memory line indicates that no cache memory system other than the cache memory system has a copy of the respective memory line, and when the cache memory system issues a write request for the respective memory line.

36. The system of claim 7, wherein each directory entry includes directory state information and each sub-block of each memory line includes a copy of the directory state information.

37. The system of claim 36, wherein:

each memory line stored in the main memory of the respective node has a home node comprising the respective node;

the cache memory system of each respective node includes, for each copy of each memory line stored in the cache memory system of the respective node, cache state information indicating whether the copy is an exclusive copy of the memory line; and

the read logic is further configured to respond to a transaction request for a particular memory line and its corresponding directory entry, when the cache memory system of the respective node stores a copy of the particular memory line and the cache state information indicates that the copy of the particular memory line is an exclusive copy, by retrieving the copy of the particular memory line from the cache memory system of the respective node and sending the retrieved copy and a predefined null directory entry value.

38. The system of claim 37, wherein the read logic is further configured to respond to the transaction request, when the cache memory system of the respective node does not store a copy of the particular memory line, by retrieving the particular memory line and the corresponding directory entry from the main memory of the respective node and sending the retrieved particular memory line and corresponding directory entry.

39. The system of claim 37, wherein the update logic is further configured to respond to a transaction request from the home node for a particular memory line and its corresponding directory entry, when the transaction request requires an exclusive copy of the particular memory line to be stored in the cache memory system of the respective node, by completing the transaction request without changing the corresponding directory entry.

40. The system of claim 37, wherein the logic is further configured to respond to a read request from the home node for a particular memory line and its corresponding directory entry, when the cache memory system of the home node stores a copy of the particular memory line, by sending the copy of the particular memory line retrieved from the cache memory system and a predefined null directory entry value and completing the read request without changing the corresponding directory entry.

41. The system of claim 37, wherein the logic is further configured to mark the cache state information to indicate that a copy of a respective memory line stored in the cache memory system of the home node is an exclusive copy when the cache memory system issues a read request for the respective memory line and the corresponding directory entry for the respective memory line indicates that no cache memory system other than the cache memory system has a copy of the respective memory line, and when the cache memory system issues a write request for the respective memory line.

42. A method for maintaining cache coherence in a multiprocessor computer system, the multiprocessor computer system having a plurality of nodes, comprising:

storing, in a main memory of a respective node of the plurality of nodes, data in a plurality of memory lines of the main memory;

wherein each memory line in the main memory of the respective node has a home node comprising the respective node;

storing, in a directory entry corresponding to each respective memory line of the plurality of memory lines in the main memory of the respective node, directory information indicating nodes, other than the respective node, where copies of the respective memory line are stored in cache memory systems;

when a copy of the respective memory line is stored in a cache memory system of the respective node, storing, in the cache memory system of the respective node, cache state information indicating whether the copy is an exclusive copy of the respective memory line; and

at the respective node, responding to a transaction request for a particular memory line and its corresponding directory entry, when the cache memory system of the respective node stores a copy of the particular memory line and the cache state information indicates that the copy of the particular memory line is an exclusive copy, by retrieving the copy of the particular memory line from the cache memory system of the respective node and sending the retrieved copy and a predefined null directory entry value.

43. The method of claim 42, further comprising responding to the transaction request, when the cache memory system of the respective node does not store an exclusive copy of the particular memory line, by retrieving the particular memory line and the corresponding directory entry from the main memory of the respective node and sending the retrieved particular memory line and corresponding directory entry.

44. The method of claim 42, further comprising responding to a transaction request from the home node for a particular memory line and its corresponding directory entry, when the transaction request requires an exclusive copy of the particular memory line to be stored in the cache memory system of the node, by completing the transaction request without changing the corresponding directory entry.

45. The method of claim 43, further comprising responding to a read request from the node for a particular memory line and its corresponding directory entry, when the cache memory system of the node stores a copy of the particular memory line, by sending the copy of the particular memory line retrieved from the cache memory system and a predefined null directory entry value and completing the read request without changing the corresponding directory entry.

46. The method of claim 43, further comprising responding to a read request from the home node for a particular memory line and its corresponding directory entry, when the cache memory system of the home node stores a copy of the particular memory line, by sending the copy of the particular memory line retrieved from the cache memory system and completing the read request without changing the corresponding directory entry.

47. The method of claim 43, further comprising marking the cache state information to indicate that a copy of a respective memory line stored in the cache memory system of the home node of the respective memory line is an exclusive copy when the cache memory system issues a read request for the respective memory line and the corresponding directory entry for the respective memory line indicates that no cache memory system other than the cache memory system has a copy of the respective memory line, and when the cache memory system issues a write request for the respective memory line.

48. A method for maintaining cache coherence in a multiprocessor computer system, wherein the multiprocessor computer system includes a plurality of nodes, comprising:

storing, in a main memory of a respective node of the plurality of nodes, data in a plurality of memory lines of the main memory;

wherein each memory line in the main memory of the respective node has a home node comprising the respective node;

storing, in a directory entry corresponding to each respective memory line of the plurality of memory lines in the main memory of the respective node, directory information indicating nodes, other than the respective node, where copies of the respective memory line are stored in cache memory systems;

storing, for each respective memory line of the plurality of memory line in the main memory of the respective node, a combined error correction code, the combined error correction code for detecting and correcting errors in both the respective memory line and the corresponding directory entry; and

detecting and correcting errors in both a respective memory line and the corresponding directory entry using the combined error correction code for the respective memory line.

49. The method of claim 48, wherein

N is an integer greater than 1;

each respective memory line is stored in the main memory in N sub-blocks, each memory line sub-block including a portion of the respective memory line data and a portion of the directory entry corresponding to the respective memory line;

the combined error correction code for each respective memory line comprises N sub-block combined error correction codes, each sub-block combined error correction code for detecting and correcting errors in both the memory line portion and directory entry portion in a corresponding memory line sub-block; and

the detecting and correcting includes detecting and correcting errors in both the memory line portion and the corresponding directory entry portion of a memory line sub-block using the sub-block combined error correction code corresponding to the memory line sub-block.

50. The method of claim 49, the directory entry storing including:

storing, in the directory entry portion of each memory line sub-block for a respective memory line, an identical copy of directory state information indicating a directory state of the directory entry corresponding to the respective memory line.

51. The method of claim 48, further comprising:

at a respective node of the multiprocessor computer system, responding to a transaction request for a specified memory line and its corresponding directory entry by;

generating a partial error correction code for the memory line based on data in the specified memory line without its corresponding directory entry;

storing the partial error correction code; and

responding to a transaction completion request for the specified memory line by;

specifying a new directory entry for the specified memory line; and

generating a new combined error correction code for the memory line based on the partial error correction code and the new directory entry.

52. The method of claim 48, further comprising

at a respective node of the multiprocessor computer system, responding to a transaction completion request for a specified memory line by:

specifying a new directory entry for the specified memory line; and

generating a new combined error correction code for the specified memory line based on predefined dummy data and the new directory entry.