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

• US 9,594,600 B2
• Filed: 07/22/2013
• Issued: 03/14/2017
• 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:
  US13/947,637
• Publication Number:
  US 20130311998A1
• Time in Patent Office: 1,331 Days
• Field of Search: 717159-166, 718/103
• US Class Current: 1/1
• 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, available space in a virtual cluster of a plurality of communicatively coupled nodes included in a computing environment, the plurality of communicatively coupled nodes arranged in a three dimensional node structure, the virtual cluster comprising a logical grouping of nodes configured to process related jobs;

determining a job of a plurality of jobs in a job queue fits the deter ined available space in the virtual cluster of nodes including;

identifying, using the one or more computers, a shape of the job, the shape of the job indicating dimensions of nodes suitable to execute the selected job;

identifying, using the one or more computers, one or more shapes of the available space, the one or more shapes of the available space indicating one or more dimensions of the available space; and

determining, using the one or more computers, whether respective identified dimensions of the available space is greater than or equal to the respective identified dimensions of nodes suitable to execute the job; and

executing the job in the available space in the virtual cluster of nodes, in response to determining the all respective dimensions of the available space are greater than or equal to the respective identified dimensions of one or more nodes suitable to execute the job.

2. The method of claim 1, wherein determining the job of a plurality of jobs fits the determined available space in the virtual cluster of nodes further comprises:

determining a number of available nodes in the virtual cluster;

selecting a first job from the job queue;

dynamically determining the shape of the first job;

determining whether the number of available nodes is enough to execute the first job, based on the determined shape thereof; and

dynamically allocating one or more of the available nodes for the first job, in the event that the determined number of available nodes is enough to execute the first job.

3. The method of claim 2, further comprising:

responsive to dynamically allocating one or more of the available nodes for the first job, recalculating the number of available nodes in the virtual cluster; and

executing the first job on the dynamically allocated one or more nodes.

4. The method of claim 3, further comprising:

in the event that either the determined number of available nodes is not enough to execute the first job, or following execution of the first job, selecting a next job in the job queue and repeating the dynamically determining an optimum shape of the next job, determining whether the number of available nodes is enough to execute the next job, based on the optimum shape thereof, and dynamically allocating one or more of the available nodes for the next job, in the event that the determined number of available nodes is enough to execute the next job.

5. The method of claim 4, wherein the job queue is initially sorted based on a job priority.

6. The method of claim 1, wherein determining an optimum job that is compatible with the available space in the virtual cluster of nodes further comprises:

sorting the job queue based on job priority;

determining an original subset of the plurality of communicatively coupled nodes, the original subset comprising nodes currently unallocated to a job;

selecting a first job from the job queue based on priority;

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

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; and

executing the selected second job using one or more processors of one or more nodes of the original subset.

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

8. The method of claim 7, further comprising dynamically allocating a job space from the original subset based on the dimensions of the job, wherein executing the selected job comprises executing the selected job using the dynamically allocated job space.

9. The method of claim 1, wherein the dimensions of nodes suitable to execute the selected job include a length, width, and height of nodes and the one or more dimensions of the available space include one or more of a length, width, and height of the available space.

10. A system comprising:

a plurality of communicatively coupled nodes of a computing environment, each node comprising at least one hardware processing unit; and

a management node configured to;

determine available space in a virtual cluster of a plurality of the communicatively coupled nodes, the plurality of communicatively coupled arranged in a three dimensional node structure wherein the three dimensional node structure reduces the number of hops between nodes, the virtual cluster comprising a logical grouping of nodes configured to process related jobs;

determine a job of a plurality of jobs in a job queue fits the determined available space in the virtual cluster of nodes including;

identify a shape of the job, the shape of the job indicating dimensions of nodes suitable to execute the selected job;

identify one or more shapes of the available space, the one or more shapes of the available space indicating one or more dimensions of the available space; and

determine whether a respective identified dimension of the one or more dimensions of the available space is greater than or equal to a respective identified dimension of the dimensions of the nodes suitable to execute the job; and

execute the job in the available space in the virtual cluster of nodes, in response to determining all respective dimensions of the available space are greater than or equal to each of the one or more identified dimensions of one or more nodes suitable to execute the job.

11. The system of claim 10, wherein the management node is further configured to:

determine a number of available nodes in the virtual cluster;

select a first job from the job queue;

dynamically determine an optimum shape of the first job;

determine whether the number of available nodes is enough to execute the first job, based on the optimum shape thereof; and

dynamically allocate one or more of the available nodes for the first job, in the event that the determined number of available nodes is enough to execute the first job.

12. The system of claim 11, wherein the management node is further configured to:

