US 6,249,802 B1 · Method, system, and computer program product for allocating physical memory in a distributed shared memory network

Abstract

A method, system, and computer program product for allocating physical memory in a distributed shared memory (DSM) network is provided. Global geometry data is stored that defines a global geometry of nodes in the DSM network. The global geometry data includes node-node distance data and node-resource affinity data. The node-node distance data defines network distances between the nodes for the global geometry of the DSM network. The node-resource affinity data defines resources associated with the nodes in the global geometry of the DSM network. A physical memory allocator searches for a set of nodes in the DSM network that fulfills a memory configuration request based on the global geometry data. The memory configuration request can have parameters that define at least one of a requested geometry, memory amount, and resource affinity. The physical memory allocator in an operating system searches the global geometry data for a set of the nodes within the DSM network that fulfill the memory configuration request and minimize network latency and/or bandwidth. During the search, each node can be evaluated to ensure that the node has sufficient available memory amount and resource affinity. The physical memory allocator can begin a search at locations which are determined based on CPU load, actual memory usage or pseudo-randomly. Faster search algorithms can be used by approximating the DSM network by Boolean cubes.

Claims42

Dependent claims

A computer program product comprising a computer useable medium having computer program logic recorded thereon for enabling a processor to allocate physical memory in a distributed shared memory (DSM) system, the DSM system having a plurality of nodes coupled by an interconnection network, each node having one or more local processors and a local memory, said computer program logic comprising:

means for enabling the processor to store global geometry data that defines a global geometry of the nodes in the DSM network;
means for enabling the processor to receive a memory configuration request having parameters that define at least one of a geometry, memory amount, and resource affinity;
and
means for enabling the processor to search for a set of the nodes in the DSM network that fulfills said memory configuration request based on said global geometry data, including means for enabling the processor to search for a set of the nodes in the DSM network representing a solution that minimizes the following expression:
α ⁢ ⁢ ∑ i = 0 n - 1 ⁢ ∑ j = 0 n - 1 ⁢ [LeftBracketingBar] G P i ⁢ P j - g ij [RightBracketingBar] 2 + ( 1 - α ) ⁢ ∑ j = 0 m - 1 ⁢ [LeftBracketingBar] G a i ⁢ P b j [RightBracketingBar] 2
over a subset of nodes {P0, P1, . . . , Pn−1}, which can range over combinations of N memory nodes selected n at a time;
where N is the number of nodes in the global geometry data G;
n is the number of nodes in a geometry g specified in the memory configuration request, m is the number of nodes having a resource affinity in the global geometry, and α is a weighting factor;
whereby physical memory address space can be distributed across said set of nodes in the DSM network in accordance with said memory configuration request.

6 more elements

A method for allocating physical memory in a distributed shared memory (DSM) system, the DSM system having a plurality of nodes coupled by an interconnection network, each node having one or more local processors and a local memory, the method comprising the steps of:

(a) storing global geometry data that defines a global geometry of the nodes in the DSM network;
(b) receiving a memory configuration request having parameters that define at least one of a geometry, memory amount, and resource affinity;
and
(c) searching for a set of the nodes in the DSM network that fulfills the memory configuration request based on the global geometry data, comprising the step of searching for a set of the nodes in the DSM network representing a solution that minimizes the following expression:
α ⁢ ⁢ ∑ i = 0 n - 1 ⁢ ∑ j = 0 n - 1 ⁢ [LeftBracketingBar] G P i ⁢ P j - g ij [RightBracketingBar] 2 + ( 1 - α ) ⁢ ∑ j = 0 m - 1 ⁢ [LeftBracketingBar] G a i ⁢ P b j [RightBracketingBar] 2
over a subset of nodes {P0, P1, . . . , Pn−1}, which can range over combinations of N memory nodes selected n at a time;
where N is the number of nodes in the global geometry data G;
n is the number of nodes in a geometry g specified in the memory configuration request, m is the number of nodes having a resource affinity in the global geometry, and α is a weighting factor;
whereby, physical memory address space can be distributed across the set of nodes in accordance with the memory configuration request.

6 more elements

A system for allocating physical memory in a distributed shared memory (DSM) system, the DSM system having a plurality of nodes coupled by an interconnection network, each node having one or more local processors and a local memory, the system comprising:

storing means for storing global geometry data that defines a global geometry of the nodes in the DSM network;
receiving means for receiving a memory configuration request having parameters that define at least one of a geometry, memory amount, and resource affinity;
and
searching means for searching for a set of the nodes in the DSM network that fulfills the memory configuration request based on the global geometry data, said searching means searching for a set of the nodes in the DSM network representing a solution that minimizes the following expression:
α ⁢ ⁢ ∑ i = 0 n - 1 ⁢ ∑ j = 0 n - 1 ⁢ [LeftBracketingBar] G P i ⁢ P j - g ij [RightBracketingBar] 2 + ( 1 - α ) ⁢ ∑ j = 0 m - 1 ⁢ [LeftBracketingBar] G a i ⁢ P b j [RightBracketingBar] 2
over a subset of nodes {P0, P1, . . . , Pn−1}, which can range over combinations of N memory nodes selected n at a time;
where N is the number of nodes in the global geometry data G;
n is the number of nodes in a geometry g specified in the memory configuration request, m is the number of nodes having a resource affinity in the global geometry, and α is a weighting factor;
whereby physical memory address space can be distributed across the set of nodes in the DSM network in accordance with the memory configuration request.

6 more elements

Dependencies are inferred from the claim text.

Method, system, and computer program product for allocating physical memory in a distributed shared memory network

Life of this patent

Method, system, and computer program product for allocating physical memory in a distributed shared memory network

Life of this patent

Abstract

Claims42