Method and system for cache coherence in DSM multiprocessor system without growth of the sharing vector

• US 6,877,030 B2
• Filed: 02/28/2002
• Issued: 04/05/2005
• Est. Priority Date: 02/28/2002
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Deneroff, Martin M.
• Primary Examiner(s): KIM, HONG CHONG
• Application Number:
  US10/084,088
• Publication Number:
  US 20030163543A1
• Time in Patent Office: 1,132 Days
• Field of Search: 709/213, 709/214, 709/216, 709/217, 711/147, 711/141, 711/148, 711/152, 711/153, 711/154, 711/144, 711/145, 712/28, 707/10
• US Class Current: 709/213
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers

Abstract

The present invention is directed to a method and a system for maintaining cache coherence in a distributed shared memory (DSM) multiprocessor system. The method begins with a receiving of a shared access request by a receiving node, where the receiving node is an arbitrary node having at least one main memory unit containing information desired to be accessed. Then, the method determines whether the shared access request originates from a local node or from a remote node. When the shared access request originates from a local node, the shared access request is processed as a shared access request. If the shared access request is granted, a sharing vector is generated or updated to reflect the sharing local node(s). When the shared access request originates from a remote node, the shared access request is converted to an exclusive access request and the sharing vector is replaced with a pointer to the requesting remote node. This limits the potential size of the sharing vector according to the local nodes.

Claims

1. A method for cache coherence in a distributed shared memory (DSM) multiprocessor system comprising:

(1) receiving a shared access request for information;

(2) determining whether the shared access request originates from a local node or from a remote node;

(3) processing the shared access request as an exclusive access request when the shared access request originates from the remote node; and

(4) processing the shared access request when the shared access request originates from the local node.

2. The method of claim 1, wherein said step of determining whether the shared access request originates from the local node or the remote node further comprises determining a memory location where the information is stored.

3. The method of claim 1, wherein said step of processing the shared access request as an exclusive access request further comprises transmitting an invalidate instruction to other local or remote nodes to eliminate copies of the requested information from other local or remote nodes.

4. The method of claim 1, wherein said step of determining whether the shared access request originates from the local node or the remote node further comprises comparing upper bits of an address of a shared access requestor with upper bits of an address of a receiving node.

5. The method of claim 4, wherein said step of processing the shared access request as the exclusive access request further comprises converting the shared access request to the exclusive access request if the upper bits of the address of the shared access requestor match the upper bits of the address of the receiving node.

6. The method of claim 1, wherein said step of determining whether the shared access request originates from the local node or the remote node further comprises comparing an address of a shared access requestor with a table of addresses stored by a receiving node.

7. The method of claim 6, wherein said step of processing the shared access request as the exclusive access request further comprises converting the shared access request to the exclusive access request if the address of the shared access requestor matches at least one address in the table of addresses stored by the receiving node.

8. The method of claim 1, wherein the method further comprises:

(5) eliminating copies of the requested information from other local or remote nodes when the shared access request is converted to the exclusive access request;

(6) storing a pointer to a shared access requestor, a location associated with the shared access request or where the requested information is cached, when the shared access request is remotely originated;

(7) determining whether the shared access request is valid;

(8) terminating an exclusive access when the exclusive access request is no longer valid; and

(9) returning information requested by the shared access request to cache.

9. The method of claim 1, wherein a shared access request from a remote node has been processed as an exclusive access request, the method further comprising:

(5) receiving a subsequent shared access request from the local node at a receiving node;

(6) transmitting an invalidate instruction from the receiving node to the remote node, when the local node transmits the shared access request;

(7) terminating an exclusive access of the remote node; and

(8) processing the shared access request of the local node as the exclusive access request.

10. The method of claim 9, wherein step (6) further comprises comparing upper bits of an address of a shared access requestor of the local node with upper bits of the address of the receiving node.

11. The method of claim 10, wherein step (8) further comprises converting the shared access request of the local node to the exclusive access request if the upper bits of the address of the shared access requestor of the local node match the upper bits of the address of the receiving node.

12. The method of claim 9, wherein step (6) of transmitting another invalidate instruction further comprises comparing upper bits of an address of the shared access request of the local node with a table of addresses stored by the receiving node.

13. The method of claim 12, wherein step (8) further comprises converting the shared access request of the local node to the exclusive access request if the address of the shared access request of the local node matches at least one address in the table of addresses stored by the receiving node.

14. The method of claim 9, wherein the method further comprises:

