Proximity-based memory allocation in a distributed memory system

• US 8,150,946 B2
• Filed: 04/21/2006
• Issued: 04/03/2012
• Est. Priority Date: 04/21/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Wu, Yuguang, Vick, Christopher A., Paleczny, Michael H., Yang, Bo, Manczak, Olaf, Freeman, Jay R., Gustafson, Phyllis E., Moreno, Miguel-Angel Lujan
• Primary Examiner(s): NGUYEN, THU HA T
• Application Number:
  US11/409,205
• Publication Number:
  US 20070250604A1
• Time in Patent Office: 2,174 Days
• Field of Search: 709/220, 709/214, 709/223, 709/224, 370/254, 370/256
• US Class Current: 709/220
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: H04L 12/00 Data switching networks interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units G06F13/00
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

A system and method for allocating the nearest available physical memory in a distributed, shared memory system. In various embodiments, a processor node may broadcast a memory request to a first subset of nodes connected to it via a communication network. In some embodiments, if none of these nodes is able to satisfy the request, the processor node may broadcast the request to additional subsets of nodes. In some embodiments, each node of the first subset of nodes may be removed from the processor node by one network hop and each node of the additional subsets of nodes may be removed from the processor node by no more than an iteratively increasing number of network hops. In some embodiments, the processor node may send an acknowledgment to one node that can fulfill the request and a negative acknowledgement to other nodes that can fulfill the request.

Claims

1. A system, comprising:

a processor node comprising a processor and a network interface;

a plurality of memory nodes, wherein each memory node comprises a memory and a network interface;

a communication network configured to interconnect said processor node and said plurality of memory nodes via said network interfaces according to a network topology, wherein each of said memory nodes is removed from said processor node by a respective number of network hops according to said network topology;

wherein said processor node is configured to;

broadcast a packet comprising a memory request to a first subset of said plurality of memory nodes, wherein each memory node of said first subset of memory nodes is removed from said processor node by no more than a given number of network hops;

determine whether one or more of said first subset of memory nodes has sent a reply to said processor node indicating that it can satisfy said memory request; and

in response to determining that no memory node of said first subset of memory nodes has sent a reply to said processor node indicating that it can satisfy said memory request;

increase said given number of network hops; and

broadcast a packet comprising said memory request to a second subset of said plurality of memory nodes, wherein each memory node of said second subset of memory nodes is removed from said processor node by no more than said increased given number of network hops.

2. The system of claim 1, wherein said processor node is further configured to:

determine whether one or more of said second subset of memory nodes has sent a reply to said processor node indicating that it can satisfy said memory request; and

in response to determining that no memory node of said second subset of memory nodes has sent a reply to said processor node indicating that it can satisfy said memory request, continue to increase said given number of network hops and to broadcast a packet comprising said memory request to a corresponding subset of said plurality of memory nodes, wherein each memory node of said corresponding subset of memory nodes is removed from said processor node by no more than said increased given number of network hops, until at least one of the following occurs;

one or more of said plurality of memory nodes indicates that it can satisfy said memory request in response to receiving a packet comprising said memory request, said processor node has broadcast a packet comprising said memory request to each of said plurality of memory nodes, or a time-out condition has been met.

3. The system of claim 1, wherein said processor node is one of a plurality of processor nodes, wherein each of said plurality of processor nodes comprises a processor and a network interface, and wherein each of said plurality of processor nodes is coupled to said communication network via said network interfaces according to said network topology.

4. The system of claim 3, wherein at least one of said plurality of processor nodes further comprises a memory.

5. The system of claim 1, wherein said network topology comprises one or more of:

a linear topology, a hierarchical tree topology, a star topology, a mesh topology, a grid topology, a ring topology, a toroidal topology, a cube topology or a hypercube topology.

6. The system of claim 1, wherein said given number of network hops is one.

7. The system of claim 1, wherein said increasing said given number of network hops comprises adding one to said given number of network hops.

