# US 2014/0351821 A1 · Strategic Placement of Jobs for Spatial Elasticity in a High-Performance Computing Environment

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0351821 A1
- Document ID: US20140351821A1
- Status: Published application
- Kind: A1
- Application number: 13/902,184
- Filed: 2013-05-24
- Published: 2014-11-27
- Earliest claimed: 2013-05-24
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Hani Talal Jamjoom; Dinesh Kumar; Zon-Yin Shae
- Web page: https://patentgrep.com/patent/US20140351821A1

## CPC

- G06F 9/50: Allocation of resources, e.g. of the central processing unit [CPU]
- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F 9/505: {considering the load}
- G06F 9/5061: {Partitioning or combining of resources}
- G06F 9/5094: {where the allocation takes into account power or heat criteria (power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Accepting a job having a job size representing a number or quantity of processors; computing an expected size, and a standard deviation in size, for the accepted job; adding the expected size to the standard deviation in size to determine a sum; comparing the sum to a number or quantity of available clusters at each of a plurality of non-leaf nodes of a tree representing a high-performance computing environment; and when the number or quantity of available clusters is more than the sum at a sub-tree of the tree and, going down one level further in the sub-tree, the number of available clusters is less than the sum, selecting the sub-tree for the accepted job such that the accepted job is placed on one or more clusters associated with the selected sub-tree.

## Claims

### Claim 1

A method comprising:
allocating a quantity of processors for processing a job in a high-performance computing environment to provide an initial allocation; and
modifying the initial allocation during a run time of the job by performing one or more of: increasing the allocated quantity of processors in response to the job being extended in size by allocating one or more free processors from a pool of free processors which are configured to meet an increased computing demand for the job; or decreasing the allocated quantity of processors in response to the job being decreased in size by reallocating one or more processors from the allocated quantity of processors to the pool of free processors.

### Claim 2 (depends on 1)

The method of claim 1 wherein the one or more free processors assigned to the job are within a vicinity of the quantity of processors used to provide the initial allocation.

### Claim 3 (depends on 1)

The method of claim 1 wherein, in response to the job being extended in size, the job is allocated to a first area of processors which is more densely occupied than a second area of processors.

### Claim 4 (depends on 1)

The method of claim 1 wherein, in response to the job being decreased in size, the job is allocated to a second area of processors which is more sparsely occupied than a first area of processors.

### Claim 5 (depends on 1)

A method as in claim 1 where the initial allocation is stored in a memory in a cloud environment.

### Claim 6 (depends on 1)

A method as in claim 1 where the modified initial allocation is stored in a memory in a cloud environment.

### Claim 7

A method comprising:
allocating a job for execution by a quantity of processors;
determining a first probability value that specifies a probability of the job being extended in size during a run time of the job;
determining a second probability value that specifies a probability of the job being reduced in size during the run time of the job;
during the run time of the job, extending the job in size as specified by the first probability value, or reducing the job in size as specified by the second probability value.

### Claim 8 (depends on 7)

The method of claim 7 wherein, in response to the job being extended in size, the job is allocated to either a sparsely occupied area of processors or a densely occupied area of processors based upon the first probability value.

### Claim 9 (depends on 7)

The method of claim 7 wherein, in response to the job being reduced in size, the job is allocated to either the sparsely occupied area of processors or the densely occupied area of processors based upon the second probability value.

### Claim 10 (depends on 8)

The method of claim 8 further comprising allocating one or more free processors to the job wherein the allocated free processors are within a vicinity of the quantity of processors.

### Claim 11

A method comprising:
allocating a quantity of processors for processing a job in a high-performance computing environment to provide an initial allocation;
determining a probability value that specifies the probability of the job being extended in size during a run time of the job;
during the run time of the job, extending the job in size; and
modifying the initial allocation during the run time of the job by increasing the allocated quantity of processors in response to the job being extended in size by allocating one or more free processors to the job from a pool of free processors which are configured to meet an increased computing demand for the job.

### Claim 12 (depends on 7)

The method of claim 7 wherein the one or more free processors assigned to the job are within a vicinity of the quantity of processors used to provide the initial allocation.

### Claim 13 (depends on 7)

The method of claim 7 wherein, in response to the probability value being greater than a threshold value, the job is allocated to a first area of processors.

### Claim 14 (depends on 7)

The method of claim 7 wherein, in response to the probability value being below the threshold value, the job is allocated to a second area of processors having a density greater than the first area of processors.

### Claim 15

A method comprising:
accepting a job having a job size representing a number or quantity of processors;
computing an expected size, and a standard deviation in size, for the accepted job;
adding the expected size to the standard deviation in size to determine a sum;
comparing the sum to a number or quantity of available clusters at each of a plurality of non-leaf nodes of a tree representing a high-performance computing environment; and
in response to the number or quantity of available clusters being more than the sum at a sub-tree of the tree and, going down one level further in the sub-tree, the number of available clusters being less than the sum, selecting the sub-tree for the accepted job such that the accepted job is placed on one or more clusters associated with the selected sub-tree.

### Claim 16 (depends on 15)

The method of claim 15 wherein the computing an expected size, and a standard deviation in size, for the accepted job, is performed by using a first probability indicative of a probability that the job will be extended in size during a run time for the job.

### Claim 17 (depends on 16)

The method of claim 16 wherein the computing an expected size, and a standard deviation in size, for the accepted job, is performed by using a second probability indicative of a probability that the job will be decreased in size during the run time for the job.

### Claim 18 (depends on 15)

The method of claim 15 wherein the comparing is performed using a depth first search procedure.

### Claim 19 (depends on 18)

The method of claim 18 wherein the depth first search procedure is performed by traversing a left sub-tree at each of the plurality of non-leaf nodes prior to traversing a right sub-tree at each of the plurality of non-leaf nodes.

### Claim 20 (depends on 18)

The method of claim 18 wherein the depth first search procedure is performed by traversing a right sub-tree at each of the plurality of non-leaf nodes prior to traversing a left sub-tree at each of the plurality of non-leaf nodes.