(9) storing a pointer to the shared access requestor of the local node;

(10) determining whether the shared access request of the local node is valid;

(11) terminating the exclusive access request of the local node when the exclusive access request is no longer valid; and

,

(12) returning information requested by the shared access request of the local node to cache.

15. A method for cache coherence in a distributed shared memory (DSM) multiprocessor system having a directory-based protocol comprising:

(1) receiving a shared access request for information by a receiving node;

(2) determining whether the shared access request originates from a local node or from a remote node;

(3) processing the shared access request as an exclusive access request when the shared access request originates from the remote node;

(4) processing the shared access request when the shared access request originates from the local node;

(5) transmitting an invalidate instruction to other local or remote nodes to eliminate copies of the requested information from the other local or remote nodes;

(6) eliminating copies of the requested information from other local or remote nodes once the shared access request is converted to the exclusive access request;

(7) storing a pointer to a shared access requestor when the shared access request is remotely originated;

(8) determining whether the shared access request is valid;

(9) terminating an exclusive status when the exclusive access request is no longer valid; and

(10) returning information requested by the shared access request to cache.

16. The method of claim 15, wherein step (2) further comprises comparing upper bits of an address of the shared access requestor with upper bits of an address of the receiving node.

17. The method of claim 16, wherein step (3) further comprises converting the shared access request to the exclusive access request if the upper bits of the address of the shared access requestor match the upper bits of the address of the receiving node.

18. The method of claim 15, wherein step (2) further comprises comparing address of the shared access requestor with a table of addresses stored by the receiving node.

19. The method of claim 18, wherein step (3) further comprises converting the shared access request to the exclusive access request if the address of the shared access requestor matches at least one address in the table of addresses stored by the receiving node.

20. The method of claim 15, wherein the method further comprises:

(11) receiving a shared access request from the local node;

(12) transmitting an invalidate instruction from the receiving node to the remote node, when the local node transmits the shared access request;

(13) terminating the exclusive access of the remote node;

(14) processing the shared access request of the local node as the exclusive access request.

21. The method of claim 20, wherein step (12) further comprises comparing upper bits of an address of the shared access requestor of the local node with upper bits of the address of the receiving node.

22. The method of claim 21, wherein step (14) further comprises converting the shared access request of the local node to the exclusive access request if the upper bits of the address of the shared access requestor of the local node match the upper bits of the address of the receiving node.

23. The method of claim 20, wherein step (12) further comprises comparing upper bits of an address of the shared access requestor of the local node with a table of addresses stored by the receiving node.

24. The method of claim 23, wherein step (14) further comprises converting the shared access requestor of the local node to the exclusive access request if the address of the shared access requestor of the local node matches at least one address in the table of addresses stored by the receiving node.

25. The method of claim 20, wherein the method further comprises:

(15) storing a pointer to the shared access requestor of the local node;

(16) determining whether the shared access request of the local node is valid;

(17) terminating an exclusive access of the local node when the exclusive access request is no longer valid; and

,

(18) returning information requested by the shared access request of the local node to cache.

26. A method for cache coherence in a distributed shared memory (DSM) multiprocessor system comprising:

(1) receiving a first shared access request by a receiving node, wherein the receiving node contains shared information;

(2) receiving a second shared access request by the receiving node;

(3) processing one of a first and a second shared access requestor as an exclusive access request; and

(4) transmitting an invalidate instruction to other of the first and the second shared access requestor.

27. The method of claim 26, wherein step (3) further comprises

(5) determining whether one of the first and the second shared access requestor originates from a local node or a remote node;

(6) processing the first shared access requestor as the exclusive access request when the first shared access request originates from the remote node;

(7) transmitting the invalidate instruction to the second shared access requestor.

28. The method of claim 26, wherein step (3) further comprises:

(5) determining whether one of the first and the second shared access requestors originates from a local node or a remote node;

(6) processing the second shared access request as the exclusive access request when the first shared access request originates from the remote node;

(7) transmitting the invalidate instruction to the first shared access requestor.

29. The method of claim 26, wherein the method further comprises processing as the shared access request to one of the first and the second shared access request when the other of the first and the second shared access originates from a local node.

30. The method of claim 26, wherein the method further comprises invalidating an exclusive access of one of the first and the second shared access request originating from a remote node when the other of the first and the second shared access request originates from a local node.

31. The method of claim 30, wherein said invalidating step further comprises:

(5) comparing upper bits of an address of one of the first and the second access requestors with upper bits of the address of the receiving node;

