Electrical computers and digital processing systems: multicomput – Miscellaneous
Reexamination Certificate
1997-09-19
2001-06-19
Rinehart, Mark H. (Department: 2152)
Electrical computers and digital processing systems: multicomput
Miscellaneous
C709S213000, C709S214000, C709S216000, C709S220000, C709S226000, C709S235000
Reexamination Certificate
active
06249802
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to multiprocessor systems.
2. Related Art
Centralized shared-memory multiprocessor systems, such as, CHALLENGE™ and POWER CHALLENGE™ systems manufactured by Silicon Graphics, Inc., use a common bus to link multiple processors and a single shared memory. Contention for bus bandwidth and memory access can limit the number of processors (also called the CPU count) which can effectively share a common bus. The size of a single shared memory also limits the ability to scale a centralized-shared-memory multiprocessor system to higher CPU counts.
A distributed shared memory (DSM) architecture, such as, a scalable shared-memory system or a non-uniform memory access (NUMA) system, typically includes a plurality of physically distinct and separated processing nodes each having one or more processors, input/output devices and main memory that can be accessed by any of the processors. The main memory is physically distributed among the processing nodes. In other words, each processing node includes a portion of the main memory. Thus, each processor has access to “local” main memory (i.e., the portion of main memory that resides in the same processing node as the processor) and “remote” main memory (i.e., the portion of main memory that resides in other processing nodes). For each processor in a distributed shared memory system, the latency associated with accessing a local main memory is significantly less than the latency and/or bandwidth associated with accessing a remote main memory. See D. Lenoski and W. Weber,
Scalable Shared
-
Memory Multi
-
Processing
, Morgan-Kaufmann Publ., U.S.A. (1995), pp. 1-40, 87-95, 143-203, and 311-316, and Hennessy and Patterson,
Computer Architecture: A Quantitative Approach
, Second Edition, Morgan-Kaufmann Publ., U.S.A. (1996), at Chapter 8, “Multiprocessors,” pp. 634-760.
On a centralized shared memory system an application's performance is typically not affected by the physical location of memory pages which the application uses. On a distributed shared memory system having non-uniform memory access times, e.g., a NUMA machine, this is not the case. Only the user really understands his or her application's needs and how data should optimally be distributed to minimize communication costs and maximize performance.
SUMMARY OF THE INVENTION
Application programmers, compilers, and other users need to be able to select a particular geometric configuration of memory including, a preferred geometry or topology, memory amount, and resource affinity. The present invention provides a method, system, and computer program product for allocating physical memory in a distributed shared memory (DSM) network. 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 which resources are associated with particular nodes in the global geometry of the DSM network.
According to the present invention, a physical memory allocator searches for a set of nodes in the DSM network that fulfills a memory configuration request based on a search of the global geometry data. The memory configuration request has parameters that define at least one of geometry or topology, 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. After a successful search, physical memory address space can be distributed across the set of nodes in the DSM network in accordance with the memory configuration request.
A user can control the type of search performed. According to one embodiment, the physical memory allocator searches for a set of nodes that represents nodes within the DSM network that fulfills the requested geometry. During the search, each node can be further evaluated to ensure that the node has sufficient available memory amount and proper resource affinity. For example, node memory amount data can be read to verify that the available node memory amount is at least equal to the memory amount specified in the memory configuration request. Node-resource affinity data (e.g. a resource affinity list) can be evaluated to ensure that nodes found in the search are located within an appropriate network distance of a resource in accordance with the resource affinity specified in the memory configuration request.
According to one embodiment of the present invention, the physical memory allocator searches for a set of nodes that represent a solution that minimizes (or approximately 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 {P
0
, P
1
, . . . , P
n−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 &agr; is a weighting factor.
According to another feature of the present invention, the physical memory allocator can begin a search at locations which are determined based on CPU load, actual memory usage, or pseudo-randomly. In this way, physical memory is allocated more evenly across a DSM network reducing overall contention and the occurrence of hot spots.
According to another embodiment of the present invention, a user is permitted to specify a geometry g which can be different types of memory topologies in a memory configuration request. In one example, the memory topology can include at least one of the following types of memory topologies: cluster, Boolean cube, Boolean cube fixed, and physical. The physical memory allocator reads the memory configuration request. If cluster memory topology is specified or if no memory topology is specified, the search begins at a selected node. The search expands radially to other nodes located topologically close to the first node based on the global geometry data until a candidate node set is found. Each candidate node is further chosen to minimize the Hamming distance between nodes. The candidate node set consists of a number of nodes equal to the number of nodes specified in the memory configuration request.
If a Boolean cube memory topology is specified, the search finds a candidate imbedded Boolean cube node set. The candidate imbedded Boolean cube node set consists of a Boolean cube imbedded in the DSM network having a number of nodes equal to the number of nodes specified in the memory topology request. Different orientations of the candidate imbedded Boolean cube node set can be evaluated to check appropriate memory amount and resource affinity.
If a fixed Boolean cube memory topology is specified, the search finds a candidate imbedded Boolean cube node set in a default orientation matching Boolean cube memory topology. If a physical memory topology is specified, the physical memory allocator searches global geometry data for the specified physical memory topology.
According to another feature of the present invention, the physical memory allocator further evaluates available memory amount for each node in the candidate node set to determine whether a successful node set has been found. The step of evaluating available memory at each node can be performed on a per node basis as each node is searched to find a candidate node set, or on per node basis after a candidate node set has been found to determine whether the candidate node set is a successful node set.
According to another feature of the prese
Richardson John L.
Stevens Luis
Rinehart Mark H.
Romero Almari
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
LandOfFree
Method, system, and computer program product for allocating... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, system, and computer program product for allocating..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, and computer program product for allocating... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2449006