System and method for topology-aware job scheduling and backfilling in an HPC environment

• US 8,336,040 B2
• Filed: 04/15/2004
• Issued: 12/18/2012
• Est. Priority Date: 04/15/2004
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Davidson, Shannon V., Richoux, Anthony N.
• Primary Examiner(s): Vo, Ted T
• Application Number:
  US10/825,021
• Publication Number:
  US 20050235286A1
• Time in Patent Office: 3,169 Days
• Field of Search: 717159-166
• US Class Current: 717/161
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/2025 using centralised failover control functionality
• CPC Class Codes: G06F 2201/815 Virtual middleware or OS functionality using virtual machines to implement generic software techniques for error detection or fault masking G06F11/1484
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A method for job management in an HPC environment includes determining an unallocated subset from a plurality of HPC nodes, with each of the unallocated HPC nodes comprising an integrated fabric. An HPC job is selected from a job queue and executed using at least a portion of the unallocated subset of nodes.

Claims

1. A method comprising:

determining, using one or more computers, an original subset of a plurality of nodes, the original subset comprising nodes currently unallocated to a job, each node in the plurality of nodes comprising a switching fabric comprising a switch integrated on the card and allowing node to node communication during execution of a job;

selecting a job from a job queue;

executing the selected job using one or more processors of one or more nodes of the original subset; and

determining that dimensions of the selected job are greater than a topology of the original subset;

selecting one or more nodes from a second plurality of nodes, the second plurality being distinct from the original subset, each of the nodes in the second plurality of nodes comprising a switching fabric integrated to a card and at least two processors integrated to the card, wherein the selected one or more nodes from the second plurality are unavailable at the time of selecting; and

adding the nodes selected from the second plurality to the original subset to satisfy the dimensions of the selected job after the nodes selected from the second plurality become available.

2. The method of claim 1, wherein selecting the job comprises selecting the job from the job queue based on priority, the selected job comprising dimensions not greater than a topology of the original subset.

3. The method of claim 2, wherein selecting the job from the job queue based on priority comprises:

sorting the job queue based on job priority;

selecting a first job from the sorted job queue;

determining dimensions of the first job with the topology of the original subset; and

in response to the dimensions of the first job being greater than the topology of the original subset, selecting a second job from the sorted job queue.

4. The method of claim 2, wherein the dimensions of the first job are based, at least in part, on one or more job parameters and an associated policy.

5. The method of claim 2, further comprising dynamically allocating a job space from the original subset based, at least in part, on the dimensions of the job, wherein executing the selected job comprises executing the selected job using the job space.

6. The method of claim 1, further comprising executing the selected job using the original subset of nodes including the nodes selected from the second plurality.

7. The method of claim 1, further comprising;

determining that a second job that was executing on a second subset of the plurality of nodes, the second subset of the plurality of nodes being distinct from the original subset, has failed;

adding the second subset to the original subset; and

adding the failed job to the job queue.

8. Software embodied in one or more non-transitory, tangible computer-readable media and when executed operable to:

determine an original subset of a plurality of nodes, the original subset comprising nodes currently unallocated to a job, each node in the plurality of nodes comprising a switching fabric integrated to a card and at least two processors integrated to the card, the switching fabric comprising a switch integrated on the card and allowing node to node communication during execution of a job;

select a job from a job queue;

execute the selected job using one or more processors of one or more nodes of the original subset; and

determine that dimensions of the selected job are greater than a topology of the original subset;

select one or more nodes from a second plurality of nodes, the second plurality being distinct from the original subset, each of the second nodes comprising an integrated fabric, wherein the selected one or more nodes from the second plurality are unavailable at the time of selecting; and

add the selected second nodes to the original subset to satisfy the dimensions of the selected job after the nodes selected from the second plurality become available.

9. The software of claim 8, wherein the software being operable to select the job comprises the software being operable to select the job from the job queue based on priority, the selected job comprising dimensions not greater than a topology of the original subset.

10. The software of claim 9, wherein the software being operable to select the job from the job queue based on priority comprises the software being operable to:

sort the job queue based on job priority;

select a first job form the sorted job queue;

determine dimensions of the first job with the topology of the original subset; and

in response to the dimensions of the first job being greater than the topology of the original subset, select a second job from the sorted job queue.

11. The software of claim 9, wherein the dimensions of the first job are based, at least in part, on one or more job parameters and an associated policy.

12. The software of claim 9, further dynamically allocate a job space form the original subset based, at least in part, on the dimensions of the job, wherein the software being operable to execute the selected job comprises the software being operable to execute the selected job using the dynamically allocated job space.

13. The software of claim 8, further operable to execute the selected job using the original subset of nodes including the nodes selected from the second plurality.

14. The software of claim 8, further operable to:

determine that a second job that was executing on a second subset in the plurality of nodes, the second subset of the plurality of nodes being distinct from the original subset, has failed;

add the second subset to the original subset; and

add the failed job to the job queue.

15. A system comprising:

a plurality of nodes, each node comprising a switching fabric integrated to a card and at least two processors integrated to the card, the switching fabric comprising a switch integrated on the card and allowing node to node communication during execution of a job; and

a management node operable to;

determine an original subset of the plurality of nodes, the original subset comprising nodes currently unallocated to a job;

select a job from a job queue;

execute the selected job using one or more processors of one or more nodes of the original subset; and

determine that dimensions of the selected job are greater than topology of the original subset;

select one or more nodes from a second plurality of nodes, the second plurality being distinct from the original subset, each of the nodes in the second plurality of nodes comprising a switching fabric integrated to a card and at least two processors integrated to the card, wherein the selected one or more nodes from the second plurality are unavailable at the time of selecting; and

add the selected one or more nodes from the second plurality to the original subset to satisfy the dimensions of the selected job after the nodes selected from the second plurality become available.

16. The system of claim 15, wherein the management node being operable to select the job comprises the management node being operable to select the job from the job queue based on priority, the selected job comprising dimensions not greater than a topology of the original subset.

17. The system of claim 16, wherein the management node being operable to select the job form the job queue based on priority comprises the management node being operable to:

sort the job queue based on job priority;

select a first job from the sorted job queue;

determine dimensions of the first job with the topology of the original subset; and

in response to the dimensions of the first job being greater than the topology of the original subset, select a second job form the sorted job queue.

18. The system of claim 16, wherein the dimensions of the first job are based, at least in part, on one or more job parameters and an associated policy.

19. The system of claim 16, wherein the management node is further operable to dynamically allocate a job space form the original subset based, at least in part, on the dimensions of the job, wherein the management node being operable to execute the selected job comprises the management node being operable to execute the selected job using the dynamically allocated job space.

20. The system of claim 15, wherein the management node is further operable to execute the selected job using the original subset of nodes including the nodes selected from the second plurality.

21. The system of claim 15, wherein the management node is further operable to:

determine that a second job that was executing on a second subset in the plurality of nodes, the second subset of the plurality of nodes being distinct from the original subset, has failed;

add the second subset to the original subset; and

add the failed job to the job queue.