(6) processing one of the first and the second shared access request as the exclusive access request if the upper bits of the address of one of the first and the second shared access requestors match the upper bits of the address of the receiving node.

32. The method of claim 30, wherein said invalidating step further comprises:

(5) comparing upper bits of an address of one of the first and the second access requestors with a table of addresses stored by the receiving node;

(6) processing one of the first and the second shared access request as the exclusive access request if the upper bits of the address of one of the first and the second shared access requestors match the table of addresses stored by the receiving node.

33. The method of claim 32, wherein the method further comprises:

(7) storing a pointer to one of the first and the second shared access requestors;

(8) determining whether the one of the first and the second shared access request is valid;

(9) terminating an exclusive access of one of the first and the second shared access requestors when one of the first and the second shared access request is no longer valid; and

,

(10) returning information requested by one of the first and the second shared access requestors to cache.

34. A system for maintaining cache coherency in a distributed shared memory (DSM) multiprocessor systems, comprising:

a plurality of processing nodes, wherein each said node is attached to at least one central processing unit (CPU) and a memory unit;

at least one receiving node for receiving a shared access request;

a means for determining whether said shared access request originates from said local node or from said remote node;

a plurality of shared memory vectors, wherein each said shared memory vector defines either said local node requesting information sharing from said receiving node or said remote node requesting information sharing from said receiving node;

an exclusive memory access pointer, wherein said exclusive memory access pointer points to said remote node in the DSM multiprocessor system that has been granted an exclusive access to information in said receiving node;

a storage unit for storing said exclusive memory access pointer; and

,

a deleting means for eliminating said exclusive memory access pointer, when said exclusive memory access pointer becomes invalid.

35. The system of claim 34, wherein the system operates using directory-based protocol environment.

36. The system of claim 34, wherein said deleting means further comprises a means for transmitting of an invalidate instruction to other said processing nodes once said exclusive memory access pointer points to said remote node in the DSM multiprocessor system.

37. The system of claim 34, wherein the system further comprises a means for transmitting another invalidate instruction to said remote node when said receiving node has received said shared access request from said local node, whereby an address of said local node matches an address of said receiving node.

38. A system for maintaining cache coherency using a directory-based protocol environment in a distributed shared memory (DSM) multiprocessor systems, comprising:

a plurality of processing nodes, wherein each said node is attached to at least one central processing unit (CPU) and a memory unit;

at least one receiving node for receiving a shared access request;

a means for determining whether said shared access request originates from said local node or from said remote node;

a plurality of shared memory vectors, wherein each said shared memory vector defines either said local node requesting information sharing from said receiving node or said remote node requesting information sharing from said receiving node;

an exclusive memory access pointer, wherein said exclusive memory access pointer points to said remote node in the DSM multiprocessor system that has been granted an exclusive access to information in said receiving node;

a means for transmitting an invalidate instruction to other said processing nodes once said exclusive memory access pointer points to said remote node in the DSM multiprocessor system;

a storage unit for storing said exclusive memory access pointer; and

,

a deleting means for eliminating said exclusive memory access pointer, when said exclusive memory access pointer becomes invalid.

39. A system for maintaining cache coherency using a directory-based protocol environment in a distributed shared memory (DSM) multiprocessor systems, comprising:

a means for receiving a shared access request for information;

a means for determining whether the shared access request originates from a local node or from a remote node;

a means for processing the shared access request as an exclusive access request when the shared access request originates from the remote node;

a means for processing the shared access request when the shared access request originates from the local node.

40. A system for maintaining cache coherency using a directory-based protocol environment in a distributed shared memory (DSM) multiprocessor systems, comprising:

a means for receiving a shared access request for information by a receiving node;

a means for determining whether the shared access request originates from a local node or from a remote node, wherein said local node is physically proximate to said receiving node, wherein said remote node is physically distant from said receiving node;

a means for processing said access request differently depending on whether said access request originates from said local node or from said remote node.

41. A computer program product comprising a computer useable medium having computer logic stored therein, said computer program logic enabling a computer system to maintain cache coherency in a distributed shared memory (DSM) system, wherein said computer program logic comprises:

a first function that enables the computer to receive a shared access request for information;

a second function that enables the computer to determine whether the shared access request originates from a local node or from a remote node;

a third function that enables the computer to process the shared access request as an exclusive access request when the shared access request originates from the remote node; and

a fourth function that enables the computer to process the shared access request when the shared access request originates from the local node.