8. The system of claim 1, wherein said memory request comprises a requested memory size, a request identifier, and a time-to-live indicator.

9. The system of claim 8, wherein a particular one of the plurality of memory nodes is configured to:

receive said memory request; and

if it is able to satisfy said memory request;

reserve a portion of memory at least as large as the requested memory size; and

send a reply to said processor node to indicate that the particular one of the plurality of memory nodes can satisfy said memory request, wherein the reply comprises the request identifier.

10. The system of claim 1, wherein said processor node is further configured to send an acknowledgement to a particular one of the plurality of memory nodes in response to receiving a reply from said particular one of the plurality of memory nodes indicating that it can satisfy said memory request.

11. The system of claim 1, wherein, in response to receiving replies from each of two or more of said plurality of memory nodes indicating that it can satisfy said memory request, said processor node is further configured to:

select a particular one of said two or more memory nodes;

send an acknowledgement to said particular memory node; and

send a negative acknowledgement to each of said two or more memory nodes other than said particular memory node.

12. A method, comprising:

a processor node broadcasting a packet comprising a memory request to a first subset of a plurality of memory nodes, wherein said plurality of memory nodes and said processor node are interconnected via a communication network according to a network topology, and wherein each memory node of said first subset of memory nodes is removed from said processor node by no more than a given number of network hops according to said network topology; and

in response to determining that none of the memory nodes of said first subset of memory nodes has sent a reply to said processor node indicating that it can satisfy said memory request, said processor node;

increasing said given number of network hops; and

broadcasting a packet comprising said memory request to a second subset of said plurality of memory nodes, wherein each memory node of said second subset of memory nodes is removed from said processor node by no more than said increased given number of network hops.

13. The method of claim 12, wherein said given number of network hops is one.

14. The method of claim 12, wherein said increasing said given number of network hops comprises adding one to said given number of network hops.

15. The method of claim 12, wherein said memory request comprises a requested memory size, a request identifier, and a time-to-live indicator.

16. The method of claim 12, further comprising:

a particular one of said plurality of memory nodes indicating that it can satisfy said memory request in response to receiving said memory request; and

said processor node sending an acknowledgement to the particular memory node.

17. The method of claim 12, further comprising:

each of two or more of said plurality of memory nodes indicating that it can satisfy said memory request in response to receiving said memory request;

said processor node selecting a particular one of said two or more memory nodes;

said processor node sending an acknowledgement to said particular memory node; and

said processor node sending a negative acknowledgement to each of said two or more memory nodes other than said particular memory node.

18. A processor node, comprising:

a processor;

an input/output interface through which said processor communicates with a communication network, wherein said communication network is configured to interconnect a plurality of memory nodes according to a network topology; and

execution logic configured to broadcast a packet comprising a memory request to a first subset of said plurality of memory nodes, wherein each memory node of said first subset of memory nodes is removed from said processor node by no more than a given number of network hops, and wherein the execution logic comprises one or more electronic circuits; and

wherein, in response to timing out rather than receiving a reply from a memory node of said first subset of memory nodes indicating that it can satisfy said memory request, said execution logic is further configured to;

increase said given number of network hops; and

broadcast a packet comprising said memory request to a second subset of said plurality of memory nodes, wherein each memory node of said second subset of memory nodes is removed from said processor node by no more than said increased given number of network hops.

19. The processor node of claim 18, wherein, in response to a particular one of the plurality of memory nodes indicating that it can satisfy said memory request in response to receiving said memory request, said execution logic is further configured to send an acknowledgement to the particular memory node.

20. The processor node of claim 19, wherein, in response to each of two or more of said plurality of memory nodes indicating that it can satisfy said memory request in response to receiving said memory request, said execution logic is further configured to:

select a particular one of said two or more memory nodes;

send an acknowledgement to said particular memory node; and

send a negative acknowledgement to each of said two or more memory nodes other than said particular memory node.