responsive to dynamically allocating one or more of the available nodes for the first job, recalculate the number of available nodes in the virtual cluster; and

execute the first job on the dynamically allocated one or more nodes.

13. The system of claim 12, wherein the management node is further configured to:

in the event that either the determined number of available nodes is not enough to execute the first job, or following execution of the first job, select a next job in the job queue and repeat the dynamically determining an optimum shape of the next job, determine whether the number of available nodes is enough to execute the next job, based on the optimum shape thereof, and dynamically allocate one or more of the available nodes for the next job, in the event that the determined number of available nodes is enough to execute the next job.

14. The system of claim 13, wherein the job queue is initially sorted based on a job priority.

15. The system of claim 10, wherein the management node is further configured to:

sort the job queue based on job priority;

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

select a first job from the job queue based on priority;

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

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; and

execute the selected second job using one or more processors of one or more nodes of the original subset.

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

17. The system of claim 16, wherein the management node is further configured to dynamically allocate a job space from the original subset based on the dimensions of the job, wherein executing the selected job comprises executing the selected job using the dynamically allocated job space.

18. The system of claim 10, wherein the dimensions of nodes suitable to execute the selected job include a length, width, and height of nodes, and the one or more dimensions of the available space include one or more of a length, width, and height of the available space.

19. One or more computer-readable hardware storage device having computer readable instructions stored thereon that, when executed by a computer, implement a method, the method comprising:

determining available space in a virtual cluster of a plurality of communicatively coupled nodes included in a computing environment, the plurality of communicatively coupled nodes arranged in a three dimensional node structure wherein the three dimensional node structure reduces the number of hops between nodes, the virtual cluster comprising a logical grouping of nodes configured to process related jobs;

determining a job of a plurality of jobs in a job queue fits the determined available space in the virtual cluster of nodes including;

identifying a shape of the job, the shape of the job indicating dimensions of nodes suitable to execute the selected job;

identifying one or more shapes of the available nodes, the one or more shapes of the available nodes indicating one or more dimensions of the available nodes; and

determining whether respective identified dimensions of the available nodes is greater than or equal to the respective identified dimensions of nodes suitable to execute the job; and

executing the job in the available space in the virtual cluster of nodes, in response to determining the all respective dimensions of the available nodes are greater than or equal to the respective identified dimensions of one or more nodes suitable to execute the job.

20. The one or more computer-readable hardware storage devices of claim 19, wherein determining the optimum job that is compatible with the available space in the virtual cluster of nodes further comprises:

determining a number of available nodes in the virtual cluster;

selecting a first job from the job queue;

dynamically determining an optimum shape of the first job;

determining whether the number of available nodes is enough to execute the first job, based on the optimum shape thereof; and

dynamically allocating one or more of the available nodes for the first job, in the event that the determined number of available nodes is enough to execute the first job.

21. The one or more computer-readable hardware storage device of claim 20, wherein the method further comprises:

responsive to dynamically allocating one or more of the available nodes for the first job, recalculating the number of available nodes in the virtual cluster; and

executing the first job on the dynamically allocated one or more nodes.

22. The one or more computer-readable hardware storage device of claim 21, wherein the method further comprises:

in the event that either the determined number of available nodes is not enough to execute the first job, or following execution of the first job, selecting a next job in the job queue and repeating the dynamically determining an optimum shape of the next job, determining whether the number of available nodes is enough to execute the next job, based on the optimum shape thereof, and dynamically allocating one or more of the available nodes for the next job, in the event that the determined number of available nodes is enough to execute the next job.

23. The one or more computer-readable hardware storage device of claim 20, wherein the job queue is initially sorted based on a job priority.

24. The one or more computer-readable hardware storage device of claim 19, wherein determining an optimum job that is compatible with the available space in the virtual cluster of nodes further comprises:

sorting the job queue based on job priority;

determining an original subset of the plurality of communicatively coupled nodes, the original subset comprising nodes currently unallocated to a job;

selecting a first job from the job queue based on priority;

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

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; and

executing the selected second job using one or more processors of one or more nodes of the original subset.

25. The one or more computer-readable hardware storage device of claim 24, wherein the dimensions of the first job are based in part on one or more job parameters and an associated policy.

26. The one or more computer-readable hardware storage device of claim 25, wherein the method further comprises dynamically allocating a job space from the original subset based on the dimensions of the job, wherein executing the selected job comprises executing the selected job using the dynamically allocated job space.

27. The one or more computer-readable hardware storage devices of claim 19, wherein the dimensions of nodes suitable to execute the selected job include a length, width, and height of nodes and one or more dimensions of the available nodes including a length, width, and height of the available nodes.